🤖 AI

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

This paper presents an LLM agent that achieves high success in generating verified weighted sum-of-squares certificates by combining supervised fine-tuning on 1.35 million synthetic polynomial examples, group relative policy optimization with symbolic rewards, and native SymPy tool usage for exact verification.

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

Published 2026-08-04

📖 7 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where computers are brilliant at following instructions but terrible at figuring out which instructions to follow. This is the current frontier of Artificial Intelligence, specifically for Large Language Models (LLMs)—the super-smart chatbots that can write stories, code, and solve riddles. While these models are great at guessing the next word in a sentence, they often stumble when a problem requires a long chain of logical steps, like a complex math proof. To fix this, scientists are teaching these AI agents to use "tools," much like a human mathematician picks up a calculator, a ruler, or a specialized software program. The big question isn't just whether the AI can use the tool, but whether it can learn to coordinate a whole toolbox to solve a puzzle that no single tool can crack alone. It's the difference between having a hammer and knowing exactly when to hammer, when to screw, and when to stop before you break the wall.

This paper dives into that exact challenge using a specific type of math puzzle called "Sum-of-Squares" (SOS) decomposition. Think of this as trying to prove that a complicated, messy polynomial equation is always positive (never negative), no matter what numbers you plug into it. The "trick" to proving this is to rearrange the equation so it looks like a sum of perfect squares (like $x^2 + y^2$ ), because squares are always positive. However, finding the right way to rearrange the equation is like trying to solve a Rubik's Cube blindfolded: there are millions of ways to twist the pieces, but only a few lead to a solution. The authors built a special AI agent that learns to use a symbolic math tool (SymPy) to check its work instantly. They trained this agent not just on the final puzzle, but on a massive library of 1.35 million smaller, simpler algebra problems first.

The results show that simply giving an AI a tool isn't enough; the AI needs to be "algebra-grounded," meaning it must deeply understand the math behind the tool before it can use it effectively. When the researchers tested their fully trained agent (which had learned the math and how to use the tool), it successfully solved 78.96% of the complex puzzles. In contrast, a version of the AI that had the same tool but hadn't been trained on the underlying math only solved 44.73% of them. Even more impressive, the fully trained agent was 91.75% accurate across nine different types of algebra tasks. The study suggests that for AI to become a true problem-solver, it needs to learn the "craft" of the trade, not just the "buttons" to push.

The Story of the Math Detective

Imagine you are a detective trying to solve a case where the suspect is a giant, messy algebraic equation. Your job is to prove that this equation is always "good" (positive) and never "bad" (negative). The only way to prove this is to break the equation down into a pile of perfect squares, like stacking up bricks that are all positive. If you can show the equation is just a pile of these bricks, you've solved the case.

But here's the catch: the equation is written in a scrambled, confusing way. To unscramble it, you need a special "Math Magic Wand" (a computer program called SymPy) that can instantly expand, shrink, or rearrange parts of the equation. The problem is, the wand doesn't tell you what to do; it just does whatever you ask. If you ask it to expand the wrong part, you might make the mess worse. You have to decide which part to twist, when to stop, and how to put the pieces back together.

The researchers at Caltech and OpenAI wanted to see if they could teach an AI to be this detective. They didn't just give the AI the wand; they built a training camp. They created 1.35 million practice problems. First, the AI practiced simple tasks like sorting letters, grouping similar items, and factoring numbers. Then, they taught it how to use the wand in a simulated environment, showing it what happens when you ask the wand to do something. Finally, they let the AI try to solve the big "Sum-of-Squares" puzzles using the real wand.

The Big Findings: Training Beats Tools

The experiment compared four different versions of the AI detective:

The Rookie (Base): An AI that had never seen the training camp and didn't have the wand.
The Student (SFT): An AI that had studied the training camp but didn't have the wand during the test.
The Tool-User (Base+Tools): The Rookie who was suddenly handed the wand but hadn't studied.
The Master (Full): The Student who had studied the camp and was given the wand.

The results were a clear victory for the Master. When faced with the complex puzzles:

The Rookie with the wand only solved about 44.73% of them.
The Master (who knew the math and had the wand) solved 78.96% of them.

This proves a crucial point: just handing a powerful tool to a smart AI isn't enough. The AI needs to understand the logic behind the tool. It's like giving a master chef a high-tech oven; if they don't know how to cook, the oven won't help. But if they know the recipes, the oven makes them unstoppable.

The study also checked if this intense math training made the AI worse at other things, like general math problems. It didn't. The Master AI actually got slightly better at general math problems too, scoring 96.29% on a standard test, showing that learning to coordinate tools didn't break its other skills.

What the AI Learned (and Didn't)

The paper is very careful about what it claims. It doesn't say the AI is now a genius that can solve any math problem in the world. The puzzles used were synthetic (made by a computer) and relatively small, involving only one to three variables. The AI didn't "discover" new math; it learned to coordinate existing tools to find a specific type of proof.

However, the study does rule out a common assumption: that you can just slap a tool interface onto a model and expect it to work. The "Tool-User" version (Base+Tools) performed worse than the "Student" version (SFT) who had no tool at all but had studied the math. This suggests that without the deep understanding of the algebra, the tool actually confused the AI, leading it to make bad choices.

The researchers also noted that the AI sometimes failed in three specific ways: it gave up too early, it built a solution that looked right but was structurally wrong, or it built a solution that was structurally right but didn't actually match the original equation. The "exact verifier" in their system caught all these mistakes, ensuring that only perfect solutions were counted.

The Takeaway

This paper offers a blueprint for building smarter AI agents. It suggests that the future of AI in fields like mathematics and science isn't just about bigger models or fancier tools. It's about coordination. By training an AI on the fundamental skills of a domain (like algebra) and then teaching it how to use tools to verify its own work, we can create agents that are much more reliable. The "Master" AI didn't just guess; it planned, executed, checked, and corrected, just like a human expert. While this specific study was limited to a controlled math environment, it lights a path forward for how we might teach AI to tackle harder, real-world problems in the future.

Technical Summary: Learning to Coordinate Symbolic Tools for Verified Sum-of-Squares Certificates

Problem Statement
The paper addresses the challenge of enabling Large Language Models (LLMs) to coordinate exact symbolic operations during multi-step search, rather than merely executing isolated algebraic transformations. While tool-using agents can invoke external computation, they must still decide which operations are useful, construct arguments, interpret observations, recover from unhelpful results, and determine when to stop. The authors focus on weighted Sum-of-Squares (SOS) decomposition as a controlled testbed. An SOS certificate proves the nonnegativity of a polynomial $f$ via an identity $f = \sum c_j p_j^2$ with $c_j \in \mathbb{Q}_{>0}$ . While verifying such an identity is exact and inexpensive (via expansion), finding one is non-unique and strategic; local algebraic correctness does not guarantee a globally valid decomposition, and the search space requires choosing among non-unique regroupings.

Methodology
The authors propose an algebra-grounded post-training pipeline applied to the Phi-4-reasoning-plus backbone. The approach combines domain-specific skill training, executable symbolic tools, and verifier-grounded optimization.

Synthetic Curriculum: The authors constructed a dataset of 1.35 million synthetic examples covering nine tasks:
- Eight supporting tasks: Four "local" operations (lexicographic ordering, collection, expansion, factorization) and four "structural" tasks (Horner form, symmetric reduction, quotient/remainder, extended GCD). These are solved via direct prediction without native tool access during training and evaluation.
- Composite task: Weighted SOS search, which requires sequential coordination of the above capabilities.
- Generation: SOS instances are generated backward by sampling base polynomials and integer weights, expanding them, and scrambling the result. The hidden decomposition is never revealed to the model.
Supervised Fine-Tuning (SFT):
- The model undergoes QLoRA SFT (rank 32, scale 16) on the 1.35 million examples.
- Crucial Design: The SFT corpus contains no native function-call messages. Instead, SOS records include simulated symbolic traces (Python-like snippets and observed results) to teach the algebraic logic and representations. Direct tasks use problem-answer pairs.
Verifier-Grounded Group Relative Policy Optimization (GRPO):
- The second stage optimizes the SFT model using task-specific symbolic rewards.
- Reward Structure: Rewards are based on the exact algebraic state reached (e.g., coefficient identity, structural validity) rather than surface string matching. For SOS, the reward is gated on the parseability of a positive-rational weighted-square structure and an exact coefficient residual.
- This allows the model to learn from multiple valid decomposition paths rather than imitating a single reference trajectory.
Deployment and Evaluation:
- Native Interface: During weighted-SOS evaluation, the "Full" system (SFT + GRPO) and "Base+Tools" (Base + Tools) interact with a native SymPy interface containing four functions: expand_polynomial, collect_terms, reorder_polynomial, and factorize_polynomial.
- Verification: Every final SOS answer is checked by an exact verifier that expands the candidate identity and compares coefficients.
- Controlled Setting: The evaluation uses 90,000 separately generated test instances (10,000 per task). The study compares four configurations: Base, SFT, Base+Tools, and Full.

Key Contributions

An Exactly Verifiable Agent Testbed: The work instantiates symbolic-tool coordination as a weighted-SOS certificate search, supported by a large-scale synthetic curriculum and a strict exact verifier.
An Algebra-Grounded Post-Training Recipe: The pipeline integrates direct algebra training, simulated symbolic traces, verifier-grounded GRPO, and a native tool interface, demonstrating that training on the operations behind a tool complements learning the tool's interface.
Complete-System Evidence: The study provides empirical evidence comparing complete systems (Base, SFT, Base+Tools, Full) on a controlled task, distinguishing between checkpoint-level algebraic skill and system-level tool coordination.

Results

Direct Algebraic Performance: On the eight supporting tasks (evaluated without tools), the Full system achieves a macro-average accuracy of 93.35%, significantly outperforming SFT (78.08%) and the Base model (42.01%).
Weighted-SOS Performance: On the native tool-calling task, the Full system reaches 78.96% verified success. This compares favorably to:
- Base+Tools: 44.73% (same base backbone, same tools, no SFT/GRPO).
- SFT: 51.82% (trained on simulated traces but no native tools at eval).
- Base: 7.63%.
System-Level Performance: Including the SOS task, the Full system achieves a 9-task macro-average of 91.75%.
Retention: The Full system shows no obvious loss in general mathematical performance on AIME-90 (38.89%) and GSM-8K (96.29%) retention checks compared to SFT.
Failure Analysis: Exact verification separates search failures into three classes: premature completion/abstention, structural failure (invalid SOS form), and identity failure (correct form but wrong polynomial).

Significance and Claims
The paper claims that algebraic grounding (training on the operations and representations behind a tool) is a plausible complement to tool access. The significant gap between Base+Tools (44.73%) and Full (78.96%) suggests that learning the underlying algebraic logic enables the agent to better coordinate exact symbolic operations during multi-step search.

The authors position this work as a case study in combining domain-specific skill training, executable tools, and verifier feedback. They explicitly state that the goal is not to achieve state-of-the-art inequality proving or general polynomial nonnegativity classification, but to study sequential exact tool coordination in a controlled environment where outputs are machine-checkable. The results support treating learned algebraic skill, tool interaction, and exact verification as distinct but necessary components of a complete agent.

Limitations
The authors note that the evidence is limited to same-generator synthetic problems with 1–3 variables, a single backbone, and one run per stage. The experimental design compares complete configurations and does not causally isolate the effects of individual components (e.g., SFT vs. GRPO vs. tools) or specific supporting tasks. The study does not cover natural benchmarks, larger polynomials, or cross-backbone transfer.

The Story of the Math Detective

The Big Findings: Training Beats Tools

What the AI Learned (and Didn't)

The Takeaway

Technical Summary: Learning to Coordinate Symbolic Tools for Verified Sum-of-Squares Certificates

More like this