💬 NLP

ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis

The paper introduces ReaComp, a framework that compiles LLM reasoning traces into reusable, zero-token symbolic solvers which achieve state-of-the-art accuracy on program synthesis benchmarks, significantly reduce token usage when combined with LLMs, and successfully transfer to real-world linguistic tasks.

Original authors: Atharva Naik, Yash Mathur, Prakam, Carolyn Rose, David Mortensen

Published 2026-05-08

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Atharva Naik, Yash Mathur, Prakam, Carolyn Rose, David Mortensen

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

The Big Problem: The "Over-Thinker"

Imagine you have a very smart, creative assistant (an AI) who is great at solving puzzles. However, when the puzzle gets really hard or long, this assistant starts to panic. They try to solve it by guessing, checking, guessing again, and writing out huge, messy notes. They eventually get the right answer, but they use up a massive amount of paper (computing power) and time to do it. Sometimes, they get stuck in a loop, repeating the same mistakes over and over.

The researchers found that while these AI assistants are powerful, they are inefficient and expensive when faced with complex, multi-step logic problems (like rewriting strings of text or finding rules in data).

The Solution: The "Recipe Book" (REACOMP)

Instead of asking the smart assistant to solve every single new puzzle from scratch, the researchers came up with a new method called REACOMP.

Think of it like this:

The Observation Phase: First, they watch the smart assistant solve a small set of practice puzzles. They watch how the assistant thinks, where it gets stuck, and what strategies it uses to succeed.
The Compilation Phase: They hire a "coding agent" (a specialized AI programmer) to watch those practice sessions. This programmer doesn't just copy the answers; they write a permanent rulebook (a symbolic solver) based on the patterns they saw. This rulebook is a set of strict, logical instructions that can solve that type of puzzle instantly.
The Execution Phase: Now, when a new puzzle comes in, they don't ask the smart assistant to think. They just hand the puzzle to the Rulebook. The Rulebook solves it instantly, using zero "thinking" power from the smart assistant.

If the Rulebook gets stuck on a really weird puzzle, then (and only then) do they call the smart assistant for help.

The Results: Speed, Savings, and Smarts

The paper tested this on two types of difficult logic puzzles (called PBEBench and SLR-Bench). Here is what happened:

The "Zero-Cost" Win: The Rulebooks (symbolic solvers) were so good that they solved the hardest puzzles 84.7% to 91.3% of the time without asking the smart assistant for help at all. This means the cost to solve these problems dropped to zero for the AI's "brain" usage.
Beating the Giants: On the hardest puzzles, the Rulebooks actually performed better than the smart assistant trying its hardest (even when the assistant was allowed to try many times). The Rulebooks were 16% more accurate than the best "guess-and-check" methods used by the AI alone.
The Hybrid Superpower: When they combined the Rulebook with the smart assistant (using the Rulebook first, and the assistant only as a backup), they got the best of both worlds. They achieved the highest accuracy ever recorded on these tests while using 78% less computing power (tokens) than the AI alone.
Real-World Test: They even tried this on a real-world language puzzle about how sounds change in ancient languages. The Rulebooks, which were never taught about this specific topic, solved it with 80% accuracy just by using the logic they learned from the practice puzzles.

The Key Takeaway

The paper argues that we shouldn't just keep asking AI to "think harder" on every new problem. Instead, we should let the AI learn how to learn once, turn that learning into a permanent, reusable tool (a solver), and then use that tool for everything.

It's the difference between hiring a genius to solve a math problem from scratch every time (expensive and slow) versus hiring a genius once to write a calculator app, and then using that app forever (cheap, fast, and reliable).

Summary of Claims

Efficiency: You can turn AI reasoning traces into reusable tools that solve problems without needing the AI again.
Performance: These tools are often better than the AI itself on hard, long tasks.
Cost: This method drastically reduces the money and energy needed to run AI systems.
Generalization: These tools can be applied to new, real-world tasks (like linguistics) without needing to be retrained.

Technical Summary: REACOMP

Problem Statement

Large Language Models (LLMs) have demonstrated capability in program synthesis tasks, particularly within the Programming by Example (PBE) paradigm. However, they suffer from significant inefficiencies and unreliability on hard instances requiring large combinatorial searches. Analysis reveals that harder instances trigger disproportionately high token usage and multiple attempts due to failures in compositional generalization and inefficient search strategies (e.g., looping, redundant exploration). While existing approaches attempt to augment LLMs with learned libraries or tools, these methods often rely on iterative reasoning and tool invocation at inference time, remaining sensitive to compute budgets and failing to consistently reuse learned structures across instances. Consequently, LLMs continue to perform largely unstructured searches over the solution space, leading to wasted computation as solution length increases.

Methodology: REACOMP

The authors propose REACOMP, a framework that compiles LLM reasoning traces into reusable symbolic solvers rather than improving inference-time reasoning directly. The approach consists of two distinct stages:

1. Offline Solver Induction

This is a one-time procedure where a coding agent distills recurring strategies and failure modes from LLM reasoning traces into a standalone symbolic program synthesizer operating over a constrained Domain-Specific Language (DSL).

Trace Dataset: A dataset of reasoning traces is constructed from an LLM (e.g., gpt-oss-120b) solving a small subset of benchmark tasks. These traces include intermediate steps, candidate programs, and outcomes, balanced across difficulty and success/failure.
Coding Agent Induction: A coding agent (e.g., Claude Code or Qwen + OpenHands) operates within a sandboxed environment containing the trace dataset and a read-only verifier. The agent iteratively edits a workspace to construct a solver implementation (e.g., SOLVER.py).
Process: The agent proposes code edits, executes them, and refines the solver based on performance over the trace dataset. The agent observes only the input-output examples available at test time, ensuring the induced solver is a standalone system requiring no LLM calls during inference.
Output: A standalone Python solver and an algorithm description file.

2. Efficient Hybrid Inference

At test time, the system employs a two-pass strategy to balance efficiency and accuracy:

Symbolic First Pass: The induced symbolic solver ( $S_\phi$ ) proposes a set of candidates for a given task $D$ . If a candidate achieves a perfect reward ( $R=1$ ), it is returned immediately at zero LLM inference cost.
LLM Fallback: If the symbolic solver fails to find a perfect solution, the system falls back to standard LLM search procedures (Best-of-K sampling or Direct Feedback iterative refinement) to resolve the remaining "hard" cases.

This structure amortizes the small one-time construction cost of the solver over many zero-token executions, reserving expensive LLM inference only for residual cases.

Key Contributions

Method for Induction: A novel method for inducing reusable symbolic solvers from LLM reasoning traces using coding agents, transforming unstructured search traces into structured, standalone synthesizers.
Strong Standalone Performance: Evidence that induced solvers function as powerful standalone systems, outperforming LLM test-time scaling on hard instances (e.g., PBEBench-Hard) with zero per-task LLM inference cost.
Pareto-Dominant Hybrid Pipeline: A neuro-symbolic hybrid pipeline that significantly reduces token usage (up to 78%) while achieving state-of-the-art results, effectively dominating approaches that apply coding agents directly to each task.
Zero-Shot Generalization: Demonstration that most induced solvers generalize zero-shot to real-world distributions, specifically in a historical linguistics case study involving forward reconstruction of sound changes.

Experimental Results

The authors evaluated REACOMP on PBEBench (string transformation) and SLR-Bench (inductive logic programming).

PBEBench-Lite: Symbolic solver ensembles achieved 91.3% accuracy, matching or exceeding LLM baselines. Hybrid inference (Symbolic + LLM fallback) reduced token usage by 36% while maintaining peak accuracy (93.9%).
PBEBench-Hard: On long-horizon cascade synthesis, LLM test-time scaling (Best-of-K) achieved 68.4% accuracy. Induced symbolic solvers significantly outperformed this, with the "All Symbolic" ensemble reaching 84.7% accuracy (a +16.3 percentage point gain) at zero LLM inference cost. Hybrid inference further improved this to 85.8% while reducing token usage by 78% compared to LLM-only baselines.
SLR-Bench: On the hardest tier, the CC symbolic solver achieved 46.8% accuracy, matching frontier models (o3, GPT-5) at zero inference cost. The hybrid approach (DF + CC) lifted hard-tier accuracy to 58.0%, surpassing all prior reported baselines. The best hybrid (DF + CC + QO) reached 86.7% overall accuracy at a fraction of the cost of frontier models.
Efficiency: Symbolic solvers are highly efficient, completing inference for 1,000+ tasks in under 5 minutes (pure Python), compared to ~2 days for LLM-based methods.
Real-World Transfer: In a forward reconstruction task for historical linguistics (predicting sound changes), induced solvers achieved 80.1% accuracy under ensembling, recovering plausible linguistic rules without retraining.

Significance and Claims

The paper claims that REACOMP demonstrates a scalable route to domain-general solver induction. By compiling reasoning traces into reusable symbolic structures, the approach addresses the fundamental mismatch between independent LLM sampling and long-horizon compositional tasks. The authors argue that:

Efficiency under Saturation: In regimes where LLM accuracy is near saturation, solver induction provides primary benefits in efficiency rather than accuracy.
Complementarity on Hard Tasks: On difficult, long-horizon tasks, symbolic solvers excel where LLMs fail (due to structured search), while LLMs cover the remaining tasks, creating a complementary hybrid system.
Amortization: The approach amortizes a small one-time construction cost over many zero-token executions, making it substantially more Pareto-efficient than applying coding agents per-instance.
Generalization: The ability of solvers to transfer zero-shot to unseen distributions (e.g., real linguistic data) suggests that the induced algorithms capture generalizable structural insights rather than mere memorization.

The authors note limitations, including the sensitivity of solver quality to the coding agent's capability and the specific nature of the DSLs used. They also observe that while solvers recover plausible rules, they sometimes favor verifier-satisfying solutions over compact, generalizable structures, indicating a need for future work on reward function alignment and solver induction search strategies.