Meta Flip Graph meets Serendipitous Product: new Fast Matrix Multiplication results Andrew I. Perminov Abstract This paper presents new results for fast matrix multiplication in small formats obtained by combining the meta flip graph framework with the serendipitous product construction. The framework has been extended to support all 680 rectangular formats with dimensions up to 16 × 16 × 16 16\times 16\times 16 . Compared to the previous state of the art, ranks are improved for 207 formats. For 84 formats, ternary schemes are found where previously only integer or rational coefficients were known. Additionally, 23 new schemes with asymptotic exponent ω < log 2 ⁡ 7 \omega<\log_{2}7 are discovered, bringing the total number of such schemes to 52. The overall distribution of coefficient types across all investigated formats is 374 ternary, 18 integer, and 288 rational. All code and discovered schemes are available as open source. Keywords Fast matrix multiplication \cdot Flip graph \cdot Serendipitous Product \cdot Tensor rank 1 Introduction Matrix multiplication is a fundamental operation in numerical linear algebra and beyond. The naive algorithm multiplies two n\times n matrices using n^{3} multiplications. Strassen’s breakthrough [ 24 ] reduced the exponent to \log_{2}7\approx 2.807 by presenting a scheme for the 2\times 2 format, launching the search for Strassen-like algorithms. The rank of multiplying an n\times m matrix by an m\times p matrix is the minimum number r for which an algorithm exists. Improvements in rank for small formats are of particular interest, as they can lead to better asymptotic exponents for matrix multiplication when combined through recursive or product constructions. The best known ranks for all formats up to certain bounds are continuously tracked in an online catalog maintained by Sedoglavic [ 20 ] , which currently contains 5426 entries and serves as the primary reference for upper bounds. Beyond the rank itself, the coefficient set used by a scheme is of practical importance. Schemes with coefficients in \mathbb{Z}_{T}=\{-1,0,1\} (ternary coefficients) are particularly attractive for hardware implementation, as they require only additions, subtractions, and no multiplications by constants beyond sign changes. Schemes requiring larger integers ( \mathbb{Z} ) introduce multiplication by non-trivial constants, while schemes with fractions ( \mathbb{Q} ) require division (or shifts when dividing by powers of two) operations, both of which add computational overhead. Various automated methods have been developed to discover matrix multiplication schemes. SAT solving with symmetry breaking [ 8 , 9 , 25 ] works for small formats but scales poorly. Constraint programming [ 3 ] is effective for exhaustive search in small spaces. Numerical optimization [ 21 ] often yields a lot of fractions and suffers from poor convergence to exact solutions. AlphaTensor [ 7 ] uses reinforcement learning and frames algorithm discovery as a game of tensor factorization. AlphaEvolve [ 16 ] extends this direction by employing language models to automate the search. However, these AI-discovered algorithms often employ large integers, fractions, or complex coefficients, introducing computational overhead for hardware implementation. More recent machine learning approaches train neural networks to directly discover low-rank decompositions [ 23 , 6 ] . An alternative paradigm that operates directly on algebraic structures is the flip graph approach. The flip graph approach [ 11 ] models schemes as vertices and local transformations as edges. The adaptive flip graph [ 1 ] introduced the plus operator, which helps avoid getting stuck in local minima and accelerates the search for lower-rank decompositions. Subsequent work [ 14 ] incorporated symmetries of matrix multiplication into the flip graph framework, significantly reducing the search space and enabling more efficient exploration. The meta flip graph [ 12 ] further extended this paradigm by introducing meta-operators that change the dimensions of schemes, enabling navigation between different matrix formats. The present work builds directly on the meta flip graph framework, continuing the direction established in previous work on flip graph search [ 17 ] and its open-source implementation [ 19 ] . This paper presents new results obtained by combining the meta flip graph approach with the serendipitous product construction introduced by Smith [ 22 ] and generalized by Sedoglavic [ 20 ] . The main contributions are as follows: • Improved ranks for 207 matrix multiplication formats compared to the previous state documented in [ 19 ] . • Rediscovery of 84 schemes in \mathbb{Z}_{T} (ternary coefficients) that were previously known only over \mathbb{Z} or \mathbb{Q} . • Discovery of 23 new schemes with asymptotic exponent \omega<\log_{2}7 , bringing the total number of such schemes to 52. • A comprehensive survey of coefficient types across 680 formats n\times m\times p with 2\leq n\leq m\leq p\leq 16 : 374 are ternary ( \mathbb{Z}_{T} ), 18 require integers outside \{-1,0,1\} , and 288 involve fractions. All code and discovered schemes are available as open source at: • Flip graph framework: https://github.com/dronperminov/ternary_flip_graph • Schemes and results: https://github.com/dronperminov/FastMatrixMultiplication The paper is organized as follows. Section 2 recalls the necessary definitions. Section 3 describes the meta flip graph framework as implemented and the procedure for exploiting serendipitous products. Section 4 presents the experimental setup and the numerical results. Section 5 discusses possible improvements and future directions. Section 6 concludes. 2 Preliminaries 2.1 Matrix Multiplication Schemes Definition 2.1 ( Matrix multiplication scheme ) . A scheme for multiplying matrices A\in\mathbb{F}^{n\times m} and B\in\mathbb{F}^{m\times p} over an arbitrary field \mathbb{F} with rank r is denoted (n,m,p:r) . It consists of three tensors U\in\mathbb{F}^{r\times n\times m} , V\in\mathbb{F}^{r\times m\times p} and W\in\mathbb{F}^{r\times p\times n} that define the computation as follows. First, r bilinear products (multiplications) are computed: \displaystyle m_{1}=(u^{(1)}_{11}a_{11}+\cdots+u^{(1)}_{nm}a_{nm})\cdot \displaystyle(v^{(1)}_{11}b_{11}+\cdots+v^{(1)}_{mp}b_{mp}) \displaystyle m_{r}=(u^{(r)}_{11}a_{11}+\cdots+u^{(r)}_{nm}a_{nm})\cdot \displaystyle(v^{(r)}_{11}b_{11}+\cdots+v^{(r)}_{mp}b_{mp}), and the elements of the result matrix C=AB are calculated as: \displaystyle c_{ij}=w^{(1)}_{ji}m_{1}+\cdots+w^{(r)}_{ji}m_{r}. For the scheme to be correct, the coefficients u^{(l)}_{i_{1}i_{2}} , v^{(l)}_{j_{1}j_{2}} , w^{(l)}_{k_{1}k_{2}} must satisfy a system of polynomial equations known as the Brent equations [ 2 ] : \sum_{l=1}^{r}u^{(l)}_{i_{1}i_{2}}v^{(l)}_{j_{1}j_{2}}w^{(l)}_{k_{1}k_{2}}=\delta_{i_{2}j_{1}}\delta_{i_{1}k_{2}}\delta_{j_{2}k_{1}}, for all indices i_{1},k_{2}\in\{1,\dots,n\} , i_{2},j_{1}\in\{1,\dots,m\} , j_{2},k_{1}\in\{1,\dots,p\} . The Kronecker delta \delta_{ij} equals 1 if i=j and 0 otherwise. Formally, each u^{(l)} is an n\times m matrix, v^{(l)} is an m\times p matrix, and w^{(l)} is a p\times n matrix. For notational convenience, these matrices are vectorized in row-major order and treated as vectors of dimensions nm , mp and pn respectively. Each such vectorized component is called a rank-one tensor. This vectorized view simplifies the algebraic manipulation of schemes and is used throughout the remainder of the paper. 2.2 Flip Graph Operators The flip graph approach [ 11 ] represents each valid scheme as a vertex. Edges correspond to local transformations that preserve correctness. The core operators are defined as follows. Definition 2.2 ( Flip ) . For two rank-one tensors with u^{(i)}=u^{(j)} , the transformation is \displaystyle u^{(i)}\otimes v^{(i)}\otimes w^{(i)}\;+\; \displaystyle u^{(j)}\otimes v^{(j)}\otimes w^{(j)}\;\rightarrow \displaystyle u^{(i)}\otimes(v^{(i)}+v^{(j)})\otimes w^{(i)}\;+\; \displaystyle u^{(j)}\otimes v^{(j)}\otimes(w^{(j)}-w^{(i)}). This preserves rank and correctness. The operator can be applied analogously when v^{(i)}=v^{(j)} or w^{(i)}=w^{(j)} . Definition 2.3 ( Plus ) . For two rank-one tensors satisfying u^{(i)}\neq u^{(j)} , v^{(i)}\neq v^{(j)} , and w^{(i)}\neq w^{(j)} , the transformation expands the scheme as: \displaystyle u^{(i)}\otimes v^{(i)}\otimes w^{(i)}\quad+ \displaystyle\quad u^{(j)}\otimes v^{(j)}\otimes w^{(j)}\quad\rightarrow \displaystyle u^{(i)}\otimes(v^{(i)}+v^{(j)})\otimes w^{(i)}\quad+ \displaystyle\quad u^{(i)}\otimes v^{(j)}\otimes(w^{(j)}-w^{(i)})\quad+\quad(u^{(j)}-u^{(i)})\otimes v^{(j)}\otimes w^{(j)} This operation increases the scheme’s rank while preserving correctness. Definition 2.4 ( Reduction ) . For two rank-one tensors with u^{(i)}=u^{(j)} and v^{(i)}=v^{(j)} , the transformation combines them as: \displaystyle u^{(i)}\otimes v^{(i)}\otimes w^{(i)}\;+\;u^{(j)}\otimes v^{(j)}\otimes w^{(j)}\;\rightarrow\;u^{(i)}\otimes v^{(i)}\otimes(w^{(i)}+w^{(j)}). This decreases the rank by one by eliminating redundant components. The operator applies analogously for equalities in other pairs of tensors. The meta flip graph framework [ 12 ] introduces operators that change dimensions, enabling navigation between different matrix formats: Definition 2.5 ( Merge ) . Combines two schemes with compatible dimensions. For example, (n,m,p_{1}:r_{1}) and (n,m,p_{2}:r_{2}) merge to (n,m,p_{1}+p_{2}:r_{1}+r_{2}) . The same applies to the other two axes. Definition 2.6 ( Product ) . Forms the tensor product of two schemes. Given (n_{1},m_{1},p_{1}:r_{1}) and (n_{2},m_{2},p_{2}:r_{2}) , the result is (n_{1}n_{2},m_{1}m_{2},p_{1}p_{2}:r_{1}r_{2}) . Definition 2.7 ( Extend ) . Naively extends a scheme by one dimension. For instance, (n,m,p:r) extends to (n,m,p+1:r+m\cdot n) by merging with a trivial (n,m,1:m\cdot n) scheme that computes each output entry directly. Analogous extensions exist for the other axes. Definition 2.8 ( Project ) . Reduces a scheme by one dimension. From (n,m,p:r) , projection along the p -axis yields (n,m,p-1:r^{\prime}) where r^{\prime}\leq r , obtained by removing entries corresponding to the last dimension and eliminating zero coefficients. The other axes are handled similarly. 2.3 Coefficient Rings Throughout this paper, the following coefficient rings are used. Notation 2.1 ( \mathbb{Z}_{2} ) . Binary coefficients \{0,1\} with arithmetic modulo 2 . Notation 2.2 ( \mathbb{Z}_{3} ) . Ternary coefficients \{0,1,2\} with arithmetic modulo 3 . Notation 2.3 ( \mathbb{Z}_{T} ) . Integer ternary coefficients \{-1,0,1\} with standard integer arithmetic. Notation 2.4 ( \mathbb{Z} ) . Integer coefficients, where at least one coefficient satisfies |c|>1 . Notation 2.5 ( \mathbb{Q} ) . Rational coefficients, where at least one coefficient is a non-integer fraction. 2.4 Tensor Structure of Matrix Multiplication Schemes A matrix multiplication scheme (n,m,p:r) can be represented as a sum of rank-one tensors: \mathcal{T}=\sum_{i=1}^{r}u^{(i)}\otimes v^{(i)}\otimes w^{(i)}. (1) Definition 2.9 ( Bud 1 1 1 This terminology was suggested by A. Sedoglavic in private communication. ) . A pair of indices (i,j) , i\neq j , such that u^{(i)}=u^{(j)} (or the same condition holds for v or w ). If equality holds for more than one tensor among \{U,V,W\} , the rank can be reduced, therefore only buds where equality holds for exactly one tensor are considered. Definition 2.10 ( Elementary matrix multiplication tensor ) . A set of indices together with the corresponding components u^{(i)} , v^{(i)} , w^{(i)} that form a self-contained matrix multiplication substructure of dimensions N\times M\times P , denoted \langle N,M,P\rangle . A scheme can be decomposed into elementary tensors formed by its buds [ 10 ] . The buds induce relations on the set of indices: equalities in U , V and W collectively suggest possible groupings. Indices can be grouped into blocks, where each block corresponds to an elementary matrix multiplication tensor \langle N_{i},M_{i},P_{i}\rangle , with N_{i} , M_{i} , P_{i} determined by the bud pattern within that block. The remaining indices (those not participating in any block) form trivial blocks \langle 1,1,1\rangle . Example 2.1 ( Elementary tensors from bud patterns ) . • A single index: \langle 1,1,1\rangle . • A U -bud (i,j) : \langle 1,1,2\rangle . • k indices with all pairwise U -buds: \langle 1,1,k\rangle . • A V -bud (i,j) : \langle 2,1,1\rangle . • A W -bud (i,j) : \langle 1,2,1\rangle . • Four indices \{i_{1},i_{2},j_{1},j_{2}\} with U -buds (i_{1},i_{2}) , (j_{1},j_{2}) and V -buds (i_{1},j_{1}) , (i_{2},j_{2}) : \langle 2,1,2\rangle . The same set of buds can sometimes be grouped into elementary tensors in different ways. For example, a \langle 2,1,2\rangle tensor can also be represented as two independent \langle 1,1,2\rangle or two independent \langle 2,1,1\rangle tensors. Definition 2.11 ( Scheme tensor structure ) . A representation of a scheme as a sum of elementary tensors: \mathcal{T}=\sum_{i=1}^{t}S_{i}\cdot\langle N_{i},M_{i},P_{i}\rangle, (2) where each \langle N_{i},M_{i},P_{i}\rangle is an elementary matrix multiplication tensor formed by a chosen grouping of indices, and S_{i} is a multiplicity factor. The rank of the scheme then satisfies r=\sum_{i=1}^{t}S_{i}\cdot N_{i}\cdot M_{i}\cdot P_{i}. (3) For a scheme without any buds, the decomposition consists of r different \langle 1,1,1\rangle tensors. 2.5 Serendipitous Product The serendipitous product construction, introduced by Smith [ 22 ] and generalized by Sedoglavic [ 20 ] , combines two matrix multiplication schemes (n_{1},m_{1},p_{1}:r_{1}) and (n_{2},m_{2},p_{2}:r_{2}) to obtain a scheme for the format (n_{1}n_{2},m_{1}m_{2},p_{1}p_{2}:r_{s}) whose rank can be lower than the naive (Kronecker) product r_{1}\cdot r_{2} . Let the first scheme be decomposed into elementary tensors: \mathcal{T}_{1}=\sum_{i=1}^{t}S_{i}\cdot\langle N_{i},M_{i},P_{i}\rangle. (4) Definition 2.12 ( Serendipitous product ) . Applying the second scheme to each elementary blocks gives \mathcal{T}_{1}\otimes(n_{2},m_{2},p_{2}:r_{2})\;=\;\sum_{i=1}^{t}S_{i}\cdot\langle N_{i}n_{2},\;M_{i}m_{2},\;P_{i}p_{2}\rangle. (5) Each term \langle N_{i}n_{2},M_{i}m_{2},P_{i}p_{2}\rangle is realized using the best known scheme for that format, with rank R(N_{i}n_{2},M_{i}m_{2},P_{i}p_{2}) . The concrete algorithm for constructing such a product is described in Section 2.6 . The total rank of the serendipitous product is therefore r_{s}=\sum_{i=1}^{t}S_{i}\cdot R\bigl(N_{i}n_{2},\;M_{i}m_{2},\;P_{i}p_{2}\bigr), (6) where R(N,M,P) denotes the best known rank for format (N,M,P) . The construction yields a genuine improvement over the naive product only when R(N_{i}n_{2},M_{i}m_{2},P_{i}p_{2})