Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers
Authors: Nico Pelleriti
Christoph Spiegel
Shiwei Liu
David Martínez-Rubio
Max Zimmer
Sebastian Pokutta
Venue: ICLR 2026 Poster (2026)
Keywords: transformer
ai4math
ai4science
sum-of-squares
polynomial
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We speed up sum-of-squares certification using a Transformer with correctness-preserving repair and expansion.

Abstract: 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 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\times$ 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. Code is available at https://github.com/ZIB-IOL/Neural-Sum-of-Squares.

Published as a conference paper at ICLR 2026
NEURAL SUM-OF-SQUARES CERTIFYING THE NON- NEGATIVITY OF POLYNOMIALS WITH TRANSFORMERS
Nico Pelleriti 12
Christoph Spiegel'.2 1.2
Shiwei Liu
David Martinez-Rubio"
Max Zimmer
Sebastian Pokutta 1.2
Zuse Institute Berlin Technical University of Berlin
ELLIS Institute Tübingen
4 Max Planck Institute for Intelligent Systems 5 TTübingen Al Center
6 Universidad Carlos IIII de Madrid
ABSTRACT
Certifying nonnegativity of polynomials is a well-known NP-hard problem with direct applications spanning non-convex optimization, control, robotics, and be- yond. A sufficient condition for nonnegativity is the Sum of Squares (SOS) prop- erty, i.e., it can be written as a sum of squares of other polynomials. practice, however, certifying the SOS criterion remains computationally expensive and of- ten involves solving Semidefinite Program (SDP), whose dimensionality grows quadratically in the size of the monomial basis of the SOS expression; hence, var- ious methods to reduce the size of the monomial basis have been proposed. In this work, we introduce the first terion. 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 systematic fall- back mechanism to ensure correct termination, which we analyze theoretically. We validate our approach on over 200 benchmark datasets, achieving speedups of over 100x compared to state-of-the-ee 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. Code is avail- able at
algorithm certify the SOS cri-
com ZIB Www.O//eeraaSSuu-----0 Sum--of-Suull
INTRODUCTION
Global optimization of high-degree, nonconvex polynomials underpins tasks as diverse as satellite- attitude control (Misra et al.) [020 Gollu 2008 Jarvis-Wloszer Wloszek et al.] 2003). energy-shaping of quadrotors, and control theory (Bramburger et al. 2024; Jarvis- Jarvis-Wloseee Wloszek et al.] 2003). Uncon- strained polynomial optimization reduces to certifying nonnegativity: the value of minxER= p(x) the largest y such that p(x) 2 for all real x. To illustrate this connection, consider the simple polynomial
pl. 22) = 4x + 12 + 9x +
We can verify that p(z1, (((21,22)=))))) - y is nonnegative for all 7 < 1 by rewriting it as - y. Since this expression is positive when 7 < 1 and zero when 7 1, we conclude that 7 is the global minimum of the polynomial. While this example admits a straightforward algebraic verification, deciding nonnegativity is NP-hard in general, even for simple quartic polynomials such as the one above, which motivates the use of convex relaxations (Ahmadi et al. 1011).
-2
widely used convex relaxation for nonnegativity certification is the SOS condition: a polynomial p(x) is SOS if it can be written as p(x) = Σ ( for some polynomials h; (x). Since any SOS polynomial is clearly nonnegative, this provides a sufficient condition for nonnegativity. For our example, we used that 22) (2x + 3xz)² + +12, which is SOS and therefore nonnegative.
Correspondence pel www.eerriiiiiiii

---

Published as a conference paper at ICLR 2026
217x
Input pogeoniia
Transformer predict Insis
Basis
Valid SOS
lossible
25x
X Not 8OS Full bosis
Eispansion
osgiinal linals
Number of terms
(i) Schematic of the learning-aun augmented SOS framework.
(ii) Speedup.
Overview of our approach for SOS verification. (i) Pipeline schematic: given a polyno- mial, Transformer predicts compact basis, then the basis is adjusted to ensure necessary con- ditions are met, and an SDP is solved with iterative expansion needed. The method guarantees correctness: if SOS certificate exists, will be found; otherwise, infeasibility is certified the full basis. (ii) Speedup over baseline for sparse polynomials with 300, 800, and 3000 distinct terms.
Figure 1:
Parrilo (0033 proved that this condition can be checked via an SDP. That is. is SOS if and only there exists Positive Semidefinite (PSD) matrix Q such that p(x) = z(x) Q @z(x), where zxx) vector of monomials (polynomial terms like z1. 21 etc.). Crucially, SDPs can be solved in polynomial time in the dimension of z(x), making the choice of monomial vector central to computational efficiency.
For our running example p(11, (2) 4zf + 12n + +0x +1, the standard monomial vector contains all monomials up half the degree of the polynomial, yielding 2xx) [1, 21 .2, 02,2 2f, However, we can compute the same SOS decomposition using the much smaller monomial vector z' z'(x) [1, "T This gives us pxx) z (x) Qz' (x) with the matrix
0
0
Q
0
4
6
0
6 9
Therefore, identifying compact monomial basis z' (x) enables drastic reduction in the size of the resulting SDP, yielding substantial computational savings.
Unfortunately, finding such compact bases is itself challenging, and long line of work has focused on reducing basis size (Reznick 1978, Waki et al. [0066] Lofberg] 2009 [aan et al. 2001b). In our example, the commonly used Newton polytope with diagonal consistency (Lofberg) 2009) method (a geometric approach that identifies relevant monomials based on the polynomial structure) would yield the basis z,v (x) [1, x2, 21 which significantly smaller than the full basis z(x)
but still not minimal
In this paper, we address the problem of efficiently selecting compact monomial bases by introducing learning- augmented approach to SOS basis selection. We pose basis selection as a prediction task: given a polynomial, predict a compact monomial basis that is sufficient to express the polynomial as an SOS and yields an SDP that is small possible. Figure proposed approach.
provides an overview of the
To this end, we train a Transformer model Vaswani et al. 2017) that takes a tokenized polynomial as input and outputs monomial basis B. The training data consists of millions of SOS polynomials and (near)-minina basis pairs, which we generate efficiently through reverse sampling process that allows us to construct a polynomial with a known compact SOS decomposition and monomial basis.
While our learning- bassing--baed approach offers the potential for finding significantly smaller bases than rule-based methods, machine learning predictions are inherently inexact. When our Transformer model predicts an incomplete basis-one missing essential monomials for valid SOS decompo- sition-we employ systematic repair strategy that preserves correctness guarantees. Specifically, if the initially predicted basis B cannot produce a valid SOS decomposition, we iteratively expand B by adding monomials until either (1) discover valid decomposition, or (2) all candidate monomials have been considered, implying no SOS decomposition exists. This fallback mechanism
A basis is minimal if it is the smallest possible basis for which given polynomial admits an SOS decomposition. To the best of our knowledge, the computational complexity of finding the true minimal basis remains open, though we derive tight lower bounds on minimal hasis size.
2

---

Published as a conference paper at ICLR 2026
ensures that method maintains the same conrectness guarantees traditional approaches: it cor- rectly identifies whether a SOS decomposition exists, while achieving significant speedups through accurate predictions. We summarize contributions as follows.
Learning-auggeetedd SOS programming. We introduce novel Baaning-augmente algorithm that addresses the fundamental computational bottleneck in SOS programming. Our approach uses Transformer model to predict compact monomial bases for constructing SOS decompositions, directly reducing the size of the resulting SDP problems. By identifying sparse monomial structures that traditional rule-based methods miss, approach achieves significant computational speedups while maintaining correctness guarantees.
Theoretical guarantees. We provide a theoretical analysis, showing that the algorithm's worst- case computational cost exceeds the standard baseline by most constant factor even when the machine learning predictions are completely incorrect. Further, we show that the computational efficiency of the algorithm directly related to the quality of the predicted basis.
Empirical evaluation. We validate our approach across different polynomial structures 200 benchmark datasets, including problems with up to 100 variables, training on over 100 million polynomials. Our experiments demonstrate multiple orders of magnitude speedups compared to state-of-the-ar baselines, while being robust to distribution shifts.
1.1 RELATED WORK
Sum of Squares (SOS) Optimization SOS programming has its theoretical foundations in sem- inal works by Parrilo (2003) and Lasserre (001). who independently developed frameworks for converting polynomial optimization problems into SDPs. Subsequent work has focused scal- ing these relaxations to higher dimensions and degrees. Upstream Desistreduction methods most checks (Lotberg) 2009)-rente -remove unnecessary monomials hefore forming the SDP, Related SOS basis pursuit meth- ods iteratively refine certificates via LP/SOCC-styl subproblems while updating change of basis for the Gram representation (at fixed lifted dimension) (Ahmadi & Hall 2016 Miller et al. 2022) Our method also acts upstream, but uses learned predictor with repair and verification select compact monomial set and thus shrink the SDP, yielding speedups with correctness guarantees. In contrast, chordal/term sparsity and structured- subset decompositions (Waki et al.) 2006 Mason & P'aaachristodollou 2014; Zheng et al. 2019 Wang et al. 2021b a Newton & Papachristoooolluu
notably
pruming (Reznick 1978) and dilagonal-inconiiterr
2022) and accelerations such as AnySOS (Driggs Fawzi 2019) primarily improve the efficiency
of solving given SOS formulation, especially in control settings (Dai & Sznaier 202T SStasssr
cct al., 202I). More recently, Li et al. (2025) study the use Large Language Models (LLMs) for SOS-related mathematical reasoning. They introduce benchmark of approximately 1,000 poly- nomials together with expert-designee supervised fine-tuning
reasoning prompts, and show that structured prompting and substantially improve direct SOS classification accuracy. In contrast to their setting, our goal is not to have an LLM directly decide whether a polynomial is SOS from the polynomial itself using prompting and procedural algebraic checks. Instead, upstream inside a verified optimization pipeline: given polynomial, our model predicts a compact monomial basis, after which we solve an SDP and use repair retain correctness guarantees.
learning
Machine Learning and Algorithms with Predictions for Combinatorial Optimization Recent advances in deep learning have demonstrated effectiveness in addressing combinatorial optimiza- tion problems, with notable successes in routing (Kool al. 2018) and mixed integer programming (air et al. 2020). To our knowledge, our approach represents the first application of learning- augmented algorithms to SOS programming, where the fundamental computational bottleneck lies in selecting compact monomial bases from exponentially large candidate sets. We analyze our ap- proach within the Algorithms with Predictions framework (Roughgarden) [021]. which provides theoretical foundations for quantifying the performance of learning -aggggg---mmeeeedde algorithms that inte- grate potentially inexact predictions while maintaining worst-case guarantees. We build upon neural approaches for computational algebra developed by Kera et al.) (025b), specifically adapting their polynomial tokenization and sequence generation techniques for our monomial basis prediction task. More broadly, our work is situated in emerging line of research the intersection of computa-
3

---

Published as a conference paper at ICLR 2026
tional algebra, symbolic computation, and machine learning (Kera et al. 2024 2025a Pelleriti al.
2025 Alfarano et al. 2024).
2 NOTATION AND PRELIMINARIES
Vectors of real numbers and variables are denoted in bold, and indexed by subscripts. We denote the set of all monomials of degree d E or less by Ma- For a subset B C Ma we denote the vector of the monomials in B by (x()) E gl Further, for a given polynomial of degree with n variables p IR [21.....,, we denote its monomial support, i.e. all monomials appearing in p, by (p) S Ma. A matrix symmetric Q E RaxE is PSD if Q z 2 for all z E R denoted Q 2 0.
For SOS polynomial p(x) (x) Qzg(x) with Q 0, call B the basis and (x() the monomial basis vector. The Newton polytope Np)) is the convex hull of exponent vectors of monomials in p. For our running example p(r1, x2) 4xr 12rf2² + +9rg + 1, the Newton polytope N(p) is the convex hull of points (44 0), (2, 2), (0, 4), (0, 0)} corresponding to the mono- mials uf, -fa3, 222, 1. For any SOS decomposition p(x) Zx)x) [zz(xx) the exponents of basis monomials in B must lie within the half Newton polytope (p) (Reznick 1978 i.c. N (p)) scaled
by factor of 1/2 about the origin. Consequently, valid basis can chosen from the finite set
{x" a E (H)( } though many such monomials are typically redundant.
METHODOLOGY
We present a leaming-auggmette algorithm for SOS basis selection. This is complementary to recent LLM-based approaches such as et al. (202)). which study direct SOS reasoning from the polynomial itself. Our method uses a Transformer to predict compact monomial basis, which is then verified through SDP solving. However, these predictions can be incorrect. When the predicted basis is incomplete, the resulting SDP may be infeasible even though the polynomial has a valid SOS decomposition. Therefore, we need systematic repair mechanism to handle incorrect predictions while maintaining the computational speedups from accurate predictions. Our approach addresses this challenge in three stages.
(i) Transformer-baser hasis prediction. Given a polynomial p. a trained Transformer model predicts a compact set of monomials likely form a valid SOS basis.
(ii) Construction of a valid initial basis. We verify that the predicted basis satisfies necessary structural conditions. not, we employ a greedy heuristic to augment the basis until these conditions are satisfied.
(iii) Iterative expansion with verification. We solve the SOS problem using the current basis. If the solver fails, we expand the basis using learnable scoring mechanism and resolve the SDP. This process iterates until either a valid SOS decomposition is found or all candidate SOS.
monomials are exhausted, certifying that the polynomial
Figure iillsstrtte the complete workflow of our approach. In the following sections, we describe each of these three components above in detail.
3.1 TRANSFORMER BASED BASIS PREDICTION
To train the Transformer, require supervised pairs of polynomials p and their SOS bases B C Ma- Because finding near-minimal SOS bases is computationally hard, we generate polynomials with known compact bases via reverse sampling: sample monomial set B MM. draw Q O. and set p(x)= = z "Qz (x). This guarantees B is a valid SOS basis for by construction and often yields near-minn manimal bases that match our lower bounds in Ampppediix (cf. Appendix E.6 for empirical verification, demonstrating that these bases are near-minimal).
To ensure comprehensive coverage, we vary the PSD structure of Q four categories: dense full-rank matrices, unstructured sparse matrices, block diagonal matrices, and low-rank matrices, as illustrated in Figure 2
across
4

---

Published as a conference paper at ICLR 2026
We further diversify training data by varying the number of vari- ables, polynomial degree, and number of terms, which yields polyno- mial families that span dense, sparse, and clique-structured polynomials across different problem scales. To validate the quality of our training data, verify that the generated bases achieve sizes close to theoret- ical lower bounds derived in Lemma 7 and Lemma 8) confirming that these bases are mear-minimal. Lemma 7 and Lemma 8 formalize struc- tural constraints that any SOS basis must satisfy, providing lower bounds and consistency relations that guide our reverse-sampling construction. These results ensure that the generated training bases are not only valid close to theoretically minimal, which essential for training a model that generalizes well to compact bases. Complete details regarding pa- rameter grids, sceds, and sample counts are provided in Appendixx D
(a)
(c) Black Diagonal
[d] Low Rank
Figure 2: Sampled ma- trix structures.
sequence generation problem. Given polynomial p, our Trans- former model predicts monomial basis B from the half Newton polytope 1.N (p) that likely admits an SOS decomposition p(x) = n (x) Q (x) for some Q ž 0, i.e.
We formulate basis prediction
TRANSFORMER(D) B
(()) E
We tokenize polynomials using the scheme from Kera et al. (202b)) Each monomial is represented
by its coefficient (prefixed with C) followed by the exponents of each variable (prefixed with E). For 12rfx2 + 92 + 1. the tokenized input
our running example p(z1, x2) 4zf
C4.0 E4 EO C12.0 E2 E2 C9.0 O EO E4 C1.0 EO EO.
The model generates sequence of monomials separated by SEP tokens, representing the predicted basis. For our example, the target output sequence is
E2 EO SEP EO E2 SEP EO EO,
which corresponds the minimal basis {=ī, 13. The model uses monomial-embeddingg to map tokenized terms like C1.0 E4 EO to vector representations, significantly reducing sequence lengths. We generate basis monomials autoregressively until producing an se-uuence token EOS.
Remark 1. Our results also indicate that the method does not fundamentally depend Transform- ers. In Appendix E.9 we compare LSTMs (Hocrreter Schmidhuber [997) and Mamba state- space models (Gu Dao 2023 Dao & Gu (022) under a fixed 5-hour training budget, with similar embedding scheme as for the Transformer. Both alternatives achieved reasonable perfor- mance, with Mamba particular being competitive with the Transformer (ef. Figure 12 and Ta-
ble 30). This suggests that other sequence-to torecce-toosae seuqueeee---eeuence architectures may also be suitable for SOS busis prediction and represent a promising direction for future work.
3.2 CONSTRUCTION OF VALID INITIAL BASIS
Before attempting to solve the SDP with the predieted basis, we first check whether it satisfies the following necessary condition that any valid SOS basis must satisfy.
Lemma 2. Let p(x) E [ [811,...,, [n]] be a polynomial and B C Ma be a basis. Then, the support of p is contained in the set of all pairwise products of monomials in B, formally S(p) C B- B where
B = {m4 my m, m, E B). We say that covers p(x) if S(p) B.
We defer the proof to Appendix F Continuing our running example, let p(21, x2) = 4x 2 Or 1 with candidate basis B (1, 11,27.20 x122). The support 5(p) = 1 x. x f2z). and the pairwise products are
B.B +1, 21 11, a 02, x
Since 2 S()) but 2 & B B, the basis cannot represent p as a sum of squares.
If the predicted basis does not cover all monomials in S(p), extend it using a greedy repair algorithm that adds monomials covering the most missing support terms, which we call COVER- AGEREPAIR and detail in Algorithm 3 in the appendix. For our example with B (1,2),0112)
5

---

Published as a conference paper at ICLR 2026
and missing monomial zÿ. could add z since z. x = allowing to cover the missing term. This process continues until all monomials in S()) can be expressed as pairwise products of basis elements, ensuring that S(p) _ B B required by Lemma
Algorithm I summarizes the initial construc- tion phase. First, obtain predicted basis Bo from the TRANSFORMER model. Since Bo may not satisfy the coverage require- ment from Lemma 2] we extend it using the COvERAGEREPAIR routine ensure that all monomials in the polynomial's support S(p) can expressed as pairwise products of ba- sis elements, yielding a basis Beov that cov- ers all support monomials. We then solve the SDP to check feasibility. If feasible, we return the decomposition; otherwise, we proceed to expansion.
Algorithm Initial Basis Construction
Input: Polynomial p
1: Bp < TRANSFORMER(P)
2: Beov < COVERAGEREPAIR Bg. S(p))
is feasible then 4: return feasible
3: if SOLVESDP(B
5: else
6: return infeasible
7: end if
3.3 ITERATIVE BASIS EXPANSION WITH VERIFICATION
Algoogoi fails to find feasible SDP solution with the coverage-repaired basis Beov. expand the basis by incorporating additional monomials from the candidate pool (p)). Rather than adding monomials arbitrarily, we rank each candidate monomial by a learned score and expand the basis in order of decreasing score.
To define the scoring function SCORE(U, p) for a monomial u given polynomial p. we exploit the fact that our Transformer is not equivariant with respect to variable orderings. That is, if we permute variables in a polynomial (e.g., swap # and 222,, the Transformer may predict different basis for the mathematically equivalent problem. We use permulation-busee scoring: run the Transformer on random variable permutations = { _ the variables the polynomial, then score each monomial u by its frequency across predictions:
SCORE(
Σ 1=1
1uu E E (Br:),
where Br, is the basis predicted for the ny-permuted polynomial and ., (Bx.) is the basis obtained 4; see Appendix E.2 for
by undoing the permutation on B Unless otherwise noted we set an ablation showing diminishing returns beyond 8.
The score function creates a ranking of all monomials in the candidate set (p))). where higher scores indicate monomials that are more likely belong valid SOS decomposition. Hence, we have to call the Transformer T. times on different variable permutations and aggregate the results.
Given the polynomial p. coverage-repairee basis Beov from Algorithm I] expansion schedule mi < m2 <... < mi I (p)). and the Newton polytope (p) as our can- didate set, sort candidate monomials by score and create an ordered list starting with Boov followed by the best candidates. For
Algorithm 2 Ordered Expansion
Input: Polynomial p; initial basis B schedule
mi < m2 < ... < mii
1: C +- sort( N()) \ Boov, SCORE(,p))
2: M + concat( Beov. C))
3: for E (2...................... k) do
each scheduled size My, we take the first m. monomials form the basis and solve the SDP. If the SDP is feasible, we have found valid SOS decomposition and terminate suc- cessfully; otherwise, we try the next larger size. In the worst case, we solve lo SDPs, with the last equivalent to the standard New- ton polytope approach. Algorithm summa- rizes this expansion process.
4: B < MM1 : m,
5: if SOLVESDP B, p) feasible then
6: return feasible
7: end if
8: end for
9: return infeasible

---

Published as a conference paper at ICLR 2026
4 EXPERIMENTS
Table I: Average results on representative configurations. Left: basis size (monomials). Right: solve time (s). Ours the proposed method (with repair); Newton the Newton polytope; Full is the dense full basis. MOSEK is used, except for low-rank cases where SCS is employed due to numerical issues. "_ indicates solver failure/timeout, Speedup ours over Newton.
Average basis size
Average solve time (s)
Speedup
Structure
d
[
Ours
Newton
Full
Ours
Newton
Full
dense
4
6
20
19
19
21
35
0.4
0.28
0.67
0.7
6
12
30
30
33
48
924
1.01
2.44
2.42
8
20
30
28
38
32
43,758
3.4
309.4
91.00
6
58
89
26,334
1,629.6
89.05
sparse
4
6
20
15
15
18
35
0.23
0.20
0.83
0.87
6
30
26
27
924
0.57
1.20
2.11
8
20
30
26
27
28
43,758
0.62
15.3
24.68
6
20
60
56
73
233
26,334
7.39
1,606.4
217.39
low-rank
4
6
20
19
19
22
35
0.35
0.29
0.68
0.83
6
12
30
30
30
48
924
0.71
25.4
35.77
8
20
30
30
35
31
43,758
1.03
301.2
292.43
6
60
57
66
26,334
39.17
1,563.1
39.90
block-diag.
4 6
20
19
20
22
35
0.32
0.28
0.67
0.88
6
30
31
48
0.64
2.44
3.81
30
30
38
43,758
0.81
17.4
21.48
6 20
60
59
71
231
26,334
7.74
1,331.1
172.02
We evaluate our approach through four experiments: (1) end-to-end performance vs. baselines, (2) isolation of Transformer prediction capabilities, (3) repair mechanism robustness, and (4) large-scale scalability beyond existing solver limits and distribution shifts.
4.1 EXPERIMENT 1: COMPARISON BASELINES
We evaluate our method against Newton polytope and full basis approaches across four polynomial structures: dense, sparse, low-rank, and block- diagonal. Our evaluation uses 100 test instances configuration, with test instances ranging from n E (4, 6, 8) variables, degree d E {6, 12, 20), and average basis sizes of 20, 30, and 60 monomials.
SDP
Trans former
Repair
Normalized Time
0.4s
1.0s
3.4s
18.3s
0.75
0.50
0.25
We use MOSEK (ASS) 2025) for SDP solving. with SCS OO'Donoghue al. (016) used for low-rank cases due to numerical issues, imposing 2-hour time limits for all instances. We measure both basis size and total runtime. For our method, runtime includes Transformer inference and coverage-repair overhead: for Newton polytope, it includes polytope construction; and for all methods, includes SDP solve time.
0.00
M+
L
Configuration
Figure 3: Time breakdown by problem size, annotated with average total solution time.
Our approach consistently achieves the smallest bases and fastest solve times, except for the smallest test cases (n = 4, d = 6, 20). Speedups range from 0.7x to over 300x, with the full-basis method timing out on larger instances. For dense and low-rank polynomials with variables and degree 20, our method maintains sub-60-second solve times, while Newton polytope requires over 1000 seconds per instance, mainly due to expensive computation of the Newton polytope (Lofberg) 2009). We also analyze the runtime breakdown in Figure 3 for the first four dense matrix configu- rations from Table I which we abbreviate as S, M, M+, L. The breakdown shows normalized times for SDP solves, Transformer inference, and repair across problem sizes. As problems become more

---

Published as a conference paper at ICLR 2026
Failure Rate (%)
Degree
# Terms J
(a) Dense
(b) Sparse
(c) Low Rank
(d) Block Diagonal
Heatmap of failure rates.
Support Coverage
0.8-
0.8
0.8
0.4-
0.4
04
8.2
Black Diegand
0.0
0.0
0.0
12
False Positives
False Positives
Number of Variables
(a) Dense
(b) Sparse
(ii) Histogram of false positives.
(iii) Support coverage variable count.
Figure 4: Isolated Transformer performance across polynomial structures. (i) Heatmaps of failure rates over degree and structure show sparse and block-diagonal cases are easiest while dense are hardest. (ii) Histograms of false positives highlight error distributions per structure. (iii) Success probability as function of the number variables demonstrates monomial-embeeddnng makes cov- erage consistent across variable counts.
complex, the Transformer inference takes less time relative to the total, while repair costs increase. In all but the smallest problem set, SDP solving takes up 75 80% of the total time, except for the smallest problems (size S) where it only accounts for 55%. The time spent on Transformer inference and repair remains reasonable across all problem sizes. In [Appenddxx E. we provide amorti- zation analysis of the training cost and show when the one-time learning expense is outweighed by per- per-instance solver speedups.
4.2 EXPERIMENT 2: TRANSFORMER BASIS PREDICTION
To isolate the Transformer's performance without repair, we evaluate raw basis prediction accuracy across 1000 generated instances spanning dense, sparse, low-rank, and block-diagonal structures with E [4, 16). d E [4. 20), and average basis sizes of 10, 20, and 30 monomials. The Trans- former's performance is highly struetur-depeeddett (ef. Figure 4i}. Sparse and block- block-diagonal instances achieve success rates of 85 95%, demonstrating the model's ability to exploit clear structural patterns. However, dense and low-rank matrices exhibit substantially higher failure rates (up to 100% for complex instances), where cross-terms and less obvious sparsity patterns challenge the prediction mechanism. This variability underscores the importance of repair mechanisms in en- suring robust performance across diverse polynomial families. False positives dense and low-rank cases. The number of variables has minimal impact on performance, except for dense cases, which attribute to the effectiveness of the monomial-embeddin approach.
common in
4.3 EXPERIMENT 3: REPAIR MECHANISM
8 variable, degree 20 polynomials across four repair strate- gies: no repair, greedy repair only, permutation-based repair (using permuted versions), and com- bined approaches. We measure three outcomes: exact match (predicted basis equals ground truth), superset (predicted basis contains ground truth but includes extra monomials), and insufficient (pre- dicted basis missing essential monomials for valid SOS decomposition).
We evaluate repair mechanisms
Figure 5i shows that greedy repair achieves high exact match rates with minimal computational overhead. Cermutation-based repair reduces insufficient cases but increases superset outcomes. The combined approach achieves the lowest insufficient rates across all polynomial structures, ensuring robust recovery from failed predictions.
8

---

Published as a conference paper at ICLR 2026
Fmncton of'nnnees
Eesc
Sianet
hoafishoa
Support Coverage
1.0-
1.0
0.8
Precision
0.6
0.6
06
0.4
0.4
0,4
Derse Sparse
0.2
0.2
Low Rank
Noue
Groady Perm
None
Greedy
Parm
Como
Nous
9em
Combi
Nooe
Ereedddy purm
4-3-2-1
0
2
--3-2-1 0
Denie
(c) Low rank
(b)
Spanse
(d) Dlockdiag
degree
degree
(i) Global repair outcomes by polynomial structure.
(ii) Precision metrics for repair mechanisms.
Figure 5: Repair mechanism performance evaluation. Global repair outcomes demonstrate the effectiveness of greedy and permutation-basee repair mechanisms across polynomial structures: permutation- approaches often generate supersets by adding many more monomials but prove less effective for dense cases, while greedy methods show more conservative monomial addition. (ii) Distribution shift evaluation results, indicating that the combined repair mechanisms are effective.
4.4 EXPERIMENT DISTRIBUTION SHIFT AND LARGE SCALE EVALUATION
We compare our method with state-of-the-ar solvers (SumOrSquares.) Weisser et al. 2019).
TSSOS (Wang et al. 2021b), Chordal decomposition (Wang et al. 2021aa) on four challengigg configurations. Experiments were run on an Intel Xeon Gold 6246 (16 cores, 512GB RAM). Our approach achieves substantial speedups: 21x faster than SoS.jl and 15x faster than TSSOS on 6 variables with degree 20, and over 2000 faster on variables with degree 20. For the largest instances (6 variables with degree 40 and 100 variables with degree 10), all bascline solvers encounter out-of-memory errors or timeouts, while our method succeeds in under 60 seconds.
Table Evaluation on large configurations. En- tries are average time (s). 00M/timeou..
For distribution shift evaluation, the Trans- former model maintains relatively strong per- formance even on degrees unseen during train- ing. This robustness likely stems from the mononial-embedding technique, which cap- tures structural patterns that generalize beyond the training distribution. Despite being trained only on degree 12 polynomials, our model can successfully predict bases for degree 20 polynomials by leveraging familiar substruc- tures thoug- it has not seen complete degree 20 monomials, it has encountered their constituent parts (e.g., isolated variables like x1). This compositional generalization has been similarly observed (Kera et al. 2025b).
Ours
SoS.jl
TSSOS Chordal
6 vars, deg 20
5.64
119.98
86.53
105.54
6 vars, deg 40
42.8
8 vars, deg 20
1,46
3037.85
2674.50
3452.98
100 vars, deg 10
18.3
THEORETICAL ANALYSIS
In this section, we establish elementary guarantees for our approach. Throughout our analysis, we assume that the computational cost of solving an SDP with basis size m scales O(m*), ), where the exponent w depends on the specific solver implementation. While the practical computational complexity of solving SDPs also depends on the number matrix constraints, we empirically ob- serve that for the sparse polynomial problems we consider, the constraint count scales linearly with the basis size m.
The standard SOS certification approach constructs single large SDP using all monomials in the half Newton polytope [y)( incurring computational cost ((m²) where m = [p)) Our method, by contrast, solves sequence of progressively larger SDPs with basis sizes m1, m2, my. terminating upon finding a feasible SOS decomposition. The total computational cost under our approach is θ [E= m²² which can be substantially smaller than the standard cost when accurate predictions enable early termination with compact bases.

---

Published as a conference paper at ICLR 2026
Given polynomial p. we define prediction as specifying: (i) an ordering v (#1..... uN) over the half Newton polytope 2 {p),), and (ii) a schedule o = (m1 <... mm)) of basis sizes to attempt. We measure the prediction quality through the coverage rank 17, defined the smallest index j such that (ui,....
is a monomial SOS hasis for the polynomial
Remark 3. This cost model provides several straightforward insights. In the best case, when the coverage rank equals the minimal basis size and Be from Aooooithi is minimal, our method finds the certificate a single SDP solve at minimal cost, which we formalize in LelLLmmm 5 In the worst case, when the coverage rank equals 12 [p)), our method requires l SDP solves with basis sizes mi..... incurring at most (kk) times the cost of the standard approach, which we formally state in Lemma 6
We conclude with a natural choice of expansion schedule, which is to increase the basis size by constant factor p > 1 at each iteration and relate this to the coverage rank.
Lemma 4 (Geometric Expansion). Let Beor be a coverage-repaived SOS basis obtained by Algo- rithm 1 Let the coverage rank be 11, set m, = |Beoll and choose p > 1. Then, Algorithm performs
at most + [log,(n/m1]] SDP solves and has total cost at most + (T-6-- 11
We refer to Theorem 9 for an ERM approach to select the parameter for the geometric expansion schedule that minimizes the expected cost of the SDP solves.
CONCLUSION AND LIMITATIONS
This paper introduces Sarming-augmentee algorithm for SOS programming that achieves signif- icant speedups while maintaining theoretical guarantees. By framing basis selection as a sequence prediction task, we bridge the gap between practical efficiency and mathematical rigor. Our ap- proach demonstrates robustness across different polynomial families and variable counts, suggesting the learned patterns generalize beyond the training distribution. The systematic repair mechanism enables the algorithm to recover from initial prediction errors, while the Transformer model learns exploit sparsity patterns that traditional methods miss. These capabilities combine to deliver consistent performance improvements across diverse problem instances.
Nonetheless, our approach has limitations. Our extensive experiments, comprising 100 million poly- nomials across 200) synthetic datasets, provide broad coverage of polynomial structures. However, the lack of widely available real-world SOS benchmarks requires us to rely on synthetic polynomial generation for empirical evaluation. More broadly, our predictor may be sensitive to non-canonical choices in representing p (beyond variable permutations), and addressing this via deterministic test- time canonicalization is interesting direction for future work (cf. RECON (Urbano et al. (026 ). Furthermore, although our method demonstrates strong performance in the studied regime, scala- bility remains challenge: going beyond 100 variables tackling problems with many more terms is difficult due to the Transformer's limited context length and the computational bottleneck posed by solving large SDPs. real-world SOS instances with sparse structure and fixed coefficients are also rare, further constraining empirical assessment; while we include one control example in the appendix (Appendix E. I.I large-scale realistic benchmarks remain an open need.
ACKNOWLEDGEMENTS
This research was partially supported by the Deutsche Forschungsgemeinsshatt (DFG) through the DFG Cluster of Excellence MATH+ (EXC-2046/1, EXC-2046/2, project 390685689), as well as by the German Federal Ministry of Research, Technology and Space (research campus Modal, fund number 05M 4ZAM, 05M20ZBM) and the VDI/VDE Innovation + Technik GmbH (fund number 161S23025B). D. Martínez- Rubio was partially funded by grant Caixa Junior Leader Fellowship 2025.
and by La
REFERENCES
Amir Ali Ahmadi and Georgina Hall. Sum of squares basis pursuit with linear and second order cone programming, 2016. (ttpssttss:/aart www.bbsa//////ooo /1500. 01597
10

---

Published as a conference paper at ICLR 2026
Amir Ali Ahmadi, Alex Olshevsky, Pablo A. Parrilo, and John N. Tsitsiklis. Np-hardness of deciding
convexity quartic polynomials and related problems. Mathemattcaal Programming. 137(1-2):
453-476, November 2011. ISSN 1436-4646. doi: 0011007/111107--11149992222 URL http:
77dx. doi wwwpoo..........000 160. 1 -
Alberto Alfarano, François Charton, and Amaury Hayat. Global Iyарunov functions: long-standing open problem mathematics, with symbolic transformers, 2024. URL https://arxii>
org/abs/22 24000 08304
MOSEK ApS. The MOSEK Python Fusion API manual. Version 11.0., 2025. URL https://
docs mosek. com/ wwo.et.commaattttt///ooo.fosisss wwtpsssiionnnnnienieieee index html
Jason J. Bramburger, Steven Dahdah, and James Richard Forbes. Synthesizing control laws from
data using sum-of-squares optimization. In 2024 IEEE Conference on Control Technology and
Applications (CCTA), pp. p05 505-510. IEEE, August 2024. doi: 10. 10.1109/ccta60707 2024.10666531 2024, 06666331
doi http:://xxxd...oo/oolee.o wttp./////..11////T////06111 URL http: pattp://áse //tx.
T. Dai and M. Sznaier. A semi semi-algebraic optimization approach to data-driven control of continuous- time nonlinear systems. IEEE Control Systems Letters, 5(2):487-492, 2021. doi: 10.1 109/
L.CSYS.2000.300333
Tri Dao and Albert Gu. Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality, In International Conference on Machine Learning (ICML), 2024.
Derek Driggs and Hamza Fawzi. Anysos: An anytime algorithm for sos programming 2019 IEEE 58th Conference Decision and Control (CDC), pp. 3012-3017, IEEE Press, 2019. doi: 10. L109CDCC40242219990933
11090
9029387
Narendra Gollu. Switched control of satellites for global stabilization and local performance: A sum of squares approach. In 2008 American Control Conference, pp. 2987-2992, 2008. doi:
D0.1009/ACC.20084555655
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.0075: 2023.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9(8):
1735-1780, 1997. doi: 10.1162/neco.1990 1997.9 1997.9.8.111... 19715..
Z. Servis-Wloszck. R. Feeley, Weehong Tan, Kunpeng Sun, and A. Packard. Some controls ap- plications of sum of squares programming. In 42nd IEEE International Conference on De- cision and Control (IEEE Cat. No.03CH37475), volume 5, pp. 4676 4681 Vol.5, 2003. doi: 10. 10.1109/CDC.2003.12220
Hiroshi Kera, Yuki Ishihara, Yuta Kambe, Tristan Vaccon, and Kazuhiro Yokoyama. Learning to compute gröbner bases, 2024. htllnttts::/ariiw.rrrr///////
12904
Hiroshi Kera, Shun Arakawa, and Yuta Sato. Calt: A library for computer algebra with transformer, 08600
2025a. /
Hiroshi Kera, Nico Pelleriti, Yuki Ishihara, Max Zimmer, and Sebastian Pokutta. Computational
algebra with attention: Transformer oracles for border basis algorithms, 2025b. URL https:
arxiv. www.vvo.rg/aaae haapg//bbs/2500 /2505 23696
Wouter Kool, Herke van Hoof, and Max Welling. Attention, Iearn to solve routing problems! In International Conference on Learning Representations, 2018.
Jean B Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11(3):79688) 2001.
Kechen Li. Wenqi Zhu, Coralia Cartis, Tianbo Ji, and Shiwei Liu. Sosl: 01 and rike reasoning llms are sum-of-square solvers, 2025. URL htRl.httss://// / .0545

---

Published as a conference paper at ICLR 2026
Johan Lofberg. Pre- and post-processing sum-of-squares programs in practice. IEEE Transactions on Automatic Control, 54(5):100--1011, 2009. doi: 2..1009/TAC.2209920111444
Richard P. Mason and Antonis Papachristodoulou. Chordal sparsity, decomposing sdps and the Iyарunov equation. In 2014 American Control Conference, pp. 531-537, 2014. doi: 10.1109/
ACC.201446859255.
Jared Miller, Yang Zheng, Mario Sznaier, and Antonis Papachristodoulou. Decomposed structured subsets for semidefinite and sum-of-squares optimization. Automatica, 137:1 March 2022.
ISSN 0005-1098, doi: 10100///..utomatica..000 100125.
1016/1. aut omatica. 2021. 110125
Rahul Misra, Rafal Wisniewski, and Özkan Karabacak. Sum-of-squares based computation of Yyаpunov function for proving stability of satellite with electromagnetic actuation. IFAC- PapersOnnLne, 53(2):7380- -385, 2020. ISSN 2405-8963 doi: htps://doloorr/1..00ffff..fu 2020. 1264. URL https:/ //wwww.//www/////// wcw.ecedireect...........o ccmm//science///tticll/p.... 6240589632031666 6666 21st IFAC World Congress.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349 2020.
Matthew Newton and Antonis Papachristoddoulou. Sparse polynomial optimisation for neural net- work verification, 2022. [tttstts::///ax
abs /atps//22..222 02241
Brendan O' D'Donoguue Eric Chu, Neal Parikh, and Stephen Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Appli- cations, 1646))1002--106, June 2016. URL http:: www.a/aoood...aooooaaaaaeeaaae
SCS. html
Pablo A Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical Progrumming, 96(2):293-320) 2003.
Matthew M. Peet and Antonis Papachristoodoulou. converse sum of squares lyapunov result with degree bound, 2012. URL http://p::///a.x...rr/aaaa//////
Nico Pelleriti, Max Zimmer, Elias Wirth, and Sebastian Pokutta. Approximating latent manifolds
in neural networks via vanishing ideals, 2025. URL htttp:///rxiv.org http://ww...rr/aa///5..22.
15051
Imre Pólik and Tamás Terlaky. New stopping criteria for detecting infcasibility in conic optimiza- tion. Optimization Letters, 3(2):187-198, 2009. doi: 11100000011110000-10111
Bruce Reznick. Extremal psd forms with few terms. Duke Mathematicll Journal, 45(2):363-374, 1978.
Tim Roughgarden. Algorithms with predictions. arXiv preprint arXiv:2006.14133: 2021.
Robin Strasser, Julian Berberich, and Frank Allgower. Data-driven control of nonlinear systems: Beyond polynomial dynamics. In 2021 60th IEEE Conference on Decision and Control (CDC). pp. 4344-4351. IEEE, December 2021. doi: 10. 100/0///444444020009933333
URL http:
7/dx. doi. org 10. 111.1...///.1.11411111 2021. 9683211
Alonso Urbano, David W. Romero, Max Zimmer, and Sehastian Pokutta. Recon: Robust symmetry discovery via can
canonical orientation normalization, 2026. Utl.tttss:/aarxiv.o
abs/2505. 13289
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Informa- tion Processing Systems, 30, 2017.
Hayato Waki, Sunyoung Kim, Masakazu Kojima, and Masakazu Muramatsu. Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM Journal on Optimization, 17(1 17(1):218- (1:1::211244 242, 2006.
12

---

Published as a conference paper at ICLR 2026
Jie Wang, Victor Magron, and Yean-Bernare Lasserre. Chordal-tssos: A moment-soe hierarchy that exploits term sparsity with chordal extension. SIAM Journal on Optimization, 31(1):114-141, January 2021a. ISSN 1095-7189. doi: 10. 10.1137/20m1323364
Jie Wang, Victor Magron, and Jean-Bemard Lasserre. Tssos: A moment-sos hierarchy that exploits term sparsity, SIAM Journal on Optimization, 31(1):30-58, 2021b. doi: 10.1137/1MM130777
Tillmann Weisser, Benoît Legat, Chris Coey, Lea Kapelevich, and Juan Pablo Vielma. Polynomial and moment optimization julia and jump. In JuliaCon, 2019. URL httpps:/ppretalx:
com http://aaaacco2///aa///////// QZBKKUU
Yang Zheng, Giovanni Fantuzzi, Antonis Papachristodoulou, Paul Goulart, and Andrew Wynn.
Chordal decomposition in operator-spliting methods for sparse semidefinite programs. Math- ematical Programming,
532, February 2019. ISSN 1436-4646. doi: 10.1007/
510107-019-01366-3, URL http: //dx doi 1tt.://r../.....10///00000000000 0133--
13

---

Published as a conference paper at ICLR 2026
A STATEMENTS
A. USE OF LARGE LANGUAGE MODELS
Large language models were used to aid in writing (polishing text), retrieval of related work, gen- erating code for plots, and implementing standard components. No novel research ideas or results were produced by LLMs.
B IMPLEMENTATION DETAILS
B.1 SOFTWARE
We implemented our approach using a combination of Python and Julia. Table lists the key soft- ware packages and their versions used in our implementation.
Table 3: Software packages and versions used in our implementation.
Package
Version
Python
3.9.19
Julia
1.11.5
Mosek
11.0.22
SumOfSquares (Julia)
0.7.4
CVXPY
1.6.5
SCS
3.2.7
NumPy
2.0.2
Experiments were run an Intel Xeon Gold 6246 (16 cores, 512GB RAM) and an NVIDIA A40 (48GB RAM).
B.2 MODEL TRAINING
We standard encoder-decoder Transformer with layers each, model dimension 512, and attention heads. Key training hyperparameters: batch size 128, learning rate x 10-1 AdamW W optimizer with weight decay x 10-4, and epoch. The model jointly trains basis selection (cross- entropy loss) and coefficient prediction (MSE loss).
Table 4: Transformer model configuration for Grid 1, 2, and
Parameter
Value
Model dimension (dmode))
512
Attention heads
Encoder/decoder layers
each
Batch size
128
Learning rate
x 10-1
Optimizer
Adam W
Weight decay
10-4
Training epochs
B.2.1 TRAINING TIME
For the Transformer models in Table the average training time is approximately hours, with maximum of under 6 hours for the dense dataset. For the harder datasets in Table 2 the average training time is approximately 10 hours, with the maximum remaining under 11 hours. Note that for smaller instances, the training time is substantially higher than the time required to solve the instances directly. In contrast, for the larger instances, traditional SOS solvers either time out after hours require more than 60 minutes, indicating that the training cost is effectively amortized over
14

---

Published as a conference paper at ICLR 2026
Table 5: Transformer model configuration for Grid
Parameter
Value
Model dimension (dioade)
1024
Attention heads
16
Encoder layers
Decoder layers
Batch size
Learning rate
10
Optimizer
A
Weight decay
10-1
Warmup ratio
0.05
Training epochs
Table Transformer model configuration for experiments 100 variables.
Parameter
Value
Model dimension (dmoode)
768
Attention heads
12
Encoder/decoder layers
each
Batch size
64
Learning rate
x 10
Optimizer
AdamW
Weight decay
10-4
Training epochs
small number of instances. In Appendix E. 12 we provide amortization analysis of the training cost and show when the one-time learning expense is outweighed by per-instance solver speedups.
C ADDITIONAL FIGURES
x²y4
3
xy
x y
x
Newton polytope.
(ii) Half Newton polytope.
Figure 6: Comparison of Newton polytope and half Newton polytope for the polynomial p(x) 7x y + zay + x² +x² 3xy. Support of the polynomial is annotated Figure 6i On the right, we show the half Newton polytope, which is the scaled down version of the Newton polytope. If an SOS decomposition exists, then the half Newton polytope must contain basis for the polynomial.
15

---

Published as a conference paper at ICLR 2026
D DATASET GENERATION
We train our models on three data grids totaling 205 datasets, each containing 1M polynomials split into 99% training, 0.5% test, and 0.5% validation sets on the following grids, generated with fixed random seed.
variables, degrees {4, 6, 8, 10, 12, 14, 16, 18, 20), average basis sizes (10, 30), matrix structures (sparse, low-rank, block diagonal, full-rank dense) (108 datasets).
Grid 1:
Grid 2:
Variables (4, 6, 8, 10, 12, 14, 16, 18, 20), degree 12, average basis size 30, matrix structures (sparse, low-rank, block diagonal, full-rank dense} (36 datasets).
Grid variables, degree 6, average basis size 20, matrix structures (sparse, low-rank, block diagonal, full-rank dense) (4 datasets).
Grid 4: 6 variables, degree 20, average basis size 60, matrix structures (sparse, low-rank, block diagonal, full-rank dense) (4 datasets).
addition, we generated a dataset with 100 variables, degree 10, average ba- sis size 20, matrix structures blockdiagonal. We also constructed a dataset with 6 variables, degree 40, average basis size 40, matrix structures full-rank dense, with the property that all basis mono- mials have only even degree in all variables. This is to make it more challenging for the model to predict the basis. (2 datasets).
Large Scale Special:
For out-of-distribution experiments, we partly reused the datasets above, i.e., using the model trained on only degree 12 monomials on the degrees (4, 6, 8, 10, 12, 14, 16, 18, 20}. In addition, we gener- ated datasets with 1000 test instances in the following grids.
Non-SOS Grid: n = 4, degree 6, 20 monomials; n = 6, degree 12, 30 monomials; n = 6, degree 20, 60 monomials. We construct non-SOS polynomials by performing eigenvalue decomposition of PSD Gram matrices and then perturbing 10 (0--200 200 of the eigenvalues to be negative while preserving the overall matrix structure. datasets).
Permutation Grid: 8 variables, block diagonal matrices with degree 8 and average basis sizes (40, 50); dense full-rank matrices with degree and average basis size 40; dense full-rank matrices with degree 7 and average basis size 50. These were used for ablation studies on the number of permutations. datasets).
OOD Grid: 6 variables, degrees (10, 12, 14). average basis sizes (20, 25, 35, 40), matrix structures (sparse, low-rank, block diagonal, full-rank dense} (48 new datasets).
This gives a total of 108 + 36 + 4 48 + = 205 datasets.
In principle, there is no need to generate these datasets, as one can generate them on the fly. For our experiments, we generated them to avoid any potential issues with the generation process. Our largest dataset (dense full-rank matrices with degree 10 and average basis size 60 and 6 variables) required 2 hours to generate, while most other datasets from Grid 1 took less then 10 minutes to generate on a core CPU.
D. POLYNOMIAL SAMPLING
For each polynomial in our datasets, sample monomials uniformly over the space of all monomi- als up to the given degree Our sampling procedure operates in two stages: (i) Degree sampling: We first sample the degree k of each monomial, where & < d. To ensure uniform distribution all monomials, we weight the degree selection by the number monomials of each degree, which (=+ for n variables and degree k. (ii) Monomial sampling: Given the selected degree k, we uniformly sample monomial of degree & from the set of all such monomials.
16

---

Published as a conference paper at ICLR 2026
E ADDITIONAL EXPERIMENTS
COST OF FAILED SDP SOLVES AND NON-SOS POLYNOMIALS
A key component of our approach is the ability to recover from failed SDP solves. However, in theory, the cost of failed SDP solve can be quite high, even for geometric expansion schedule, due to a potentially large number SDP solves. We show that in practice, the cost of a failed SDP solve is not high expected.
We choose p = 1.5 and permutations. Here we only consider instances, where method has to fallback to the Newton polytope. For these instances, we compute the time-weighted runtime ratio, which the ratio of the runtime of the combined runtime of the SDPs and the final SDP based on the Newton polytope. Across all configurations, the time- tine-weighted runtime ratio is very close to 1, indicating that the cost of failed SDP solve
on the out-o--distribution datasets from the ablation study on
high as expected.
Table 7: Time-weighted runtime ratio by configuration.
Configuration
Config
Config
Config 3
Config 4
Config 5
Config 6
Runtime Ratio
1.069
1.068
1.097
1.009
1.003
1.004
We conjecture that this favorable runtime behavior is actually caused by SDP problems with small bases being not only infeasible but strongly infeasible, which can potentially be detected much faster by interior point solvers (P6lik & Terlaky 2009).
While approach accelerates the computation of positive SOS certificates, it cannot accelerate the computation of negative SOS certificates. This because proving non-existence of an SOS decomposition requires considering the full Newton polytope. Our approach therefore incurs addi- tional overhead for non-SOS polynomials compared to the standard Newton polytope approach. To assess the impact of this overhead, construct non-SOS polynomials by performing eigenvalue decomposition of PSD Gram matrices and then perturbing the cigenvalues, making approximately 10 20% of them negative while preserving the overall matrix structure, creating polynomials that are subtly non-SOS.
We compute the computational overhead as the ratio of the runtime of the combined runtime of the SDPs and the final SDP based on the Newton polytope, using p = 1.5 and L = 4.
Table 8: Overhead for non-SOS polynomials relative to standard Newton polytope approach.
Dataset
Runtime Ratio
1, degree 6, 20 monomials
2.24
6, degree 12. 30 monomials
1.76
2 6, degree 20, 60 monomials
1.05
The overhead decreases for larger problem instances, ranging from 2.24x for small problems to only 1.05x for larger ones, suggesting that the computational penalty for non-SOS cases becomes negligible as problem size increases.
E.2 ABLATION: NUMBER OF PERMUTATIONS
We investigate the impact of the number of permutations L E (1,2,4,6,8 10, 12) on repair mechanism's performance. We evaluate our method on oftto---dittibutioo test cases where the model encounters polynomials with different characteristics than those seen during training. This distribution shift causes the initial predictions to less accurate, making the repair mechanism necessary and allowing study its effectiveness.
17

---

Published as a conference paper at ICLR 2026
Specifically, Transformer trained polynomials with 6 variables, degree 12, average basis size 30, and sparse matrix structure, and test on six different configurations, which were selected based on the criterion that initial success rates (after greedy repair) were below 50%:
Configuration I: Block diagonal matrices, degree 8, basis size 40
Configuration 2: Block diagonal matrices, degree 8, basis size 50
Configuration 3: Block diagonal matrices, degree 9, basis size 30
Configuration 4: Dense full-rank matrices, degree 9, basis size 40
Configuration 5: Dense full-rank matrices, degree 7, basis size 50
Configuration 6: Dense full-rank matrices, degree 10, basis size 30
All configurations maintain 6 variables while varying degree, matrix structure, and basis size. These configurations test the model's ability generalize across different polynomial complexities and underlying matrix structures.
1.0
Dorkg
Success Rate
0.8
Grig
0.8
0.6
Corlg
0.4
8.0
0.0
10
Number of ermutations
Number of Permutations
(i) Success rate number of permutations.
(ii) Number of SDP solves permutations.
Figure 7: Performance metrics as a function of permutation count.
Expansion Mean
1.5
3.
Omele Time
1.0
0.5
0.0
0
10
10
Number of Pormutations
Number of Permutations
(i) Number basis expansions vs permutations.
(ii) Oracle time vs permutations.
Figure 8: Computational overhead analysis for varying permutation counts.
18

---

Published as a conference paper at ICLR 2026
Config
Config
Config
50
35
17.5
SDP Time
15.0
Orade
Basis Ext. Time
40
30
12.5
25-
Time (5)
30
Time
10.0
Time
20
7.5
20-
5.0
10
2.5
5-
0.0
6
10
12
2
10
12
10
12
Number Permutations
Number Permutations
Number Pormutations
Config 4
Config
Config 6
30
20.0
25
20
15.0
Tiree 3
Time (8)
Time (3)
155
10.0
10-
7.5
10
5.0
2.5
0.0
6
10
12
2
6
8
10
12
2
8
10
12
Number Permutaaions
Number of Permutations
Number of Permutations
(i) Runtime allocation for configurations and permutations.
Figure 9: Basis expansion behavior with varying permutation counts.
Key Results: The ablation study reveals several important trends: (1) Success rates improve sub- stantially with increasing permutations, with diminishing returns beyond L 8; (2) Transformer inference time scales approximately linearly with the number of permutations, expected; (3) The number of SDP solves decreases with more permutations, likely due to better scoring; (4) Fallback Newton polytope methods decreases as more permutations increase the probability of finding valid basis; (5) The average number of basis expansions remains relatively constant, indicating that additional permutations primarily improve success rate rather than requiring more expansions per successful case.
Figure 9 shows that the runtime typically dominated by SDP solves. The optimal number of permutations is usually around L 4 8, where the success rate plateaus and further increases in permutations mainly increase the inference time.
Empirically, this platcauing effect motivates choice of L 4-8 practical default. For clarity, consider an example from the sparse setting in Table 1 the true minimal basis contains monomials. Taking the union of L permutations produces candidate set with 78 monomials;
L = 8 gives 82; by L = 16, still only 82. In contrast, the full Newton polytope contains 242 monomials. Thus, additional permutations rapidly saturate the set-extra candidates rarely appear beyond L 8. This demonstrates that moderate values of L reliably yield compact, near-minimal candidate bases, while avoiding the computational cost associated with much larger sets.
E.3 ABLATION: EXPANSION SCHEDULE
We ablate the expansion factor E {1.1, 1.4, 1.6, 1.8, 2.0) while keeping all other hyperparam- eters fixed. Compared to the permutation count, p has smaller effect overall performance.
19

---

Published as a conference paper at ICLR 2026
1.0
Corpp Gorky
Orly
Suvvess Rate
0.8-
0.8
0.4
0.2
1.1 1.2
1.4
1.6
1.8 2.0
1.1 1.2
1.4
1.6
1.8
2.0
Expansion factor P
Expansion factor P
(i) Success rate
(ii) Number of SDP solves
Figure 10: Performance metrics as a function of the expansion factor.
30
Orly
Expansion Mean
1.5
SDP Time
10
1.1
1.2
1.4
1.6
1.8
2.0
1.1
122
1.4
1.6
1.8
2.0
Expansion
P
Expansion
P
(i) Number of basis expansions VS
(ii) Average SDP time vs
Figure 11: Expansion behavior and solver time across expansion factors.
The expansion factor is less critical than the number of permutations. Larger p re- duces the number of basis expansions, as expected, while SDP time remains fairly consistent across settings, likely due to the large gap between the Newton polytope size and the initially proposed basis. Overall, slightly smaller expansion factors (e.g., P S 1.4) are marginally more favorable, though differences are modest.
Key Results:
E.4 BASIS EXTENSION ALGORITHMS
The basis extension mechanism described in Section 3.3 employs two key algorithms. Algorithm presents the main extension algorithm, which iteratively adds monomials to the basis until it can theoretically represent the SOS decomposition of the polynomial. At each iteration, it computes which monomials from the support S are missing from the current basis products, then selects the promising candidate add.
The algorithm calls the subroutine add to the basis (Algorithm 4). Given set of missing monomials M and current basis B, the subroutine counts how many times each candidate monomial d appears as divisor of monomials in M, then returns the most frequent candidate.
to select the most promising monomial
E.5 BASIS EXTENSION ANALYSIS
We analyze the performance of the basis extension mechanism in the context the additive combi- natorics inverse problem. We test our ability to recover the complete set A from partial observation A' and the complete sumset A.
For this experiment, generate a polynomial with known basis A and then remove k elements from the basis to create partial observation A'. We then use our extension mechanism to attempt to recover the missing elements and reconstruct A. Finally, recover the original set A exactly (equal), the original set A is subset of the recovered set (superset), or the recovered set does not contain the original set (insufficient).
measure whether were able to
20

---

Published as a conference paper at ICLR 2026
Algorithm COVERAGEREPAIR
Input: Initial basis Bo, polynomial p, maximum iterations max
Output: Extended basis B
1: < Bo
2: 5 support(p)
3: for = 1 to mar jter do
4: P {mi m2 mi, m2 B}
5: .M +- 5 P
6: if M then
7:
return B
8:
else
9:
d' < FIND-CANDIDATE(M, B)
10: end if
11: if d' None then
12:
return B
13: else
14:
B Bu
15: end if
16: end for
return B
Algorithm 4 FIND-CANDIDATE B)
Input: Set of missing monomials M, current basis B
Output: Monomial d" add the basis
1: D +- empty counter
2: for each m E M do
3: for each b E B do
4: m. is divisible by then
5: d m/bb
6:
Increment D[d] by 7: end if
8: end for
9: end for
10: if D is empty then
return None
12: end if
13: d" f- arg maxaeD D(d]
14: return d'
21

---

Published as a conference paper at ICLR 2026
k
Equal
Superset
Insufficient
1
999
0
1
2
992
6
3
982
16
942
34
5
801
67
132
6
695
13
292
Table Basis extension analysis the additive combinatorics setting. The table shows how many times the original set A recovered exactly (equal), the original set A is subset of the recovered set (superset), or the recovered set does not contain the original set (insufficient) for different values of k missing elements from the partial observation A'.
The results show that the basis extension mechanism is able to recover the original for most cases if k I 4. This demonstrates the effectiveness of our greedy approach to the additive combi- natories inverse problem: given A' C A and A A, we can reliably recover A when the partial observation A' contains most of the elements of A. Removing more elements results in higher number of insufficient cases, highlighting the fundamental difficulty of the inverse problem when the partial observation becomes too sparse.
E.5.1 FALSS POSITIVES ANALYSIS
We also analyze the impact of false positives on the extension mechanism. In the additive combi- natories setting, this corresponds the scenario where the sumset A + contains erroneous elements that are not actually part of the true sumset.
We generate polynomial with known basis A and then remove k elements from the basis to create A'. Then we add the same number of random elements to the sumset A + A (simulating false pos- plus the elements that would
itives) and measure whether we can recover exactly the original generate the false positive sumset elements (exact), the recovered set contains additional unneces- sary elements (superset), or recovered set is insufficient to cover the original set A (insufficient).
Exact
Superset
Insufficient
991
7
2
980
20
0
3
957
43
0
4
902
98
0
745
205
50
6
640
154
206
Table 10: Analysis of basis extension with false positives in the additive combinatorics setting. The table shows how many times we recovered exactly the original set A plus the elements needed generate the false positive sumset elements (exact), recovered superset containing additional unnecessary elements (superset), or failed to recover the complete set A (insufficient) for different values of k missing elements from the partial observation A'.
The results show that the extension mechanism is able to recover the original set for the majority of cases, adding additional elements beyond those necessary explain the false positive elements in the sumset. This demonstrates the robustness of our greedy approach to the additive combinatorics inverse problem even in the presence of noise in the sumset data.
22

---

Published as a conference paper at ICLR 2026
E.6 EMPIRICAL BASIS SIZE ANALYSIS
To demonstrate that the theoretical lower bounds are often tight in practice, we conducted extensive empirical analysis across multiple polynomial structures and problem sizes. This analysis validates that our training data generation produces near-minimal bases, supporting the key message that these bounds are often tight and therefore we trained the model on near minimal basis.
The analysis builds on two key theoretical results established in Lemma 7 and Lemma The combinatorial lower bound (LB,) establishes that for any SOS basis polynomial with support
V1+8|8(p]]1 This bound arises from the fact that basis of m monomials can generate at most m(m+1] distinct monomials through pairwise products. The Newton polytope vertices lower bound (LB,)) provides geometric constraint, requiring that certain vertices of the half Newton polytope must appear in any valid basis.
S()). we have B 2
2
We conducted systematic experiments across four polynomial matrix structures: block-diagonal matrices with sparse block patterns, low-rank matrices with reduced rank structure, dense full-rank matrices with general structure, and sparse matrices with many entries. For each structure, tested multiple configurations with problem sizes n E (4, 6} variables, degrees E {3, 6, 10), and target basis sizes 3 E {20, 30, 60).
Each table reports metrics for measuring lower bound tightness. 8 denotes the actual basis size used generate the polynomial. LB, and LB, represent the Newton polytope vertices and com- binatorial lower bounds respectively. N gives the size of the half Newton polytope used in |
traditional approaches. ( B LB, and p(v) B* /LB, measure the gap and ratio be- tween actual basis size and vertex bound, while A (c) and p! provide analogous metries for the combinatorial bound.
The results demonstrate that the Newton polytope vertices bound is remarkably tight across all polynomial structures. For low-rank and dense matrices, observe ( 0 (perfect tightness) in most cases, with (( = 1.000. For block-diagonal and sparse matrices, gaps remain small with A (v) < and pl)) < 1.065. The combinatorial bound shows varying tightness depending on structure, achieving pfc) =s 1.000 - 1.030 for structured matrices but pl*) = 1.5 2.5 for sparse structures. Importantly, the half Newton polytope [p)[ is significantly larger than actual basis sizes, containing 3-15x more monomials than necessary and demonstrating substantial redundancy in traditional approaches.
Table 11: Lower bounds for blockdiagonal matrices with 6 variables and degree d = 10.
B*
LB
LB.
1 H [p))
A (e)
((v)
A (c)
p(a)
60
60
32
299
0
1.000
28
1.875
66
62
33
339
1.065
33
2.000
55
31
1,018
25
1.806
55
54
31
240
1
1.019
24
1.774
60
60
32
248
0
1,000
28
1.875
66
64
33
281
2
1.031
33
2,000
55
31
211
1.000
24
1.774
53
31
295
3
1.057
25
1.806
23

---

Published as a conference paper at ICLR 2026
Table 12: Lower bounds for low-rank matrices with n
variables and degree d 10.
L.
I.Bg
1 Np))
A (+)
((
(e)
pl
73
73
252
1.000
1.028
70
70
325
1.000
1.014
63
63
62
250
1.000
1.016
64
64
63
215
1.000
1.016
74
74
378
1.000
1.014
65
292
1.000
1.016
69
69
68
331
1.000
1.015
72
72
71
316
1.000
1.014
59
59
59
254
1.000
1.000
Table 13: Lower bounds for dense full-rank matrices with n
variables and degree d 10.
B"
LB,
LB.
[p)
A (+)
(e)
ple)
48
48
243
1.000
1.000
58
58
57
227
1.000
1.018
74
74
73
378
1.000
1.014
73
73
71
252
1.000
1.028
70
70
325
1.000
1.014
68
68
331
1.000
1.015
59
59
59
254
1.000
0
1.000
63
63
63
250
1.000
1.000
47
47
175
1.000
1.000
Table 14: Lower bounds for sparse matrices with n variables and degree d = 10.
B*
LB,
LB.
1 (p))
(6)
p(v)
(c)
p(
56
32
189
1.000
24
1.750
58
56
30
235
2
1,036
28
1.933
61
61
42
288
0
1,000
19
1.452
54
33
211
1.019
22
1.667
36
281
1.031
30
1.833
66
65
36
339
1.015
30
1.833
56
55
32
295
1
1,018
24
1.750
67
66
35
280
1.015
32
1.914
42
1,000
1.476
57
34
212
0
1.000
23
1.676
Table 15:
Lower bound tightness for block diagonal matrices, 4, d = 3, average sampled basis
size 8
B*
LB.,
LB.
[p)
(6)
(())
(c)
p (c)
28
14
29
14
2.000
17
2.545
19
18
10
21
1
1.056
9
1.900
22
16
10
21
6
1.375
12
2.200
11
11
7
15
0
1.000
4
1.571
12
17
1.083
5
1,625
25
16
28
9
1.562
14
2.273
14
13
8
16
1
1.077
6
1.750
15
14
8
24
1.071
7
1.875
21
15
25
6
1.400
11
2.100
25
13
28
12
1.923
2.273
24

---

Published as a conference paper at ICLR 2026
Table 16:
Lower bound tightness for low rank matrices, 4, d
average sampled basis size
B = 20.
B
LB
LBc
Nx)1
(
f
A
p(
11
11
11
15
1.000
0
1.000
19
18
16
24
1.056
1.188
22
24
1.000
1.294
13
13
17
1.000
1.000
28
25
19
29
1.120
1.474
25
24
18
28
1.042
1.389
15
15
14
24
1.000
1.071
14
16
1.000
1.077
21
20
17
25
1.050
1.235
13
13
12
15
1.000
1.083
Table 17:
Lower bound tightness for dense matrices, 4, d 3, average sampled basis size
B" = 20.
B
LB.
LB.
Np)
A (+)
((0)
A (c)
pfc)
11
11
15
1.000
1.000
19
18
16
24
1.056
1.188
13
13
13
17
1.000
1.000
22
22
24
1.000
1.294
28
25
19
29
1.120
1.474
25
24
18
28
1.042
1.389
21
20
17
25
1.050
1.235
14
14
16
1.000
1.077
15
1.000
1.071
25
23
18
28
1.087
1.389
Table 18:
Lower bound tightness for sparse matrices, n 4, d 3, average sampled basis size
B 20.
B
LB.,
LB.
[p((
(6)
(v)
(c)
p
22
13
30
1.692
1.833
4
0
1.000
2
1.500
13
13
7
14
0
1.000
6
1.857
5
0
1.000
3
1.600
16
1.062
8
1,889
20
16
22
4
1.250
9
1,818
6
4
O
1.000
2
1.500
11
11
6
17
0
1.000
5
1.833
19
14
24
1.357
11
2.375
26
15
28
11
1.733
15
2.364
25

---

Published as a conference paper at ICLR 2026
Table 19: Lower-bound tightness for block diagonal matrices,
average sampled basis
size B 30.
B
I.Bg
LBC
(p))
(
p(v)
A (c)
p(o)
40
37
16
89
3
1,081
24
2.500
40
38
16
64
2
1,053
24
2.500
14
1,031
19
2.357
38
15
59
1.026
24
2.600
33
33
14
46
0
1.000
19
2.357
19
19
10
24
0
1.000
1.900
21
21
10
28
0
1.000
11
2.100
12
46
1.000
17
2,417
38
37
15
67
1
1.027
23
2.533
22
22
10
27
1.000 0
12
2,200
Table 20: Lower-bound tightness for low rank matrices, 6, d 6, average sampled basis size
B = 30.
B
LB.
LBc
(p))
A
(())
A (c)
pfc)
19
19
19
24
1.000
1.000
33
33
33
73
1.000
0
1.000
40
40
39
89
1.000
1.026
21
28
1.000
1.000
40
40
64
1.000
1.026
23
23
23
33
1.000
0
1.000
33
33
33
16
1.000
1.000
39
39
59
1.000
1.026
22
1.000
1.000
29
29
29
46
1.000
1.000
Table 21: Lower-bound tightness for random matrices, 6, d 6, average sampled basis size
B* 30.
B
LB,
LB,
[P)(
(+)
(())
(c)
((o)
33
33
73
1.000
1.000
39
39
38
59
1.000
1.026
27
27
27
42
1.000
0
1.000
40
40
61
1.000
1.026
19
24
1.000
1.000
29
29
29
46
1.000
1.000
33
33
33
46
1.000
0
1.000
23
23
23
33
1.000
1.000
38
38
67
1.000
1.027
21
28
1.000
1.000
26

---

Published as a conference paper at ICLR 2026
Table 22:
Lower-bound tightness for sparse matrices, 6,
6, average sampled basis size
B = 30.
B²
I.B
LBc
(1)(
(+))
p(v)
A (c)
p(o)
32
32
14
50
0
1,000
18
2.286
32
32
18
69
0
1.000
14
1.778
25
1,000
14
2.273
10
22
0
1.000
1.700
24
24
12
33
0
1.000
12
2.000
32
32
18
71
0
1.000
14
1.778
35
35
18
52
0
1.000
17
1.944
17
1.029
19
2.118
20
20
11
23
0
1.000
1.818
24
24
12
38
1.000 0
12
2.000
E.7 ADDITIONAL OUT-OF-DISTRIBUTIOO RESULTS
We evaluate a Transformer trained on polynomials with degree 12 and average basis size 30 and full-rank dense matrices on the OOD Grid, i.e., 6 variables, degrees { {10. 12, 14), average basis sizes {20, 25, 35, 40), matrix structures (sparse, low-rank, block diagonal, full-rank dense}.
We report the share of instances that are feasible after repair and scored expansion well as the average number of expansions performed.
Table 23: Out-of-distribution results for sparse matrices. Transformer trained on full-rank dense
matrices.
Degree
Variables
Monomials
Feasible after repair
Feasible after scored expansion
Expansions
0..7
0.83
10
6
25
0.11
0.23
0.89
10
6
35
0.06
0.22
0.94
10
6
40
0.06
0.15
0.94
12
6
20
0.26
0.33
0.74
12
25
0.17
0.21
0.83
0.13
0.20
0.87
12
6
40
0.11
0.13
0.89
0.22
0.32
0.78
0.20
0.24
0.80
14
6
35
0.13
0.22
0.87
14
6
40
0.10
0.14
0.90
16
6
20
0.13
0.30
0.87
16
6
25
0.14
0.30
0.86
0.16
0.14
0.84
0.23
0.94
27

---

Published as a conference paper at ICLR 2026
Table 24: Out-of-distributioo results for full-rank dense matrices. Transformer trained full-rank dense matrices.
Degree
Variables
Monomials
Feasible after repair
Feasible after scored expansion
Expansions
1.00
0.00
0.00
10
6
25
1.00
0.00
0.00
10
6
35
0.98
0,02
0.02
10
6
40
0.89
0.06
0.11
12
6
20
1.00
0.00
0.00
12
6
25
1.00
0.00
0,00
1.00
0.00
0,00
1.00
0.00
0.00
12
6
40
0.82
0.16
0.18
1.00
0.00
0.00
6
25
1.00
0.00
0.00
14
6
35
0.93
0,07
0.07
14
6
40
0.77
0.19
0.23
16
6
20
1.00
0.00
0.00
6
25
1.00
0.00
0.00
0.86
0.14
0.14
16
6
40
0.66
0.28
0.35
Table 25: Out-of-distribution results for block-diagonal matrices.
Transformer trained full-rank
dense matrices.
Degree
Variables
Monomials
Feasible after repair
Feasible after scored expansion
Expansions
20
0.18
0.27
0.82
0.06
0.16
0.94
10
6
35
0.01
0.08
0.99
10
6
40
0.00
0.03
1.01
12
6
20
0.17
0.20
0.83
12
6
25
0.04
0.14
0.96
12
35
0.00
0.06
1.00
0.00
0.00
1.00
14
6
20
0.18
0.25
0.82
0.08
0.15
0.92
0.00
0.05
1.00
14
6
40
0.00
0.05
1.00
0.09
0.30
0.91
16
6
25
0.02
0.20
0.98
16
6
35
0.00
0.05
1.00
0.00
0.03
1.00
While the Transformer generalizes well on instances with similar structure to the training data (i.e. other full-rank dense matrices), it struggles with instances with different structure. We compare this with a Transformer trained on polynomials with degree 12 and average basis size 30 and sparse matrices the same OOD Grid.
The results are shown in Table 26 Table 27 and Table 28
The Transformer trained on sparse matrices generalizes well other structures. We conjecture that this is because the Transformer is forced to learn the structure the sparse matrices, which in particular misses many cross-terms, ie., products of two distinct monomials from the basis.
28

---

Published as a conference paper at ICLR 2026
Table 26: Out-of-distributioo results for sparse matrices, Transformer trained on sparse matrices.
Degree
Variables
Monomials
Feasible after repair
Feasible after scored expansion
Expansions
10
6
20
0.98
0,00
0.02
10
6
25
0.90
0.02
0.10
0.92
0.01
0.08
10
0.86
0.06
0.14
0.90
0.01
0.10
12
25
0,90
0.01
0.10
12
6
35
0.89
0.03
0.11
12
6
40
0.88
0.05
0.12
14
6
20
0.93
0.04
0.07
14
6
25
0.90
0.02
0.10
14
6
35
0.81
0.13
0.19
0.08
0.20
16
6
20
0.73
0.18
0.27
0.76
0.21
0.24
0.67
0.16
0,33
16
6
40
0.55
0.32
0.45
Table 27: Out-of-distribution results for full-rank dense matrices, Transformer trained sparse
matrices.
Degree
Variables
Monomials
Feasible after repair
Feasible after scored expansion
Expansions
1.00
0.00
0.00
1.00
0.00
0.00
10
6
35
1.00
0.00
0.00
10
6
40
1.00
0.00
0.00
12
6
20
1.00
0.00
0.00
12
6
25
1.00
0.00
0.00
12
30
1.00
0.00
0.00
1.00
0.00
0.00
12
6
40
0.99
0.01
0.01
0.00
0.00
1.00
0.00
0.00
14
6
35
0.91
0.09
0.09
14
6
40
0.78
0.20
0.22
16
6
20
1.00
0.00
0.00
16
6
25
0.99
0.01
0.01
0.71
0.25
0.29
0.55
0.33
0.45
29

---

Published as a conference paper at ICLR 2026
Table 28: Out-of-distribution results for blockdiagonal matrices, Transformer trained on sparse ma-
trices.
Degree
Variables
Monomials
Feasible after repair
Feasible after scored expansion
Expansions
0.99
0.00
0.01
10
6
25
0.97
0.03
0.03
10
6
35
0.97
0.03
0.03
10
6
40
0.89
0.11
0.11
12
6
20
1,00
0.00
0.00
12
6
25
0.98
0.01
0.02
0.95
0.04
0.05
0.87
0.12
0.13
14
6
20
0.98
0.02
0.02
0.03
0.03
6
35
0.85
0.13
0.15
14
40
0.77
0.22
0.23
20
0.82
0.17
0.18
16
6
25
0.76
0.23
0.24
16
6
35
0.54
0.42
0.46
0.45
0.51
0.55
E.8 ABLATION: RANDOM INITIAL BASIS
To assess the necessity of meaningful initial basis, we compare our method against two uninformed baselines: a basis consisting only of the constant monomial and (ii) uniformly sampled random basis from the half Newton polytope. For both baselines, we apply the same greedy repair mechanism used our full pipeline. We evaluate the repair success rate on three representative configurations:
Config is the small instance with 4, d 6, 20 and dense structure;
8, d 20, 30 and sparse structure (both Config is the medium instance with
appear in Table T);
Config 3 is the large-scale n = 100, d = 10, m = 20 block-diaggnal instance from Table
Table 29;
Greedy repair success, average repaired basis size, and runtime relative to the Newton- polytope baseline for uninformed initial bases.
Config
Init.
Success
Overhead vs Newton
Const.
{1}
5%
3.93
Config
Random
4%
3.54x
Const. {1}
5%
2.05x
Config 2
Random
5%
1.96x
Const.
{1}
0%
Config 3
Random 0%
the constant monomial or a randomly sampled subset-lead to extremely low repair success (0-5%) and incur substan- tial runtime overheads of up to 3x-4x the Newton-polytope method. In particular, repair has no structural signal to exploit, causing the algorithm to revert almost entirely to full Newton bases. These results demonstrate that greedy repair cannot compensate for uninformative starting point; a meaningful, learned initializer therefore essential for obtaining any reduction in basis size or runtime.
Conclusion:
Across all configurations, uninformed initial
30

---

Published as a conference paper at ICLR 2026
E.9 ABLATION: DIFFERENT ARCHITECTURES
To isolate the effect of sequence model architecture, we directly compared Transformer, LSTM
(Hochreiter Schmidhuber 1997), and a Mamba model [Gu & Dao 2023 Dao
Gu 2024 under
fixed wall-clock training budget of hours on the large benchmark dataset 6, d 10, 60,
dense structure (cf. Table 2).
Transformer: dmndel 512, encoder layers 6, decoder layers 6, 8 attention heads. Total parameters: 106,486,272 (106.49M)
LSTM: dmodee 512, 8 layers, bidirectional, dropout 0.1. Total parameters: 74,227,432 (74.23M)
Mamba: dmuseel = 512, 8 layers, datate = 16, deams 4, expand factor 3, unidirectional, cross-attention enabled, dropout 0.1.
Total parameters: 115,144,168 (115.14M)
Train Loss vs Relative Wall Time
4.0
Transformer
LSTM
Train Loss
3.0
Mamba
1.5-
0.5
0.0
2500
5000
7500
10000
12500
15000
17500
Wall Time (seconds)
Figure 12: Train loss function of relative wall time for different sequence- model architectures under a fixed 5-hour training budget.
Model
LSTM
Mamba
Transformer
Test classification error
0.067
0.041
0.038
Table 30: Final test classification error for basis prediction after 5 hours of training.
Under matched training budget and comparable parameter scales, the Transformer and Mamba models exhibit very similar behavior: both converge rapidly and reach substantially lower error than the LSTM baseline. The Transformer achieves the lowest final classification ror, but the margin over Mamba small (0.038 vs. 0.041), and their learning curves track each other closely throughout training. In contrast, the LSTM optimizes more slowly and remains no- ticeably less accurate despite using comparable hidden size. Overall, these results suggest that via self-attention or selective
Conclusion:
architectures capable of capturing long-raud cong-range state-space mechanisms are particularly effective for SOS basis prediction.
E. ABLATION: CHECKPOINT PERFORMANCE ACROSS TRAINING
To evaluate how the method's performance evolves throughout training, we assess our Transformer- model at various checkpoints corresponding to different numbers of training samples E (10000, 100000, 200000, 300000, 400000, 500000, 1000000). We report results for two representa- tive configurations from Table (i) 8. sparse structure, degree 20, average basis size 30; and (ii) n 4, dense structure, degree 6, average basis size 20. For each, we report test classification enrrr and coverage support and solver runtime.
31

---

Published as a conference paper at ICLR 2026
samples
error
support coverage
solve time
10,000
0.4955
0.00
12.59
100,000
0.1583
0.04
9.45
200,000
0.0382
0.11
2.59
300,000
0.0159
0.34
1.77
400,000
0.0101
0.56
1.05
500,000
0.0067
0.60
0.93
1. 1,000,000
0.0029
0.62
0.62
Table 31: Checkpoint performance on configuration (i) (n 8, degree 20, average basis size 30).
samples
crror
support coverage
solve time
10,000
0.03003
0.17
1.13
100,000
0,00095
0.67
0.67
200,000
0.00078
0.71
0.43
300,000
0.00065
0.71
0,40
400,000
0.00063
0.71
0.40
500,000
0.00061
0.71
0,40
1,000,000
0.00061
0.71
0.40
Table 32: Checkpoint performance on configuration (ii) (n = 4, degree 6, average basis size 20).
Across both experiments, performance improves consistently as the number of training samples increases. At very small checkpoints (c.g., m 10,000), the model exhibits high variance and comparatively poor error, reflecting underconstrained estimation. Once reaches the mid-range 1100,000-30,,000 3000,,00000,,.,. error drops by more than an order of magnitude and coverage support stabilizes near zero, indicating that the classifier has effectively learned the underlying structure. Increasing m further provides diminishing but still measurable gains: the lowest errors consistently occur at or near m 1,000,000. Overall, these results show that the method benefits substantially from additional training samples early on, but transitions to a regime of slow incremental improvement once sufficient data available.
Conclusion:
E.11
CASE STUDY: VAN DER POL OSCILLATOR
We consider the standard Van der Pol system
dx
((1
x²)
+ x ==
dt
dt
As candidate Lyapunov function, we use polynomial from (Pect & Papachristodoulou 2012)
((11,22) (6.93z, 2.45x2)) (2.45(x; + xラ + 4.48x2)
+ +2.45xz x² + (x1 + ui + 1.45x2)
We plug this candidate into SumO j1. The package automatically constructs sufficient monomial basis for the SOS constraint, namely
B [.g 3i, 31 xf22),
which is strictly larger than necessary.
In contrast, the Transformer-model trained on sparse instances with n variables correctly iden- tifies the minimal SOS basis
B2 [21, D2, 2f02],
which is exactly the set of monomials that appear linearly in the four square terms defining V.
32

---

Published as a conference paper at ICLR 2026
E.12 TRAINING TIME AMORTIZATION
To evaluate the practical trade-off between one-time training cost and per-instance solver speedup, consider four representative datasets spanning the regimes in Tables and
Small: dense G-variable, degree-12 12 instances (cf. Table lb;
Medium: variables, degree 20 (cf. Table 2);
Large: 8 variables, degree 20 (ef. Table 2);
XL: 100 variables, degree 10 (cf. Table 2).
Tranning Cost per Model
Amortization Training Cost
10'
31:00
# Instances to Break Even
Training Time (hours)
10"
10.0
7.5
5.0
60'
25-
6. Small
10'
Medium
Large
XL
Small
Medium
Large
Figure 13: Training cost amortized speedups. Left: total training time (hours) for the four representative problem scales. Right: number of instances required to amortize training. computed as Neeakeevenn / AT', where AT is the average per-instance time saved compared to the best baseline solver (up to the 2-hour timeout for XL). For small instances, training would only amortize after thousands of solves; for large and XL. configurations, amortization occurs after roughly 6-8 problems, each saving tens of minutes to about two hours of solver time.
As shown in Figure 13 small-scale models train quickly (~22 h) but offer only sub- savings per instance, making amortization impractical unless thousands of solves are required. In contrast, for larger configurations-wleeee one-time training cost (4-111 h) is amortized after only 6-8 SOS problems. This demonstrates that learning-augmented basis prediction is most beneficial precisely in the high-dimensional regime where classical SOS methods struggle computationally.
single solve can save from tens of minutes up to the 2-hour timeout-
E. QUALITATIVE MODEL BEHAVIOR
We briefly analyze the Transformer's predictions. In simple settings, it learns intuitive algebraic patterns- for instance, including z² whenever higher-order terms like x² appear, echoing common SOS structures. Even in complex cases such the high-degree experiments Table 2 (degree 40), the model selects compact bases that outperform naïve degree-based heuristics. Overall, the Trans- former captures meaningful dependencies among monomials despite the typical difficulty of fully interpreting its internal representations.
F PROOFS
Lemma 2. Let p(x) E R[ be a polynomial and B C. Ma be basis. Then, the support of is contained in the set of all pairwise products of monomials in B, formally S(p) S B- where B {m, my m, m, B). say that covers p(x) if S(p) S B B.
Proof. Let E [ .n) be polynomial and B C Ma be basis. If p has SOS decompo- sition using basis B, then
p(x) = xx() (x)(x)
for some PSD matrix Q. Let S(p) be any monomial appearing in Since p(x) n (x) 2 (x)(x), the monomial u must arise from some product 2; 2xxx), where Zi, E B. Therefore, B B.
33

---

Published as a conference paper at ICLR 2026
Lemma 5 (Consistency). Let Booy be feasible SOS basis obtained by Algorithm 1 If |B and Beool = B. then Algorithm finds a SOS certificate by solving only a single SDP with the smallest possible basis size.
Proof. This is immediate from the definition of 1) and the fact that [Bow]] [B%] Therefore, the algorithm will find the certificate on the first SDP solve.
Lemma 6 (Robustness). The combined computational cost of Algorithm ] and Algorithm 2 is at most k times the cost of the standard Newton polytope approach.
Proof. In the worst case, our algorithm fails to find feasible SOS decomposition until the final attempt with basis size my N (the full sufficient set). By our assumption that the cost of the SDP with basis size scales θ (m²²), the total computational cost is bounded by
θ
Σ
m
The cost of the standard Newton polytope approach scales θ (NW). Therefore, the competitive ratio is bounded by
+ E my
m Σ No
8 θ (Nw)
= 0
-(K).
Lemma 4 (Geometric Expansion). Let Beov be coverage-repaired SOS busis obtained by Algo-
rithm 1 Let the coverage rank be n,. set m1 = BBool and choose p > Then, Algorithm 2 performs at most + [log,(n/m1]] SDP solves and has total cost at most θ (I-=='") 11
Proof. Let the schedule satisfy mi = |Beoel and m4+1 = [pms]] with > 1. By induction, my pm We must reach a basis of size at least the coverage rank n, the smallest j with p² m1 2 17 satisfies I + (n/m))
For the cost bound, note that the cost of our schedule is θ
(EE
mt²
Further, note that m Therefore, E/_1 my S
and thus m, = [pm,-1] & pn.. For any t S j. m. I
my p3-
S
A7 ps
(pn) 3 p ws < T-p 1f", which yields the claimed θ
1----- 7"
Finding minimal SOS bases is computationally hard as involves to minimization. Instead, establish lower bounds on the size of basis that are often tight in practice.
Lemma (Combinatorial bound). For any SOS basis B of polynomial p(x) with support S(p), we
have B > v1+8 s(p)
2
Proof. Suppose we are given a valid SOS decomposition p(x) = zx(x) (x(xx of Then, we can rewrite 2 (x)T T 2 as sum of squares linear forms:
xxxx)²
xx(x) Q (z((x)=
= (x)x(())
2.
Therefore, the number of distinct monomials in xx T [QZ((x) is at most Σ1 k [B[( Since n (x) T Q z (x) = p(x) we have that [S(p) < [B +1).
2
Therefore, B > S1+8S(pp)
34

---

Published as a conference paper at ICLR 2026
Intuitively, the combinatorial bound follows from the fact that basis of m monomials generate most m=(m++) distinct monomials. Finally, the Newton polytope vertices lemma shows that certain 2
vertices of the Newton polytope must appear in any SOS basis.
Lemma 8 (Newton polytope vertices). For any SOS basis B of polynomial p(x) with support S(p) and half Newton polytope vertices = vertices( N (p)), we have {u E V :u² E S()) C B.
Proof. Suppose u E V is a vertex of (p) and x² E S(p). Further, we know that due to being vertex of (p),, there are other monomials 11, U2 [N)pp) such that 42 u². Therefore, the only way to obtain u² in any SOS decomposition of p is to include u in the basis. Since this holds for all vertices of (p) for which we have x² E S(p), we have that any SOS decomposition of p must include all monomials in V.
2
We now study schedule selection with an unknown coverage rank. Given an initial basis size my and geometric expansion factor p > 1, let j denote the first iteration where Algorithm 2 finds feasible solution with basis size m,. Feasibility requires
p'm, 2 my 2 1)
In practice, we do not know the true coverage rank 1) in advance. If r were known, we would jump size 17 in a single step. Since rj instnnce-deeendent and unknown expansion time, we model
"
as random variable and pose the stochastic optimization problem
k(p)
min
Σ (o'm,)) m²)
k(p) logp mm )
p> 1.
Using empirical risk minimization, let Xi,..., XM be samples of X (and allow mi, vary if desired). We then solve
M kp(p)
min ((p = Σ Σ
m)))))))
==1 mm1
X₂ m1,1
s.t. kp(p) = log,
(ERM)
1>1.
Because the cost function is increasing in basis size and ks decreases with P (and is piecewise constant), it suffices to evaluate finite grid of p values and select the one with smallest cost. Theorem 9 (Finite candidate grid for optimal p). Let J (p) denote the ERM objective introduced above. Then, there exists a finite grid of p values such that the minimizer of J (p) lies in the grid.
Proof. We first show that (p) has a minimizer. Note that m1, X; for all i, therefore k;(p) 2 1. 1M is bounded, there exists Pmax > 1 such that (x((max) 1 for all i. Further, for all > Pmax we have that {pp 2 (Pmmx)) Further, we have that as p - 1, (p) - co. Therefore, (p) has minimizer that lies in [Pminn Panax] for some Pmax > Pmin 1.
Since ( Ji=1
Next, note that all ks(p) are piecewise constant, and there are finitely many breakpoints. Therefore, there exists a finite grid of values P1...., PL such that for all (Ps, P:+1) all kp(p) are constant. Since (p"m,,))" is strictly increasing in p, we have that (() is strietly increasing for all intervals (pi, Pi+1). Therefore, the minimizer of ((p) lies in the left endpoint of one of the intervals (pi, Pi+1).
Remark 10. Further refinements of the proposed approach are possible. Instead of fixed geo- metric expansion, any increasing sequence of basis sizes my m2 < <... < my can be used and potentially similarly be optimized via ERM. Here, chose the geometric expansion for its simplicity.
35


Reviews:
[{"review_id": "5blyyPMneb", "reviewer": "Reviewer_rzN3", "summary": "This paper addresses the challenge of certifying the non-negativity of polynomials efficiently being constructing a minimal basis based on the output of a trained transformer model and subsequently correcting the prediction to form a valid basis. The paper presents a comprehensive set of experiments to demonstrate their claims of drastic speedups for SOS programming.", "questions": "1. Since basis repair is being performed, how would the method perform when initialized with a random starting basis, as opposed to predicting them from a learnt model?\n\n2. How does the performance of the method change across different checkpoints during training?\n\n3. From line 693, it appears that only one epoch of training is required, suggesting very fast convergence. Could the authors provide insights into why this is the case?\n\n4. Why would other sequence-to-sequence models, such as RNNs, LSTMs, or SSMs, not be suitable for this task?\n\n5. Several lemmas (Lemmas 4, 5, and 6) and a theorem (Theorem 8) are presented in the appendix without reference in the main text. Could the authors include a discussion in the main body explaining the significance of these results and how they contribute to the development of the method?\n\n6. In lines 262-263, the authors state: ‘’we exploit the fact that our Transformer is not equivariant with respect to variable orderings.’’ Could the authors provide a brief justification for this claim?\n\n7. The paper claims that ‘’Despite being trained only on degree 12 polynomials, our model can successfully predict bases for degree 20 polynomials by leveraging familiar substructures—though it has not seen complete degree 20 monomials.’’ It remains unclear whether this behavior would extend to settings with a much larger number of variables (say 1000s).\n\n---\nSome minor comments/nitpicks that did not affect the decision:\n\nLine 156: Specify that $Q$ is a *symmetric* matrix; this would improve clarity and rigor.\n\nFigure 3 is presented after Figure 4; consider reordering for consistency.\n\n**Looking forward to the discussion period to clarify these questions and strengthen this work.**", "limitations": "", "rating": 2, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "**Well-Motivated and Interesting Problem**:\nThe problem of identifying a compact basis is, in the reviewer’s opinion, interesting, and this paper proposes a novel learning-based algorithm to address this challenge.\n\n**Comprehensive Experimental Evaluation**:\nThe paper presents a range of experiments that provide strong empirical evidence supporting its claims.\n\n**Strong Experimental Results**:\nThe proposed solution consistently demonstrates substantial speedups over baseline methods.\n\nThe authors also provide readable and well-documented code in the supplementary material, which aids reproducibility (although I have not attempted to reproduce the results).", "weaknesses": "**No Insight into the necessity of transformers**:\nIt is not clear why transformers, in particular, are essential to the proposed method. As presented, the approach appears applicable to any sequence-to-sequence model with a similar encoding scheme. Furthermore, the paper does not provide insights from the learned model itself that could help explain how or why the trained models can predict compact bases efficiently.\n\n**Several missing discussions/references**:\nThis work does not adequately address the rich body of related work on basis selection in Polynomial Optimization. In particular, the authors should make note of and should consider baselining against the following works:\n\n[1]. Zheng et al - Chordal decomposition in operator-splitting methods for sparse semidefinite programs, 2023\n\n[2] Mason and Papachristodoulou - Chordal sparsity, decomposing SDPs and the Lyapunov equation, 2014\n\n[3] Newton and Papachristodoulou - Sparse polynomial optimisation for neural network verification, 2023\n\n[4] Ahmadi and Hall - Sum of squares basis pursuit with linear and second order cone programming, 2015\n\n[5] Miller et al, Decomposed structured subsets for semidefinite and sum-of-squares optimization, 2022\n\n**Lack of experiments on real-world datasets**: \n\nWhile the basis pursuit for SOS verification is promising, this work suffers from a lack of applications to problems of interest that utilize polynomial optimization. Moreover, there is a lack of baselining against methods that don’t use basis search to improve efficiency - for instance, how does the end-to-end performance of the proposed transformer-based approach compare with AnySOS [6]? Can the proposed approach be used for real-time data-driven control that uses SOS programming, such as [7],[8]?\n\n[6] Driggs and Fawzi. AnySOS: An anytime algorithm for sos programming, 2019\n\n[7] Dai and Sznaier. A semi-algebraic optimization approach to data-driven control of continuous-time nonlinear systems, 2021\n\n[8] Strasser and Berberich. Data-driven control of nonlinear systems: Beyond polynomial dynamics. 2021", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YnKSl8GTSs", "reviewer": "Reviewer_wmbZ", "summary": "This paper proposes a learning-augmented algorithm for certifying the nonnegativity of polynomials via the sum-of-squares (SOS) criterion, a classic computational bottleneck in polynomial optimization. The authors leverage a Transformer model to predict a compact monomial basis for a polynomial, reducing the size (and cost) of the associated semidefinite program (SDP) used for SOS verification. They propose a fallback mechanism to ensure correctness for incomplete predictions, provide theoretical analysis on algorithmic efficiency, and empirically validate the method over a very large synthetic dataset and multiple benchmark scenarios, demonstrating substantial speedup over state-of-the-art methods while maintaining correctness guarantees.", "questions": "1. Are there plans or possibilities to evaluate the framework on real-world, domain-specific SOS problems (e.g., systems or control, chemical design, robotics)? Can the authors comment on what barriers exist to acquiring such benchmarks, or how the method would fare on “messier” non-synthetic input?\n\n2. Could the authors expand on the types and frequency of solver instabilities encountered, e.g., when switching from MOSEK to SCS? Are there specific structures or matrix conditions that systematically cause difficulties? What practical guidelines could be recommended?\n\n3. For the few cases where the coverage-repaired basis remains insufficient and a large number of basis expansions are required, what failure patterns emerge? Do these correlate with any specific polynomial properties, and can they be detected a priori?\n\n4. Is there any pathway to either guarantee (or at least probabilistically certify) that the learned basis is minimal, or offer reliable bounds on non-minimality? Are there pathological cases in the data generation or in-the-wild polynomials that routinely “confuse” the model?\n\n5. For the non-SOS (negative) polynomials, what is the practical cost for fallback expansion, especially for high-degree/large-variable settings? Could this be further accelerated with early termination heuristics, and would this threaten guarantees?\n\n6. Have the authors tried scaling beyond 100 variables or polynomials with very large/structured sparsity—are there new bottlenecks for the Transformer or SDP solvers in such regimes?\n\n7. Are there possible theoretical refinements to the expansion schedule or the permutation scoring to further reduce worst-case number of SDPs or average expansion cost?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper tackles the persistent computational challenge of SOS certification with a hybrid approach that smartly decomposes basis selection into a learning-driven task, while retaining the robustness of fallback combinatorial methods. The integration of a Transformer model into this traditionally symbolic and combinatorial problem is notably creative.\n\n2. The systematic repair and iterative expansion procedure ensures that, even when the learned model predictions are imperfect, the algorithm retains the worst-case correctness guarantees of classical approaches. The underlying fallback logic is clearly explained and theoretically justified.\n\n3. The empirical evaluation, including Table 1 and Table 2, is broad, comparing against strong baselines such as Newton polytope and full-basis SDP, and modern solvers like SoS.jl and TSSOS. The results are benchmarked across polynomial structure (dense, sparse, low-rank, block-diagonal), variable and degree diversity, and stress test the approach on scalability and distribution shifts.\n\n4. The paper rigorously analyzes the robustness, computational savings, and expansion scheduling, connecting prediction quality to overall efficiency and validating these claims empirically.\n\n5. The paper delivers detailed ablations on design choices such as permutation count and expansion scheduling, showing how performance and computational tradeoffs play out in practice.", "weaknesses": "1. The empirical results rely almost entirely on synthetically generated polynomial instances. The lack of real-world or domain-specific SOS instances is acknowledged as a limitation, but is still significant. This limits the evidence for generalization beyond the synthetic distribution and may mask domain-specific failings.\n\n2. Although Table 1 and other results show strong average-case speedups, there is only brief mention of numerical instability (e.g., SCS used for low-rank cases due to issues with MOSEK). There is little detailed discussion on how the approach fares with poorly conditioned or pathological instances, or the frequency and severity of failed or unreliable SDP solves.\n\n3. While there are useful heatmaps and success rate statistics, the paper stops short of a rigorous exploration of the behavioral regime where the Transformer model fails most catastrophically (e.g., in dense and low-rank polynomials). Further, it remains unclear whether model “hallucinations” or systematic biases exist in certain polynomial structures that could lead to silent failure, even after repair.\n\n4. The algorithm for fallback/expansion and scoring monomials by permutation frequency is mathematically described, but several technical implementation choices and their rationale (e.g., why a specific permutation count $L=4\\sim8$ balances computational cost and recall) are only empirically motivated. It would be beneficial to see more theoretical discussion or even bounds on the expected number of necessary expansions under mild error assumptions. Furthermore, the text can be unclear on the relationship between minimum basis selection and coverage repair, especially when the predicted basis is far from minimal.\n\n5. The paper claims generalization to degrees and distributions not seen in training, but the OOD analysis (while a nice touch) remains somewhat superficial and is itself conducted over synthetic shifts. More rigorous OOD characterization (such as sharp ablation on unfamiliar sparsity, more adversarial polynomials, or empirically ill-posed SDPs) is missing.\n\n6. The model is said to predict “near-minimal” bases, but there is no formal guarantee, and the possibility of pathological overextension (and thus loss of computational gains) is not fully explored in the main paper.\n\n7. The repair algorithms are shown to work well overall, but the impact of their greedy design is not fully characterized in failure cases, such as cases with many missing basis elements or in noisy/perturbed input. Table 9 and Table 10 provide some view on combinatoric recovery, but the exhaustive performance of the repair mechanism, especially as the dataset difficulty increases, is left for future work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VRMS60GuHt", "reviewer": "Reviewer_JFgt", "summary": "This paper presents a novel learning-augmented approach to Sum-of-Squares (SOS) certification, using transformers to predict small monomial bases resulting in large reduction of the corresponding SDP problem. An iterative fallback mechanism is deployed to ensure correctness of the approach. Empirical results demonstrate important speedups, as well as robustness across polynomial structures, supported by experiments on extensive synthetic datasets. The writing is clear, figures are informative, and the method’s motivation, i.e., addressing the core computational bottleneck in SOS programming, is convincing.", "questions": "## Questions\n\n1. Why is it not reasonable to pick a single transformer architecture that is not dependent on the data, and that has some specialized features, such as equivariance under variable ordering?\n\n2. You generate non-SOS polynomials by perturbing PSD spectra in order to test the overhead of your approach. Did you also consider the inverse procedure — starting from non-SOS polynomials and projecting or adjusting them into the SOS cone — to obtain more realistic and challenging borderline SOS instances for the training data?\n\n3. Any rationale for why your approach underperforms on small and simple test cases?\n\n4. In Table 2, what is the structure of polynomials used for testing? Averages are taken over how many instances?\n\n5. In Figure 7(ii), why is #$\\text{SDPs}$ (y-axis) between 0 and 1?\n\n6. What is $B^{*}$ in Table 1?\n\n7. What is the meaning of the numbers above the bars in Figure 3?\n\n8. Why is $L=2$ used in Experiment 3? By “combined approach,” do you mean first using the greedy approach to ensure the necessary condition from Lemma 1, then using permutation-based expansion with $L=2$?\n\n9. What modifications are necessary for your approach to be applied to general (un)constrained polynomial optimization problems?\n\n10. Which repair mechanism was used in Figure 5(ii)?\n\n11. Line 1563: What is $T$?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The approach is novel, sound, supported by experiments, and demonstrates consistent speedups across different polynomial structures. The writing of the main part is mostly clear, and the overall methodology is both coherent and practically relevant.", "weaknesses": "While the approach is promising, the evaluation is limited to synthetic data, making its generalization to real or benchmark SOS problems unclear. The theoretical analysis offers mainly worst-case guarantees and does not fully characterize how prediction quality influences solver performance. Comparisons with modern sparsity-based SOS solvers are brief.\n\n### Major Points\n\n- The paper relies on several different transformer architectures for different experiment grids, but the reasons behind these architectural choices are not clearly explained. In addition, training appears to require very large datasets, but there is no information about the training costs. As a result, it is difficult to evaluate the practical trade-off between the cost of learning and the runtime improvements obtained during SOS solving.\n\n- Although the paper claims real-world SOS benchmarks are not widely available, there are well-established applications, such as Lyapunov stability certification in control. Testing even a small selection of such problems would greatly strengthen the practical relevance and demonstrate generalization beyond synthetic data.\n\n- Theoretical results give useful worst-case guarantees for the fallback mechanism, but they do not provide any attempt of a principled explanation of when the transformer should produce accurate predictions that yield substantial speedups. At present, the conditions under which the learning generalizes reliably (e.g., to sparse or block-diagonal structure) are supported only by experiments.\n\n\n### Minor Points\n\n- It would be appropriate to distinguish between a polynomial $p \\in \\mathbb{R}[x_1,\\dots,x_n]$ and its evaluation $p(\\mathbf{x}) \\in \\mathbb{R}$ at some point $\\mathbf{x} \\in \\mathbb{R}^n$.\n- Line 106: “…smallest possible basis *for which a given polynomial* $p$ admits an SOS decomposition.”\n- Lines 126–129: rephrase for clarity.\n- Figures should be placed and discussed immediately after they are introduced. For example, Figure 1 is only referred to at Line 185. Apply this consistently throughout the paper (**especially Section 4**) and appendix for all figures and tables to improve readability.\n- Line 210: there should be an intersection with $\\mathbf{Z}^n_{\\geq 0}$, as the networks likely do not predict rational exponents.\n- A lemma typically denotes a nontrivial intermediate theoretical result. Since Lemma 1 is a direct observation from the SOS definition, calling it a remark may probably be more appropriate.\n- It is not necessary to include the Newton polytope in the input to your algorithms, as the polytope depends on the true input $p$.\n- Line 343: replace *is* by *are*.\n- Figure 3 (or Section 4.1) could be improved by reporting, for example, the average gap between the Transformer’s prediction and the minimal necessary basis size.\n- Figure 6 seems more appropriate for the main text, where it could help illustrate the concept on your simple toy example.\n- Line 1001 (Table 9): k should be in math mode.\n- Use $\\hat{B}$ consistently for a single meaning (see Lines 1069–1070).\n- Algorithm 2: write the concatenation $(B_{\\text{cov}}, C)$ properly. Also, use t\\in`\\{2,...,k\\}`  instead of \n$t \\in (2, \\dots, k)$.\n- Line 1511: $|S|$ should be $|S(p)|$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)