acceptodds
Under review as a conference paper at ICLR 2027

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

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 without ground truth labels, 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, in domains with exact verification, reasoning traces can be compiled into reusable symbolic solvers that solve many tasks directly and complement LLM inference on hard cases. We release code and data for reproducibility.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Program Synthesis, Coding Agents, Test Time Scaling, LLM Reasoning, Inductive Reasoning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_ASVLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ReaComp, which uses coding agents to turn a small collection of LLM reasoning traces into reusable symbolic program synthesizers for constrained DSLs. The induced solvers run without LLM calls at test time; unresolved instances are passed to Best-of-K or direct-feedback LLM search. Experiments cover PBEBench string-rewrite synthesis, SLR-Bench Prolog-rule induction, a List Functions pilot, and a historical-linguistics case study. The solver ensemble achieves 84.7% on PBEBench-Hard, while the independent-fallback hybrid reaches 85.8% versus 68.4% for LLM search with 78% fewer fallback tokens. The paper also analyzes solver diversity, induction costs, and seeded fallback.

Critical strengths
  • Reasonable design. Reusable symbolic solvers with LLM fallback provide a practical way to reduce repeated inference costs.

  • Extensive evaluation. The paper presents substantial experiments and detailed appendix analyses of solver performance, construction costs, and hybrid search.

Critical weaknesses
  • Limited novelty. Related work has already explored converting LLM outputs into executable search mechanisms: EoH (ICML 24) translates natural-language heuristic ideas into code and evolves them through execution-based evaluation, while HySynth (NeurIPS 24) learns a task-specific surrogate from LLM completions to guide symbolic program synthesis. ReaComp’s distinguishing claim is to construct reusable solvers across tasks from reasoning traces, but the experiments do not sufficiently establish what this adds beyond ordinary LLM-assisted solver construction. The authors should clarify the methodological distinction from these approaches and add a comparison using the same coding agent, verifier access, and construction budget to build solvers directly from the DSL specification and input-output examples.
  • Unclear motivation. For a new problem, it is unclear how to determine whether an existing solver is applicable or a new solver must be constructed. Does each new task family require collecting LLM reasoning traces for approximately 100 tasks again? If so, are these trace collection and solver reconstruction costs included in the efficiency analysis?
  • Unclear task separation. Section 2.2 samples solver-induction examples from the benchmark tasks, but the evaluation does not clearly identify a disjoint task subset or quantify overlap. The authors should disclose the induction and evaluation task IDs and report performance with induction tasks excluded.
  • Unclear presentation. The introductory figure presents ReaComp’s workflow without comparing it with prior approaches, making the methodological distinction difficult to understand. A side-by-side comparison would clarify the contribution.
  • Limited case analysis. Although a linguistic case study is provided, the paper lacks a clear worked example showing how specific reasoning traces inform the induced search algorithm and how that solver handles a new task. Such an example would make the proposed mechanism easier to assess.
Questions for authors
  1. What methodological advance does reasoning-trace-based solver induction provide over EoH (ICML 24), HySynth (NeurIPS 24), and direct coding-agent-based solver construction? Please support the distinction with a budget-matched comparison and a worked example linking reasoning traces to the induced algorithm.
  2. How can users determine whether an existing solver applies to a new task family? When reconstruction is required, what are the full costs—including trace generation, selection, and solver construction—and how many subsequent tasks are needed to recover this investment?
  3. Are the solver-induction and evaluation tasks disjoint? Please disclose their task IDs, quantify any overlap, and report performance with induction tasks excluded.
2 comments
AuthorsOpenReview ↗

Response to Reviewer ASVL

Thank you for the review. Several of your points were also raised by other reviewers, so the full tables for those are in the general response (G2, G3) and in our response to U92J.

W1, Q1: Relation to EoH and HySynth

The authors should clarify the methodological distinction from these approaches and add a comparison using the same coding agent, verifier access, and construction budget to build solvers directly from the DSL specification and input-output examples.

EoH evolves heuristic functions for combinatorial optimization inside a hand-designed algorithm, with many LLM calls per generation. HySynth samples LLM programs for each task, fits a per-task grammar, and uses it to guide a hand-written synthesizer, so it calls the LLM on every task. ReaComp writes the whole synthesizer once per task family from unlabeled traces, and then solves new tasks without LLM calls. On HySynth's SyGuS string benchmark (U92J, W1), we also guided HySynth with gpt-oss-120b, the LLM ReaComp uses for getting reasoning traces:

SyGuS string benchmark, 70 tasksLLM samples per taskSolved
HySynth, guided by GPT-4o10049
HySynth, guided by gpt-oss-120b10053
gpt-oss-120b, direct sampling10059
ReaComp solvers only057
ReaComp solvers, then gpt-oss-120b on the 13 unsolved tasks100 on those 13 (19 on average)64

Please see the matched ablation in G2 (PBEBench-Lite and Hard). The direct-construction baseline with the same agent and budget is condition (i), and condition (ii) builds from the I/O examples.

W2, Q2: When an existing solver applies, and full costs

How can users determine whether an existing solver applies to a new task family? When reconstruction is required, what are the full costs—including trace generation, selection, and solver construction—and how many subsequent tasks are needed to recover this investment?

A solver is tied to a DSL and verifier, so a new task family needs new traces and a new build. Applicability can be checked without labels from the solver's pass rate on the new tasks. Real-FR is an example where a PBEBench solver transfers without rebuilding. The full cost of a new family is small: traces for about 100 unsolved tasks ($0.10 here) plus one build ($1 to $15). Selecting the traces is a seeded random draw balanced over successful and failed attempts, with no LLM calls or labels, so it adds no cost. On PBEBench-Hard, against BoK, a solver pays for itself after about 20 tasks for the QO build ($0.95), about 45 for the CC build ($2.10), and about 320 for a $15 build (U92J, W4).

W3, Q3: Induction tasks and IDs

Are the solver-induction and evaluation tasks disjoint? Please disclose their task IDs, quantify any overlap, and report performance with induction tasks excluded.

They are not disjoint on PBEBench-Hard and SLR-Bench. Please see G3, which gives the overlap (91 PBEBench-Hard and 87 SLR-Bench test tasks, none from PBEBench-Lite) and the results with the induction tasks removed: every system drops by at most 1.6 points. We will release the task indices.

W4: Figure comparing with prior approaches

A side-by-side comparison would clarify the contribution.

We agree. We will add a side-by-side figure contrasting per-task LLM search, library learning, LLM-guided symbolic synthesis, and ReaComp.

W5: Worked example

Although a linguistic case study is provided, the paper lacks a clear worked example showing how specific reasoning traces inform the induced search algorithm and how that solver handles a new task.

Please see U92J, W2: a heuristic the agent derived from one trace, the code it wrote, a test task it solves, and the accuracy without it (Lite 66.2 → 46.3, Hard 75.0 → 65.0, both versions evaluated under the same conditions). We will add this to the appendix.

Dear Reviewer ASVL,

We thank you for your constructive review! This is a gentle reminder to respond to the rebuttal and share any additional concerns.

Best,
ReaComp Authors

Reviewer_Qb9LOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes ReaComp, a two-stage pipeline for program synthesis. In the first stage, reasoning traces from an LLM are used without ground-truth programs to induce a standalone symbolic solver via a coding agent. In the second stage, the solver runs at test time with zero LLM cost, and an LLM-based search method is used only as a fallback for unresolved tasks. The method is evaluated on string-rewriting PBE tasks (PBEBench), inductive logic programming (SLR-Bench), and a historical linguistics transfer task. The main claims are that induced solvers are competitive standalone systems, that hybrid inference improves accuracy while reducing token usage, and that the approach transfers to a real-world task without retraining.

Critical strengths
  1. The task setting is appropriate and the verification is reliable. Program synthesis on constrained DSLs with exact execution rewards means every reported number has a clear correctness standard, avoiding the ambiguity common in many LLM reasoning benchmarks.

  2. The label-free induction idea is a real contribution. The authors show that a small set of reasoning traces, including failed attempts, can be distilled into a solver without accessing ground-truth programs. The one-time construction cost is small and amortizes naturally, which makes the approach practically appealing.

  3. The empirical evaluation is broad and unusually cost-transparent. The comparison against BoK, DF, a direct coding-agent baseline, and a compute-matched library-learning baseline is useful, and the separate reporting of inference cost and construction cost makes the efficiency claims difficult to game.

Critical weaknesses
  1. The largest risk is that induction traces and evaluation tasks may share distribution or instances, since the paper only says induction uses a small subset of benchmark tasks without confirming disjointness.

  2. "All Symbolic" and "CC+QO" are oracle-like unions of multiple stochastic induction runs, yet are used as headline results without a practical selection rule. Run-to-run variance is high, so single-run comparisons, especially on SLR-Bench, are unreliable. The hybrid is a cascade, not a neuro-symbolic integration; the seeded variant is consistently better but is not the default, weakening the complementarity claim.

  3. The transfer result is mostly an ensemble effect: individual solvers range from 4% to 70% on the linguistics task, so robustness is not a property of the method but of a after-the-fact union.

Questions for authors
  1. Are the induction tasks fully disjoint from the evaluation set? What would the headline numbers be on a held-out subset never seen by the trace LLM or the coding agent?
  2. How is All Symbolic computed, what is its total per-task wall-clock cost, and is it intended as a deployed system or an upper-bound analysis?
  3. With identical inputs producing 53-79% Lite accuracy, can the authors report median and range over at least five induction runs for the key comparisons, rather than single best runs?
  4. How should a practitioner select or weight solvers at deployment time without held-out ground truth?
  5. Why is the seeded fallback not the default method?
2 comments
AuthorsOpenReview ↗

Response to Reviewer Qb9L

Thank you for the careful questions. We answer them in order below. For Q1 and Q3 the tables are in the general response (G3 and G4).

Q1: Induction and test tasks

Are the induction tasks fully disjoint from the evaluation set? What would the headline numbers be on a held-out subset never seen by the trace LLM or the coding agent?

They are not disjoint on PBEBench-Hard and SLR-Bench. For PBE solvers, we used 91 PBEBench-Hard tasks, and for SLR we used 87 SLR-Bench test tasks. No PBEBench-Lite task was used. The coding agent never sees ground-truth programs for any instances. In G3, we report the results with the induction tasks removed from the test sets. Every system drops by at most 1.6 points, including the LLM baselines. This drop is because the used tasks were on average easier rather than a generalization issue.

Q2: How All Symbolic is computed and what it costs

How is All Symbolic computed, what is its total per-task wall-clock cost, and is it intended as a deployed system or an upper-bound analysis?

We intended it to be a deployable condition, not an upper-bound analysis. All Symbolic runs the 7 induced PBEBench solvers on each task and keeps the highest-scoring candidate on that task's own examples, breaking ties by program length. It uses no ground truth or held-out data, so it is not an oracle. The same verifier feedback is also used for the LLM scaling baselines like BoK and DF and the coding agent direct solving so the solvers don't have an unfair advantage. We also extend to a condition with held-out input-output pairs per instance not accessible to the verifier in our response to reviewer U92J's "W5, Q7: What a perfect verifier score certifies".

For wall clock time, on PBEBench-Hard it takes 11.3 CPU-hours for 1,216 tasks run sequentially (33.5 s per task), or about 4.4 hours with the solvers in parallel, versus about two days for BoK at 8 workers. At $0.05 per vCPU-hour, this CPU time costs about $0.57 in total (under $0.001 per task), compared with $57.83 of LLM cost for BoK.

Q3: Median and range over repeated builds

With identical inputs producing 53-79% Lite accuracy, can the authors report median and range over at least five induction runs for the key comparisons, rather than single best runs?

Please see G4. We now report the range and median over 5 independent builds for both the Claude Code and the QO solver.

Q4: Choosing solvers without ground truth

How should a practitioner select or weight solvers at deployment time without held-out ground truth?

Selection doesn’t need ground truth. On each task, All Symbolic runs every solver and keeps the program that scores highest on that task's own I/O examples (the verifier each task comes with), breaking ties by program length, i.e., the simplest program consistent with the examples (Q2). Nothing held out is used, so the same rule applies at deployment. To check that this choice generalizes, we scored the selected programs on 100 unseen inputs per PBEBench-Hard task (our response to U92J, W5): All Symbolic's choice reaches 51.2% held-out accuracy, on par with BoK's best sample picked by an oracle that sees the held-out strings (50.9%).

To lower the cost of running many solvers, they can also be ordered by their pass rate on unlabeled tasks, stopping at the first accepted program. The top three solvers on PBEBench-Hard reach 83.4% at 1.3 CPU-hours, close to all seven (84.7% at 3.9 CPU-hours), and early exit alone cuts the cost of running all seven from 11.3 to 3.9 CPU-hours. Moreover, solvers can be run in parallel if more CPUs are available to trade off computational cost for lower wall clock time.

Q5, W2: Seeded fallback as the default; cascade vs. integration

The hybrid is a cascade, not a neuro-symbolic integration; the seeded variant is consistently better but is not the default, weakening the complementarity claim.

We agree that the seeded variant is the better default and that the independent fallback is a cascade. We have now run the seeded fallback on PBEBench-Hard. DF alone solves 86.9% (LLM cost $22.73), DF + CC 88.6%, and Seeded DF + CC 93.5% at under half of DF's LLM cost ($10.76, plus $2.10 to build the solver). With the same solver, seeding adds 4.9 points over the independent fallback (Seeded DF + All Symbolic: 93.3; Seeded DF + QO: 91.8 at $13.06 + $0.95). We will present solver-seeded fallback as the main hybrid in the revision.

W3: Transfer as an ensemble effect

The transfer result is mostly an ensemble effect: individual solvers range from 4% to 70% on the linguistics task, so robustness is not a property of the method but of a after-the-fact union.

The two primary solvers transfer on their own (CC 70.2%, QO 70.5% on Real-FR). One build (4.1%) uses a strategy that fails on IPA data, and the union reaches 80.1%. We will report the per-solver median next to the union.

Dear Reviewer Qb9L,

We thank you for your constructive review! This is a gentle reminder to respond to the rebuttal and share any additional concerns.

Best, ReaComp Authors

Reviewer_U92JOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ReaComp, a framework for constructing reusable symbolic program synthesis solvers with coding agents. The authors collect LLM reasoning traces from a small set of programming-by-example tasks. A coding agent is then given these traces, the domain-specific language (DSL), and a verifier. It writes and tests a standalone Python solver. At inference time, this solver searches for a program that fits the task examples. An LLM is called only when the solver does not find a fully consistent answer.

The experiments cover PBEBench string-replacement tasks and SLR-Bench Prolog rule induction, with additional studies on list functions and historical linguistics. The reported accuracy and token savings are impressive in some settings, particularly on PBEBench-Hard. However, I am not yet convinced that the experiments establish a substantial methodological advance over conventional symbolic synthesis, or isolate the benefit of reasoning traces in constructing the solvers.

Critical strengths
  1. The motivation is practical. Repeated LLM sampling can be wasteful for tasks with a well-defined search space and an executable verifier. Amortising solver construction over many tasks is a sensible direction.

  2. The empirical results are interesting. In particular, the symbolic solver ensemble performs well on PBEBench-Hard, and the hybrid systems reduce LLM calls while maintaining or improving accuracy. The paper also reports solver construction costs and inference-time performance.

  3. I appreciate the relatively detailed analysis of the generated algorithms in Appendix F.2, including their different search strategies and considerable variation between independent construction runs. This is useful for understanding what the coding agents actually produced.

Critical weaknesses

1. The key advantage over conventional symbolic program synthesis has not been established

This is my main concern. The produced solvers use fairly standard synthesis and search techniques. Appendix F.2 describes input-output difference extraction, greedy and beam search, safety constraints, lookahead, permutation reordering, and complexity-ordered rule enumeration. These methods are not new, and can be implemented without LLM reasoning traces.

The experiments mainly compare these symbolic solvers with repeated LLM inference, per-task coding agents, and TroVE. But the most relevant question is whether the LLM-generated solvers are any better than a conventional symbolic synthesiser on the same DSL. A strong performance gap against LLM sampling does not answer this. It could simply show that symbolic search is better suited to a restricted, verifiable problem.

I suggest adding carefully implemented non-LLM symbolic baselines. For PBEBench these could include difference-based candidate generation with greedy or beam search, with and without bounded lookahead. For SLR-Bench, complexity-bounded ILP search with appropriate candidate pruning would be a useful baseline. They should use the same DSL, verifier, execution time and search budgets. The comparison should examine accuracy, number of candidates evaluated and wall-clock time. If the main benefit is reduced solver development effort, that should be stated and evaluated separately.

2. The contribution of LLM reasoning traces is not sufficiently isolated

The coding agent already understands programming and common search algorithms. It receives the full DSL and verifier, and can repeatedly execute and debug its solver. It is therefore unclear how much of the final solver comes from the traces, rather than from the coding agent's prior knowledge and verifier-guided trial and error.

The no-CoT ablation is helpful, but does not answer this question. It compares full traces against a setting with final programs. There is no clean comparison against an agent given only the task specification, DSL and verifier. Also, solver construction has large run-to-run variance. In Table 13, three independent runs with the same 100-example CoT setting obtain 51.8% to 74.7% accuracy on PBEBench-Hard. This makes single-run ablations hard to interpret.

I suggest comparing, under matched construction budgets: (i) DSL and verifier only, (ii) DSL, verifier and task input-output examples, (iii) the same with final programs, and (iv) full reasoning traces. Several independent runs are needed for each condition. More importantly, the authors should give one concrete, trace-grounded example: which observation in the traces led to which pruning or ranking heuristic? What happens when that heuristic is removed from an otherwise unchanged solver? Without such evidence, the claim of compiling reasoning remains rather difficult to distinguish from coding-agent-based algorithm engineering.

3. The benchmark DSLs are narrow, and broader claims about program synthesis need qualification

PBEBench uses ordered cascades of short replace(A, B) operations. Long cascades create a large combinatorial search space, but the underlying operation semantics are simple. They do not require control flow, recursion, rich data structures, types, or general program state. Thus PBEBench-Hard is hard largely in search depth and ordering, not in the expressiveness of the programming language.

SLR-Bench introduces logical rules, but still restricts the target predicate and available background predicates. The generated solvers perform largely template-based rule generation, enumeration and pruning. The additional historical linguistics study uses the same broad string-replacement formulation, while the list-functions pilot also relies on a fixed set of primitives and exact checking.

These are valid benchmarks for constrained synthesis. Yet I am not convinced they support wider implications about reusable reasoning solvers for program synthesis in general, let alone complex software development. This limitation is more than a minor future-work issue: the strong performance of the method may depend precisely on the hand-specified DSL and cheap verifier.

A more convincing test would use a substantially richer DSL, perhaps with conditionals, more complex data structures or recursive constructions, and compare against an established symbolic synthesiser in that setting. Otherwise, the paper should explicitly limit its claims to fixed-DSL, verifier-backed tasks. A long sequence of simple replacements should not be treated as evidence of general program synthesis ability.

4. Efficiency should be evaluated as cost per successful task, not mainly token reduction

The paper gives useful token and reference-dollar estimates, but token savings alone are not the right measure of practical value. A solver may consume zero LLM tokens at inference time while still requiring construction, CPU search and verification. The key metric is the total cost of completing a task correctly, preferably reported at matched accuracy.

For a workload of N tasks, a relevant quantity is

=\frac{C_{\mathrm{construction}}+C_{\mathrm{solver\ execution}}+C_{\mathrm{LLM\ fallback}}}{N_{\mathrm{solved}}}.$$ This should be reported at several workload sizes, because the construction cost is amortised. A fair comparison also needs a cost-accuracy frontier, not just a fixed Best-of-32 baseline. The evaluation uses gpt-oss-120b for LLM search; it does not establish whether the advantage persists against a competitive, inexpensive current model (for example, an appropriate DeepSeek Flash model) with tuned sampling and early stopping. I am not assuming such a model will win, but it is a relevant alternative if cost is a central claim. I suggest reporting total end-to-end cost per successfully solved task, with symbolic execution and verifier costs included, and comparing at similar solve rates. Model prices change quickly, so the analysis should also include a price-sensitivity or break-even study. This would make the economic argument substantially stronger. ### 5. Correctness on observed examples is not the same as recovering a general rule The paper largely treats verifier reward 1.0 as a solved task. For PBE this can mean that the proposed program matches all supplied input-output pairs, not necessarily that it recovers the intended program or generalises to new inputs. This distinction matters especially for the historical linguistics case study. The paper's own compression analysis shows a considerable drop when shorter rule sequences are required. The authors also acknowledge that long cascades may patch individual examples rather than discover plausible sound laws. I suggest separating example consistency from out-of-sample correctness wherever held-out pairs are available. Program complexity and, for linguistic tasks, domain validity should also be assessed. This would help determine whether the solvers discover reusable structure or mainly exploit flexibility in the DSL to fit the provided examples.
Questions for authors
  1. What is the unique practical advantage of the generated solver? Is it better search quality, reduced development cost, easier adaptation to a new DSL, or something else? The paper should identify its primary claim and compare directly against the corresponding conventional alternative.

  2. Which heuristic is genuinely derived from a reasoning trace? Can the authors show a specific trace pattern, the resulting change in solver logic, and a controlled ablation of that change? For instance, how much do the safety constraint or two-step lookahead contribute, keeping the rest of the solver fixed?

  3. Would the coding agent produce a comparable solver without any traces? Please compare DSL-plus-verifier-only construction with examples-only, final-program, and full-trace settings. Match the agent and construction budget, and report variability across runs.

  4. How does ReaComp compare with established symbolic synthesis methods? In particular, can the authors provide strong baselines using the same DSL, verifier and runtime budget, rather than relying primarily on LLM search baselines?

  5. What is the actual price of a correct solution? Please report total cost per solved task and cost-accuracy curves, with construction and execution included, and examine cheaper LLM inference alternatives. At what workload size does ReaComp become cheaper than each alternative?

  6. How far does the method extend beyond narrow DSLs? Is there evidence that solver construction still works when the language contains branching, recursion or richer program semantics? If not, please state this boundary clearly.

  7. What does a perfect verifier score certify? Please clarify the relationship between fitting the given examples, recovering the intended programme, and generalisation to held-out inputs, especially in the linguistic case study.

6 comments
AuthorsOpenReview ↗

Response to Reviewer U92J (Part 1)

Thank you for the detailed review. We respond to each point below. G1 to G4 refer to the general response.

Q1: Main advantage of the generated solver

Easier adaptation to a new DSL; please see G1. We agree that the induced solvers use standard search techniques, and we do not claim new search algorithms. Our claim is that a coding agent produces a competitive solver automatically, which saves the expert time otherwise needed to write a synthesizer for each new DSL. While the search is standard, the solvers contain DSL-specific heuristics taken from the traces (e.g. the two-step candidate generation in W2).

W1, Q4: Comparison with conventional symbolic synthesizers

But the most relevant question is whether the LLM-generated solvers are any better than a conventional symbolic synthesiser on the same DSL.

For PBEBench's ordered-rewrite DSL, we are not aware of an established synthesizer, so we ran ReaComp on a benchmark that has one. We added HySynth's SyGuS string benchmark (Barke et al., 2024), which has a richer DSL (conditionals, substrings, indices, integer arithmetic) and strong hand-built solvers. We use their 70 test tasks with 10 minutes per task, and every program is checked against the task's grammar and examples. We reran Probe, an off-the-shelf weighted bottom-up search synthesizer evaluated in HySynth from the released code, and also ran HySynth with gpt-oss-120b samples so that it uses the same LLM as ReaComp. Our solvers were built from 53 SyGuS-Comp string tasks that share no examples, inputs, or equivalent functions with the 70 test tasks. We will add the full setup and per-task results to the appendix of the revised draft.

SyGuS string benchmark, 70 test tasksLLM calls (total)Solved / 70
Probe (reported 25)027
HySynth, GPT-4o guidance, 100 samples per task (reported 49)7,00049
ReaComp solver, 3 builds ($7 to $15 each)027 to 47 (median 33)
ReaComp, union of the 3 solvers057
All three below use gpt-oss-120b (ReaComp's LLM), 32 / 100 samples per task:
HySynth, guided by gpt-oss-120b instead of GPT-4o2,240 / 7,00049 / 53
gpt-oss-120b, direct sampling2,240 / 7,00056 / 59
ReaComp union, then gpt-oss-120b on unsolved tasks416 / 1,30062 / 64

Without any LLM calls at test time, the union of the induced solvers solves 57 tasks, more than HySynth with 100 GPT-4o samples per task (49), and it solves 15 tasks that HySynth does not. To rule out that this comes from using a stronger LLM, we also guided HySynth with gpt-oss-120b, the LLM ReaComp uses. It improves only to 53, which is below direct sampling from the same model (59). With this LLM and the same number of samples per task, ReaComp outperforms both, and it calls the LLM on only 13 of the 70 tasks (one sample each already gives 60). Individual builds vary (27 to 47), so we report the union next to the per-build range, as for PBEBench.

AuthorsOpenReview ↗

Response to Reviewer U92J (Part 2)

W2, Q2, Q3: Isolating the traces

Would the coding agent produce a comparable solver without any traces? Please compare DSL-plus-verifier-only construction with examples-only, final-program, and full-trace settings.

We ran this comparison with the four conditions you list, using the same agent and budget and 5 builds per condition. Please see G2 for the table.

Which heuristic is genuinely derived from a reasoning trace? Can the authors show a specific trace pattern, the resulting change in solver logic, and a controlled ablation of that change?

Yes. Below is one example from the paper's QO PBEBench solver. We will add it to the appendix section on solver construction ablations.

In demo 15, the pair UNWjaL → YeWcYjaL cannot come from one legal rewrite (replacements have at most 3 characters). gpt-oss solves it with a feeding cascade: replace('NW','WcY') creates the context that replace('UW','YeW') then rewrites. While debugging this demo, the coding agent notes that "it could be a multi-step process" and adds two-step candidate generation, where the output of one rule is the input of the next ("Demos 15 is now fixed!"). The code is in generate_candidates, lines 106 to 129 of the released solver. PBEBench-Hard task 915 (not an induction task) needs replace('U','Kq') followed by replace('Kqz','qnz'), and Kqz occurs in no input. The full solver finds this program. Without the heuristic it does not.

QO solver with and without this heuristic (both versions evaluated under the same conditions):

QO solverPBEBench-LitePBEBench-Hard
Full (the paper's solver; the paper reports 74.7 on Hard)66.275.0
Without the trace-derived multi-step heuristic46.365.0

A second example is from a Claude Code SLR-Bench build. The trace for one task reasons "eastbound if there exist two cars with different colors ... Need inequality. In Prolog use dif/2". The agent tests rules it labels "LLM's hints", notes "Demo 89 scores 1.0 with a "multicolor" rule using variable-variable inequality. I need to add this rule type to the solver", and adds a dedicated search over such rules (find_multivalue_two_car_rules). That task had been stuck at a partial score through every earlier self-evaluation and is solved right after. The same appendix section will list further examples, including heuristics taken from the LLM's failed attempts.

AuthorsOpenReview ↗

Response to Reviewer U92J (Part 3)

W3, Q6: Narrow DSLs

Otherwise, the paper should explicitly limit its claims to fixed-DSL, verifier-backed tasks.

We agree that PBEBench-Hard is hard because of search depth and not because of language expressiveness. We will state the scope as fixed-DSL, verifier-backed program search in the Limitations section. The SyGuS experiment (W1) adds a DSL with conditionals and string operations.

W4, Q5: End-to-end Cost per solved task

Thanks for the suggestion. We now report the total cost per correctly solved task, counting trace generation, one-time solver construction, LLM fallback, and solver CPU time. The full breakdown will be added to the appendix on computational cost. Generating the traces costs about $0.10 (PBEBench) and $0.08 (SLR-Bench), and solver CPU time is negligible.

On PBEBench-Hard, the QO solver alone costs $0.0011 per solved task versus $0.0695 for BoK and pays for itself after about 20 tasks. It also dominates BoK's whole cost-accuracy curve (BoK: 28.3% at K = 1 for $1.81, 68.4% at K = 32 for $57.83; QO solver: 74.7% with no LLM calls and 0.37 CPU-hours for all 1,216 tasks). BoK + All Symbolic costs $0.0197 per solved task and breaks even after about 200 tasks. The strongest LLM baseline on PBEBench-Hard, DF, costs $0.0215 per solved task. Seeded DF + CC costs $0.0113 and is 6.6 points more accurate (93.5 vs. 86.9), recovering its one-time cost after about 210 tasks. All these costs include solver CPU time, priced at $0.05 per vCPU-hour: 0.37 CPU-hours ($0.02) for the QO solver, 1.5 ($0.07) for the CC solver, and 11.3 ($0.57) for All Symbolic over the 1,216 tasks, small next to the LLM costs.

On SLR-Bench, Seeded DF + CC costs $0.014 per solved task versus $0.022 for DF, breaking even after about 490 tasks.

For price sensitivity, every LLM cost scales linearly with price, so these orderings hold from 0.25x to 4x current prices. If only inference prices change, break-even points scale inversely with price; if build and inference prices change together, they stay the same.

On cheaper LLM alternatives: gpt-oss-120b is itself an inexpensive open model at the prices we use ($0.039 per million input and $0.19/M output tokens), the BoK curve above covers K = 1 to 32, and DF stops at the first verified success. We have not yet repeated the comparison with a second inexpensive model. Since every LLM cost in the comparison scales with per-token price, a cheaper model would lower the per-task saving and raise break-even points proportionally; we will add such a model to the revision.

W5, Q7: What a perfect verifier score certifies

I suggest separating example consistency from out-of-sample correctness wherever held-out pairs are available. Program complexity and, for linguistic tasks, domain validity should also be assessed.

Reward 1.0 certifies consistency with the given examples, which is the standard PBE criterion. To measure generalization, we re-ran every saved PBEBench-Hard program on 100 unseen inputs per task.

PBEBench-HardShown acc.Held-out acc. (all 100 strings)Held-out strings correct
BoK68.435.493.4%
BoK, oracle choice among its 32 samples68.450.9-
CC solver69.726.297.1%
QO solver74.737.396.9%
All Symbolic84.751.298.2%
BoK + All Symbolic85.855.198.4%

Fifty shown strings often do not determine the cascade, so strict held-out accuracy is lower for every system, but the returned programs reproduce 93 to 98% of unseen strings. Choosing on shown examples only, All Symbolic matches BoK even when BoK's choice is made by an oracle.

On PBEBench-Lite (same protocol, new held-out set) the picture differs. The LLM's own programs generalize better than single solvers (held-out accuracy: BoK 41.4, DF 40.2, CC solver 20.4, QO solver 18.8, All Symbolic 39.0; BoK + All Symbolic 32.7). This is consistent with short Lite cascades being easier for the LLM to infer exactly.

For the linguistic case study, the appendix on real-world forward reconstruction already shows induced rules that match documented sound changes, such as word-initial /b/ > /f/ lenition in Amis, word-final /ʔ/ > /h/ in Bahasa Indonesia and glottal stop deletion in Bidayuh, alongside the compression analysis showing that unconstrained cascades also patch individual words. In addition, a historical linguist rated a random sample of 60 induced rules from 15 language pairs not shown in the paper as plausible or attested, possible but unusual, or implausible:

Induced rulesRulesPlausible or attestedUnusualImplausible
Compressed cascades (at most n/5 or n/3 rules)2928 (97%)01
Unconstrained solver3127 (87%)22
All6055 (92%)23

The few implausible rules mostly come from unconstrained cascades, as the compression analysis predicts.

Please let us know if you have any further concerns.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response

We thank the reviewers. Below, we clarify our main claim and answer the common points raised by the reviewers; the individual responses refer back here.

G1. Main claim. ReaComp's main contribution is making it easy to get a strong solver for a new verifier-backed DSL. A coding agent turns a small set of unlabeled reasoning traces from an LLM doing program synthesis into a standalone Python synthesizer (without LLM calls) in a couple of hours, for $1 to $15 per build, with no domain expert. We show this on string rewriting (PBEBench), Prolog rule induction (SLR-Bench), and list functions, plus zero-shot transfer to real historical-linguistics data. We do not claim that a solver alone beats the strongest LLM baseline (DF); the claim is about cost and accuracy together. Once the one-time solver build with the coding agent is amortized, ReaComp systems sit on the cost-accuracy Pareto front. At low budgets the solvers alone dominate: they make no LLM calls and already match or beat BoK. As the budget grows, the hybrids take over, and solver-seeded fallback pushes the frontier past every LLM baseline. Seeded DF + CC has the highest accuracy on all three benchmarks (PBEBench-Hard 93.5, PBEBench-Lite 94.5, SLR-Bench 93.3), with the largest gains on hard instances (SLR-Bench hard tier: 76.4 vs. 34.4 for DF):

PBEBench-HardTotal costAccuracy
QO solver alone$0.95 (one-time build)74.7
Seeded DF + CC$12.86 ($2.10 build + $10.76 LLM)93.5
DF (strongest LLM baseline)$22.7386.9

SLR-Bench shows the same pattern (Seeded DF + CC: 93.3 at $12.76 vs. DF: 79.6 at $17.43). We will make this explicit in the abstract and introduction.

G2. Do the reasoning traces matter? (U92J, ASVL) We ran a matched ablation: the same agent (QO) and budget building the solver from (i) only the task specification, (ii) the I/O examples, (iii) the LLM's final programs, or (iv) full reasoning traces, 5 build runs for each setting, all evaluated one task at a time under the paper's time limits:

Built fromPBEBench-Lite, per buildLite medianPBEBench-Hard, per buildHard median
(i) Specification only26.8, 39.8, 56.2, 57.6, 73.856.20.2, 0.2, 0.2, 16.3, 19.70.2
(ii) I/O examples18.8, 28.1, 39.6, 46.1, 47.539.614.2, 14.6, 16.7, 18.6, 23.516.7
(iii) Final programs16.4, 27.5, 41.1, 41.3, 43.841.112.2, 16.7, 24.3, 30.1, 54.424.3
(iv) Full reasoning traces33.2, 53.4, 59.6, 66.2, 79.259.626.8, 41.4, 51.8, 58.9, 74.751.8

Without traces, the agent tends to write a brute-force search over rewrite rules. That suffices for Lite's short cascades (up to 5 rules; the best specification-only build reaches 73.8, though about 300 times slower than a trace-built solver), but it does not scale to Hard's cascades of up to 20 rules: three of five specification-only builds solve almost nothing (0.2%), and the best reaches 19.7. On Hard, the median trace-built solver solves 51.8%, against 16.7% from I/O examples and 24.3% from final programs. Individual builds vary widely in every condition (one final-program build reaches 54.4, one trace build only 26.8), but the traces matter most where the search is deep.

G3. Tasks used for solver induction. (Qb9L, ASVL) The coding agent sees the LLM's own attempts on a set of tasks (its reasoning, final answer, and whether the verifier accepted it on the task's examples), never ground-truth programs. These induction tasks are 91 PBEBench-Hard and 87 SLR-Bench test tasks; no PBEBench-Lite task was used. For completeness, results with the induction tasks removed:

All tasksInduction tasks removed
Hard: BoK68.466.8
Hard: QO solver74.773.6
Hard: All Symbolic84.783.8
Hard: BoK + All Symbolic85.885.0
SLR: DF79.678.6
SLR: Seeded DF + CC93.393.1

Every system in the table drops by at most 1.6 points, including BoK and DF, which never see the induction traces or the solver and so act as independent reference points. This shows that the induction tasks are simply easier than average. On them, the solvers do about as well as BoK (Hard: CC 90.1, QO 87.9 vs. BoK 89.0), and the gap to the baselines is unchanged or larger with them removed. On the 1,125 non-induction PBEBench-Hard tasks, the QO solver, All Symbolic, and BoK + All Symbolic each still beat BoK (exact McNemar p ≤ 1.2e-7), and on the 913 non-induction SLR-Bench tasks, Seeded DF + CC still beats DF (p = 5.7e-33). We will release the task indices and add this analysis to the appendix.

AuthorsOpenReview ↗

General Response Cont'd

G4. Variance and repeated builds. (Qb9L, U92J) We now report 5 independent builds per setting (the original builds plus new ones with fresh context), all evaluated one task at a time under the paper's time limits. Claude Code:

Claude Code solver, 5 buildsRangeMedian
PBEBench-Lite74.1 to 89.880.7
PBEBench-Hard69.7 to 88.981.7
SLR-Bench68.4 to 87.681.8

The new builds are at or above the original one on every benchmark. QO builds vary more (condition (iv) of G2, 5 builds): PBEBench-Lite 33.2 to 79.2, median 59.6; PBEBench-Hard 26.8 to 74.7, median 51.8. We will report unions next to the per-build spread.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.