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.

01Weigh each product
bit=∣Wit∣ ∥Ut∥1∥Vt∥1,ei=∑tbit.\begin{aligned}b_{it}&=|W_{it}|\,\lVert U_t\rVert_1\lVert V_t\rVert_1,\\ e_i&=\sum_t b_{it}.\end{aligned}

UtU_t and VtV_t give the two input combinations for product tt. WitW_{it} is its coefficient in output ii. Each norm is the sum of absolute entries.

02Switch the heavy quadrants
ELstationary=12L,ELswitched=12⋅8L−1(L≥1).\begin{aligned}E_L^{\rm stationary}&=12^L,\\E_L^{\rm switched}&=12\cdot8^{L-1}\quad(L\ge1).\end{aligned}

The four output weights are (12,4,4,12)(12,4,4,12). 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.

03Bound every seven-product formula
F=∑t=17∥Ut∥1∥Vt∥1∥Wt∥1,F≥32.\begin{aligned}F&=\sum_{t=1}^7\lVert U_t\rVert_1\lVert V_t\rVert_1\lVert W_t\rVert_1,\\ F&\ge32.\end{aligned}

For every exact real seven-product formula for 2×22\times2 matrix multiplication, the mass is at least 32. With four outputs, the mean weight at any node is at least 32/4=832/4=8.

By induction the mean at depth LL is at least 8L8^L, even when nodes choose different formulas. The peak is at least the mean. For n=2Ln=2^L, the historical schedule attains a peak of 32n3\tfrac32 n^3, giving the matching asymptotic base. The finite-depth optimum over the entire real family remains open.

Depth-two weights in all 16 outputs. The four largest entries fall from 144 to 96 when switched.
The same total weight, redistributedBoth maps sum to 1,024. Switching evens out the second level inside each root quadrant and lowers the largest entry by one third.
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 PQ−1PQ^{-1}, QR−1QR^{-1} and RP−1RP^{-1}. 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 x,yx,y of one coordinate frame and write d=∣det⁡(x,y)∣d=|\det(x,y)|. The triangle with vertices 0, xx and yy satisfies

T=∥x∥1∥y∥1∥x−y∥1 ≥ 2d3/2.T=\lVert x\rVert_1\lVert y\rVert_1\lVert x-y\rVert_1\ \ge\ 2d^{3/2}.

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 a,ba,b, with ab=dab = d, and the remaining side has length a+ba + b. The inequality follows from the arithmetic–geometric mean inequality.

In each frame the three primal directions are xx, yy and x−yx - y, each twice. The corresponding dual lengths are the same three lengths divided by dd, each twice. The frame contributes T4/d6≥16T^4/d^6\ge16 to the product of the six rank-one masses. Multiplying across three frames gives at least 163=4616^3=4^6. 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 mm output positions, put μ=m−1∑iei\mu=m^{-1}\sum_i e_i and B=max⁡i,tbitB=\max_{i,t} b_{it}. Each product occurrence may independently relabel output rows and columns, with corresponding input relabelings. Let ZZ give the flattened coefficient weight of a particular output word. With the empty-word weight one, its recurrence and optimal asymptotic peak are

Zv(iw)=∑tbπv(i),tZvt(w),EL=max⁡∣w∣=LZroot(w),inf⁡Slim sup⁡L→∞EL1/L=max⁡(μ,B).\begin{aligned} Z_v(iw)&=\sum_t b_{\pi_v(i),t}Z_{vt}(w),\\ E_L&=\max_{|w|=L}Z_{\rm root}(w),\\ \inf_{\mathcal S}\limsup_{L\to\infty}E_L^{1/L}&=\max(\mu,B). \end{aligned}

Averaging over output words gives the μ\mu lower bound. Following a largest single term at every level gives the BB 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 bb at each leaf, stored inputs, unit roundoff uu, and no underflow or overflow, the corresponding forward bound at n=b2Ln=b2^L is

∥C^−AB∥max⁡ ≤ b[(1+u)5L+b−1]⋅EL ∥A∥max⁡∥B∥max⁡.\begin{aligned}\|\widehat C-AB\|_{\max}\ \le\ &b\big[(1+u)^{5L+b}-1\big]\\[-2pt]&{}\cdot E_L\,\|A\|_{\max}\|B\|_{\max}.\end{aligned}

The exponent counts at most one rounding for each input’s linear form and three for output recombination per level, plus at most bb 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 319/18≈17.7222319/18\approx17.7222. 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

QuantityStationary StrassenD’Alberto’s ruleSettingInterpretation
Exact coefficient peak14496Depth 2Known two-level example
Exact coefficient peak61,917,364,2241,610,612,736Depth 10Same seven products per node
Peak float32 error1× reference for ratio0.206–0.408×Depth 10Range of four panel medians
Within 1% peak error0 of 123 of 12Depth 5, Metal float16Native GEMM passed all 12
Within 1% peak error0 of 120 of 12Depth 6, Metal float16The 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.

Exact peak coefficient weight divided by the stationary baseline at depths two through ten.Median paired float32 CPU peak-error ratio by recursion depth.Cases passing the one-percent peak error threshold on a CPU using binary16.Worst binary16 peak error on the Metal GPU compared with the one-percent threshold.
What changes with recursion depthFour input families and three seeds per depth. Each ratio uses its own stationary formula as baseline. CPU float32 uses sides 64–4,096, CPU float16 uses scalar leaves and sides 4–1,024, and Metal uses the same twelve 256 × 256 inputs at every depth.

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 b,cb,c 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.

A=(1bc1),∣b∣,∣c∣≤2−12,RN⁡(1+x)=1,RN⁡(x−1)=−1(x=b,c).\begin{aligned} A&=\begin{pmatrix}1&b\\c&1\end{pmatrix},\quad |b|,|c|\le 2^{-12},\\ \operatorname{RN}(1+x)&=1,\quad \operatorname{RN}(x-1)=-1\quad(x=b,c). \end{aligned}

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 21922^{192} 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.

Four-by-four sign grids show a Walsh pattern and a best row-and-column route. Four marked positions disagree, hiding eight small entries.
Why a single set of swaps cannot protect every entryEach square represents two small entries among four quadrants at the same position. In this smaller example, even a best route leaves four of the sixteen squares exposed to rounding.
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 m=64m=64, a sharp sign-sum bound leaves m2−m3/2=3584m^2-m^{3/2}=3584 small entries hidden under the best fixed route. The condition number of every input is at most 513/511513/511.

A route choice can itself communicate something about those entries. For an alphabet of size qq, write kak_a for the number of hidden entries under route aa. Counting distinct messages gives the lower bound below. Hall’s matching theorem shows that a decoder attaining the bound exists.

b∗=max⁡ ⁣(0,⌈−log⁡2∑aq−ka⌉).b_* = \max\!\left(0,\left\lceil-\log_2\sum_a q^{-k_a}\right\rceil\right).

Using the published count of six-variable bent functions and bounding the remaining terms gives 42,916 bits at q=4099q=4099. 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.

Static signed channel permutation · one M4 Max CPU thread
ChannelsMethodWrong entriesTime (ms)
256Convolution00.0342
Gather + signs00.0135
512Convolution65,5360.2765
Gather + signs00.0412
1,024Convolution262,1442.0190
Gather + signs00.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 XX or YY. For the same scatter difference GG, the temporal midpoint gives an alternative calculation

G=XXT−YYT=MDT+DMT,M=(X+Y)/2,D=X−Y.\begin{aligned}G&=XX^{\mathsf T}-YY^{\mathsf T}\\ &=MD^{\mathsf T}+DM^{\mathsf T},\\ M&=(X+Y)/2,\qquad D=X-Y. \end{aligned}

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.

Mean normalized peak error of eight methods on the original and fresh changed video pairs.Median time in milliseconds for 36 patch pairs, including detection and transfers, on a log axis.
Matching cost and accuracy on OpenCV patchesError is averaged over changed pairs. Timing covers all 36 pairs in each fixture. Smaller values are better in both panels. Select any panel to view it at full size.
Apple M4 Max · 29 changed pairs for accuracy · 36 pairs for time
MethodExecutionMean peak errorMedian batch time
Direct float32 GEMMGPU4.39e−70.509 ms
Temporal midpointGPU · known pairing3.26e−80.585 ms
Paired product identityGPU · known pairing5.63e−80.598 ms
Kahan summationGPU · ordinary products1.25e−71.762 ms
Blind matching + GEMMGPU · search included1.09e−710.130 ms
Blind matching + GEMMCPU search, GPU product1.09e−785.755 ms
Float64 → float32CPU · rounded output1.20e−80.074 ms
Float64 GEMMCPU · native output0 (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 2.780×10−62.780\times10^{-6} to 1.848×10−61.848\times10^{-6}. The simpler GPU midpoint reached 3.264×10−83.264\times10^{-8}. 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 A=[X  Y  0]A=[X\;Y\;0] and B=[X  −Y  0]TB=[X\;{-Y}\;0]^{\mathsf T}, we report each case’s maximum entry error divided by ∥A∥max⁡∥B∥max⁡\lVert A\rVert_{\max}\lVert B\rVert_{\max} 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

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/}
}