Let's Revise Step-by-Step: A Unified Local Search Framework for Code Generation with LLMs

We sincerely appreciate your thoughtful and constructive review. Thank you for recognizing the motivation and promise of our approach, especially the value of using fine-grained reward signals. Below, we address your remaining questions and concerns in detail.

W1: The use of classical local search algorithms (Hill Climbing, Genetic Algorithms) in this work is viewed as incremental rather than novel.

Thank you for raising this important point. We agree that hill climbing and genetic algorithms are classic search strategies and not novel on their own. However, our contribution lies not in simply reusing these algorithms, but in adapting and integrating them into a principled and effective local search framework tailored for LLM-based code generation, which faces unique challenges compared to classical optimization problems. We would like to clarify the sources of novelty in our work:

1. Adapting Classical Local Search for LLM-Based Code Generation.

   • While hill climbing and genetic algorithms are classical methods, applying them effectively to LLM-based code generation is far from straightforward. Traditional local search relies on well-defined, dense objective functions, whereas in code generation, feedback is often sparse, binary, and noisy. Moreover, candidate programs are structured and long-form, making it non-trivial to sample meaningful local neighborhoods under tight token budgets.

   • To overcome these challenges, we build on the core idea of iterative refinement. Based on this perspective, we propose a modular framework tailored for LLMs, which decomposes the process into four components: initialization, neighborhood generation, candidate evaluation, and incumbent update.

   • Each module is designed to support flexibility and task-specific adaptation. For instance, initialization can use plan-based prompting or pure sampling depending on the scenario. Neighborhood generation can leverage execution signals for repair tasks. Classic algorithms like hill climbing and genetic algorithms are adapted to operate over these components in a way that respects the nature of LLMs and the discrete, structured nature of code.

2. Revision Reward Model Tailored for Local Search.

   We agree that the reward model is a core component of our approach. However, it is not an isolated module that can be separated from the framework. It is designed specifically to address a fundamental challenge of evaluating candidates within neighborhoods during the local search process. Inspired by the local search principle of leveraging structural locality, our revision reward model uses revision distance to provide fine-grained, relative feedback based on relationships among parent, child, and sibling code candidates.

W2: Marginal gains (32.7% to 33.4%) may not justify the added complexity of training the revision reward model.

We would like to clarify that ReLoc_HC improves performance from 32.7% to 38.4% on the code generation task, compared to Plan Search, and also achieves better results on the code repair task. These gains demonstrate that even with a lightweight local search procedure, our approach can effectively leverage the revision reward model to guide the search process.

Training the revision reward model involves a one-time cost, but it offers broad and lasting utility. Once trained, the model can be reused across different tasks and model families without retraining. To demonstrate this, we apply the reward model trained solely on data from Qwen2.5-32B-Instruct to a stronger frontier model, GPT-4o, and observe continued performance gains with even better token efficiency, as shown below:

W3 & Q4: The importance of the revision strategy.

Thank you for identifying this area where additional clarification is needed.

In the ReLoc, the Revision Strategies component refers to prompting the LLM to first generate natural language descriptions of revision plans (e.g., “Failed to initialize, missing basic state definition”), which are then used to guide code edits during the neighborhood generation. This is one specific sampling strategy within the neighborhood generation module.

As you correctly observed, when we ablate this component and instead directly prompt the LLM to revise code without revision descriptions, the performance drops only modestly (e.g., 38.4% → 35.9%). This result highlights ReLoc performs well even without this natural language planning.

Q1: The computational cost of generating the training data. How does this pre-computation cost weigh against the claimed inference-time efficiency gains?

Thank you for your insightful question regarding the pre-computation cost for training the revision reward model. While data sampling introduces some overhead, the use of BFS makes it efficient, and the reward model is trained only once. Below, we address the computational cost from two perspectives:

1. Efficient Data Sampling via BFS and Locality-Based Comparison.

   • We limit the maximum depth to d_max=5 and the branching factor to K = 3 to avoid combinatorial explosion. In practice, due to duplicate or correct code samples during sampling, each code tree contains only ~11 unique nodes on average.

   • More importantly, our comparison strategy leverages locality, comparing each node to its parent, children, and siblings. As a result, each node participates in 2.4 comparisons on average, making efficient use of every sampled code snippet.

   • To further scale this process, we build a highly parallelized sampling system using vLLM, running on 4×H100 GPUs, completing data collection in 2.3 days, generating 178M tokens. This cost is entirely manageable in modern training pipelines and requires no human annotation.

2. Robust Training with Small Subsets of Data.

   We perform additional experiments to test the sample efficiency of the revision reward model. As shown below, the model maintains strong performance even with significantly reduced training data:

   Downsampling Strategy	LiveCodeBench	TACO
   Random Quarter (218K pairs)	38.1	13.2
   Random Half (436K pairs)	38.3	13.1
   Full-scale Training (872K)	38.4	13.3

Q2: Clarify how the 37% token reduction is calculated

We appreciate the opportunity to clarify the source and calculation of the "37% reduction in token consumption".

While this figure was referenced alongside Figure 4, it is in fact derived from a separate comparison between ReLoc and Plan Search under unconstrained token settings, as shown in the table below. This analysis evaluates both performance and token usage on the code generation tasks in LiveCodeBench and TACO:

Averaging across tasks, ReLoc uses 7.3K tokens compared to 11.6K for Plan Search, resulting in a 37% reduction in token consumption, while also achieving better overall accuracy.

Q3: Clarify GA crossover prompt and validate offspring diversity and effectiveness.

Thank you for pointing this out. In the ReLoc framework, assessing the diversity of offspring is indeed crucial, especially for population-based algorithms such as Genetic Algorithm (GA). We have included the exact prompt template used for neighborhood generation in Appendix Section D, Table 6.

To evaluate the diversity of the generated offspring, we adopt two evaluation strategies:

• CodeBLEU analysis [1]: We compute CodeBLEU between offspring and parents to assess non-trivial changes. A lower scores indicate meaningful edits beyond simple averaging or minor tweaks.
• BERT-based diversity measure [2]: Following prior work, we measure diversity by averaging BERT cosine similarity across candidates. Lower scores reflect greater diversity.

We also include Reflexion, a well-known multi-step refinement method, as a baseline for comparison. The results below are reported on the LiveCodeBench benchmark.

ReLoc_GA generates offspring that are more structurally and semantically different from their parents, and promotes greater population diversity, demonstrating effective exploration behavior.

[1] Ren, Shuo, et al. "Codebleu: a method for automatic evaluation of code synthesis." arXiv preprint arXiv:2009.10297 (2020). [2] Light, Jonathan, et al. "Scattered forest search: Smarter code space exploration with llms." arXiv preprint arXiv:2411.05010 (2024).

Thank you again for all your constructive feedback. We will include these clarifications, especially the revision strategies, and updates in our revision.

Thank you very much for your thoughtful and encouraging review. We sincerely appreciate your recognition of the key contributions of our work, including the motivation, design and clarity of the ReLoc framework, as well as the effectiveness of the revision reward model. Below we provide detailed responses to your remaining questions.

W1 & Q1: Generalization across model families, such as GPT or Claude Sonnet.

Thank you for your valuable suggestion. We agree that evaluating the effectiveness of our method across different model families, especially frontier models, is crucial to demonstrate its generality. To show this, we conduct an experiment using GPT-4o (gpt-4o-2024-1120) as the base model for both code generation and revision. The revision reward model used in this setting was a Qwen2.5-7B-Instruct, consistent with the setup described in Section 4.1. We then applied the ReLoc_HC framework on LiveCodeBench. Here's the result:

These results demonstrate that both our ReLoc framework and the revision reward model are highly adaptable across model families, and can be effectively applied even to strong frontier models like GPT-4o. This highlights their robustness and general applicability in real-world code generation and revision scenarios.

W1: Paper does not provide insights into what kind of errors are recovered during the revision phrase.

Thank you for the insightful question. Based on our analysis of the LiveCodeBench results, we observe that two major categories of errors are effectively corrected by ReLoc during the local search process:

1. Partial correctness and incomplete logic.

   Initial code often passes some public test cases but fails on edge conditions due to narrow or missing logic. Revisions gradually generalize the solution.

   • Example: A divisor function fails on prime inputs. Revisions add checks and extend logic to handle all cases correctly.

2. Runtime and semantic errors surfaced by execution feedback.

   Explicit errors like index out-of-bound errors, incorrect loop bounds, or type mismatches. These signals are especially helpful because they explicitly point out failure modes, guiding the model toward targeted repairs.

   • Example: A loop with incorrect bounds causes a runtime error. Feedback directs the model to adjust the iteration logic, quickly fixing the issue.

Q2: Importance of initial code quality and alternative initialization strategies.

We agree that the quality of the initial code population has a notable impact on the performance of ReLoc. As shown in Table 3 of the main paper, we have experimented with random sampling as an alternative initialization strategy. The results show that even with simple sampling, ReLoc remains highly competitive, highlighting its robustness to the choice of initial candidates.

Sensitivity to Seed Code Quantity: We further study how the number of initial seed codes affects performance. As shown below, ReLoc still delivers strong performance even with a single initial code sample, highlighting its ability to iteratively revise and improve suboptimal solutions.

In summary, while better initial code helps improve performance, ReLoc does not heavily rely on initialization quality thanks to its iterative improvement nature.

Q3: Accuracy of reward model on distinguishing correct vs. incorrect code pairs on unseen samples.

We conduct an evaluation on unseen problems, measuring the accuracy of the revision reward model in identifying the correct code from a pair consisting of one correct and one incorrect solution. We compare our model against two strong baselines: the open-source Skywork-27B model and the proprietary GPT-4o. The results are shown below:

Our revision reward model significantly outperforms both baselines in identifying correct code, even in challenging cases where the incorrect and correct solutions are highly similar and both reside within the same local neighborhood of a code sample. This highlights the effectiveness of our reward model, which is explicitly trained to leverage the locality structure of code revisions and capture subtle differences that general-purpose LLMs often overlook.

Q4: How did you decide 7k token budget for experiments?

Thank you for the thoughtful question. Controlling the search budget is indeed a critical factor in real-world deployment.

We select a 7K token budget to reflect realistic resource constraints, while still enabling effective search. Although ReLoc continues to improve with larger budgets, as shown in Figure 4 where it consistently outperforms baselines as the token budget grows, we intentionally evaluate under a 7K token setting to simulate practical use cases. Scenarios such as code assistants or classroom tools often operate under latency or cost limits, making small-budget inference particularly relevant.

This setup highlights ReLoc’s strength under constrained conditions, while preserving its ability to scale gracefully when more resources are available.

Thank you again for your valuable and encouraging feedback. We will incorporate all these clarifications and improvements into our revision.

Thank you very much for your detailed and thoughtful review. We truly appreciate you highlighting the strengths of revision-based reward design and the strong empirical results. Regarding your questions, we provide our responses as follows.

W1: Generalization of the revision reward model across different search strategies.

The core idea of our revision reward model is to effectively differentiate promising incorrect code candidates by comparing their revision distance. As introduced in Line 158 of the main paper, we use breadth-first search to construct training data for the revision reward model. This way, we construct comparison pairs within local neighborhoods (parents, children, siblings) of a node in the BFS tree without being tied to any specific search behavior, which can well capture the relationship between the incumbent code sample and the neighborhood code samples in local search. This design ensures the learned preferences are transferable across various local search algorithms.

W2: Lack of hyperparameter sensitivity analysis for key parameters (e.g., d_max and K).

Thank you for raising this important point. We provide a two-part analysis to demonstrate the robustness of our method to hyperparameter and data variations.

1. The revision reward model is robust to different BFS sampling hyperparameters.

   We vary the tree depth $d_{\text{max}}$ and branching factor $K$ used to collect training data. As shown below, performance remains stable even with shallower or narrower trees, indicating that our reward model does not require broad exploration to be effective.

   Sampling Setting	ReLoc_HC (Pass@1)
   Full scale (d_max = 5, K = 3)	38.4
   Shallower tree (d_max = 3, K = 3)	38.2
   Narrower tree (d_max = 5, K = 1)	37.4

2. The revision reward model remains effective even with limited training data.

   We evaluate sample efficiency by downsampling the training set. As shown below, performance drops only slightly even with a quarter of the data, confirming that the reward model benefits from the locality structure and generalizes well with fewer training pairs.

   Downsampling Strategy on Training set	LiveCodeBench	TACO
   Random Quarter (218K pairs)	38.1	13.2
   LiveCodeBench subset (363K pairs)	37.9	12.4
   Random Half (436K pairs)	38.3	13.1
   Full-scale training (872K pairs)	38.4	13.3

Q1: Prediction accuracy of the reward model on edit distance supervision.

Thank you for your valuable suggestion. We agree that evaluating the accuracy of the reward model is essential for understanding its ability to capture fine-grained revision signals. To show this, we evaluate its pairwise accuracy on training and validation sets. We compare it with two strong baselines: the open-source model Skywork-27B and the proprietary GPT-4o. As shown in the table below, our model significantly outperforms both baselines:

This result underscores several important observations:

• Revision-based ranking is a challenging but effective learning task. Even subtle code edits require fine-grained discrimination beyond generic correctness signals.
• Our model generalizes well, achieving 72.6% accuracy on unseen validation tasks—substantially outperforming general-purpose LLMs like GPT-4o.

Together, these results confirm that our reward model effectively captures differences between code candidates, offering reliable guidance for local search where general LLMs fall short.

Thank you again for all your constructive feedback. We will include these clarifications, especially the construction of the reward model data, and updates in our revision.

We sincerely appreciate your in-depth and constructive feedback. We are also grateful for kindly pointing out that our method is well-motivated and implies high expandability and flexibility. Regarding your concerns, we provide our responses below:

W1: Ablation study on the local search algorithm and the revision reward model.

We conduct additional ablations on the local search algorithm and revision reward model to further assess their robustness and effectiveness. Results are summarized below:

1. Ablation on Seed Code Number. To assess the robustness of our local search framework, we vary the number of initial seed code candidates in ReLoc_HC and ReLoc_GA. As shown below, performance slightly drops when using only a single seed due to reduced diversity in the initial population. However, the overall performance remains strong and stable across different settings, demonstrating that both variants are highly robust to initialization size.

   Seed Code Number	ReLoc_HC (Pass@1)	ReLoc_GA (Pass@1)
   1	35.2	34.1
   3	38.4	35.9
   5	38.4	35.7
   7	38.7	35.4

2. Ablation on Revision Reward Model Data Construction. We evaluate the impact of key parameters in constructing the training data for the revision reward model, including the maximum depth of the code tree (d_max), the number of revisions per node (K), and the use of locality-based comparison pairs.

   The results show that our reward model is robust and effective even when using smaller or shallower trees, indicating strong sample efficiency and low reliance on large-scale supervision. This is largely due to our use of comparison pairs built from local relationships among parent, child, and sibling nodes, which provide meaningful training signals to guide the local search process.

   Setting	ReLoc_HC (Pass@1)
   Full setting (d_max = 5, K = 3)	38.4
   Shallower tree (d_max = 3, K = 3)	38.2
   Fewer revisions (d_max = 5, K = 1)	37.4

W2: Limited comparison to recent baselines from ICLR 2025 and other new work.

Thank you for raising this point. We fully agree that including recent baselines is important for a fair and up-to-date evaluation. We have already incorporated several strong and representative methods from ICLR 2025, ICML 2025, and NAACL 2025 into our experiments.

These methods are included in Table 1 of our main results and are clearly categorized by their inference strategy and reward signal.

[1] CodeTree: Agent-guided Tree Search for Code Generation with Large Language Models, NAACL 2025

[2] SFS: Smarter Code Space Optimization Improves LLM Inference Scaling, ICLR 2025

[3] Planning in Natural Language Improves LLM Search for Code Generation, ICLR 2025

[4] Reasoning Through Execution: Unifying Process and Outcome Rewards for Code Generation, ICML 2025

W3: Lack of empirical evidence demonstrating the efficiency of the proposed local search algorithm.

Thank you for your valuable suggestion. We fully agree that search efficiency is a critical concern, especially under realistic resource constraints. To demonstrate efficiency more concretely, we provide two forms of evidence:

1. Efficiency under different token budgets. As shown in Figure 4, ReLoc achieves comparable or better performance than Best-of-N methods with significantly fewer tokens. For example, ReLoc reaches the same Pass@1 as BoN under 15K tokens using only 3K tokens, illustrating its superior token efficiency.

2. Comparison of token usage and performance across methods. We further report the token consumption and Pass@1 accuracy of various methods on the LiveCodeBench benchmark. As shown below, ReLoc strikes the best balance between effectiveness and efficiency:

   Method	Pass@1 (%)	Tokens (1K)
   Plan Search	33.8	11.6
   Code Tree	29.1	15.3
   TOT	25.4	11.9
   BoN	31.3	15.1
   ORPS	30.0	14.7
   ReLoc_HC (Ours)	38.4	7.1

Unlike prior methods such as MCTS or agent-based search, which consume large token budgets (Section 1, Line 62), ReLoc uses lightweight decision rules to guide local revisions efficiently. These results confirm that ReLoc achieves state-of-the-art accuracy with significantly fewer tokens, making it well-suited for practical deployment.

W4: Sample efficiency of the revision reward model under limited training data.

We appreciate the reviewer’s concern regarding the practicality of training the revision reward model with 872K training pairs. We address this issue from both the efficiency of training and the effectiveness under limited data:

1. Efficient and Sample-Efficient Training. While our full-scale training uses 872K training pairs, it requires only 36 GPU hours on 4 H100 GPUs, which is practical in real-world settings. Importantly, we did not perform any sophisticated data filtering, all sampled data were used. In practice, we found that the revision reward model still exhibits strong performance in combining with ReLoc given fewer samples. We evaluated three downsampling strategies:

   • Random Quarter (218K pairs)
   • LiveCodeBench subset (363K pairs, only using data sampled from LiveCodeBench)
   • Random Half (436K pairs)

   The results on LiveCodeBench and TACO benchmarks (using ReLoc_HC) show that even with reduced data, the reward model remains effective. This confirms that our revision distance based formulation is sample-efficient and robust under data constraints.

   Downsampling strategy	LiveCodeBench	TACO
   Random Quarter (218K pairs)	38.1	13.2
   LiveCodeBench subset(363K pairs)	37.9	12.4
   Random Half (436K pairs)	38.3	13.1
   Full-scale training(872K pairs)	38.4	13.3

2. Robustness Across Models. To further demonstrate the practicality and generalization of the reward model, we trained it using data collected from Qwen-32B and applied it to guide GPT-4o, a strong closed-source model. The results are shown below:

   Methods	Rew.	Pass@1 (%)	Tokens (1K)
   Plan Search	self-evaluation	42.7	16.7
   BoN	Pass Rate	41.8	12.2
   ReLoc_HC (Ours)	Revision Reward Model	44.2	8.7

   Despite being a 7B reward model, it significantly boosts GPT-4o’s performance on code tasks, showing strong robustness across model scales and architectures.

Thank you again for your valuable and encouraging feedback. We will incorporate all these clarifications and improvements into our revision.