PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Accuracy: Prefix-Invariant Realizations of Low-Precision Fast Matrix Multiplication

Shuxiao Xie, Shuyang Xie, Yuan Cao, Dezhi Ran, Wei Yang, Tao Xie

arXiv:2609.39816v1cs.LG

TL;DR

Rounding in fast matrix multiplication can make language-model outputs depend on later token rows, despite the prefix-only dependence required by likelihood scoring. The paper certifies bounded-integer realizations that match a row-local classical int8 operator bit for bit. These realizations use 49 rather than 64 block multiplications, though faster kernels remain future work.

  • Problem

    Rounded block sums can let later token rows affect earlier outputs, threatening the prefix invariance on which likelihood-based evaluation relies.

    Source: §1 · p. 1

  • Method

    The paper quantizes token rows to bounded integer codes, mixes and cancels them exactly, and certifies bitwise equality with a prescribed classical int8 operator.

    Source: §1 · pp. 2–3

  • Results

    49 instead of 64 block multiplications: certified two-level Strassen realizations match classical int8 bit for bit and inherit its prefix invariance.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Among certified realizations, choice becomes a cost decision because running one rather than another cannot change a scored likelihood.

    Source: §1 · p. 3

    Whether full-range overflow correction retains the multiplication saving depends on its implementation.

    Source: §5 · p. 9

Abstract

from arXiv · show

Fast matrix multiplication saves multiplications through exact cancellation, but rounding sums that mix token rows can leave contributions from later tokens in earlier language model outputs. This threatens prefix invariance, which multiple-choice likelihood scoring relies on: a scored likelihood must depend only on its allowed prefix. On Qwen2.5-14B-Instruct, two fast FP8 realizations repaired to ordinary-looking accuracy still change the answers chosen by likelihood on 5.83% and 10.00% of 240 OpenBookQA items when only the text after the allowed prefix is replaced with the bf16 model's own greedy continuation. Both row-local controls, the bf16 model and a deployed FP8 matrix multiplication kernel, change none. Accuracy thus does not certify prefix invariance, and the stability criteria we analyze cannot tell realizations apart: across all 512 sign variants of two-level Strassen they stay constant while teacher-forced perplexities span a 772.4$\times$ range on the same model. We therefore construct certified realizations of two-level Strassen on bounded integer codes that quantize token rows independently, then mix and cancel exactly before rescaling, using 49 block multiplications instead of 64. Our certificate guarantees bitwise equality to a prescribed row-local classical int8 operator at the same quantization specification, so every certified realization inherits its prefix invariance. Certification thus turns realization choice into a pure cost decision: which certified realization runs can no longer change a single scored likelihood.

1 Introduction

Rounded fast matrix multiplication can make earlier language-model outputs depend on later token rows, undermining prefix invariance required by likelihood scoring. The paper shows that accuracy and coefficient-based stability criteria do not rule this out, then certifies integer-code realizations that match a row-local operator bit for bit.

1 Introduction

  • Rounded block sums can leave later-token contributions in earlier outputs, violating prefix invariance required for likelihoods to depend only on their allowed prefixes.In a linear layer, the causal attention mask does not prevent this dependence.Source: §1 · pp. 1–2
  • 5.83% and 10.00% of 240 OpenBookQA items changed answers when repaired fast FP8 outputs were scored after replacing text beyond the allowed prefix.The bf16 model and a deployed FP8 matrix multiplication kernel changed none.Source: Figure 1 · p. 2, §1 · p. 2
  • 772.4×: teacher-forced perplexity spans this range across 512 two-level Strassen sign variants, although the analyzed coefficient-magnitude criteria assign them one value.The variants were evaluated under the same FP8 schedule on the same model.Source: §1 · p. 2
  • The construction quantizes each token row to bounded integer codes, mixes and cancels them exactly, then applies scales; certification checks equality with the classical int8 operator.Every certified realization matches that operator bit for bit and inherits its row locality.Source: §1 · pp. 2–3
  • 49 vs 64 block multiplications: certified realizations match classical int8 bit for bit, while making them faster than classical int8 remains future work.Certification makes the choice among passing realizations a cost decision without risking prefix invariance.Source: §1 · p. 3

2 Realizations and prefix invariance

This section describes fast block algorithms and their sign variants, defines the quantized classical int8 reference operator, and distinguishes prefix invariance from deterministic inference. The distinction concerns which text an output may depend on, not merely how a fixed computation is executed.

2.1 Fast algorithms and their sign variants

  • Fast algorithms multiply block sums whose unwanted cross terms cancel; two-level Strassen has 512 sign variants that preserve the product and multiplication count but can differ in low-precision accuracy.Two-level Strassen uses 49 block multiplications instead of the classical 64.Source: §2.1 · p. 3

2.2 Quantization and the reference operator

  • Quantization specification c fixes code bounds, group scales, rounding, and output rescaling and summation order; the classical int8 reference is row-local.It gives each row of A and each column of B its own scale per group.Source: §2.2 · p. 3

2.3 Prefix invariance

  • Prefix invariance requires outputs to match when allowed prefixes match; rounded block sums can mix token rows and, in packed batches, requests.The causal mask does not by itself guarantee the property.Source: §2.3 · pp. 3–4
  • Deterministic inference concerns execution-dependent changes, while prefix invariance concerns which text may affect an output at a fixed execution plan and input shape.Fixing sum order or making summation order-independent does not by itself prevent fast algorithms from mixing later text into an output.Source: §2.3 · p. 4

3 Exactly equivalent realizations are not interchangeable

Accuracy repair and coefficient-based stability criteria do not certify prefix invariance: repaired FP8 realizations still change likelihood choices, while the criteria cannot distinguish Strassen sign variants with widely differing realized perplexity.

3.3 What the stability criteria cannot see

  • Accuracy misses prefix-invariance violations, while the analyzed stability criteria miss both those violations and large differences in realized error.Source: §3 · p. 4, §3.3 · p. 6

3.1 Accuracy repair does not restore prefix invariance

  • The audit scores each answer token in matched-shape inputs that preserve its allowed prefix while replacing that token and later text with filler or a bf16 greedy continuation.The comparisons use the bf16 model and deployed row-local FP8 kernel as controls.Source: §3.1 · p. 4
  • 5.83% and 10.00% of OpenBookQA items changed answers under greedy continuation for repaired #1 and #2, respectively; row-local controls changed none.The repaired models had 35.42% and 32.92% accuracy, against 34.58% for bf16.Source: §3.1 · p. 4, Table 1 · p. 5
  • Of repaired #1’s 14 changed answers, nine were wrong both before and after, so answer changes barely moved accuracy.Three changed from correct to wrong and two from wrong to correct.Source: §3.1 · p. 4

3.2 How the violation can arise and how far it extends

  • FP8-rounded block sums can carry later token rows into earlier rows, and masked attention can then carry those rows to a scored position.Two-level Strassen adds rows at matching offsets; repaired #1 adds pairs, while repaired #2 adds the same rows as the unrepaired two-level algorithm.Source: §3.2 · p. 5, Figure 2 · p. 5
  • Violations also appear in next-token predictions across five models and in first-request distributions when same-shape batches replace a second request’s text, unlike the controls.The cross-request test separates attention between requests and uses no key–value cache.Source: §3.2 · p. 5

3.3 What the stability criteria cannot see

  • Coefficient-only criteria assign all 512 sign variants one value, and independent symmetric random-matrix error checks also give the variants identical error distributions.The criteria include Φ, nonzero-coefficient count, largest coefficient magnitude, and Q and E from a rounding-error bound.Source: §3.3 · p. 6
  • 1.367–1056.0 bf16-normalized WikiText-2 perplexity ratios span the 512 variants, a 772.4× spread; filler retains 0.985× of the teacher-forced spread.The original-sign variant has a 63.11× ratio.Source: §3.3 · p. 6

4 Certified realizations on bounded integer codes

The section constructs certified two-level Strassen realizations that compute classical int8 bit for bit while retaining fewer block multiplications, with an overflow correction extending the code range. It also compares the resulting operators’ language-model quality with a deployed FP8 kernel.

4.1 Prefix-safe products force the classical count

  • Any algorithm safe product by product uses at least mkn block multiplications, the classical count, while two-level Strassen uses 49 instead of 64.Two-level Strassen therefore carries later block-row contributions into earlier outputs, which must vanish by the time those outputs are formed.Source: §4.1 · p. 6

4.2 Computing classical int8 with a fast algorithm

  • The certificate ensures bitwise equality to classical int8 by keeping code products exact and applying scales as specified; two-level Strassen is certified at code bound 31 with 0.7656 of the classical multiplication count.The conditions are checked from coefficients, tiling, and quantization specification before inputs are seen; the model test reports no changed OpenBookQA answers among 240 items on any of four models.Source: §4.2 · pp. 7–8

4.4 Model quality and the choice of realization

  • At code bound 31, excess NLL exceeds the deployed FP8 kernel’s on three of four models raw and all four adjusted; with overflow correction at 127, it is at or below the kernel’s on all four in both settings.The comparison uses eight 2048-token WikiText-2 chunks; raw scores are at temperature 1, while adjusted scores use temperatures fitted on the other seven chunks.Source: Figure 4 · p. 8, §4.4 · p. 8

4.3 Full-range codes with an overflow correction

  • The overflow correction splits out-of-range block sums and adds correction products, enabling bitwise classical int8 computation at code bound 127 with groups of 128.The correction products add to the cost and are counted separately.Source: §4.3 · p. 8

5 Cost and future work

The multiplication saving depends on how the full-range overflow correction is implemented, and the kernels tested are slower than classical int8. Whether fewer multiplications can be turned into speed remains open.

5 Cost and future work

  • At code bound 31, two-level Strassen performs 0.7656 of classical int8’s multiplications, while the code-bound-127 correction brings excess NLL to or below the deployed FP8 kernel’s on all four models.Faster kernels, including one for the correction, and timing across shapes and GPUs are left to future work; certified optimizations preserve the same output bits.Source: §5 · p. 9
  • 0.79–0.82 of classical int8’s multiplications are used when correction multiplies only overflowing entries, versus 1.43–1.71 times as many when it multiplies every row and column holding an overflow.These figures are from sampled layer slices from three models; whether full-range codes retain the saving depends on correction implementation.Source: §5 · p. 9
  • On 4096 × 4096 matrices on an NVIDIA H20, one Strassen level takes 2.04–3.17 times as long as classical int8 across three group sizes, and two levels take 27.9 times as long.The authors leave open whether, and how far, multiplication savings can be converted into speed.Source: §5 · p. 9

6 Conclusion

The conclusion presents certified two-level Strassen realizations that preserve prefix invariance while retaining fewer block multiplications. Appendix A.1 shows that enforcing prefix safety product by product instead requires the classical multiplication count.

6 Conclusion

  • Two-level Strassen uses 49 block multiplications instead of 64, and certified bounded-integer realizations reproduce the row-local classical int8 operator bit for bit.Because the certified output is row-local, each realization inherits prefix invariance; choosing among certified realizations is therefore a cost decision.Source: §6 · p. 9

A.1 Prefix-safe products force the classical count

  • Product-by-product prefix safety requires at least mkn block multiplications, matching the classical algorithm’s count.Prefix safety makes the sets of products that read and feed each block row disjoint, although each set must contain at least kn products.Source: §A.1 · p. 12
  • Strassen’s seven products share M1 across two rows, saving one multiplication but making that product feed the earlier row while reading the later row.The example identifies how a shared product violates prefix safety.Source: §A.1 · pp. 12–13

A.2 The inner dimension and its scales

The inner-dimension results show why fast algorithms must mix indices and how bounded integer codes can still reproduce classical int8 output bits. The construction’s exactness depends on code bounds, accumulation ranges, and keeping each call within one scale group.

A.2 The inner dimension and its scales

  • Any algorithm whose products each read only one block column of A, or only one block row of B, requires at least mkn block multiplications.The count follows by considering inputs with only one inner-dimension index active; the contributing products must produce all mn output entries.Source: §A.2 · p. 13
  • For arbitrary positive diagonal scales, representing AΛB with fixed bilinear products requires at least mkn products.The argument recovers each of the mkn distinct forms A_ilB_lj by comparing Λ = I + E_ll with Λ = I.Source: §A.2 · p. 13

A.3 Proof of Proposition 1

  • Exact classical int8 output requires code magnitudes at most 127, accumulation bounds below 2^31 for int32 or 2^24 for fp32, and calls contained within one inner-dimension group.The group condition lets exact call products combine into the group’s integer product before rescaling.Source: §A.2 · p. 13, §A.3 · p. 14
  • Under those conditions, calls and group sums are exact, so the realization matches classical int8 bit for bit.The proof also accounts for signed zero: any zero-representation difference disappears in the specified sum over groups.Source: §A.3 · p. 14

B.1 What the criteria read, and what the operands decide

The analyzed stability criteria depend on algorithm coefficients, yet sign variants with identical criteria can have different measured errors. Synthetic tests show that the differences depend on operand distributions.

B.1 What the criteria read, and what the operands decide

  • The analyzed criteria read coefficient properties, including magnitudes and nonzero patterns, which sign changes can leave unchanged.The set includes the expected-error measure and Ballard et al.’s prefactor and stability factor.Source: §B.1 · p. 14
  • 1.367 to 1056.0: the WikiText-2 perplexity ratio varies across sampled two-level Strassen sign variants while every analyzed stability criterion stays constant.The table reports four of 512 variants on Qwen2.5-14B-Instruct under the FP8 schedule.Source: §B.1 · p. 14, Table 2 · p. 15
  • On synthetic matrices, average-error spans were about 1.005 for entries uniform on [−1, 1] and 2.59 for entries uniform on [0, 1].Across variants, the two halves’ averages correlated at 0.121 and 0.9997, respectively.Source: §B.1 · p. 15

B.2 Seven models, and an outlier test

Across seven models, sign-variant perplexity spread varies substantially, and the tested outlier ratio does not separate models with catastrophic variants. Additional tests find operand rotation and product order can shift measured error, while repeated runs reproduce the tested results.

B.2 Seven models, and an outlier test

  • 1.07× on Qwen2.5-7B-Instruct to 772.4× on Qwen2.5-14B-Instruct: sign-variant spread varies by model, while deployed-kernel ratios range from 1.0009 to 1.0138.Table 3 reports WikiText-2 perplexity ratios over the bf16 model on the same chunks.Source: Table 3 · p. 15, §B.2 · p. 15
  • Outlier ratios of 1553.4 and 1760.5 yielded 0 of 512 catastrophic variants each, while Qwen2.5-32B-Instruct had 8 of 512; no threshold separates these three models.A catastrophic variant is defined as one whose perplexity exceeds ten times its own bf16 model’s.Source: §B.2 · pp. 15–16

B.3 A rotation, other summation orders and repeated runs

  • Hadamard rotation narrowed the error spread from 2.137 to 1.300 for shared column offsets, but widened it from 1.240 to 1.317 for random-sign offsets.The random-sign condition includes three percent of offsets forty times larger than the rest.Source: §B.3 · p. 16
  • 4.6080 to 68.6687: product reordering alone produced a 14.90× perplexity-ratio span on one realization; reordering deployed-kernel scaling groups changed its ratio by 1.00459×.The sign-variant spread reported in Section 3.3 keeps the original product order.Source: §B.3 · p. 16
  • Eight fresh processes on eight GPUs reproduced each tested extreme ratio exactly, with relative difference 0.0.The reported checks were within one container instance.Source: §B.3 · p. 16

C.1 What the two inputs of a comparison share

The comparisons test whether replacing text beyond an allowed prefix changes earlier predictions, answer choices, or intermediate projections. They cover multiple-choice scoring, other models, and packed requests, with row-local controls included.

C.1 What the two inputs of a comparison share

  • Each comparison preserves the allowed prefix and replaces the scored token and later text; the two replacement sources are C4 validation text and bf16 greedy continuations.The comparison keeps the realization, weights, product order, and input length fixed; across two container runs, chosen answers were reproduced for repaired #1 and both row-local controls.Source: §C.1 · pp. 16–17

C.2 The 14 changed answers

  • Repaired #1 changed its chosen answer on 14 OpenBookQA items under greedy-continuation replacement, while both row-local controls kept their answer on all 14.Table 5 lists the items and groups changes by their effect on correctness.Source: §C.2 · p. 17, Table 5 · p. 18

C.3 How a later row reaches an earlier output

  • Changing row 40 changed output rows 4, 16, and 28 under two-level Strassen and repaired #2, while classical multiplication changed only row 40.The test replaces the last input row before padding; the affected earlier rows share its offset across the other blocks.Source: §C.3 · p. 17

C.4 Other models

  • 0 of 1,305,600 kept-prefix predictions changed under either row-local control across five models, while the window test found changes under fast realizations.The test compares top-1 predictions at positions in the kept first quarter of 1,024-token windows after replacing the remainder.Source: §C.4 · p. 18, Table 6 · p. 19

C.5 Other requests

  • 768 of 768 packed-request pairs changed the first request’s next-token distribution under the unrepaired realization and repaired #2; neither row-local control changed it.The comparison packs two requests into one forward pass without a key–value cache and replaces the second request.Source: §C.5 · p. 19, Table 6 · p. 19
  • Every recorded key and value projection differed under the unrepaired realization and repaired #2, beginning at the first layer; neither row-local control changed any recorded projection.This held across all rows and pairs in the 64-pair Qwen2.5-3B test.Source: §C.5 · p. 19

D Construction details

The construction specifies quantization and code bounds, then certifies that its integer computation matches classical int8 under stated conditions. The section also reports model checks and quality-measurement scope.

Model verification

  • Two-level Strassen at code bound 31 matched classical int8 bit for bit in 15,456 Qwen2.5-14B-Instruct, 36,288 Llama-3.1-8B-Instruct, 36,288 OLMo-2-7B-Instruct, and 40,824 Qwen3-8B layer invocations.Source: D Construction details · p. 19

Quantization specification

  • The model quantizer uses row-wise activation scales and column-wise weight scales over groups of 128, with nearest-even codes bounded by b=31 or b=127.It rescales and accumulates group products in ascending inner-dimension order, then casts to bf16 before adding bias.Source: D Construction details · p. 19

Code bounds

  • For two-level Strassen, code bound 31 makes the quantization step 4.0968 times coarser than full-range int8; the other 49-multiplication algorithms cited have code bounds no higher than 18.Source: D Construction details · pp. 19–20

Dense uniform codebooks on FP8

  • For e4m3 with two-level Strassen’s four-code block sums, at most nine evenly spaced codes remain, versus 63 codes admitted by the int8 condition.Source: D Construction details · p. 20

The corrected computation’s certificate

  • At code bound 127, the overflow correction splits block sums so each of four products multiplies int8 values, and its stated conditions yield the classical int8 result bit for bit.The certificate requires int32 integer arithmetic and the same quantization, rescaling, and fp32 addition order as classical int8.Source: D Construction details · p. 20

Model quality

  • Table 7 reports excess negative log-likelihood per token over bf16 on eight 2,048-token WikiText-2 chunks; Qwen3-8B’s raw excess at code bound 31 is negative.For Qwen3-8B, the bf16 model fits this text best at temperature 1.30 on the tested grid.Source: Table 7 · p. 20, D Construction details · p. 20

E Cost details

The cost section reports correction-term multiplication counts, GPU timing comparisons, and sensitivity to product order. It also identifies the scope of the reported task-accuracy evaluation.

Model quality

  • Table 8 evaluates OpenBookQA accuracy on the first 240 test items using likelihood scoring and the classical reference operators represented by the certified int8 realizations.Source: Table 8 · p. 21

The correction’s multiplications

  • Correction terms at code bound 127 total 0.79–0.82 of classical int8’s multiplications when counting nonzero entries, but 1.43–1.71 times as many when counted as dense products over affected rows and columns.The counts are from slices of three linear layers; each corrected computation reproduced classical int8 bit for bit.Source: E Cost details · p. 21

The timings

  • Two levels of Strassen at code bound 31 took 27.9 times as long as classical int8 at groups of 256 on 4096×4096 matrices.One-level Strassen took 2.04, 3.17, and 2.09 times as long at groups of 128, 256, and 512, respectively.Source: E Cost details · p. 21
  • Running the executor’s 64 classical block products already took 2.25 times as long as its classical int8 kernel at groups of 256.Source: E Cost details · p. 21

The order of the products

  • Across timed product orders, the slowest took 1.46 times the fastest for two-level Strassen and 1.97 times for the one-level-Strassen/one-level-classical hybrid.A rule based on least compiler-allocated local memory selected the fastest of 200 untimed orders in each of two pools.Source: E Cost details · p. 21

F Reproducibility details

The reproducibility details tie printed numbers to stored program outputs and list the arithmetic, hardware, software, models, and datasets behind result families. They also state the conditions under which exact results hold across hardware.

From stored outputs to printed numbers

What holds on any hardware

  • Coefficient quantities, multiplication counts, and certified operator identities hold on any hardware when integer arithmetic is exact and quantization, rescaling, and accumulation follow specification c.The model fp32 emulation satisfies this condition because every integer intermediate stays below 2^24.Source: F Reproducibility details · p. 22

Software

  • The runs used several recorded PyTorch, CUDA, and kernel-library versions; timing and quality measurements used NVIDIA H20 GPUs.Source: F Reproducibility details · p. 22

Models and data

  • The experiments span the listed Qwen, Llama, OLMo, and Yi models, with multiple-choice tests on the first 240 OpenBookQA and ARC-Easy items.Window and sequence measurements use WikiText-2 test and C4 validation text as specified for each experiment.Source: F Reproducibility details · p. 23
Loading 2609.39816v1…