# Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers

arXiv: https://arxiv.org/abs/2510.13444 · HTML: https://mlsanity.com/paper/2510.13444/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 22 references that are in the map.
- First posted on arXiv 15 Oct 2025.

## Builds on (most cited first, 9 of 9)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [TSSOS: A Moment-SOS hierarchy that exploits term sparsity](https://mlsanity.com/paper/1912.08899/) (2019)
- [Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension](https://mlsanity.com/paper/2003.03210/) (2020)
- [Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms](https://mlsanity.com/paper/2505.23696/) (2025)
- [SoS1: O1 and R1-Like Reasoning LLMs are Sum-of-Square Solvers](https://mlsanity.com/paper/2502.20545/) (2025)
- [Synthesizing Control Laws from Data using Sum-of-Squares Optimization](https://mlsanity.com/paper/2307.01089/) (2023)

## Built on by (most cited first, 2 of 2)

- [The Agentic Researcher: A Practical Guide to AI-Assisted Research in Mathematics and Machine Learning](https://mlsanity.com/paper/2603.15914/) (2026)
- [Learning to Coordinate Symbolic Tools: LLM Agents for Verified Sum-of-Squares Certificates](https://mlsanity.com/paper/2608.00326/) (2026)

## Abstract (arXiv)

Certifying nonnegativity of polynomials is a well-known NP-hard problem with direct applications spanning non-convex optimization, control, robotics, and beyond. A sufficient condition for nonnegativity is the Sum of Squares (SOS) property, i.e., it can be written as a sum of squares of other polynomials. In practice, however, certifying the SOS criterion remains computationally expensive and often involves solving a Semidefinite Program (SDP), whose dimensionality grows quadratically in the size of the monomial basis of the SOS expression; hence, various methods to reduce the size of the monomial basis have been proposed. In this work, we introduce the first learning-augmented algorithm to certify the SOS criterion. To this end, we train a Transformer model that predicts an almost-minimal monomial basis for a given polynomial, thereby drastically reducing the size of the corresponding SDP. Our overall methodology comprises three key components: efficient training dataset generation of over 100 million SOS polynomials, design and training of the corresponding Transformer architecture, and a systematic fallback mechanism to ensure correct termination, which we analyze theoretically. We validate our approach on over 200 benchmark datasets, achieving speedups of over 100× compared to state-of-the-art solvers and enabling the solution of instances where competing approaches fail. Our findings provide novel insights towards transforming the practical scalability of SOS programming.