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

Atharva Naik Yash Mathur Prakam Carolyn Rose David Mortensen · 2026

Read ReaComp : Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis by Atharva Naik Yash Mathur Prakam Carolyn Rose David Mortensen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-05485.txt.

Introduction

Atharva Naik, Yash Mathur Prakam, Carolyn Rose, and David Mortensen present ReaComp, a way to turn language model reasoning into reusable solvers. Language models can synthesize programs, but hard cases demand huge searches and repeated model calls. ReaComp instead uses coding agents to compile a few reasoning traces into symbolic synthesizers that need no model at test time.

The compiled solvers reached about ninety-one percent accuracy on a lite benchmark and eighty-five percent on a hard one. Paired with model search, they raised hard-set accuracy while cutting token use sharply. They even transferred to a historical linguistics task, predicting sound changes in real languages.

Catalog record

CREATORAtharva Naik Yash Mathur Prakam Carolyn Rose David Mortensen
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE99 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.05485

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

ReaComp : Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis Atharva Naik Yash Mathur Prakam Carolyn Rose David Mortensen Abstract LLMs can solve program synthesis tasks but remain inefficient and unreliable on hard instances requiring large combinatorial search. Given a small set of reasoning traces, we use coding agents to compile them into reusable symbolic program synthesizers over constrained DSLs. The resulting solvers require no LLM calls at test time and are strong standalone systems: symbolic solver ensembles reach 91.3% accuracy on PBEBench-Lite and 84.7% on PBEBench-Hard, outperforming LLMs with test-time scaling for the latter by +16.3 percentage points at zero LLM inference cost. They also complement LLM search, improving PBEBench-Hard accuracy from 68.4% to 85.8% while reducing reported token usage by 78%, and raising SLR-Bench hard-tier accuracy from 34.4% to 58.0% in a neuro-symbolic hybrid setting. Compared to directly using coding agents as per-instance solvers, induced solvers are substantially more Pareto-efficient, amortizing a small one-time construction cost over many zero-token executions. Finally, most solvers transfer zero-shot to a real historical linguistics task — predicting sound changes in natural language data — reaching 80.1% accuracy under ensembling and recovering some plausible linguistic rules. Together, these results show that reasoning traces can be compiled into reusable symbolic solvers that solve many tasks directly, complement LLM inference on hard cases, and provide a scalable route to domain-general solver induction. We release code and data for reproducibility 1 1 1 https://github.com/cmu-llab/ReaComp Figure 1 : ReaComp : offline solver induction compiles LLM reasoning traces into a reusable symbolic solver; test-time inference applies the solver directly (zero LLM cost) and falls back to LLM search only for unresolved cases. 1 Introduction The Programming by Example (PBE) paradigm ( Gulwani 2011 ) provides a controlled setting for studying structured reasoning and compositional generalization, with applications spanning code transformation, data wrangling, text processing, and historical linguistics. Recent work shows that large language models (LLMs), when combined with scaling strategies such as Best-of- K sampling and iterative refinement, can achieve strong performance on PBE tasks ( Li and Ellis 2024 ; Naik et al. 2025b ) . In particular, prior work like PBEBench ( Naik et al. 2025b ) demonstrates that sufficiently powerful reasoning models, together with these scaling strategies, can achieve high accuracy on PBE tasks without explicit symbolic structure. However, this performance comes at a substantial computational cost. Through analysis of reasoning traces and scaling behavior, we find that harder instances require disproportionately more attempts and token usage (Figure 3 ), often due to failures of compositional generalization and inefficient search. Even strong reasoning models such as gpt-oss-120b exhibit unstable behaviors, including looping within a single attempt and redundant exploration across attempts in iterative refinement settings. Moreover, we observe that LLM-based search performs well on short, simple programs but degrades significantly on longer, compositional transformations. These patterns suggest that, despite their capability, LLMs lack an explicit mechanism for structuring search over candidate programs, leading to wasted computation on difficult tasks, especially as solution length increases. A natural approach is to augment LLMs with tools or learned libraries, including approaches that induce reusable abstractions from experience ( Wang et al. 2024b ; Stengel-Eskin et al. 2024 ; Yue et al. 2025 ) . While these methods demonstrate that LLMs can acquire useful structure, they typically rely on iterative reasoning and tool invocation at inference time, and thus remain sensitive to compute budgets. Compute-matched evaluations show that their gains are largely driven by increased inference-time compute rather than effective reuse of learned tools, with limited evidence of consistent tool reuse across instances ( Sesterhenn et al. 2025 ) . As a result, they continue to perform a largely unstructured search over the solution space. In this work, we propose ReaComp : instead of improving inference-time reasoning, we compile it into a reusable symbolic structure. Our approach consists of two stages: offline solver induction and test-time inference . In the offline phase, we induce symbolic solvers directly from LLM reasoning traces by using coding agents to distill recurring strategies and failure modes into standalone program synthesizers over a constrained DSL. These solvers require no LLM calls at test time and can solve a large fraction of tasks directly, often matching or exceeding LLM search on harder instances. At test time, the solver provides a cheap, structured first pass, and the LLM is invoked only as a fallback on unresolved cases ( Zhang and Park 2025 ) . We evaluate ReaComp on recent, challenging benchmarks — PBEBench ( Naik et al. 2025b ) and SLR-Bench ( Helff et al. 2025 ) — and show that induced symbolic solvers achieve strong standalone performance while significantly improving inference efficiency. Symbolic solver ensembles reach 91.3% accuracy on PBEBench-Lite and 84.7% on PBEBench-Hard, outperforming a test-time scaling LLM baseline on Hard by +16.3 percentage points (pp) at zero LLM inference cost. On SLR-Bench, symbolic solvers match frontier LLMs on the hardest tier and, when combined with direct feedback, improve hard-tier accuracy from 34.4% to 58.0%. Hybrid inference reduces token usage by up to 78%. By amortizing a small one-time construction cost over many zero-token executions, induced solvers Pareto-dominate approaches that directly apply the same coding agent to each task individually. Finally, most solvers transfer zero-shot to forward reconstruction in historical linguistics — predicting how sounds change across related languages — reaching 80.1% accuracy under ensembling and recovering plausible sound change rules. Contributions. We propose ReaComp , contributing: (1) a method for inducing reusable symbolic solvers from LLM reasoning traces via coding agents; (2) evidence that induced solvers are strong standalone systems, outperforming LLM test-time scaling on hard instances at zero per-task LLM inference cost; (3) a hybrid neuro-symbolic pipeline that Pareto-dominates per-task agentic effort, reducing token usage by up to 78% while achieving state-of-the-art results; (4) a demonstration that most induced solvers generalize zero-shot across distributions, with a case study on forward reconstruction in historical linguistics. 2 Method Problem formulation. Let \mathcal{X} and \mathcal{Y} denote input and output spaces. A PBE task is a finite set of examples \mathcal{D}=\{(x_{i},y_{i})\}_{i=1}^{n} . The goal is to infer a program p\in\mathcal{P} (from a DSL \mathcal{P} ) such that p(x_{i})=y_{i} for all examples. We use a task-level reward R(p;\mathcal{D})\in[0,1] , with R=1 indicating a fully correct solution. We propose ReaComp , a two-stage approach that (1) compiles LLM reasoning traces into symbolic solvers and (2) uses these solvers in a hybrid inference pipeline with LLM-based search. 2.1 LLM Search Procedures An LLM defines a conditional distribution p\sim\pi_{\theta}(\cdot\mid\mathcal{D}) . We consider two standard test-time scaling strategies, both selecting p^{*}=\arg\max_{p\in\mathcal{C}}R(p;\mathcal{D}) : Best-of- K (BoK). Sample K programs independently and select the highest-scoring candidate: \mathcal{C}=\{p_{k}\}_{k=1}^{K} . Direct Feedback (DF). Generate a trajectory \{p^{(t)}\}_{t=1}^{T} via iterative refinement conditioned on verifier feedback: \mathcal{C}=\{p^{(t)}\}_{t=1}^{T} . Early stopping is applied for both when R=1 . Both define candidate sets \mathcal{C} used in our hybrid inference. 2.2 Offline Solver Induction Solver induction is a one-time offline procedure that compiles reasoning traces into a standalone symbolic program synthesizer. Given training tasks \{\mathcal{D}_{j}\}_{j=1}^{m} and corresponding traces \{\tau_{j}\}_{j=1}^{m} , we induce a solver S_{\phi}:\mathcal{D}\mapsto\mathcal{P} by approximately maximizing \sum_{j}R(S_{\phi}(\mathcal{D}_{j});\mathcal{D}_{j}) via a coding agent that distills reusable structure and failure modes from traces. Trace dataset. We construct a dataset

Read the complete text