- 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
- 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.
- 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?
- 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
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
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
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:
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
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
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
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
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.