Plain language
What this result means
Strassen multiplies two blocks with seven products where the usual formula uses eight. Adding and subtracting the results makes some output positions more sensitive than others. Repeating the same pattern sends the largest weights back into the same corners. A known way to switch the corners between products brings the worst growth down. The coefficient bound tells us how far switching can go. In FP16, a small input can also disappear in the very first addition. Once two inputs have become the same seven operands, later arithmetic has no way to tell them apart.
Growth derivation · FP16 routing proof · MNN experiment · OpenCV video experiment
- The limit concerns the coefficients in a worst-case error bound. Actual roundoff also depends on the inputs, arithmetic precision and evaluation order.
- D’Alberto published the switching rule in 2014. Our contribution is the lower bound over the real seven-product family and the proof that the historical rule attains its optimal exponent.
Why eight is the limit
At each level, Strassen combines input blocks, multiplies seven pairs, and adds the products back into four outputs. To trace how much weight can accumulate in one output, start with a single product.
and give the two input combinations for product . is its coefficient in output . Each norm is the sum of absolute entries.
The four output weights are . D’Alberto switches column labels in four of the seven child products. Each output sends half its weight to each orientation. After the first level, every new level multiplies the peak by eight.
For every exact real seven-product formula for matrix multiplication, the mass is at least 32. With four outputs, the mean weight at any node is at least .
By induction the mean at depth is at least , even when nodes choose different formulas. The peak is at least the mean. For , the historical schedule attains a peak of , giving the matching asymptotic base. The finite-depth optimum over the entire real family remains open.
How the mass bound follows from a triangle
De Groote’s classification expresses every real rank-seven formula through three invertible changes of coordinates of Strassen’s formula, up to symmetries and term rescaling. The one full-rank term has factors , and . Their determinants multiply to one. The entrywise norm of a 2 × 2 matrix is at least twice the square root of its absolute determinant, giving this term mass at least eight.
For the other six terms take the columns of one coordinate frame and write . The triangle with vertices 0, and satisfies
To see this, slide the vertex opposite a fixed side parallel to that side. Between places where another side aligns with an axis, the logarithm of each moving side length is concave. The product tends to infinity at the two ends of the line, so a minimum occurs at an axis alignment. Keep that side fixed and repeat. The aligned legs have lengths , with , and the remaining side has length . The inequality follows from the arithmetic–geometric mean inequality.
In each frame the three primal directions are , and , each twice. The corresponding dual lengths are the same three lengths divided by , each twice. The frame contributes to the product of the six rank-one masses. Multiplying across three frames gives at least . Hence the six masses sum to at least 24. Adding the full-rank term gives 32. Strassen has masses 8, 4, 4, 4, 4, 4, 4 and reaches equality.
Exact tensor and factor checker (Python) · Independent planar inequality check (Python + Z3) · Z3 results
The fixed-formula result and the floating-point bound
For an exact fixed square formula with output positions, put and . Each product occurrence may independently relabel output rows and columns, with corresponding input relabelings. Let give the flattened coefficient weight of a particular output word. With the empty-word weight one, its recurrence and optimal asymptotic peak are
Averaging over output words gives the lower bound. Following a largest single term at every level gives the lower bound. For the upper bound, independently sample uniformly from the transitive relabelings at each node. A moment bound for a fixed word, followed by a union bound across words, gives schedules arbitrarily close to that base.
For the standard 18-addition kernel with a sequential dot product of length at each leaf, stored inputs, unit roundoff , and no underflow or overflow, the corresponding forward bound at is
The exponent counts at most one rounding for each input’s linear form and three for output recombination per level, plus at most from a leaf. Shared roundings are allowed. The lower bound on coefficient growth gives no matching lower bound on errors observed with particular data.
How the same result applies to 3 × 3 multiplication
We also checked 17,376 archived Heule–Kauers–Seidl formulas, each using 23 products. Within these representatives and power-of-two diagonal scalings, the smallest growth base with one orientation shared throughout a level was 25.5. Independent choices at each product reduced the optimum to exactly . The attaining seed has mean 319/18 and largest individual weight eight. A practical 36-state rule has a certified base below 17.85518. This comparison covers the pinned archive and specified transformations. Other rank-23 families could admit smaller values. Catalogue counts and certified values
Result table
What changes as recursion goes deeper
| Quantity | Stationary Strassen | D’Alberto’s rule | Setting | Interpretation |
|---|---|---|---|---|
| Exact coefficient peak | 144 | 96 | Depth 2 | Known two-level example |
| Exact coefficient peak | 61,917,364,224 | 1,610,612,736 | Depth 10 | Same seven products per node |
| Peak float32 error | 1× reference for ratio | 0.206–0.408× | Depth 10 | Range of four panel medians |
| Within 1% peak error | 0 of 12 | 3 of 12 | Depth 5, Metal float16 | Native GEMM passed all 12 |
| Within 1% peak error | 0 of 12 | 0 of 12 | Depth 6, Metal float16 | The largest entry error improved on all 12 |
When does the better bound show up in the answer?
In float32 the switched rule reduced maximum-entry error on 105 of 108 paired tests. At depth ten the median within each of the four input families was 21–41% of stationary Strassen’s peak error. Across all inputs the median ratio of relative Frobenius errors, which measure error over the whole matrix, was 1.001.
In the GPU float16 test, native multiplication passed the 1% peak-error gate on every input. The switched and stationary schedules both passed every input through depth one and passed nine of twelve at depth two. At depth five, switching rescued three inputs. At depth six, every recursive result missed the threshold. These measurements give zero extra levels that work for the whole panel.
Exact coefficients at all tested depths · CPU float32 measurements · CPU float16 measurements · Metal float16 measurements
What survives the first FP16 rounding?
Multiplication by the identity should return every input entry. Consider a 2 × 2 matrix with ones on its diagonal and small, exactly representable FP16 numbers in its other two positions. Standard Strassen starts by forming seven left operands. In binary16, with rounding to nearest and ties to even, all seven can become independent of both small entries.
Every such input reaches the multiplier as the same seven numbers. Even an exact final sum must then return the same answer for inputs that require different outputs. Swapping coordinates first can rescue this example. How much information can the best choice of swaps preserve on a larger matrix?
We constructed a well-conditioned family of 128 × 128 matrices with the identity on the right. At one Strassen level, the encoder can independently swap 64 pairs of rows, 64 pairs along the shared dimension and 64 pairs of output columns. It sees the input before choosing from routes. We give the decoder the route label for free, along with the seven rounded operands.
Exactly 42,916 additional bits are necessary and sufficient to recover the correctly rounded product for every input in this family. Each small entry can take 4,099 values drawn from zero and the normal FP16 numbers in the interval above. The best fixed route needs 43,012 bits. Adaptive routing saves 96 bits under these assumptions. The count applies when the original input is unavailable to the decoder.
How the exact bit count is proved
Each site specifies which opposite pair must be stored directly. A row swap and an inner-coordinate swap combine by exclusive-or. Choosing swaps to protect the most sites is the Gale–Berlekamp switching problem. For our Walsh sign pattern with block width , a sharp sign-sum bound leaves small entries hidden under the best fixed route. The condition number of every input is at most .
A route choice can itself communicate something about those entries. For an alphabet of size , write for the number of hidden entries under route . Counting distinct messages gives the lower bound below. Hall’s matching theorem shows that a decoder attaining the bound exists.
Using the published count of six-variable bent functions and bounding the remaining terms gives 42,916 bits at . Allowing subnormal values enlarges the alphabet to 6,145 and raises the requirement to 45,010 bits. The proof establishes existence. Its matching construction would be impractical as an encoder at this size. Exact counts and small matching checks · Proof and executable replay
Which errors can still be repaired?
Given the stored operands, we can work backwards through the rounded additions to find every compatible input entry. For a requested output we compute the smallest and largest attainable dot products. When both round to the same FP16 value, the correct result is determined. Clamping an estimate to the rounded interval can only improve or preserve its absolute error against the correctly rounded answer.
On 24 fresh pairs of 64 × 64 matrices, standard Strassen incorrectly rounded 507 of 1,152 sampled entries. Clamping corrected 249 and brought another 112 closer, leaving 258 incorrect. Native Metal multiplication rounded every sampled entry correctly. Checking the whole matrix costs cubic work in our implementation. Held-out measurements
When a channel copy goes through Strassen
A static 1 × 1 convolution with one weight of +1 or −1 per row and column, zero bias and no activation simply reorders channels and changes some signs. Its exact output is available by indexing the input. We used this as a test of Alibaba’s MNN 3.6.2 on the ARM CPU of an Apple M4 Max.
With 512 channels and weights embedded in the model, MNN’s low-precision convolution changed 65,536 of 262,144 entries. The largest absolute error was 1/4,096. A debugger trace reached the FP16 Strassen–Winograd merge routine 32 times. MNN uses a different seven-product schedule from the standard Strassen formula in the proof above.
| Channels | Method | Wrong entries | Time (ms) |
|---|---|---|---|
| 256 | Convolution | 0 | 0.0342 |
| Gather + signs | 0 | 0.0135 | |
| 512 | Convolution | 65,536 | 0.2765 |
| Gather + signs | 0 | 0.0412 | |
| 1,024 | Convolution | 262,144 | 2.0190 |
| Gather + signs | 0 | 0.1703 |
MNN’s existing Gather and Multiply operators returned every value exactly. They ran 6.7× faster at 512 channels and 11.9× faster at 1,024. This was a manually expressed equivalent layer on one machine. An automatic rewrite would need to recognize suitable weights in exported models and preserve the layer’s layout and numerical semantics.
Dense weights, timing boundaries and controls
With dense Walsh weights, changing the sign of a whole small input quadrant gave byte-identical low-precision outputs at 512 and 1,024 channels, even though the correctly rounded references differed. With weights supplied as separate operator inputs, the low-precision path distinguished the pair and matched both references. High precision with embedded weights reproduced the original input’s exact real product. Gathering channels only implements the signed-permutation case.
Both timing columns use the median of twelve interleaved CPU executions after three warmups. Model conversion, input copies and output reads fall outside the timed interval for both methods. The workloads use one batch and finite FP16-representable inputs. The low-precision setting itself promises no correctly rounded output. Timing samples and error counts · Download the MNN reproducer and controls
OpenCV experiment
Is it worth detecting cancellation in video patches?
We tested a different idea on small matrices from OpenCV’s vtest.avi. If two frames are similar, the scatter matrices of their patches are nearly equal. Their difference can be small enough for roundoff to matter. A blind matcher searches for nearly cancelling product terms before multiplication. In an ordinary video pipeline we also know which patch came from the same spatial position, giving us a cheaper control.
Each frame contributes thirteen centered 27-component patch vectors, forming a matrix or . For the same scatter difference , the temporal midpoint gives an alternative calculation
The blind matcher sees the packed product operands. It uses sampled entries to propose neighbors, scores candidates, selects disjoint pairs and rewrites the product before GEMM. The GPU matcher selected the same unordered pairs as the CPU matcher on all 72 cases. The centered input vectors lie on a fixed binary lattice, so an integer calculation gives the exact reference for every entry.
| Method | Execution | Mean peak error | Median batch time |
|---|---|---|---|
| Direct float32 GEMM | GPU | 4.39e−7 | 0.509 ms |
| Temporal midpoint | GPU · known pairing | 3.26e−8 | 0.585 ms |
| Paired product identity | GPU · known pairing | 5.63e−8 | 0.598 ms |
| Kahan summation | GPU · ordinary products | 1.25e−7 | 1.762 ms |
| Blind matching + GEMM | GPU · search included | 1.09e−7 | 10.130 ms |
| Blind matching + GEMM | CPU search, GPU product | 1.09e−7 | 85.755 ms |
| Float64 → float32 | CPU · rounded output | 1.20e−8 | 0.074 ms |
| Float64 GEMM | CPU · native output | 0 (exact) | 0.069 ms |
Blind matching cut mean peak error roughly fourfold relative to direct float32 GPU multiplication. On individual changed pairs it improved 27, tied on one and worsened one. With temporal correspondence available, the midpoint produced about 3.3× less error in about 1/17 of the blind GPU time. Kahan summation was faster than blind GPU matching and had slightly higher mean peak error. CPU float64 reproduced the exact target on every entry and was quickest here, including conversion of the inputs. Rounding its results once to float32 gave the correctly rounded output for every entry.
Keeping the patches on the GPU gave the same ordering. With fresh matching inside every timed call, the fresh 36-pair batch took 5.349 ms for blind matching and multiplication, 0.250 ms for the midpoint, 0.903 ms for Kahan and 0.165 ms for direct GEMM. All four methods reproduced their host-to-host peak errors when we read the outputs back after timing. Device-resident measurements
We also ran the actual three-level, rank-23 fast formula used in the detector prototype. On the fresh changed pairs, CPU matching followed by that Metal kernel lowered its mean peak error from to . The simpler GPU midpoint reached . The detector remains a demonstration on these patches. The new evidence supports using the midpoint when frame correspondence is already known, or float64 on this CPU when the patches start in host memory.
Inputs, timing boundaries and precision
Both fixtures contain 36 patch pairs from the same pinned video. The first takes adjacent frames, and the second uses a three-frame separation and a different spatial sample. The original fixture has 28 nonzero targets and the fresh fixture has 29. “Changed” means the target has at least one nonzero entry. No population-level claim follows from two samples of one video.
All controls start with the same packed host float32 arrays and end with a host result. The GPU blind run includes candidate search, matching, preparation, multiplication, output transfer and diagnostic index transfer. The Kahan control compensates the summation of ordinary float32 products. The midpoint and paired-product controls have labeled temporal correspondence. Decoding, patch extraction and model-independent input construction are outside all timings. We used two warmups and eleven shuffled, interleaved measurements per method and fixture, with device synchronization. CPU BLAS was configured for one thread.
For the packed matrices and , we report each case’s maximum entry error divided by and average those values across changed cases. This denominator stays meaningful for strong cancellation. The 1% threshold used in the separate Strassen experiment has a different denominator.
Metal/MPS on this machine rejected a float64 tensor with CPU fallback disabled. Both float64 rows above ran explicitly on CPU. A native double-precision GPU, larger matrices, or inputs already resident on the device would require fresh measurements. The rank-23 comparison used a separate synchronized run with a reusable Metal kernel and CPU detection. Its outputs agreed bit for bit with its CPU arithmetic reference across 104,976 entries.
All controls, per-case errors and timing samples · GPU matcher parity · Float64 capability probe · Rank-23 GPU results · Download the OpenCV replay bundle
Method
How it was found
Numaro’s research agents searched recursive schedules and compared their coefficient profiles with published rules. Recognizing D’Alberto’s assignment turned the question into an optimization over all real seven-product formulas.
- Use de Groote’s classification to reduce all rank-seven formulas to changes of coordinates of the same seven terms.
- Bound the combined coefficient mass of those terms and check which historical schedule attains the resulting base.
- Replay exact coefficients and measure errors against higher-precision references on the same inputs for every schedule.
Verification
How it was checked
Exact tensor arithmetic checks the standard formula and the rank-one factorization. An independent real-arithmetic check with Z3 excludes counterexamples in both sign cases of the planar inequality. The proof uses de Groote’s classification for coverage of the entire real family. The numerical panels test implementations and have finite coverage.
Scope
What is not being claimed
The theorem concerns exact real bilinear formulas, independent product occurrences and classical coordinates at the boundary of every recursive node. Other ranks, persistent alternative bases, compensated kernels and different error objectives require their own analysis. Priority and the proof remain open to independent specialist review.
References
Baseline sources
- de Groote (1978) · Classification of optimal 2 × 2 bilinear algorithms
- Castrapel & Gustafson · Earlier recursive permutation method
- D’Alberto (2014) · The Better Accuracy of Strassen–Winograd Algorithms
- FastMMW · The product switches in the historical implementation
- Ballard et al. (2016) · Stability vectors and nonuniform recursion
- De Silva, Gustafson & Wong (2018) · Error-based quadrant rotations
- Dumas, Pernet & Sedoglavic · Growth factors and coordinate changes
- Roth & Viswanathan · Hardness of decoding the Gale–Berlekamp code
- Preneel · Enumeration of six-variable bent functions, Chapter 8
- Alibaba MNN 3.6.2 · Strassen–Winograd operand formation
- OpenCV · The pinned vtest.avi video fixture
- Apple · Metal Shading Language specification
- Related Numaro result · Additions in fast matrix multiplication
Citation
How to cite
Numaro AI Autoresearch Team. "Sharp coefficient growth for real seven-product matrix multiplication." Numaro Research Report NUMARO-2026-024, 2026.
@techreport{numaro2026StrassenStability2026,
title = {Sharp coefficient growth for real seven-product matrix multiplication},
author = {Numaro AI Autoresearch Team},
institution = {Numaro},
number = {NUMARO-2026-024},
year = {2026},
url = {https://numaro.tech/research/strassen-stability-2026/}
}