- Rating
- 4
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper investigates why Scattered Forest Search (SFS) is effective for multi-turn program correction. It develops a version-space framework that contrasts sequential program refinement with refinement of repair instructions, positioning SFS between these two approaches. Motivated by this analysis, the authors introduce IRRI, a simpler method that revisits fixed initial programs while accumulating insights to improve subsequent repair instructions.
The paper validates its perspective through analysis of SFS search depths and experiments across multiple coding benchmarks and language models. The results support the interpretation that, within the studied budgets, much of SFS’s benefit can be retained through shallow exploration and accumulated repair guidance. IRRI achieves performance comparable to SFS while requiring fewer model calls and tokens.
Critical strengths
-
A thoughtful combination of theoretical and empirical analysis. The version-space perspective provides an elegant framework for distinguishing refinement of programs from refinement of repair instructions. The search-depth analysis is particularly valuable: it examines how SFS actually finds solutions and provides concrete evidence motivating the simpler approach. This connection between conceptual analysis and observed behavior makes the paper more informative than a performance comparison alone.
-
A consequential simplification supported by broad evaluation. IRRI turns the paper’s analysis into a practical algorithm that retains much of SFS’s performance without its tree-search machinery. The evaluation across several models and benchmarks, together with the computational-cost comparisons, strengthens the case that this simplification is useful. Understanding which parts of a complex inference-time method are necessary is a meaningful contribution.
Critical weaknesses
One limitation I can think of is that the scaling plots use the number of generated solutions as the computational budget. Including plots with cumulative token usage on the x-axis would make the efficiency comparison more direct, since different methods incur different overheads per generated solution. The aggregate cost tables partially address this concern, and I view the additional plots as a useful strengthening of the evaluation. Overall though the paper is well written, and its central claims are supported by complementary analyses and experiments.
Questions for authors
-
Could the authors provide a concrete example of how feedback from an unsuccessful repair is distilled into shared information and improves a subsequent repair instruction? This would help make the proposed mechanism more tangible.
-
Could the authors clarify whether the reported token costs include all auxiliary calls, such as generating repair instructions and updating shared information? This would help readers interpret the efficiency comparison.
3 comments
All my concerns have been addressed. I maintain my positive assessment of the paper. Good luck!
Thank You for Your Feedback
Thank you very much for your positive assessment and for taking the time to consider our responses. We sincerely appreciate your time and thoughtful feedback.
Response to Reviewer pJB6
A1. Thank you for your insightful comment. We have added figures to the paper (pp. 35-36) comparing inference scaling, with the cumulative number of tokens used on the x-axis. We found that SFS and IRRI perform on par with prior methods at small budgets, but scale better as the token budget increases. Notably, the two methods exhibit similar behavior across the entire budget range.
A2. Thank you for your comment. We provide a concrete example below (which has also been added to the paper pp. 36-37). The failed repair attempt focuses on a superficial error-prevention measure: “adding a guard to ensure that the number of sticks does not become negative when −x is encountered”. From this failure, more general problem-solving guidelines are extracted, such as "the validation logic should account for all possible configurations of the board" and "the counting mechanism should be checked to ensure that it satisfies the problem requirements." Based on them, the successful repair improves upon the initial attempt by moving beyond simply adding exception handling and instead modifying the underlying logic to correctly maintain the state required by canbuild.
(Unsuccessful Repair)
Ensure that the plank count is updated correctly after each event. When processing the −x operation, ensure that the count does not drop below zero. This can be done by checking if the count of x is greater than zero before decrementing. This will prevent any erroneous states where the count becomes negative, which could lead to incorrect calculations in the canbuild function.
(Shared Information Extracted)
(Successful Repair)
Ensure that the update logic for the counts in the event processing loop correctly reflects the changes in the number of planks. Specifically, when a plank is added or removed, check if the count of that plank length crosses the thresholds for pairs or quadruples. This will allow the canbuild function to have accurate data to work with after each event.
A3. Thank you for your comment. The numbers of LLM calls and tokens reported in Tables 8–12 include all auxiliary calls, such as those for generating repair candidates and updating shared information. We have added this clarification to the paper.
(before) To reveal the efficiency of IRRI, we compared SFS and IRRI in terms of the number of LLM calls, the number of output tokens, and the total number of tokens, reporting the average over five runs.
(after) To reveal the efficiency of IRRI, we compared SFS and IRRI in terms of the number of LLM calls, the number of output tokens, and the total number of tokens, reporting the average over five runs. The LLM calls, output tokens, and total tokens reported in all tables include every auxiliary call, such as generating repair instructions and updating the shared information.