Learning to Coordinate Symbolic Tools: LLM Agents for Verified Sum-of-Squares Certificates

arXiv:2608.00326 · cs.AI · Submitted 2026-08-09 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Learning to Coordinate Symbolic Tools: LLM Agents for Verified Sum-of-Squares Certificates".

Jane: The paper was written by Bohan Chen, Shivam N. Patel, Richard Hoffmann, Sam Looi and Tony Yue Yu from California Institute of Technology and OpenAI.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the channel, everyone. I’m Tom, and alongside me is the brilliant Jane. Today we’re cracking open a paper that’s got a mouthful of a title: “Learning to Coordinate Symbolic Tools: LLM Agents for Verified Sum-of-Squares Certificates.”

Jane: And Tom, I have to say, that title is dense, but it’s hiding something really cool. It’s about teaching an AI to not just do math, but to *use tools* to do math, and then to *prove* it got the right answer.

Tom: Exactly. So, first off, the authors—Bohan Chen, Shivam Patel, Richard Hoffmann, Sam Looi, and Tony Yue Yu—they’ve set up this whole system where a language model gets to call on a symbolic math engine, like SymPy, to do the heavy lifting.

Jane: Right. And the key phrase in that title is “verified.” That’s the part that gets me excited. The AI doesn’t just guess an answer and hope it’s right. It has to produce a certificate, a mathematical proof, that its answer is correct.

Tom: And that’s a huge deal, because normally when we ask an AI to do math, it’s just predicting the next token. Here, they’re forcing it to interact with exact tools and then checking the final result against a strict, machine-checkable standard.

Jane: So it’s like the difference between an AI telling you a recipe and an AI actually cooking the dish and having a food critic verify it tastes right. The verification is the key.

Tom: I love that analogy, Jane. And the implications are big. If we can get AIs to reliably use external tools and then verify their work, we’re not just making them better at math. We’re making them more trustworthy for all sorts of tasks where correctness matters.

Jane: And that’s the hook for today. We’re going to dig into how they actually built this thing, what the numbers look like, and what it means for the future of AI reasoning. Stick around.

Summary: Tom: So we’re back, and we’re still on “Learning to Coordinate Symbolic Tools.” Jane, you gave us the big picture. Let’s get into the meat of what they actually did.

Jane: Okay, so the core problem is this thing called a weighted sum-of-squares certificate. In math, if you want to prove a polynomial is always positive, one way is to write it as a sum of squares, each multiplied by a positive weight. That’s a certificate.

Tom: And finding that certificate is hard, because there are a million ways to group terms. But *checking* a certificate is easy. You just expand it and see if it matches the original polynomial.

Jane: Exactly. So they built an AI agent that has to *search* for this certificate. It has tools like expansion, factorization, and reordering. And at the end, a verifier checks the final answer exactly.

Tom: And the results are pretty striking. The fully trained system, which they call “Full,” gets a seventy-eight point nine six percent success rate on these weighted SOS problems. That’s compared to just forty-four point seven three percent for the base model with the same tools.

Jane: So just giving the AI tools isn’t enough. You have to train it on how to use them. That’s the “coordination” part of the title. The base model had the same toolbox but didn’t know how to sequence the operations.

Tom: Right. And they trained it in two stages. First, supervised fine-tuning on a huge dataset of one point three five million synthetic examples covering eight different algebra tasks. Then, they used reinforcement learning, specifically GRPO, to optimize for getting the certificate right.

Jane: It’s like teaching someone the rules of chess and then having them play thousands of games to learn strategy. The tools are the rules; the RL is the strategy.

Tom: And the coolest part is that the final answer is always checked by exact expansion. No approximation, no “close enough.” It either expands to the target polynomial, or it fails.

Jane: So we’re getting AI that can do multi-step symbolic reasoning with a guarantee of correctness. That’s a big step forward, and I can’t wait to see how they got the training data to work.

Improvements: Tom: Welcome back. We’re talking about “Learning to Coordinate Symbolic Tools,” and Jane, we just covered the headline numbers. But what’s the *improvement* here? What did they actually add to the field?

Jane: The big improvement is the training recipe. They didn’t just throw a bunch of examples at the model. They built a whole curriculum. Eight supporting tasks, like factoring, expanding, and reordering, plus the main SOS task.

Tom: And that’s key. The model learns the *individual moves* first, and then learns how to combine them. It’s like learning scales before you play a concerto.

Jane: Exactly. And there’s a really clever detail. The supervised fine-tuning data doesn’t include any native tool-calling messages. It’s all simulated. The model learns what expansion *does* by seeing examples, but it doesn’t see the actual function call syntax.

Tom: So then, at test time, when it suddenly gets access to the real tools, it has to figure out how to map its learned knowledge onto the actual interface.

Jane: Right. And that’s where the reinforcement learning comes in. GRPO lets the model try different sequences of tool calls, get feedback from the verifier, and learn which sequences work.

Tom: And the improvement is dramatic. The full system is thirty-four points better than just the base model with tools. That’s not a small bump. That’s a fundamental difference in capability.

Jane: It also shows that the RL stage is doing something real. The SFT model gets fifty-one point eight two percent on SOS, but the full model gets seventy-eight point nine six percent. So the reinforcement learning is adding a huge amount of value on top of the supervised training.

Tom: So the improvement isn’t just “more data.” It’s a smarter training pipeline that separates learning the operations from learning the strategy.

Jane: And that’s a recipe that could apply to other domains, not just math. Anywhere you have exact tools and a verifiable end state, this approach could work.

Tom: Great point. Now, let’s actually look at the first page of the paper and see how they frame this whole problem.

First Page: Tom: We’re back for another segment on “Learning to Coordinate Symbolic Tools.” Jane, let’s actually read the opening of the paper. What’s the first thing they hit us with?

Jane: They start with a really sharp observation. They say, “Exact tools can make an individual operation reliable without making an agent’s overall strategy correct.”

Tom: That’s the whole ballgame right there. You can have a perfect calculator, but if you don’t know what to calculate, you’re lost.

Jane: Exactly. And they frame the central question as: Can algebra-grounded post-training enable an LLM to coordinate exact symbolic operations during multi-step search?

Tom: And they mention the Jacobian conjecture, which is this famous unsolved problem in math. It’s a nice way to show why polynomial reasoning matters, even if their task is different.

Jane: Right. They’re not trying to solve the Jacobian conjecture. They’re using a smaller, controlled problem to study how AI agents can learn to use tools strategically.

Tom: And they’re very clear about the scope. They say it’s a “controlled setting” with small synthetic polynomials. They’re not claiming to have solved all of math.

Jane: But that’s what makes it a good scientific study. They isolate the variable. They hold the backbone model fixed, they control the data generation, and they measure the effect of their training pipeline.

Tom: And they also introduce the idea of the “terminal verifier.” That’s the thing that checks the final answer. It’s not enough to have a well-formed answer. It has to be *exactly* right.

Jane: And that’s the standard we should hold AI to. Not just “looks plausible,” but “provably correct.” The first page sets that bar really clearly.

Tom: So we’ve got the problem, the approach, and the standard. Now, let’s wrap this up and see what it all means for the world.

Conclusion: Tom: And that brings us to the end of our discussion on “Learning to Coordinate Symbolic Tools: LLM Agents for Verified Sum-of-Squares Certificates.” Jane, what’s the one thing you want listeners to remember?

Jane: I think it’s that giving an AI tools isn’t the same as teaching it to use them. The full system’s seventy-eight point nine six percent success rate versus the base model’s forty-four point seven three percent shows that training on the *strategy* is what makes the difference.

Tom: And that strategy is learned through a combination of supervised learning on basic algebra and reinforcement learning on the actual search problem.

Jane: Right. And every single success is verified by exact expansion. There’s no fudging. The machine checks the math, and the machine is always right.

Tom: So what’s the impact? This is a blueprint for building AI agents that can do reliable, multi-step reasoning in any domain with exact tools and verifiable outputs.

Jane: Think about code generation, formal proofs, even scientific discovery. If we can train agents to coordinate tools and then prove their work, we can trust them with harder problems.

Tom: And that’s the exciting part. This isn’t just a math paper. It’s a case study in how to build trustworthy AI.

Jane: Well said, Tom. We’re saying goodbye to this paper, but we’re taking its lessons with us. Thanks for listening, and we’ll see you on the next one.

Bohan Chen, Shivam N. Patel, Richard Hoffmann, Sam Looi, Tony Yue Yu

California Institute of Technology · OpenAI

cs.AI

Submitted: 2026-08-09

Updated: 2026-08-11

Comments: 15 pages, 4 figures

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 69/100

Key concepts

Sum-of-Squares (SOS) Certificate
A weighted sum-of-squares certificate is a mathematical proof used to show that a polynomial is always positive. It involves writing the polynomial as a sum of squares, each multiplied by some positive weight. The AI agent must search for this specific structure and verify it using exact expansion.
Tool Coordination
LLM agents use external symbolic math engines (like SymPy) as tools. The core challenge is not just having access to these tools, but learning the correct sequence of operations—the coordination—to solve a multi-step problem. This is what differentiates the trained system from the base model.
Verification
Verification means the AI must provide a mathematical proof (a certificate) that its solution is correct. The system uses an exact verifier that checks the final result against the original polynomial using exact expansion, ensuring no approximation is accepted.

Terminology

Summary

Core research question: Can algebra-grounded post-training enable an LLM to coordinate exact symbolic operations during multi-step symbolic search, rather than merely execute isolated algebraic transformations?

Task studied: Weighted sum-of-squares (SOS) decomposition, a machine-checkable route to proving polynomial nonnegativity. A weighted SOS certificate is an identity of the form f = Σ cⱼ pⱼ2, with cⱼ ∈ Q>0. Such an identity proves global polynomial nonnegativity and can be checked exactly by expansion. Finding such an identity is non-unique and strategic: expansion hides square structure, mixed terms admit several plausible groupings, and a locally correct transformation can leave an unusable remainder.

Key distinction: "Exact tools can make an individual operation reliable without making an agent's overall strategy correct. A tool-using language model must still decide which operation is useful, construct its arguments, interpret the observation, recover from an unhelpful result, and know when to stop."

Methodology:

  1. Synthetic curriculum: Nine tasks, each contributing 150,000 generated examples, totaling 1,350,000 examples before a 5% validation split (1,282,500 training records). Inputs use one to three declared variables and one to five initial terms. The nine tasks are:

  • Four local operations: lexicographic term ordering, collection, expansion, factorization

  • Four broader structural tasks: Horner form, symmetric reduction, quotient/remainder, extended GCD

  • One composite target task: weighted SOS

  1. Supervised fine-tuning (SFT): Applied four-bit QLoRA to Phi-4-reasoning-plus. Only assistant tokens are prediction targets; system and user tokens are masked from the loss. The SFT corpus contains no native function-call messages or tool descriptions—only direct problems and simulated symbolic traces with Python-like snippets and returned algebraic results, including retries and errors. Run configuration: rank 32, scale 16, dropout 0.05, 2,048-token limit, learning rate 5×10−5, one epoch, one H100, 181,848 packed sequences, approximately 3.72×108 tokens, 22,731 optimizer steps.

  2. Verifier-grounded GRPO: Starting from the SFT model, uses task-specific symbolic rewards. Reward formula: Rk(y) = −1 if the answer wrapper is absent; otherwise 0.1·I fmt(y) + 0.9·rk(y), where rk ∈ [0,1] is computed from the exact task contract rather than string equality. GRPO uses a global prompt batch of 64, eight generations per prompt, 20,039 optimizer steps, approximately 55 hours on four 80GB H100 GPUs.

  3. Native SOS deployment: At test time, tool-enabled systems (Base+Tools and Full) interact with four SymPy-backed functions: expand polynomial, collect terms, reorder polynomial, and factorize polynomial. Limits: at most ten calls, at most three decomposition attempts, five seconds per call, 60 seconds per episode.

Acceptance contract: A candidate is accepted only if it parses as a finite sum of the form f = Σ cⱼ pⱼ2, every weight is an exact positive rational number, every summand is a polynomial square, and expand(f − Σ cⱼ pⱼ2) = 0 coefficient by coefficient. Because every accepted summand is nonnegative on Rn, this identity immediately certifies f(a) ≥ 0 for every real input a.

Evaluated configurations:

  • Base: Unadapted Phi-4, no native tools on SOS

  • SFT: QLoRA SFT checkpoint, no native tools on SOS

  • Base+Tools: Unadapted Phi-4 with native tools on SOS

  • Full: SFT → GRPO with native tools on SOS

Results:

  1. Direct algebraic performance (eight supporting tasks, native tools disabled for all checkpoints):

  • Base: 42.01% eight-task macro-average

  • SFT: 78.08% eight-task macro-average

  • Full: 93.35% eight-task macro-average

  • Full is strongest on every supporting task. Per-task Full results: term ordering 97.61%, collection 96.84%, expansion 98.73%, Horner form 89.47%, symmetric reduction 82.19%, quotient/remainder 93.28%, extended GCD 91.53%, factorization 97.12%.

  1. Verified weighted-SOS performance (the only native tool-calling task):

  • Base: 7.63%

  • SFT: 51.82%

  • Base+Tools: 44.73%

  • Full: 78.96%

  • Relative to Base, SFT improves by 44.19 percentage points and Base+Tools by 37.10 points; Full is a further 27.14 points above SFT and 34.23 points above Base+Tools.

  1. Nine-task system macro: Base 38.19%, SFT 75.16%, Full 91.75%.

  2. Post-hoc family analysis: Relative to SFT, Full gains 12.46 points on local operations, 18.08 points on structural algebra tasks, and 27.14 points on weighted SOS. The increasing gap is consistent with the complete system providing larger improvements as tasks require more global representation and search choices.

  3. Terminal failure taxonomy: Unsuccessful terminal outputs fall into three classes: (1) premature completion or abstention, (2) an expression that is not a valid weighted SOS (structural failure), (3) a well-formed weighted SOS whose expansion is the wrong polynomial (identity failure). Exact verification prevents all three from being counted as proofs.

  4. Tool-use statistics: Successful Full episodes use 3.8 native calls on average, below the ten-call limit.

  5. General-mathematics retention checks (tools disabled, avg@16, one 16-sample pass):

  • AIME-90: Base 16.67%, SFT 34.44%, Full 38.89%

  • GSM-8K: Base 91.58%, SFT 93.71%, Full 96.29%

  • These secondary results are retention checks: they show no obvious loss of general mathematical performance in this evaluation pass, but they are not evidence of broad transfer or generalization.

Key findings and interpretations:

  • "Exact execution does not remove coordination errors. A backend can execute a requested operation perfectly while the agent chooses an unhelpful operation, argument, grouping, or stopping point. The 44.73% Base+Tools result and the three terminal failure types make this distinction concrete."

  • "Algebraic grounding is a plausible complement to tool access. The Full system's advantage over Base+Tools is consistent with the hypothesis that training on the operations and representations behind a tool can complement learning its interface."

  • "Discovery, interaction, and verification must be distinguished. Every evaluation polynomial has a weighted-SOS certificate by construction, but the prompt does not reveal this fact and credit is awarded only for an accepted certificate. Thus the reported success rate is certificate-search yield under a fixed budget, not SOS recognition; abstention is a failed search, not a correct negative."

Contributions claimed:

  1. An exactly verifiable agent testbed: weighted-SOS certificate search supported by eight direct algebraic tasks, 1.35 million generated examples, and 90,000 separately generated test problems.

  2. An algebra-grounded post-training recipe combining assistant-token QLoRA SFT, verifier-grounded GRPO, a native four-function SymPy interface, and exact terminal verification.

  3. Complete-system evidence with calibrated scope: four-configuration comparison, direct-task checkpoint performance, terminal failure categories, and explicit distinction between empirical findings and broader design hypotheses.

Limitations explicitly stated:

  • The evidence is limited to same-generator synthetic problems with one to three variables, weighted SOS, one backbone, and one run per stage.

  • The experimental design compares complete configurations; component-level effects of SFT, GRPO, tools, individual supporting tasks, and the internal model–harness control split are outside its scope.

  • The study does not cover natural inequality benchmarks, larger polynomials, non-SOS classification, constrained certificates, repeated training seeds, or cross-backbone transfer.

  • The current configurations establish the behavior of the complete deployed system, not the separate contribution of this representation change.

  • The grouping is descriptive, and per-task causal attribution is outside the experimental design.

  • The study evaluates the combined reward and does not isolate individual reward components.

Positioning relative to related work: The paper distinguishes itself from NSPI (which trains a direct SOS conjecturer with numerical refinement and Lean verification) by stating: We instead study sequential exact tool coordination without numerical repair. The empirical object is therefore tool coordination in a controlled certificate-search environment, not state-of-the-art inequality proving. It also positions itself relative to AIPS, LIPS, IneqSearch, APPIRL, NeuralSOS, and AquaForte, noting the distinction is the scientific object: weighted SOS is used as an exactly checkable environment for studying a sequential tool agent rather than as a claim of general or state-of-the-art inequality solving.

Conclusion: "Weighted-SOS search provides a controlled setting in which local algebra is exact, global search remains nontrivial, and final correctness is machine checkable. An algebra-grounded Phi-4 checkpoint trained with SFT and verifier-grounded GRPO, then deployed with native SymPy calls, reaches 78.96% verified SOS success versus 44.73% for the same base backbone with the same interface. Together with the direct-task results and terminal failure separation, this supports treating learned algebraic skill, tool interaction, and exact verification as distinct parts of a complete agent."

Improvements for AI systems

Based on the paper, here are specific improvements I can implement in an AI system, along with what the improved system can do:

Implementation:

  • Construct a synthetic curriculum of 1.35M examples across nine tasks: four local operations (term ordering, collection, expansion, factorization), four structural tasks (Horner form, symmetric reduction, quotient/remainder, extended GCD), and one composite task (weighted SOS).

  • Apply assistant-token QLoRA SFT on direct algebra problems and simulated symbolic traces (no native tool calls in training data).

  • Continue with GRPO using task-specific symbolic rewards that check exact algebraic contracts (e.g., polynomial equality, reduced remainder, Bézout identity) rather than string matching.

  • Deploy with a native four-function SymPy interface (expand, collect, reorder, factorize) and an exact terminal verifier.

What the improved system can do:

  • Achieve 78.96% verified success on weighted SOS certificate search (vs. 44.73% for base model with same tools).

  • Reach 91.75% macro-accuracy across nine polynomial tasks.

  • Distinguish between schema-valid calls, successful execution, and terminal mathematical acceptance—rejecting premature completion, structural failures, and identity failures.

The improved AI system can:

  1. Coordinate exact symbolic tools (expand, collect, reorder, factorize) during multi-step search for polynomial certificates.

  2. Produce machine-checkable proofs of polynomial nonnegativity via weighted SOS, with 78.96% verified success on held-out synthetic problems.

  3. Learn from verifier feedback (GRPO) to revise unhelpful branches and stop only when the terminal identity is exact.

  4. Maintain general math performance (AIME-90: 38.89% avg@16, GSM-8K: 96.29%) while specializing in algebraic reasoning.

  5. Provide transparent failure analysis by separating premature completion, structural invalidity, and identity mismatch.

  6. Scale to broader algebraic tasks (91.75% macro-accuracy across nine tasks) with a training budget of 55 hours on four H100s for GRPO and one H100 for SFT.

Abstract

Tool calling allows large language models (LLMs) to invoke external computation during problem solving, a useful capability in various fields including AI for mathematics. We study this setting through weighted sum-of-squares (SOS) decomposition, a machine-checkable route to proving polynomial nonnegativity and hence polynomial inequalities. A candidate decomposition can be checked exactly, but finding one requires choosing among non-unique regroupings and coordinating multiple symbolic transformations. We develop an agent that combines algebraic task training, symbolic tools, and verifier-grounded optimization for this task. Rather than training only on the composite SOS task, we construct 1.35 million synthetic examples covering eight supporting polynomial tasks together with weighted-SOS decomposition. We first apply supervised fine-tuning (SFT) to direct algebra problems and simulated symbolic traces, and then use Group Relative Policy Optimization (GRPO) with task-specific symbolic rewards. The SFT corpus contains no native tool-calling messages; at evaluation, the agent uses native SymPy calls for expansion, collection, reordering, and factorization. Every final SOS answer is checked by exact expansion and coefficient comparison. On held-out, same-generator synthetic problems, the full SFT+GRPO+tools system is the strongest of four evaluated configurations, reaching 78.96% verified success on weighted SOS, compared with 44.73% for the base model with the same tools, and 91.75% macro accuracy across nine polynomial tasks. Within this controlled setting, our work provides a case study of combining domain-specific skill training, executable tools, and verifier feedback, and may inform the design of tool-calling agents in other domains with exactly checkable outputs.

Sources

Related papers