# SoS1: O1 and R1-Like Reasoning LLMs are Sum-of-Square Solvers

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in Mathematical reasoning, one of 17 directions in LLM reasoning.
- Builds on 20 of its 50 references that are in the map.
- First posted on arXiv 27 Feb 2025.

## Placed in

- LLM reasoning / [Mathematical reasoning](https://mlsanity.com/lr/mathematical-reasoning/)

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Large Language Models Encode Clinical Knowledge](https://mlsanity.com/paper/2212.13138/) (2022)
- [LlamaFactory: Unified Efficient Fine-Tuning of 100+ Language Models](https://mlsanity.com/paper/2403.13372/) (2024)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Instruction Tuning for Large Language Models: A Survey](https://mlsanity.com/paper/2308.10792/) (2023)
- [Large Language Models as Tool Makers](https://mlsanity.com/paper/2305.17126/) (2023)
- [DeepSeek-Prover: Advancing Theorem Proving in LLMs through Large-Scale Synthetic Data](https://mlsanity.com/paper/2405.14333/) (2024)
- [From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models](https://mlsanity.com/paper/2406.16838/) (2024)
- [T1: Advancing Language Model Reasoning through Reinforcement Learning and Inference Scaling](https://mlsanity.com/paper/2501.11651/) (2025)
- [DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization](https://mlsanity.com/paper/1706.02586/) (2017)
- [Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity](https://mlsanity.com/paper/1607.01151/) (2016)
- [On the complexity of finding a local minimizer of a quadratic function over a polytope](https://mlsanity.com/paper/2008.05558/) (2020)
- [A bounded degree SOS hierarchy for polynomial optimization](https://mlsanity.com/paper/1501.06126/) (2015)
- [Sparsity-Exploiting Moment-Based Relaxations of the Optimal Power Flow Problem](https://mlsanity.com/paper/1404.5071/) (2014)
- [Higher-Order Newton Methods with Polynomial Work per Iteration](https://mlsanity.com/paper/2311.06374/) (2023)
- [Sums of Separable and Quadratic Polynomials](https://mlsanity.com/paper/2105.04766/) (2021)
- [Sparse sum-of-squares (SOS) optimization: A bridge between DSOS/SDSOS and SOS optimization for sparse polynomials](https://mlsanity.com/paper/1807.05463/) (2018)
- [Convex Ternary Quartics Are SOS-Convex](https://mlsanity.com/paper/2404.14440/) (2024)

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

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [GridRoute: A Benchmark for LLM-Based Route Planning with Cardinal Movement in Grid Environments](https://mlsanity.com/paper/2505.24306/) (2025)
- [Rethinking the Unsolvable: When In-Context Search Meets Test-Time Scaling](https://mlsanity.com/paper/2505.22290/) (2025)
- [Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers](https://mlsanity.com/paper/2510.13444/) (2025)
- [The Periodic Table of LLM Reasoning: A Structured Survey of Reasoning Paradigms, Methods, and Failure Modes](https://mlsanity.com/paper/2606.11470/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have achieved human-level proficiency across diverse tasks, but their ability to perform rigorous mathematical problem solving remains an open challenge. In this work, we investigate a fundamental yet computationally intractable problem: determining whether a given multivariate polynomial is nonnegative. This problem, closely related to Hilbert's Seventeenth Problem, plays a crucial role in global polynomial optimization and has applications in various fields. First, we introduce SoS-1K, a meticulously curated dataset of approximately 1,000 polynomials, along with expert-designed reasoning instructions based on five progressively challenging criteria. Evaluating multiple state-of-the-art LLMs, we find that without structured guidance, all models perform only slightly above the random guess baseline 50%. However, high-quality reasoning instructions significantly improve accuracy, boosting performance up to 81%. Furthermore, our 7B model, SoS-7B, fine-tuned on SoS-1K for just 4 hours, outperforms the 671B DeepSeek-V3 and GPT-4o-mini in accuracy while only requiring 1.8% and 5% of the computation time needed for letters, respectively. Our findings highlight the potential of LLMs to push the boundaries of mathematical reasoning and tackle NP-hard problems.