Learning-Guided Flip-Graph Search for Low-Rank Polynomial Multiplication

Polynomial multiplication is a fundamental bilinear operation whose bilinear algorithms correspond to rank-1 decompositions of a structure tensor, with scalar multiplication count equal to the number of rank-1 terms. We study algorithm discovery as learning-guided search over a tensor flip graph, whose nodes are exact decompositions and edges are local algebra-preserving transformations. We propose PolyDiscover, a learning-guided Monte Carlo Tree Search (MCTS) framework that uses a Transformer policy/value model to guide this search. Starting from the schoolbook FOIL decomposition, PolyDiscover navigates orbit flips, zero-sum additions, and recursive rank-reducing rewrites. Under the coefficient restriction {-1,0,1}, all candidate algorithms are verified by reconstruction of the polynomial tensor. For degrees 1–100, the discovered decompositions achieve fewer scalar multiplications than the published Weimerskirch–Paar counts in 84 cases and match them in the remaining 16 under the coefficient restriction over general rings. Structural analysis shows that the discovered algorithms form a recursive subset-sum basis where scalar multiplications are products of overlapping coefficient sums, and output coefficients are recovered by signed inclusion–exclusion.