PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Kechen Li, Wenqi Zhu, Coralia Cartis, Tianbo Ji, Shiwei Liu

arXiv:2502.20545v1cs.LG

TL;DR

The paper investigates a fundamental mathematical problem related to Hilbert's Seventeenth Problem, which plays a crucial role in various fields. It introduces SoS-1K, a dataset of approximately 1,000 polynomials with SoS reasoning instructions; LLMs achieve up to 81% accuracy.

  • Problem

    The paper investigates a fundamental mathematical problem related to Hilbert's Seventeenth Problem, which plays a crucial role in various fields.

    Source: §1 · p. 1, §7 · p. 8

  • Method

    The paper introduces SoS-1K, a dataset of approximately 1,000 polynomials with SoS reasoning instructions.

    Source: §7 · p. 8

  • Results

    LLMs achieve up to 81% accuracy, with accuracy boosts across models reaching up to 21%.

    Source: §1 · p. 2, §7 · p. 8

  • Takeaways & Limitations

    SoS-1K contributes a dataset of approximately 1,000 polynomials and SoS reasoning instructions.

    Source: §7 · p. 8

    For long-input cases, invalid samples occur.

    Source: Q6: Do SOTA LLMs have any limitations? · p. 7

Abstract

from arXiv · show

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.

1 Introduction

The introduction frames polynomial nonnegativity and sum-of-squares problems as a demanding test of mathematical reasoning, situating reasoning LLMs within classical and AI-based research. It presents SoS-1K as a benchmark for evaluating LLMs with structured guidance and discusses performance improvements alongside the computational limits of classical methods.

1 Introduction

  • Determining whether a general polynomial is nonnegative is NP-hard, even for relatively low-degree polynomials or those with few variables.The problem is closely related to Hilbert’s Seventeenth Problem and is central to global polynomial optimization.Source: §1 · pp. 1–2
  • Classical sum-of-squares approaches yield large semidefinite programming problems, making them challenging to scale.The paper motivates evaluating whether reasoning LLMs can solve large-scale sum-of-squares programming problems.Source: §1 · p. 2
  • SoS-1K contains approximately 1,000 polynomials and expert-designed reasoning instructions organized around five progressively challenging criteria.The criteria concern polynomial degree, leading search-direction nonnegativity, special structures, square-form expressions, and monomial quadratic-form matrix decomposition.Source: §1 · p. 2
  • Most models achieve only around 60% accuracy on plain questions, slightly above the 50% random-guess baseline; high-quality reasoning traces boost accuracy by up to 21%.Models also perform better with higher-quality traces.Source: §1 · p. 2
  • Reasoning-focused LLMs generally outperform general-purpose models, while higher-capacity models need fewer thinking tokens and lower-capacity models need more steps for optimal performance.Source: §1 · p. 2
  • Qwen2.5-14B-Instruct-1M uses the Motzkin polynomial to generate previously unseen counterexamples to Hilbert’s 17th problem (Motzkin, 1967).The introduction says prompted models demonstrate an understanding of research-level questions.Source: §1 · pp. 2–3
  • The findings suggest that LLMs exhibit reasoning patterns that expand the boundaries of solving NP-hard problems.Source: §1 · p. 3
  • The work is presented as a pilot study of reasoning LLMs for SoS problems, aimed at research-level mathematical questions using AI.Source: §1 · p. 3

1.1 Related Work

  • Research on SoS and nonnegative polynomials spans over 120 years.Source: §1.1 · p. 3
  • Classical SoS methods express polynomials as quadratic forms of monomials and reformulate the problem as an SDP; the Lasserre hierarchy dates to 2001 (Lasserre, 2001).Source: §1.1 · p. 3
  • Numerical SoS solvers began emerging in 2009, including GloptiPoly and SoSTOOLS (Papachristodoulou et al., 2013).Source: §1.1 · p. 3
  • Alfarano et al. (2024) trained Transformers to discover Lyapunov functions guaranteeing global stability in polynomial dynamical systems, a problem tied to the SoS framework.Source: §1.1 · p. 3
  • That approach was tested on systems with at most five equations and showed promising results against conventional solvers.Source: §1.1 · p. 3

2 SoS-1K Dataset

The paper introduces SoS-1K alongside expert-designed instructions that guide models through progressively detailed checks for identifying sum-of-squares polynomials. The dataset contains five subsets of polynomials with labels, justifications, and difficulty levels.

Definition 2.1 SoS polynomial (Ahmadi et al.,

2.1 Expert-Designed Reasoning Instructions for SoS

  • SoS Plain asks whether a polynomial can be expressed as a sum of squares, while SoS Simple groups cases under five concise criteria.The three instruction variants are SoS Plain, SoS Simple, and SoS Reasoning.Source: §2.1 · p. 4
  • SoS Reasoning is a structured five-step framework that guides mathematical verification of whether a polynomial is SoS.It provides proof- and theorem-based reasoning traces, examples, and intermediate steps involving the Q matrix and squared form.Source: §2.1 · p. 4

2.2 Construction of SoS-1K Test Set

  • SoS-1K contains five subsets of polynomials corresponding to cases filtered out at Steps 1–5.The dataset provides labels, justifications, and difficulty levels; most polynomials are kept within 4,000 tokens.Source: §2.2 · pp. 4–5

3 Evaluation of LLMs on SoS

Across the evaluated models, structured SoS instructions improve accuracy over plain prompts, with SoS Reasoning producing the strongest reported results. Reasoning-purpose LLMs also achieve higher average accuracy than general-purpose models.

OB1. All LLMs fail when presented with a plain

  • Without explicit prompting, all LLMs achieve 50%–60% accuracy on SoS Plain, except QwQ-32B-Preview at 64% valid accuracy.The authors interpret these results as evidence that models struggle to solve SoS problems without explicit prompting.Source: OB1. All LLMs fail when presented with… · p. 5

mance boost when prompted with high-quality

OB3. Reasoning-purpose LLMs benefit more

  • Reasoning-purpose LLMs average 79.0% accuracy, compared with 72.9% for general-purpose LLMs.The authors suggest stronger reasoning capabilities contribute to improved performance on SoS problems.Source: OB3. Reasoning-purpose LLMs benefit more · p. 5

4 Further Analysis

Further analyses examine how models reason through SoS problems, handle long polynomial inputs, and respond to different reasoning lengths. The results identify improved accuracy with structured checks alongside limits involving shortcuts, difficult polynomials, and invalid outputs.

step by step verification process?

  • Correctness checks can be logically and mathematically sound step by step, with o1-mini stopping after deriving an answer.The example follows the SoS Reasoning instruction and is shown in Appendix F.Source: step by step verification process? · pp. 5–6

mation from long-context polynomials?

  • For long polynomials, QwQ-32B-Preview struggles beyond 4K tokens, while most SOTA LLMs can extract necessary coefficients from 4K-length inputs.The analysis focuses on extracting critical information from structured polynomial expressions.Source: mation from long-context polynomials? · p. 6

Reasoning does the accuracy improve?

  • On the more challenging test sets, accuracy continuously improves from SoS Plain to SoS Simple and further in the SoS progression; the simplest Test Set 1 achieves 100% accuracy across all prompting methods.Source: Reasoning does the accuracy improve? · p. 6

during reasoning?

  • o1-mini and QwQ-32B-Preview may skip Step 5 on simpler problems, while DeepSeek-V3 completes all steps and takes 40 seconds.o1-mini's reported runtime is 17 seconds; shortcuts are especially associated with long inputs and complex polynomials.Source: during reasoning? · p. 7

Q5: How does reasoning length affect accuracy?

Q6: Do SOTA LLMs have any limitations?

  • On small polynomials, LLM accuracy is close to 90%, but models struggle when a quadratic form involves low-rank matrix decomposition.For long-input cases, DeepSeek-R1 returns only 234 valid samples out of 340; prematurely guessing at difficult steps can hurt accuracy.Source: Q6: Do SOTA LLMs have any limitations? · p. 7

5 Performing SFT on SoS-1K

The paper fine-tunes a 7B model on SoS-1K and reports its accuracy and response-time comparisons with larger models. SoS-7B achieves 70% total accuracy and responds faster than DeepSeek-V3.

5 Performing SFT on SoS-1K

  • SoS-7B is produced by supervised fine-tuning Qwen2.5-7B-Instruct-1M on SoS-1K.The passage also reports a four-hour training duration.Source: §5 · p. 7
  • 70% total accuracy lets SoS-7B outperform 671B DeepSeek-V3 at 69%, with response times of 1.8 seconds versus 100 seconds.o1-mini reports 75% accuracy; the authors also compare SoS-7B's 1.8-second response time with 34.9 seconds.Source: §5 · p. 7

6 Model’s Understanding of SoS and Nonnegativity

The section probes whether models can generate and assess unfamiliar nonnegative, non-Sum-of-Squares polynomials. It contrasts plain prompting with SoS reasoning and examines a newly generated example.

6 Model’s Understanding of SoS and Nonnegativity

  • Under plain prompting, Qwen-14B-1M gave only known examples, while Qwen-7B-1M returned an incorrect example.The section says the incorrect example was nontrivial, and notes YALMIP could not extract global optimality because rank conditions did not ensure it.Source: §6 · p. 8
  • With SoS reasoning, the model correctly rejected pa as a NNSoS candidate because it is a nonnegative quartic polynomial in two variables.The section attributes the improvement to Step 4 of SoS Reasoning.Source: §6 · p. 8
  • With SoS reasoning, Qwen-14B-1M derived a new valid NNSoS example, which YALMIP confirmed.The example is qa; the section also describes how it was constructed from a known example by adding a variable and modifying coefficients.Source: §6 · p. 8
  • The generated qa example adapts a known NNSoS example by adding a variable and slightly changing its coefficients.The authors present this as evidence that the trained model can recognize existing patterns and construct novel cases.Source: §6 · p. 8

7 Conclusion and Discussion

The conclusion frames polynomial nonnegativity as a consequential research problem and introduces SoS-1K with SoS-specific reasoning instructions. It reports accuracy up to 81% and points to AI’s potential for mathematical problems.

7 Conclusion and Discussion

  • SoS-1K contains approximately 1,000 polynomials and is paired with SoS-specific reasoning-guiding instructions.The paper studies whether a given multivariate polynomial is SoS, a problem closely related to Hilbert’s Seventeenth Problem.Source: §7 · p. 8
  • With expert-designed reasoning instructions, LLMs achieve up to 81% accuracy.The conclusion presents the instructions as based on progressively challenging criteria and reports an in-depth analysis of model responses.Source: §7 · p. 8
  • The authors highlight AI’s potential for tackling large-scale open problems in mathematics.The conclusion describes the studied task as determining whether a multivariate polynomial is SoS.Source: §7 · p. 8

8 Limitation and Potential Risks

The paper limits its evaluations to SoS questions within a 4K context and says most polynomials remain within traditional-solver capacity. Its background reviews the complexity and mathematical tools behind SoS, then gives a stepwise reasoning procedure.

8 Limitation and Potential Risks

  • SoS questions are constrained to a 4K context; most polynomials therefore remain within traditional-solver capacity, and the authors plan to target harder cases.The authors also flag potentially misleading LLM decisions and say traditional solvers are needed for verification.Source: §8 · p. 9

A Literature Review for SoS

  • General polynomial nonnegativity is described as NP-hard, while SoS provides a sufficient nonnegativity criterion that can be reformulated as an SDP.The review notes that special cases exist where nonnegativity and SoS are equivalent.Source: A Literature Review for SoS · p. 11

Definition B.1 (Total degree polynomial space)

  • Definition B.1 introduces Pp′[x] as a polynomial space whose entries have degree at most p′.The definition names n as the dimension and x as the variables.Source: Definition B.1 (Total degree… · p. 12

B Mathematical Background for SoS

  • An SoS polynomial can be represented using a positive semidefinite matrix Q and a polynomial basis vector.The cited definition states that the polynomial equals ϕ_d(x)^T Qϕ_d(x) for all x, with Q ⪰ 0.Source: Definition B.1 (Total degree… · p. 12

C SoS Simple

  • The SoS Simple procedure checks the highest-degree parity and coefficients, considers special polynomial families, then tries direct squares or matrix methods.Its listed special cases include quadratics, quartics in one to three variables, and even-degree univariate polynomials.Source: C SoS Simple · p. 12

D SoS Reasoning

This section presents a progressively stronger protocol for testing whether polynomials are sums of squares, including checks for special classes where nonnegativity implies SoS. It also describes how test examples and counterexamples were constructed and checked, and directs readers to Table 3 for test-subset details.

D SoS Reasoning

  • Odd-degree polynomials and univariate polynomials with a negative highest-degree coefficient are ruled out as SoS; otherwise, the protocol proceeds to further checks.Even degree is a necessary first criterion, not sufficient evidence of SoS.Source: D SoS Reasoning · p. 12
  • A negative constant or a negative value found by grid evaluation, minimum search, or dominant-term analysis proves a polynomial is not SoS.The protocol also checks translated and scaled forms for negative values.Source: D SoS Reasoning · p. 13
  • For a candidate square representation, the protocol seeks an expression as a sum of squares of polynomials and examines term symmetries when the polynomial is expanded.Examples and counterexamples for this check are assigned to Test Set 2.Source: D SoS Reasoning · p. 13
  • Nonnegative quadratics, nonnegative quartics in one or two variables, and nonnegative homogeneous quartics in up to three variables are SoS.The listed cases also include nonnegative even-degree univariate polynomials and polynomials with a quadratic term and quartic regularization.Source: D SoS Reasoning · pp. 13–14
  • For an even-degree polynomial, the final theoretical check constructs a monomial-basis matrix Q and tests its positive definiteness; if earlier tests fail, the protocol can use semidefinite programming.A positive-definite Q establishes SoS, while failure to find one makes non-SoS likely; the representation is not unique.Source: D SoS Reasoning · p. 14
  • Test examples use positive semidefinite Q matrices, including sparse, low-rank, and ill-conditioned cases.The counterexamples are generated using indefinite Q.Source: D SoS Reasoning · p. 14
  • The Test Sets 5.1–5.4 “Not SoS” classifications were cross-checked with classic solvers, since conclusively proving a polynomial is not SoS requires examining all possible Q.Counterexamples generated from indefinite Q are likely not SoS, but that alone is not conclusive proof.Source: D SoS Reasoning · p. 14

E Details for Test Subsets

F Sample Model’s Response under SoS Reasoning Prompt

The sample responses apply the provided SoS reasoning steps, using highest-degree checks to distinguish an odd-degree example from an even-degree case that proceeds to further analysis.

F Sample Model’s Response under SoS Reasoning Prompt

F.2 o1-mini response for a difficult polynomial under SoS Reasoning Prompt

  • For the difficult example, the highest total degree is 4, so the response proceeds because that degree is even.Source: §F.2 · p. 15
  • The next listed check for the difficult example concerns the highest degree in a univariate polynomial.Source: §F.2 · p. 15

G Further Results for Performance of SOTA LLMs

The section presents polynomial examples for discussing SoS and nonnegativity, then frames finding nonnegative polynomials that are not SoS as an ongoing research problem. It also asks whether a general formula or a new example can be constructed.

2. Can you construct a general formula for nonnegative polynomials that are not SoS?

  • The section asks for a general formula for nonnegative polynomials that are not SoS and for a new example not previously found.Source: §2 · p. 16

1. Can you comment on the sum of squares (SoS) and nonnegativity properties of the following

  • The first three listed polynomials are identified as known examples of nonnegative polynomials that are not SoS.The first is the Motzkin polynomial, and the second is the Robinson polynomial.Source: §2 · p. 16

2. Can you construct a general formula for nonnegative polynomials that are not SoS?

  • Finding nonnegative polynomials that are not SoS is described as a significant ongoing problem in real algebraic geometry and polynomial optimization.The passage connects it to Hilbert’s 17th problem, semidefinite programming, and positivity certificates in polynomial optimization.Source: §2 · p. 16

Related papers

Loading 2502.20545v1…