Let's Revise Step-by-Step: A Unified Local Search Framework for Code Generation with LLMs
Authors: Zhiyi Lyu
Jianguo Huang
Yanchen Deng
Steven Hoi
Bo An
Venue: NeurIPS 2025 poster ()
Keywords: LLM
Code generation
Local Search
Primary area: deep_learning

Abstract: Large Language Models (LLMs) with inference-time scaling techniques show promise for code generation, yet face notable efficiency and scalability challenges. Construction-based tree-search methods suffer from rapid growth in tree size, high token consumption, and lack of anytime property. In contrast, improvement-based methods offer better performance but often struggle with uninformative reward signals and inefficient search strategies. In this work, we propose $\textbf{ReLoc}$, a unified local search framework which effectively performs step-by-step code revision. Specifically, ReLoc explores a series of local revisions through four key algorithmic components: initial code drafting, neighborhood code generation, candidate evaluation, and incumbent code updating, each of which can be instantiated with specific decision rules to realize different local search algorithms such as Hill Climbing (HC) or Genetic Algorithm (GA). Furthermore, we develop a specialized revision reward model that evaluates code quality based on revision distance to produce fine-grained preferences that guide the local search toward more promising candidates. Finally, our extensive experimental results demonstrate that our approach achieves superior performance across diverse code generation tasks, significantly outperforming both construction-based tree search as well as the state-of-the-art improvement-based code generation methods.

Let's Revise Step-by-Step: A Unified Local Search Framework for Code Generation with LLMs
Zhiyi Lyu'
Jianguo Huang'
Yanchen Deng
Steven Hoi
Bo An'
Nanyang Technological University
2 Alibaba Group
Abstract
Large Language Models (LLMs) with inference-time scaling techniques show promise for code generation, yet face notable efficiency and scalability challenges. Construction-based tree-search methods suffer from rapid growth in tree size, high token consumption, and lack of anytime property. In contrast, improvement- based methods offer better performance but often struggle with uninformative reward signals and inefficient search strategies. In this work, we propose ReLoc, a unified local search framework which effectively performs step-by-step code revision. Specifically, ReLoc explores series of local revisions through four key algorithmic components: initial code drafting, neighborhood code generation, candidate evaluation, and incumbent code updating, each of which can be instanti- ated with specific decision rules to realize different local search algorithms such Hill Climbing (HC) Genetic Algorithm (GA). Furthermore, we develop a specialized revision reward model that evaluates code quality based on revision distance to produce fine-grad fine-grained preferences that guide the local search toward more promising candidates. Finally, our extensive experimental results demonstrate that our approach achieves superior performance across diverse code generation tasks, significantly outperforming both construction-based tree search as well as the state-of-the-art emprovement-baseee code generation methods. The code is available SapattgooRReee /ReLoc.
at https:/ /tte:://gtttttt thub. com/ allaalpphaa alphatooo
1 Introduction
Large Language Models (LLMs) like GPT-4 (Achiam et al., 2023) and Claude (Wang et al., 2024a) have demonstrated remarkable capabilities in code-related tasks, including code generation (Chen et al., 2021; Austin et al., 2021), repair (Xia and Zhang, 2022; Jiang et al., 2023; Jin et al., 2023), and optimization (Shypula et al., 2023; Cummins al., 2023). However, when facing challenging tasks, their auto-regressive token generation process prohibits the use of additional computational resources achieve better performance (Yao et al., 2023; Snell et al., 2024). To fully unleash the power of LLMs, recent studies have focused on inference-time scaling techniques like construction-base search algorithms (Feng et al., 2023; Wang et al., 2024b), which incrementally build a nigh-quality full response via exploring tree of intermediate reasoning steps guided by a value model (Wang al., 2023) or a braseds-based Reward Model (PRM) (Lightman al., 2023).
tree-
Despite their potential, construction-batt tree-search methods suffer from a rapid increase in tree size and excessive token consumption the number of reasoning steps grows, which inevitably leads to insufficient exploration given a practical budget. Besides, these methods do not hold the anytime
CCorespondence to: ycdengontu. edu. ag
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

property (Zilberstein, 1996), since they cannot return a response until they find reasoning path from the root to a leaf in the search tree. In contrast, recent approaches (Li et al., 2024a; Light et al., 2024) that utilize multi-turn improvements (Zheng et al., 2024) on complete responses for code generation have shown promise. These multi-turn approaches explore series of local revisions on the code by feeding the execution feedback from public test cases (Xia et al., 2024) back to the LLM, which mirrors how humans iteratively refine code drafts and enjoys the anytime property.
However, the existing improvement-basee proaches still face significant challenges in efficiently finding high-quality codes (Olausson et al., 2023). First, many of those methods rely on ad-hoc reward functions (c.g., the pass rate on the public test cases or simply an L.M's self-evaluated score) to measure the code quality, which may fail to provide informative direction to guide the search process (ef. Figure 1). In more detail, since the number of public test cases is usually small ge.g., 2-3 test cases per task), the pass rate often collapse to binary signals (i.e., 0% 100%), offering little guidance in selecting promising code revisions.
ap-
Problem Krupactc Prophrs..
Code A: Greedy
Code DP
Correct Code
netadd
releol
"ol muugehort
If
"er innorreti
rallie (EEE-mott 1i1 4-
Lotan (IX
Pass Rato: 0%
?
Pass Rate: 0%
Interpreter
OO
Code 7/10
Code 5/10 Higher complesity
Time-efficient..
self-evaluation, on the other hand, is prone to hallucinations (Zhang et al., 2024a) and can mislead the search by inaccurately as- sessing a code revision's 's potential. Second, the ineffi- cient code revision generation and search algorithms exacerbate the token consumption. For example, the agentic methods (Li al., 2024a; Wang al., 2024a) exploit complex workflows which would consume a large number of tokens even over a few improvement iterations. Besides, search algorithms like Monte Carlo Tree Search (MCTS) (Li et al., 2024b) often re- quire significant number of improvement iterations to balance exploration and exploitation, leading to excessive computational overhead, e.g., running at least 50 iterations for comparable performance which consumes over 20,000 tokens on a single task. An extended discussion of related work is available in the Appendix.
LUM
Code contains
Code
approach.
Correct approach.
Revidan model
In the 0-1 Knapsack problem, the LLM favors an efficient but incorrect greedy solution (Code A) over a conceptually correct yet buggy DP version (Code B). As the tied pass rate offers no guidance, a revision reward model instead prioritizes candidates that are easier to revise into correct solutions.
Figure 1:
In light of this, we introduce a lightweight, unified local search framework for improvement- based code generation with LLMs. The core idea behind our approach is to explore the neighborhood of the incumbent code with simple-yet-effectve decision rules. To this end, we first frame the iterative improvement process within a local search framework with four key algorithmic components: initial code drafting, neighborhood code generation, candidate evaluation and incumbent code updating, Each component can be instantiated with a specific decision rule, allowing the development of different local search algorithms for code generation with LLMs. Furthermore, to facilitate candidate evaluation in each iteration, we develop specialized revision reward model tailored for local search which is trained to prefer the code with a smaller revision distance, i.e., the minimum number of revision steps required to transform it into a corrected version. Intuitively, instead of solely maximizing the pass rate on the public test cases which sometimes can be uninformative, our reward model works directly on the textual space and guides the local search to explore the codes close to the correct ones. Specifically, our main contributions are summarized as follows.
1) We propose ReLoc, a lightweight and unified local search framework for code generation. ReLoc can be effectively instantiated into different local search algorithms such as Hill Climbing (HC) (Russell and Norvig, 2016) and Genetic Algorithm (GA) (Mitchell, 1998) by implementing each algorithmic component with specific decision rule.
2) We develop a revision reward model trained with pairwise supervisions derived from revision distance comparisons. By constructing win/loss pairs based on which candidate is closer to the corrected code, we train the reward model using the Bradley-Terry framework (Bradley and Terry, 1952) produce fine-grained preferences that guide the local search toward promising candidates, even when explicit correctness signals are uninformative.
3) We conduct extensive experimental evaluations on popular code generation benchmarks including LiveCodeBench (Jain et al., 2024) and TACO (Li et al., 2023). The results demon-
2

---

strate that our local search approaches consistently outperform both construction-based tree- search methods and existing improvement based approaches, achieving a 33.8% % improvement in Pass I on LiveCodeBench and an 11.5% 15.33% gain on 'AACO over the strongest baseline, while reducing token consumption by 37 % (cf. Figure 4).
2
Preliminaries
Code generation tasks. A code generation task can be defined as a triple = (zi, U4, Ut) where where z; is the problem statement given in natural language, u, is set of public test cases, and v; is set of private test cases. A code sample is deemed correct it passes all test cases in both uN and v/- Given set of code generation tasks T = TN }, the performance of code generation policy
is measured by @ TT
where is the total number of codes sampled for (2)
each task with policy æ and oj is the number of correct code samples for task T; (Chen et al., 2021).
ceaprovement-basede code generation. The improvement-base code generation process can be formalized as an episodic Partially Observable Markov Decision Process (POMDP), defined by the tuple (8, A, O, p, T)). The state s, E S includes the code generation task T, the current code sample or, the execution feedback from public test cases f(a;; u) and the one from private test cases v(a; for each time step Particularly, the initial state so T. The action at E A is token sequence which constitutes code sample. The state transition function p S x A - S deterministically updates the state by evaluating the code sample d++1. yielding $t+1- The observation or E O is subset of st. consisting of (I,, uz). O and fa;; u), as the LLM can only access public test cases and the corresponding feedback. The reward function r assigns reward of if the last time step code sample ar passes all test cases, where T is the time horizon. The history 7t (Oo, 01, .1......0. 0t) captures the whole trajectory of actions and observations up to the t-th time step. Finally, the policy æ outputs code revision based on the history for each time step, i.e., ar+1 ~ (-IT.).
Local search. Local search (Pirlot, 1996) is an important class of heuristic methods to solve compu- lationally challenging optimization problems. Instead of systematically exploring the whole solution space, local search iteratively improves an incumbent solution by exploring its local neighborhood until given termination condition is met. Local search naturally enjoys the anytime property (Zilberstein, 1996), in the sense that it can return solution at anytime and the solution quality is monotonically non-decreasing over time by simply caching the best solution found so far.
3 Methodology
While existing improvement-basee methods offer the advantage of iterative code revision through multi-turn interactions, they suffer from two critical limitations: (1) inefficient exploration due to complex revision workflows that consume excessive tokens, and (2) inaccurate reward functions that provide limited guidance for selecting promising candidates. To address these challenges, we introduce lightweight and unified Revision Local Search (ReLoc) framework, which leverages decision rules to perform step-by-step code revision (cf. Figure 2). In Section 3. we elaborate the essentials and key algorithmic components of ReLoc. To address the limitations of prior ad-hoc evaluation heuristics, we further introduce a revision reward model trained to rank code candidates according to their revision distance in Section 3.2. Finally, show the flexibility and expressiveness of our ReLoc framework by implementing two well weollnnnown local search algorithms (i.e., Hill Climbing and Genetic Algorithm) in Section 3.3.
3.1 Local Search Framework
As shown in Algorithm 1, our ReLoc framework consists of four algorithmic components that can be instantiated with different decision rules: (1) DRAFTCODE, which generates an initial code sample population Po based on the problem statement x; and public test cases of code generation task Ta: (2) GENER ATE.HIIGOOOOOOOOO.., which constructs a set of neighborhood code samples P. by prompting the LLM propose new code revisions based on the history and the execution feedback
3

---

Problem x₁t Given two sorted arrays of size and respectivelyy return the median of the two armys..
Seare
02
4g
(1
d5
4/>
Input: [1.3)
Public
My
Outgut 2
Stup
</>
Input: [1.2]
EvalnateCandidates
Outgut 2.5
Draft Code
Incumbent Code
Candidate Code
Nobbie
</>
Local rogion of
laper sample
sample layer
XC
</>
MOO5 revbiou of
(a)
(b)
Figure 2: (a) Overview of the ReLoc framework. Starting from an initial draft code, ReLoc iteratively generates a neighborhood of candidate code samples around the current incumbent code. Each candidate assessed by the revision reward model. (b) Training the Revision Reward Model. A code tree is constructed by iteratively revising an initial incorrect code. Each code sample in the tree is labeled with its revision distance, i.e., the minimum number of revisions needed reach a correct version. Pairwise comparisons in local region create preference data.
which utilizes an interpreter and our
which assigns each candidate in current neighborhood Pt with score measuring its quality; and (4) UPDATEINCUMBENT, which implements the move strategy by selecting the next incumbent solution a, from the neighborhood P.. Finally, we maintain the best-so-far code sample a with score e" to enforce the anytime property.
from the public test cases; (3) EVALUUATECANDIDAA
Algorithm ReLoc: Revision local search framework for code generation with LLMs
Input: Code generation task T,, LLM n, iteration limit T
Output: Code sample a*
1: Po + generate initial code sample population with DRAFTCODE
2: Eg < evaluate code samples Po with EVALLATECCNNDIDATES
3: ag f select a code sample from Po with UPDATEINCUMBENT, a" + ag e² + E Eg(ao]
4: for 1,...,T do
5: Pt + generate neighborhood code samples with GENERATENEIGHIORIIOO
6: Eg + evaluate code samples Pt with CVALUATECANDIDAATES + select a code sample from P; with UPDATELNCUMBENT if [e(ed] > then
7:
8:
9:
a" t- ae E" + Es[ar]
return
3.2 Revision Reward Model
A key question in implementing ReLoc is how evaluate the quality of the generated code candidates (cf. EVALUAATECANDDDTTESS which determines the search direction for each iteration. As we will show in Section 4.2, simple heuristics like pass rate public test cases or M.LM- self-evaluation scores fail to effectively guide the search direction, since they often either collapse to binary signals or prone to hallucinations.
cnttoome-basel reward model (Shen and Zhang, 2024), the other hand, solely focuses on the correctness of the code samples rather than how likely an incorrect candidate will be revised into correct code in future steps, which is also not applicable to scenario.
Instead of directly assessing the correctness, we train a specialized revision reward model rank code samples according to their revision distance, i.e., the minimal number of revision steps required to transform into the correct version. This way, addition to prioritizing correct code samples, we also effectively differentiate incorrect ones and enable local search to focus promising candidates with smaller revision distance, thus guaranteeing the overall search efficiency even when the correctness signals are uninformative (c.g., 0% pass rate public test cases for all candidates).

---

To train our reward model, given a training task T,, we build special code tree (cf. Figure 2(b)) where the root an incorrect code ag sampled from the LLM policy. Then we incrementally expand the tree in a breadth-first fashion up to depth limit dmax. That is, for each incorrect code sample da-i in the (d 1)-th layer, we prompt the LLM to generate K code revisions for d-th layer:
k(j-1)*k ~ π (-IREVISE_PT) ad
E [e.....,K), K}.
(I)
where REVISE_ PT' is the prompt template instructing the LLM π to revise the code sample 4'-1 according to the problem statement 2; and execution feedback f( u,) on public test cases, and the generated code revision dd k(}-1)+k is then inserted to the tree as child of d2-1'
Once the code tree is built, recursively label the revision distance of each code sample in the tree according to the following rule:
0,
is correct;
Haaz =
00, + min aeCi(aa) 7(a), otherwise,
a is incorrect A Ch(a)) = 0;
(2)
where Ch(aa) is the children of a/j in the code tree. Note that a code sample is considered correct if and only it passes all public test cases W; and private test cases ry. After that, we proceed to build win/loss pairs of code samples and train our reward model with Bradley-Terry framework (Bradley and Terry, 1952; Ouyang et al., 2022). Particularly, we confine the comparison within a small region around code sample in the code tree reflect the locality of the local search. Specifically, for code sample d'y, we consider the following neighborhood code samples:
N(aa)) = (Pa(a))) UCh(d)) USib(a)))
where Pa(az) is its parent and Sib(a')) = fala E Ch(Pa(a)) Aa + dd) is the siblings of a'. Then for each code sample a' E (a(2)) with r(a2)) < <>(a"), we model the preference probability as
P(ay a'(xs) (Ro(ugla.)) (Ro())=((RR(((
Re((a(=.)).
where o-)) is the sigmoid function and R (z)) represents the learned reward score for code samples given problem statement z₁. The learning objective of the reward model is to maximize the expected prebbabbbbly::
max E (a a') log P(a > a'|x:)).
(5)
where the pair dataset is constructed by collecting the pairs of code samples in each code tree.
3.3 Case Study
To demonstrate the flexibility and expressiveness of our ReLoc framework, now present two well-known local search algorithms, i.e., Hill Climbing (HC) (Russell and Norvig, 2016) and Genetic Algorithm (GA) (Mitchell, 1998) for improvement-basee code generation with LLMs by instantiating each algorithmic component with specific decision rules.
DRAFT CODE. It is widely acknowledged that the quality of the initial solution has significant impact on the performance of local search (Lourenço et al., 2018). Therefore, to guarantee the quality of the initial code sample population Po. we adopt the LLM to enumerate N diverse natural language plans that outline different algorithmic strategies. Then for each plan, we prompt the LLM synthesize a corresponding code implementation, forming a candidate pool Pa = (a.....,
-hen-Gene paradigm by firstly prompting
a
GENERATENNEGHHOOROOO For each iteration t, we generate neighborhood code samples Pt according to the following rules.
Hill Climbing, Given the incumbent code sample a and the feedback far-1;; from public test cases us we generate the neighborhood code revisions by first prompting the
5

---

LLM to propose K natural language revision strategies Q₁ = . condition logic", "refactor loop"). Then for each strategy q., we prompt the LLM क to generate candidate code revision:
... of (e.g.. "fix
P. = {a] (a.....,aE)
N~ ( (-1 (I;, at-1
(;); (;),
(6)
where HC_PT is the prompt template instructing the LLM to generate a code revision based on problem statement 24, previous code a;-1, execution feedback f(a--1: u,) and revision strategy q².
Genetic Algorithm. For each iteration t > 1, we select two parent code samples a, a' from the history (ao...., ax-1) according to their fitness, i.c.. the scores evaluated by EVALUATECANDIDATT Particularly, we select parent code samples from Po when Then we prompt the LLM to generate K new candidates:
{at ... af df ~~ x 1 GA (æi, a, fla; u.), f(a's u))))
(7)
where GA_PT is the prompt template instructing the L.LM generate a code revision by combining the strengths or addressing the shared weaknesses of the parent code samples. To maintain diversity, we also implement an aging mechanism where each code sample disqualified from being selected as parent after it has been used in this role 3 times.
To evaluate the candidate code samples Pt, we propose a synergistic approach that leverages both public test cases and the learned revision reward model. Let P pass {a E Pt f(a; u.) pass} be the subset of candidates that pass all public test cases. Then, the evaluation score candidate is defined as:
EVALUATE CANDIDATES.
Ro(als), Ro(alz;), -0,
if passs 0; if E Ppussi otherwise.
Eg
(8)
That is, when no candidate passes all public tests, we fall back to using the reward model R& to score all candidates. If there are successful candidates, we score them using Rg, while assigning the rest with score of coo This way, we provide fine- fine-grained preferences that guide the local search toward promising candidates by explicitly differentiating the candidates with the same correctness signal.
UPDATELNCUMBENT Given the current code samples Pt and the corresponding evaluation scores, UPDATEINCUMBEN aims to select a code sample as the incumbent solution for iteration t. Tech- nically, decision rules like e-greedy, Boltzmann distribution (Landau and Lifshitz, 2013) or more complex simulated annealing acceptance rule (Delahaye et al., 2018) can be applied. Here we choose to greedily select the one with the maximum evaluation score for simplicity and efficiency, i.e., a, arg max [a], where ties are broken alphabetically.
4 Experiments
In this section, we present extensive empirical evaluations to demonstrate superiority across diverse code-related tasks. Our experiments aim to answer the following research questions:
RQ1: How well do our local search methods perform on code-related tasks compared to state-of-the-art construction-based and improvement-based approaches?
RQ2: Can our proposed revision reward model provide more effective guidance for local search than heuristic rewards or catcome-basee reward model?
RQ3: How does the performance of our local search methods scale with increasing token budgets at inference time?
RQ4: What are the individual contributions of planning, revision strategies, and execution feedback to the overall performance of our local search methods?
? All prompt templates provided in the Appendix.

---

Table 1: Pass@ accuracy (%) of different methods the LiveCodeBench and TACO benchmarks.
All methods are evaluated under the same token budget (7K) to ensure fair comparison. Methods are categorized construction- (Con.) improvement- beaded (Imp.), and further distinguished by reward functions: PRM (9o), self-evaluation ( ),, pass rate and revision reward model (2)).
Methods
Cat.
Rew.
LiveCodeBench
TACO
Code gen
Code repair
Code gen
Code repair
RAP
Con.
22.9
21.2
5.4
4.1
TOT
Con.
25.6
20.4
6.8
3.7
Code Tree
Imp.
27.7
24.1
8.2
5.6
Reflexion
Imp.
25.6
23.9
7.1
6.1
Plan Search
Imp.
32.7
31.3
11.2
8.2
BoN
Imp.
30.2
30.5
10.8
6.3
SFS
Imp.
32.1
27.3
10.5
8.1
ORPS
Imp.
28.8
26.6
9.8
7.8
ReLoc HC (Ours)
Imp.
38.4
33.4
13.3
9.7
ReLoc_GA (Ours)
Imp.
35.7
29.9
15.3
11.5
4.1 Experimental Setup
Benchmarks. We evaluate methods two benchmarks: LiveCodeBench (Jain al., 2024), using 511 problems from May 2023-May 2024 for training and 268 problems from Jul 2024-Jan 2025 for testing; and TACO (Li et al., 2023), which aggregates problems from CodeContests, APPS (Hendryeks et al., 2021), and other sources. From TACO's original 25,443 training and 1,000 test problems, we randomly sample 4,000 and 200 respectively due computational constraints. Both datasets provide 2-3 public test cases per problem. For code repair, we construct a buggy-code dataset by sampling incorrect solutions from diverse models (Qwen2. (0een2.5-7B/32///T7 GPT-4o) to ensure range of error types and complexities.
Implementation details. Our base model through- out the experiments is Qwen2.5-32B. Instruct. During training, we use the training splits of Live- CodeBench and TACO to construct code revision pairs as described in Section 3.2, where expand code trees via breadth- fiist search up to a maximum depth of dmaz 5, with K 3 revisions per node. These pairs are used to train a specialized revision reward model based on Qwen2. S--B-Instruct, fol- lowing the reward modeling procedure from (von Werra et al., 2020). The distribution of pairwise com- parisons is shown in Figure 3. For inference, we adopt decoding settings consistent with (Jain et al., 2024), using temperature of 0.2 and top-p of 0.95. To ensure fair comparison across all methods, fix the token budget to 7K tokens per problem. Additional implementation and training details are provided in the Appendix.
Distribution of Pair Samples
TACO
LCB
Number of Pairs
Revision Distance Difference
Figure Distribution of 872K training pairs by revision distance difference (y(los)) ((wn)).
Baselines. We compare our methods with the following approaches. (1) Construction- approaches like ToT (Yao et al., 2023) and RAP (Hao et al., 2023), which build solutions via search (BFS MCTS); (2) Improvement-based methods with self-evaluation. which leverage internal ussessment mechanisms to guide search, such as CodeTree (Li et al., 2024a) and Reflexion (Shinn al., 2023), which use multi-agent evaluation or test case generation with reflective learning; and WannanndSSearch (Wang et al., 2024c), which prompts LLMs to search among candidate solution plans expressed in natural language. (3) Improvement-
methods with pass rate, which utilize performance public test cases to provide reward signals, including Best-of-N (BoN) (Cobbe et al.,

---

2021), which randomly samples N solutions and filters according to the pass rate; SFS (Light et al., 2024), which employs MCTS to revise code using pass rate as the reward function; and OPRS (Yu et al., 2024), which combines self-scoring and pass rate to guide beam search.
4.2 Empirical Results
Performance comparison. We systematically compare local search methods against state- of-the-art baselines and present the results in Table 1. It can be concluded that ReL.o consistently outperforms all baseline methods across both LiveCodeBench and TACO benchmarks the Pass fass@1 metric. Specifically, Rel.oe_He _C achieves the best performance of 38.4% % and 33.4% on Live- CodeBench, while ReLoc_ GA reaches 15.3% and 11.5% on TACO. It is interesting to find that ReLoc_ HCC outperforms ReLoc_ Ba on the easier LiveCodeBench benchmark, while the reverse is observed on the more challenging TACO tasks. This phenomenon highlights the distinct merits of each algorithm: ReLoc HC is particularly effective for straightforward tasks where the underlying solution is relatively obvious and the primary challenge lies in fixing minor bugs or syntax errors, while ReLoc GA excels in more complex scenarios by strategically integrating the advantages from parent code samples to discover non-trivial solutions for conceptually challenging tasks in TACO.
Compared to construction-bast performance under the same computational budget, thanks to the anytime property of local search algorithms. On the other hand, improvement-basee methods with self-evaluation often are prone to hallucinations, leading to unreliable assessments of code quality. While such methods can be somewhat effective for guiding high-level search, as evidenced by Plan Search, they cannot fully leverage the detailed execution feedback. Unlike Plan Search that explores high-level strategies in an abstract plan space, ReLoc implements fine- grained planning and code-level revision, achieving an average improvement of 4.9 % over Plan Search on Code gen tasks.
methods like ToT and RAP, ReL.oc exhibits significantly superior
Finally, the improvement-base basded techniques using pass rates from public test cases struggle with sparse binary reward signals, which also offer insufficient guidance for search. SFS-based MCTS methods require extensive exploration with high computational costs, while ORPS employing beam search suffers from low exploration efficiency, unable select the most promising code candidates. ReLoc adeptly navigates these challenges through lightweight decision rules, guided by revision reward model, achieving an average improvement of 5.6 % over pass rate-based methods across different tasks.
Effectiveness of revision reward model. To evaluate the effectiveness of our revision reward model when guiding local search, we conduct controlled experiments on LiveCodeBench and TACO on ReLoc HC with different reward functions. Specifically, five basclines: public test case pass rate, LLM- -MMggeeertedd test case pass rate, LLM self-evaluation, Skywork-27B reward model (Liu al., 2024), and ORM-7B, i.e., outcome-based reward model trained with the same architecture as the revision reward model (Qwen2.5-79)
compare revision reward model against
As shown in Table 2, pass rate and self-evaluation heuristics offer weak guidance. That is not surprising because execution-based scores are often coarse or binary, while self-evaluated scores often suffer from hallucinations, leading to unreliable rankings. In contrast, methods using a reward model perform better, with our revision reward model outperforming ORM by 35.9%=33.4 % and 9.7%->13.8 % on LiveCodeBench and TACO. We attribute this to the ability of the revision reward model to differentiate incorrect candidates based on their likelihood of future correction, which is a property the ORM lacks due to its exclusive focus on code correctness.
Inference-time scaling law. To further evaluate the scaling performance of ReLoc_ with increasing computational resources, we vary the token budget from 1K to 15K. We compare our method against three representative baselines: BoN, ORPS, and ToT. Figure 4 illustrates the scaling behavior of different methods on the LiveCodeBench and TACO benchmarks. Notably, as the token budget increases, ReLoc_HC demonstrates a faster improvement in terms of Pass @ 1, highlighting the benefit of guided local search and our learned revision reward model. This is particularly evident in the LiveCodeBench, where Rel.oe_ HC reaches over 40% Pass under 1 15K token budget, outperforming the BoN with the same budget by significant margin.
8

---

Table 2: Pass@1 accuracy of ReLoc_ HC with different reward functions under 7K token budget. Our revision reward model achieves the highest Pass@) on both LiveCodeBench and TACO, demon- strating strong inference-time performance without relying test case generation self-evaluation.
Reward Function
Gen Test Case
Self Score
Reward Model
LiveCodeBench
TACO
Pass Rate
X
33.5
10.3
w/ Gen Test case
29.0
8.4
Self Evaluation
29.3
Skywork-27B
X
X
V
31.9
9.4
ORM-7B
X
X
V
35.9
9.7
Revision Reward Model (Ours)
38.4
13.3
Scaling Law LiveCodeBench
Scaling Law TACO
40
BoN
BoN
ReLoc_Ho [Ours)
ReLoc_HC
ORPS
ORPS
Pass@1 (9)
36
Pass@11 (%6
28
24
3K
SK
10K
15K
1K
5K
7
10K
15K
Token Budget
Token Budget
Figure 4: Scaling Law. Pass@ accuracy of ReLoc_HH (Ours) compared to baselines (BoN, ORPS, ToT) on LiveCodeBench and TACO benchmarks token budget increases from IK 15K.
Table 3: Ablation study of ReLoc We evaluate the impact of core components in both ReLoc HC
and ReLoc GA. Removing natural language plans, revision strategies, or execution feedback.
LiveCodeBench
TACO
Method
Pass @ (%)
Tokens (1K)
Pass@ (%)
Tokens (1K)
ReLoc_HE
38.4
7.1
13.3
7.6
w/o Natural Language Plans
36.9
6.5
13.7
7.1
w/o Revision Strategies
35.9
4.7
11.7
5.5
w/o Execution Feedback
34.8
7.5
11.4
7.7
ReLoc_Co _G
35.7
6.8
15.3
7.7
w/o Natural Language Plans
34.3
4.9
12.9
6.6
w/o Execution Feedback
34.6
5.8
13.5
6.8
Ablation study. We conduct ablation study on both ReLoc HC and ReLoe_Ga to assess the importance of each design choice. As shown in Table 3, removing natural language plans during initialization and replacing them with randomly sampled code reduces performance. Notably, eliminating revision strategies significantly reduces the number of generated tokens (e.g., from 7.1K to 4.7K in ReLoc_HC), However, this also limits the diversity of candidate code samples explored during the search, ultimately resulting in inferior performance. Furthermore, execution feedback plays particularly crucial role, as it enables precise and targeted revision in each iteration, improving the overall Pass @ accuracy by 2.1%.

---

5 Conclusion
In this work, we present ReLoc, a lightweight and unified local search framework for improvement- based code generation with LLMs. Unlike computationally expensive construction-basee inference- time scaling methods like ToT and MCTS, ReLoc finds high-quality solutions and enjoys the anytime property by exploring series of local revisions of an established code sample. Besides, compared to the existing improvement-basee
methods, ReLoc leverages simple yet effective decision rules to navigate the search space. Furthermore, specialized revision reward model effectively differentiates code samples based on the potential of each code sample being corrected in future steps, which provides tine-griieed preferences when the correctness signal is uninformative. Finally, show the flexibility and expressiveness of ReLoc by developing two well-known local search algorithms, i.e., Hill Climbing and Genetic Algorithm. Extensive experiments on benchmarks like LiveCodeBench and TACO validate the effectiveness of ReLoc in significantly improving code generation performance while reducing computational cost.
Acknowledgments
This research is supported by the RIE2025 Industry Alignment Fund - Industry Collaboration Projects (IAF-ICP) (Award 12301 (3006,,,,), administered by A STAR, as well as supported by Alibaba Group and NTU Singapore through Alibaba-NTU Global e-Sustainability CorpLab (ANGEL).
References
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Iige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. GPT-4 technical report. arXiv preprint arXiv:2303.0m 08774, 2023.
Xingyao Wang, Boxuan Li, Yufan Song, Frank F Xu, Xiangru Tang, Mingchen Zhuge, Jiayi Pan, Yueqi Song, Bowen Li, Jaskirat Singh, et al. Openhands: An open platform for Al software developers as generalist agents. In ICLR, 2024a.
Mark Chen. Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph. Greg Brockman, et al. Evaluating large language models trained code. arXiv preprint arXiv:2107.03377 003347440033 2021.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoe Le. et al. Program synthesis with large language models. arXiv preprint arXiv:2108.05 10773220 2021.
Chunqiu Steven Xia and Lingming Zhang. Less training, more repairing please: Revisiting automated program repair via zero-shot learning. In ESEC/FSE, pages 959-971, 2022.
Nan Jiang, Kevin Liu, Thibaud Lutellier, and Lin Tan. Impact of code language models on automated program repair. In ICSE, pages 1430-1442, IEEE, 2023.
Matthew Jin, Syed Shahriar, Michele Tufano, Xin Shi, Shuai Lu, Neel Sundaresan, and Alexey Svyatkovskiy. Inferfix: End-to-end program repair with LLMs. In ESEC/FSE, pages 1646-1656, 2023.
Alexander Shypula, Aman Madaan, Yimeng Zeng, Uri Alon, Jacob Gardner, Milad Hashemi, Graham Neubig, Parthasarathy Ranganathan, Osbert Bastani, and Amir Yazdanbakhsh. Learning performance-imprroing code edits. arXiv preprint arXiv:2302.07867, 2023.
Chris Cummins, Volker Seeker, Dejan Grubisic, Mostafa Elhoushi, Youwei Liang, Baptiste Roziere, Jonas Gehring, Fabian Glocckle, Kim Hazelwood, Gabriel Synnaeve, et al. Large language models for compiler optimization. arXiv preprint ar XrXi::2309 07002, 2023.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36: 16:111809-1188 11822, 2023.
10

---

Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling LLM test-time compute optimally can more effective than scaling model parameters. arXiv preprint arXiv:2408.03314, 2024.
Xidong Feng, Ziyu Wan, Muning Wen, Stephen Mareus McAleer, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero- like tree-search can guide large language model decoding and training. arXiv preprint wixi:2309..7779, 2023.
Chaojie Wang, Yanchen Deng, Zhiyi Lyu, Liang Zeng, Jujie He, Shuicheng Yan, and Bo An. Q#: Improving multi-step reasoning for LLMs with deliberative planning. arXiv preprint arXiv:2406. 14283, 2024b.
Peiyi Wang, Lei Li, Zhihong Shao, RX Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce LLMs step-by-step without human annotations. arXiv preprint arXiv:2312.008933 2023.
Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In ICLR, 2023.
Shlomo Zilberstein. Using anytime algorithms in intelligent systems. Al Magazine, 17(3))73-73, 1996.
Jierui Li, Hung Lc, Yingbo Zhou, Caiming Xiong. Silvio Savarese, and Doyen Sahoo. Code- tree: Agent-guides -uideeuuddddddd tree search for code generation with large language models. arXiv preprint UrXiv:2411.04322 2024a.
Jonathan Light, Yue Wu, Yiyou Sun, Wenchao Yu, Xujiang Zhao, Ziniu Hu, Haifeng Chen, Wei Cheng, et al. Scattered forest search: Smarter code space exploration with LLMs. arXiv preprint arXiv:2411.05010, 2024.
Kunhao Zheng, Juliette Decugis, Jonas Gehring, Taco Cohen, Benjamin Negrevergne, and Gabriel Synnaeve. What makes large language models reason (multi-turn) code generation? arXiv preprint arXiv:2410.08100 2024.
Chunqiu Steven Xia, Yinlin Deng, Soren Dunn, and Lingming Zhang. Agentless: Demystifying LLM-based software engineering agents, arXiv preprint arXiv:2407.01489, 2024.
Theo X Olausson, Jeevana Priya Inala, Chenglong Wang, Jianfeng Gao, and Armando Solar-Lezama. Is self-repair silver bullet for code generation? arXiv preprint arXiv:2306. 09896, 2023.
Xiaoying Zhang, Baolin Peng, Ye Tian, Jingyan Zhou, Lifeng Jin, Linfeng Song, Haitao Mi, and Helen Meng. Self-alignment for factuality: Mitigating hallucinations in LLMs via self-evaluation. arXiv preprint arXiv:2402.09267, 2024a.
Qingyao Li, Wei Xia, Kounianhua Du, Xinyi Dai, Ruiming Tang, Yasheng Wang, Yong Yu, and Weinan Zhang. RethinkMCTS: Refining erroneous thoughts in monte carlo tree search for code generation. arXiv preprint arXiv:2409.095: 095844 2024b.
Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. pearson, 2016.
Melanie Mitchell. An Introduction to Genetic Algorithms. MIT press, 1998.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324 345, 1952.
Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang. Armando Solar-Lezama, Koushik Sen, and lon Stoica. Livecodebench: Holistic and contamination free evaluation of large language models for code. arXiv preprint 2403:0440,,,7744, 2024.
Rongao Li, Jie Fu, Gen Zhang, Tao Huang, Zhihong Sun, Chen Lyu, Guang Liu, Zhi Jin, and Ge Li. TACO: Topics in algorithmic code generation dataset. arXiv preprint arXiv:2312.14885 2023.
Mare Pirlot. General local search methods. European Journal of Operational Research, 92(3): 493-511, 1996.
11

---

Wei Shen and Chuheng Zhang. Policy filtration in rlhf to fine-tune Ilm for code generation. arXiv preprint arXiv:2409.06955 069.099906997.. 2024.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. In NeurlPS, pages 27730-27744 2022.
Helena Ramalhinho Lourenço, Olivier C Martin, and Thomas Stützle. Iterated local search: Frame- work and applications. In Handbook of Metaheuristics, pages 129-168. Springer, 2018.
Lev Davidovich Landau and Evgenii Mikhailovich Lifshitz. Course of Theoretical Physics. Elsevier, 2013.
Daniel Delahaye, Supatcha Chaimatanan, and Marcel Mongeau. Simulated annealing: From basics to applications. In Handbook of Metaheuristics, pages 1-35. Springer, 2018.
Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, et al. Mcasuring coding challenge competence with APPS. arXiv preprint arXiv:2105.0990 2021.
Leandro von Werra, Younes Belkada, Lewis Tunstall, Edward Beeching, Tristan Thrush, Nathan Lambert, Shengyi Huang, Kashif Rasul, and Quentin Gallouédec. TRL: Transformer reinforcement learning. https: //gi thub. com/ http///ggggggg/////eeeee tr1, 2020.
Shibo Hao, Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model. arXiv preprint arXiv:2305.14999 2023.
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. NeurlPS, 36:8634-86633 2023.
Evan Wang, Federico Cassano, Catherine Wu, Yunfeng Bai, Will Song, Vaskar Nath, Ziwen Han, Sean Hendryx, Summer Yue, and Hugh Zhang. Planning in natural language improves LLM search for code generation. arXiv preprint arXiv:2409.037333 2024c.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reicchrr Nakano, al. Training verifiers solve math word problems. arXiv preprint arXiv:21 1121110.1440 14168, 2021.
Zhuohao Yu, Weizheng Gu, Yidong Wang, Zhengran Zeng, Jindong Wang, Wei Ye, and Shikun Zhang Outcome-refining process supervision for code generation. arXiv preprint arXiv:2412.151188 2024.
Chris Yuhao Liu, Liang Zeng, Jiacai Liu, Rui Yan, Jujie He, Chaojie Wang, Shuicheng Yan, Yang Liu, and Yahui Zhou. Skywork-reward: Bag of tricks for reward modeling in LLMss. arXiv preprint arXiv:2410. 184551, 2024.
Shuai Lu, Daya Guo, Shuo Ren, Junjie Huang, Alexey Svyatkovskiy, Ambrosio Blanco, Colin Clement, Dawn Drain, Daxin Jiang, Duyu Tang, et al. Codexglue: A machine learning benchmark dataset for code understanding and generation. arXiv preprint arXiv: 222.1022244620 04664, 2021.
Fenia Christopoulou, Gerasimos Lampouras, Milan Gritta, Guchun Zhang, Yinpeng Guo, Zhongqi Li, Qi Zhang, Meng Xiao, Bo Shen, Lin Li, et al. Podgr- Program synthesis with function-level language modeling. arXiv preprint 220. 2022.
Daya Guo, Qihao Zhu, Dejian Yang, Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Yu Wu, YK Li, et al. DeepSeck-Codee When the large language model meets programming-the rise of code intelligence. arXiv preprint arXiv:2401. 14196, 2024.
Binyuan Hui, Jian Yang, Zeyu Cui, Jiaxi Yang, Dayiheng Liu, Lei Zhang, Tianyu Liu, Jiajun Zhang, Bowen Yu, Keming Lu, et al. Qwen2. 5-coder technical report. arXiv preprint arXiv:2409.122 12186, 2024.
Andy Zhou, Kai Yan, Michal Shiapentokh-Rothmanlt Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning acting and planning in language models. arXiv preprint T.Xiv:2310.04406, 2023.
12

---

Li Zhong, Zilong Wang, and Jingbo Shang. Debug like a human: A large language model debugger via verifying runtime execution step-by-step. arXiv preprint arXiv:2402.16906, 2024.
Kechi Zhang, Jia Li, Li, Xianjie Shi, and Zhi Jin. Codeagent: Enhancing code generation with tool-integrated agent systems for real-world repo-level coding challenges. arXiv preprint arXiv:2401.07339, 2024b.
Daoguang Zan, Zhirong Huang, Ailun Yu, Shaoxin Lin, Yifan Shi, Wei Liu, Dong Chen, Zongshuai Qi, Hao Yu, Lei Yu, et al. Swe-bench-java: A github issue resolving benchmark for java. arXiv preprint arXiv:2408, 14354, 2024.
Harrison Lee, Samrat Phatale, Hassan Mansoor, Thomas Mesnard, Johan Ferret, Kellie Lu, Colton Bishop, Ethan Hall, Victor Carbune, Abhinav Rastogi, al. Rlaif rlhf: Scaling reinforcement learning from human feedback with ai feedback. arXiv preprint arXiv:2309.0026; 2023.
Zhenru Zhang, Chujie Zheng. Yangzhen Wu, Beichen Zhang, Runji Lin, Bowen Yu, Dayiheng Liu, Jingren Zhou, and Junyang Lin. The lessons of developing process reward models mathematical reasoning. arXiv preprint arXiv:2501.0730/ 2025.
Jinhao Jiang, Zhipeng Chen, Yingqian Min, Jie Chen, Xiaoxue Cheng, Jiapeng Wang, Yiru Tang, Haoxiang Sun, Jia Deng, Wayne Xin Zhao, et al. Technical report: Enhancing Ilm reasoning with reward-guided tree search. arXiv preprint 2rXiv:2411.I1 16694, 2024.
Dakota Mahan, Duy Van Phung, Rafael Rafailov, Chase Blagden, Nathan Lile, Louis Castricato, Jan-Philipp Fränken, Chelsea Finn, and Alon Albalak, Generative reward models. arXiv preprint arXiv:2410.12832. 2024.
Nat McAleese, Rai Michael Pokorny, Juan Felipe Ceron Uribe, Evgenia Nitishinskaya, Maja Trebacz, and Jan Leike. Llm crities help catch Ilm bugs. arXiv preprint arXiv:2407.002155 20244
Lunjun Zhang, Arian Hosseini, Hritik Bansal, Mehran Kazemi, Aviral Kumar, and Rishabh Agarwal. Generative verifiers: Reward modeling as next-token prediction. arXiv preprint arXiv:2408. 15240, 2024c.
Xiusi Chen, Gaotang Li, Ziqi Wang, Bowen Jin, Cheng Qian, Yu Wang, Hongru Wang, Yu Zhang, Denghui Zhang, Tong Zhang, et al. Rm-rl: Reward modeling as reasoning. arXiv preprint arXiv:2505.02387, 2025.
13

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificcton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Both the abstract and introduction sections outline our research scope, method- ology, motivations, experimental findings, and key contributions. Refer Section I
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
14

---

Justification: In our work on ReLoc, due to limited resources, we did not utilize more powerful models like 2een2.5-22-iinstruee train the revision reward model. Additionally, we only explored two different local search algorithms. Please refer to the appendix for more details.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well vell-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [NA]
Justification:
This paper does not include assumptions and proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We introduce all details of our method in Section 4.1 and appendix.
15

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We submit our code and data as supplemental materials. We provide instruc- tions that contain the exact command and environment needed to reproduce the results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ /nips. fisisscoo wttpccccppccccceeeccccecccccccet httplii//ggie////ee/ee iodeeSumiissioooolll wwwssssssiioooooso for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
16

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We specify all demonstration selection and test details the Section 4.1. The full details can be found in code, which be provided as supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report average results and standard deviation illustrate the statistical significance our method Figure
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Detailed compute resource specifications are provided in the appendix.
Guidelines:
17

---

The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / tttp:://eerrss..cppbiiic////e ctwcchiiihiiieeeeeeee.e
Answer: [Yes]
Justification: We confirm that our work fully complies with the NeurlPS Code of Ethics in all respects.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e-g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This research aims advance the fields of large language models and code generation. While our work may have various societal implications, we have chosen not to emphasize any specific impacts within the scope of this paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
18

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The models and datasets presented in this paper are publicly accessible via HuggingFace and GitHub
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We cite the original paper that produced the code package or dataset,
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This work does not release assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
19

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We do not use LLMs for developing our core idea and methodology.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to LLM policy (https: //tpeeien....//// co//onnferecce///00000 for what should or should not be described.
20

---

A Related Work
Code Generation with Large Language Models. Recent advances in large language models (LLMs) have significantly boosted code generation by leveraging pretraining large-scale code corpora (Lu et al., 2021; Christopoulou et al., 2022; Guo et al., 2024; Hui et al., 2024). At inference time, two main strategies have emerged further enhance performance. Construction-baan generate solutions step-by-step, often guided by value models (Yao et al., 2023; Wang et al., 2024b), process-based reward models (Lightman al., 2023), planning techniques like Monte Carlo Tree Search (Hao et al., 2023; Zhou et al., 2023). In contrast, improvement based approaches iteratively refine full code drafts using multi-turn updates, agentic workflows (Wang al., 2024a: Zhong et al., 2024; Zhang et al., 2024b), and test-time feedback, sometimes with multi-agent collaboration (Li al., 2024a; Zan et al., 2024). While effective, many of these methods are resource- intenssvve and complex. Our work introduces lightweight local search framework that streamlines key components into an efficient and scalable loop.
methods
Reward Models. Reward models play a central role in RLHF (Ouyang et al., 2022), providing learning signals for policy optimization. To reduce dependence on human-labeled data, RLAIF (Lee et al., 2023) proposed an automated reward data pipeline. More recently, reward models have been extended to reasoning tasks. Math-Shepherd (Wang al., 2023) and others (Zhang al., 2025) trained process- process-based reward models to guide inference- time strategies, while outcome-basee models have supported tree search (Jiang et al., 2024). Generative Reward Models (GRMs) (Mahan et al.. 2024; McAleese et al., 2024; Zhang et al., 2024c; Chen et al., 2025) further leverage CoT- based self-critique for scoring outputs. Distinct from these paradigms, we propose a reward model trained to estimate revision distance, capturing the minimal steps needed to reach correct solution. This enables more efficient candidate evaluation and improves the effectiveness of iterative code refinement.
B Experimental Setup.
B.1 Revision Reward Model
This section outlines the hyperparameters and settings used during the training phase of the revision reward model. We trained the revision reward model on Qwen2.5 library (von Werra et al., 2020) with DeepSpeed ZeRO Stage on NVIDIA H100 GPUs. The training was conducted for one epoch on a combined dataset of LiveCodeBench and TACO. Table details the training configuration.
using the TRL
Table 4: Revision reward model training Configuration
Parameter
Value
Mixed Precision
6
Batch Size per Device
8
Number of Epochs
1
Gradient Checkpointing
True
Learning Rate
5.0e-6
Logging Steps
25
Evaluation Strategy
Steps
Evaluation Interval
Every 500 steps Every 3000 steps
Save Interval
Max Sequence Length
2048
Push to Hub
False
Optimizer Warmup Ratio
paged_adanne adamaaaaaa222 32bit
0.05
Learning Rate Scheduler
Cosine
Number of GPUs
4 x NVIDIA H100
21

---

B.2 Local Search Hyperparameters
We use (xee22.-32B--. -SB-IInstuct as the inference model throughout all experiments. with decoding temperature of 0.2 and top-p value of 0.95. All algorithms are run under a fixed token budget of 7,000 tokens per task.
For Hill Climbing (HC), we initialize with draft codes and expand 3 neighbors for each candidate during each improvement iteration.
For the Genetic Algorithm (GA), we similarly maintain a population draft codes. In each iteration, we select 2 codes from the candidate pool as parent codes, with each code allowed to be selected as a parent up times.
C Additional Evaluation on GPT-4o
To further validate the effectiveness of RELOC, conduct experiments the closed-source model gpt-4o-2024-1120 Specifically, we evaluate RELOC and several baselines, including the state-of-
the-art Plan Search algorithm and Best o N sampling, on the LIVECODEBENCH benchmark. For RELOC, we employ the revision reward model trained as described in Section B. to guide the search process.
In our evaluation, the revision reward model guiding RELoc's local search was trained entirely on data sampled from the open-source Qwen2. 5-22.5-32B-- Instrrutt model, setting that differs in both distribution and model family from the target inference model, GPT-4o. Remarkably, as shown in Table 5, RELoc achieves the highest Pass @ score (44.2%) while consuming only 8.7K tokens average-reeresentinee representing a 52% reduction in token usage compared to Plan Search. This underscores the efficiency of RELOC's local search mechanism.
More importantly, these results demonstrate that revision reward model, trained on Qwen- generated code trajectories, generalizes robustly to guide search on GPT-4o. This transferability is non- trivial: GPT-4o may exhibit different stylistic tendencies, error patterns, and semantic representations compared to Qwen2.5-321 Yet, the reward model still provides reliable signals for ranking candidate revisions, suggesting that it captures model-agnostic features of code quality-such as syntactic closeness correct solutions, functional coherence, and local editability.
Such robustness distributional shifts suggests broader applicability of our approach. It indicates that RELOC, and particularly its reward model component, can serve as plug-and-plaay module to improve inference-time performance across diverse LLMs, without the need for costly re-annotation or model-specific retraining. This is particularly valuable for deployment in scenarios involving closed-source or frequently updated models, where direct supervision signals or fine-tuning access unavailable.
Table 5: Performance comparison on GPT-4o (gpt-40-2024--122)
Methods
Rew.
Pass 1 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
22

---

D Prompts
Table 6: Write diverse observations based on the problem guide the generation of draft code.
Attribute
Description
DRAFTCODE
You are an expert Python programmer. You will be given competitive programming question (problem specification). You will return 5 useful, non-obvious, and correct observations about the problem, like hints solve the problem. You will NOT return any code. Be as creative as possible, going beyond what you think is intuitively correct. For each observation should be between tag [OBSERVATION] and [/OBSERVATION]. [OBSERVATION]
Outputs
Observation 1: A permutation can be fixed with at most one swap if and only if it has most 2 inversions.
[OBSERVATION]
IOBSERVATION Observation Only 3-cycles (like "bea" and "cab") cannot be solved with a single swap operation. [OBSERVATION]]
Table 7: ReLoc HC generates diverse modification strategies for incumbent code
Attribute HC_NEIGHBOR
Description
You are an expert in debugging Python code. You will be provided with a code snippet that requires debugging, along with a revision history for reference. Your task is to begin by writing brief textual explanation of the current code summarizz its intended behavior and any evident issues between [explanation] and [/explanation]. Next, propose three refinement directions that could help improve the code. Please put each direction between tag [direction] and [/direction]. Important: Do not include any Python code in your responsc-only the explanation and the three refinement directions.
Outputs
[explanation]
The feedback indicates that the main issue is the function returns only the first element of min-k and max-k, instead of the entire lists.
//explnaatio]
[direction]
Modify the return statement to return the full min-k and max-k lists. [/direction]
[direction]
Include input validation to ensure K is non-negative integer. [direction]]
23

---

Table ReLoc HC revises code according different strategies
Attribute HC ME_NERIBBOR
Description
You are helpful programming assistant and expert in Python. The user has written code that contains errors. You will be provided with a Python programming problem, the user's code, revision history, explanation, and directions for refinement. Your task is to debug and revise the code to conrectly solve the problem. Generate corrected version of the complete program, incorporating the explanation, refinement directions, and revision history. Output only one corrected program enclosed within single pair of code delimiters. Do not include any additional commentary or text.
Outputs
def minimumBoxes aappleppcck, box_ cox_ccpacities): for box caxacityy in box_capacin current_capacity cox_capacities:
box_capacity
boxes_used +=
if purrent_capacit) >= total_apples:
return boxes_ used return goxes_used
apple_packs = [1, 3, 2]
box_catacities [4, 3, 5, 2] print (oainimmummss appllppackk, box_ cox_ciitct)))s)
apple_packs - [6, 5, 5]
box_capacities [2, 4, 7]
print (minimumBoxes (applel
box_capacities)
Table 9: ReLoc_Ge GA directly prompts LLM to generate neighborhood by referencing parent code
Attribute
Description
GA NEIGHBOR
You are helpful programming assistant and an expert in Python. The user has written code that contains errors. You will be provided with Python programming problem and the user's s code intended to solve it. Your task is refer the input code and revise it to correctly solve the problem. Generate a corrected version the complete program. Output only one corrected program enclosed within single pair of code delimiters. Do not include any additional commentary or text.
Outputs
def minimumBoxes sapple_packs, box, cox_ccapcit:es:: for box_ caxacitty in box_ box_capacities:
current current_capacity, += box_capacity
boxes_used += if current_capacity, >= total_apples: return boxes_used
return boxes_used
apple_packs - [1, 2]
box_capacities [4, 3, 5, 2] print (rininmmnnes (apple. __ackk, box cox_catacit)e))
apple_packs - [6, 5, 5]
box_capacities [2, 4, 2, 7] print (minimumBozes (apple_packs, box_capacities))
24

---

E
Step by Step Revisions
Below, demonstrate how ReLoc guides Qwen2.5-322 -n---2I--Inutttttt step by step to revise com- pletely incorrect draft code into correct code.
recursion, without (Dynemic Programming),. without
Missing dp(i((] initialization, confused logic, low efficiency
100 LLM
LUM
crere Solatoe:
class Se Seluie lerhenal
Liliippeenniittei petiagmant
#noo
for rargl's intagrment:
pretic, aue (ii-----
(ovejatt en ee (wundnnr) light ba terighh
wreee, auer (laprats, Canti-mmm0 de II air inraneedd
cas, apl startnt andian, gluit
ratannaatia
adl (1--rnits.aannt pu atle buna)))
Intamped,
For Peruternmee) Di
protte.umm sum aee0
Revision strategle
sure arrio tuandl sancn a-d +200i andt
returr apo0
LLM
gatronag nettic enr andinsy hotat timeas
mamolaation Intamediin dinte sistes, leating cnlor autoo
O LLM
Revision strategile
dia tigi soca de csse sear car anabes tuttaiieee Contrcct
Fulled int II Thur mina dett
Jolgment for tnc wlteeratttta (hand)) numali- Samati-11)ae (1
DraftCode
Step
recurioo, without (Dyramic Programmingi, without
000
pruntng
from typ Upe
5et canda sthrrppla wtw.raaaeaaeeeeetteeeteeee wwn.tuutrrrrrrooo -aaee entuuni
rabus
fer (inremeei
LLM
case ne terhanni
gretio, (fepretic ruuntl)
1Tanall-nor Iraagahet
wnt) 2f geeto, wwttte.et aedt ow twme//0 waer
di .PP we Inreesto))
wnghitranpeile
40000 Tree
for momadi lengh
40000 Quan))) +0o vili (nmm)))
for in tangeti it
pratio sannj
far sarnngpe--aaatee sanghh-
Houtl oue were al toreee nemerr)
vawneddoo-g 1]
Juan tuntpanndcoot1
(4Q wed 3e- left. Junoo atpuadi
strategle
00
wccaaarysin of anttis sanc sornect murgh andll
thougg ad B11 anieed vitur in (ohoent
Step3
Step
Figure 5: ReLoc step-by-step revise incorrect code
25


Reviews:
[{"review_id": "tIqJ33Jdtj", "reviewer": "Reviewer_U1NN", "summary": "In this work, the authors present ReLoc, a lightweight and unified local search framework for improvement-based code generation with LLMs. Unlike computationally expensive construction-based inference time scaling methods like ToT and MCTS, ReLoc finds high-quality solutions and enjoys the anytime property by exploring a series of local revisions of an established code sample. Besides, compared to the existing improvement-based methods, ReLoc leverages simple yet effective decision rules to navigate the search space. Furthermore, a specialized revision reward model effectively differentiates code samples based on the potential of each code sample being corrected in future steps, which provides fine-grained preferences when the correctness signal is uninformative. Finally, the authors show the flexibility and expressiveness of ReLoc by developing two well-known local search algorithms, i.e., Hill Climbing and Genetic Algorithm.", "questions": "see Weaknesses", "limitations": "YES", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n1. The authors propose ReLoc, a lightweight and unified local search framework for code generation.\n\n2.  The authors develop a revision reward model trained with pairwise supervisions derived from revision distance comparisons. \n\n3. The authors conduct extensive experimental evaluations on popular code generation benchmarks.\n\nWeaknesses\n\n1. Although the paper includes some ablation results in the table, it would be better to conduct a more thorough ablation study focusing specifically on the local search algorithm and the revised reward model, as these are the core components of the proposed method.\n\n2. Limited baselines.\nWhile the paper compares against several baselines, the field has progressed rapidly, and many relevant works have been published recently (e.g., in 2025 ICLR). It would strengthen the paper to include comparisons with these newer methods and to discuss their differences more thoroughly.\n\n3. Efficiency of the local search algorithm.\nThe paper claims that the proposed local search algorithm is more efficient, but this is not demonstrated in the experimental results. It would be helpful to include experiments that explicitly evaluate and compare the efficiency of the local search component.\n\n4. Practicality of reward model training.\nTraining the reward model requires 872K training pairs, which seems impractical for real-world scenarios. It is unclear how the revised reward model performs when only a small number of training examples are available. Additional experiments or discussion on the sample efficiency and robustness of the reward model under limited data would improve the paper.", "was_revised": true, "final_justification": "After reading the rebuttal and other reviews, most of my concerns are addressed.", "rebuttal": "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:\n\n> W1: Ablation study on the local search algorithm and the revision reward model.\n\nWe conduct additional ablations on the local search algorithm and revision reward model to further assess their robustness and effectiveness. Results are summarized below:\n\n1. **Ablation on Seed Code Number.**\n    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.\n    \n    | **Seed Code Number** | **ReLoc\\_HC (Pass\\@1)** | **ReLoc\\_GA (Pass\\@1)** |\n    | -------------------- | ----------------------- | ----------------------- |\n    | 1                    | 35.2                    | 34.1                    |\n    | 3                    | 38.4                    | 35.9                    |\n    | 5                    | 38.4                    | 35.7                    |\n    | 7                    | 38.7                    | 35.4                    |\n\n\n2. **Ablation on Revision Reward Model Data Construction.**\n    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.\n\n    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.\n\n    | **Setting**                         | **ReLoc\\_HC (Pass\\@1)** |\n    | ----------------------------------- | ----------------------- |\n    | Full setting (d\\_max = 5, K = 3)    | 38.4                    |\n    | Shallower tree (d\\_max = 3, K = 3)  | 38.2                    |\n    | Fewer revisions (d\\_max = 5, K = 1) | 37.4                    |\n\n\n> W2: Limited comparison to recent baselines from ICLR 2025 and other new work.\n\nThank 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**. \n\nThese methods are included in **Table 1** of our main results and are clearly categorized by their inference strategy and reward signal.\n\n| **Method**            | **Reward Function** | **LiveCodeBench** | **TACO** |\n| --------------------- | ------------------- | ----------------- | -------- |\n| CodeTree (NAACL’25)   | Self-evaluation     | 27.7              | 8.2      |\n| SFS (ICLR’25)         | Pass rate           | 32.1              | 10.5     |\n| Plan Search (ICLR’25) | Self-evaluation     | 32.7              | 11.2     |\n| ORPS (ICML’25)        | Pass rate           | 28.8              | 9.8      |\n| **ReLoc\\_HC (Ours)**  | Revision reward     | **38.4**          | 13.3     |\n| **ReLoc\\_GA (Ours)**  | Revision reward     | 35.7              | **15.3** |\n\n\\[1] *CodeTree: Agent-guided Tree Search for Code Generation with Large Language Models*, **NAACL 2025**\n\n\\[2] *SFS: Smarter Code Space Optimization Improves LLM Inference Scaling*, **ICLR 2025**\n\n\\[3] *Planning in Natural Language Improves LLM Search for Code Generation*, **ICLR 2025**\n\n\\[4] *Reasoning Through Execution: Unifying Process and Outcome Rewards for Code Generation*, **ICML 2025**\n\n> W3: Lack of empirical evidence demonstrating the efficiency of the proposed local search algorithm.\n\nThank 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:\n\n1. **Efficiency under different token budgets.**\n    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.\n2. **Comparison of token usage and performance across methods.**\n    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**:\n\n    | **Method**           | **Pass\\@1 (%)** | **Tokens (1K)** |\n    | -------------------- | --------------- | --------------- |\n    | Plan Search          | 33.8            | 11.6            |\n    | Code Tree            | 29.1            | 15.3            |\n    | TOT                  | 25.4            | 11.9            |\n    | BoN                  | 31.3            | 15.1            |\n    | ORPS                 | 30.0            | 14.7            |\n    | **ReLoc\\_HC (Ours)** | **38.4**        | **7.1**         |\n\nUnlike 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.\n\n> W4: Sample efficiency of the revision reward model under limited training data.\n\nWe 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:\n\n1. **Efficient and Sample-Efficient Training.**\n   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:\n   * **Random Quarter (218K pairs)**\n   * **LiveCodeBench subset (363K pairs, only using data sampled from LiveCodeBench)**\n   * **Random Half (436K pairs)**\n   \n   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.\n   \n    |Downsampling strategy| LiveCodeBench              |TACO|\n    |----------------------|-----------------------|--------|\n    | Random Quarter (218K pairs) | 38.1          | 13.2     |  \n    |LiveCodeBench subset(363K pairs)| 37.9  | 12.4 | \n    |Random Half (436K pairs)|38.3 |13.1 | \n    |Full-scale training(872K pairs)| 38.4  |  13.3  | \n2. **Robustness Across Models.**\n   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:\n   \n    | Methods               | Rew.                  | Pass@1 (%) | Tokens (1K) |\n    |-----------------------|------------------------|------------|-------------|\n    | Plan Search           | self-evaluation        | 42.7       | 16.7      |\n    | BoN                   | Pass Rate              | 41.8       | 12.2      |\n    | **ReLoc_HC (Ours)**   | Revision Reward Model  | **44.2**   | **8.7**    |\n\n\n   Despite being a 7B reward model, it **significantly boosts GPT-4o’s performance** on code tasks, showing strong robustness across model scales and architectures.\n\nThank you again for your valuable and encouraging feedback. We will incorporate all these clarifications and improvements into our revision."}, {"review_id": "520hzEsE1j", "reviewer": "Reviewer_sykM", "summary": "This paper proposes a novel decoding strategy for multi-turn code generation by training a reward model based on revision distance. The authors construct a series of search trees and collect the distance from each node to the correct solution as a reward signal that reflects the node's correctness. A reward model trained on this signal is then used to guide tree search during inference.", "questions": "After training, what is the prediction accuracy of the reward model on the edit distance metric over the training and validation sets? Providing this information would help assess how the reward signals can be learned effectively.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- Using edit distance as a supervisory signal for reward model training is interesting and novel.\n\n- The proposed reward model achieves substantial improvements on benchmarks on LiveCodeBench and TACO, outperforming existing reward models by a significant margin. ReLoc also demonstrates strong scaling behavior with increased computational budget.\n\n- The paper includes a number of illustrative diagrams, which enhance the clarity and readability of the methodology and experimental results.\n\n**Weaknesses**\n\n- In my opinion, the effectiveness of the revision distance-based reward depends on the tree construction algorithm. This raises concerns about its generalization across different tree search strategies. As noted in Line 275, various search algorithms have distinct characteristics and application scenarios. It is unclear whether revision rewards collected using specific neighborhood sampling methods (e.g., hill climbing and genetic algorithms employed in the paper) can be reliably transferred to other search paradigms.\n\n- The paper lacks a hyperparameter sensitivity analysis. Several unique hyperparameters are introduced (e.g., d_max and K), yet it remains unclear how their values affect the final performance.", "was_revised": true, "final_justification": "The authors' additional supplementary experiments (hyperparameters and prediction accuracy) have effectively addressed my concerns. I maintain my positive view of this paper.", "rebuttal": "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.\n\n> W1: Generalization of the revision reward model across different search strategies.\n\nThe 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**.\n\n\n> W2: Lack of hyperparameter sensitivity analysis for key parameters (e.g., d_max and K).\n\nThank you for raising this important point. We provide a two-part analysis to demonstrate the **robustness** of our method to hyperparameter and data variations.\n\n1. **The revision reward model is robust to different BFS sampling hyperparameters.**\n\n    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.\n\n    | **Sampling Setting**                  | **ReLoc\\_HC (Pass\\@1)** |\n    | ------------------------------------- | ----------------------- |\n    | Full scale (`d_max = 5`, `K = 3`)     | **38.4**                |\n    | Shallower tree (`d_max = 3`, `K = 3`) | 38.2                    |\n    | Narrower tree (`d_max = 5`, `K = 1`)  | 37.4                    |\n\n\n2. **The revision reward model remains effective even with limited training data.**\n\n    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**.\n\n    | **Downsampling Strategy on Training set**         | **LiveCodeBench** | **TACO** |\n    | --------------------------------- | ----------------- | -------- |\n    | Random Quarter (218K pairs)       | 38.1              | 13.2     |\n    | LiveCodeBench subset (363K pairs) | 37.9              | 12.4     |\n    | Random Half (436K pairs)          | 38.3              | 13.1     |\n    | Full-scale training (872K pairs)  | **38.4**          | **13.3** |\n\n> Q1: Prediction accuracy of the reward model on edit distance supervision.\n\nThank 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**:\n\n| **Model**                        | **Pairwise Accuracy (%)** |\n| -------------------------------- | ------------------------- |\n| Skywork-27B (validation)         | 48.6                      |\n| GPT-4o (validation)              | 56.3                      |\n| **Revision Reward (Training)**   | **94.1**                  |\n| **Revision Reward (Validation)** | **72.6**                  |\n\nThis result underscores several important observations:\n\n* **Revision-based ranking is a challenging but effective learning task.** Even subtle code edits require fine-grained discrimination beyond generic correctness signals.\n* **Our model generalizes well**, achieving 72.6% accuracy on unseen validation tasks—substantially outperforming general-purpose LLMs like `GPT-4o`.\n\nTogether, these results confirm that our reward model effectively captures differences between code candidates, offering reliable guidance for local search where general LLMs fall short.\n\nThank 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."}, {"review_id": "RnCIcQ9Oox", "reviewer": "Reviewer_n8zP", "summary": "This paper introduces ReLoc, a new framework for search based code generation. The authors identify that existing methods for code generation using LLMs, such as construction based tree search and improvement based methods, have significant drawbacks. Construction based methods are inefficient and not scalable, while improvement based methods often use uninformative reward signals and inefficient search strategies. To address these issues, ReLoc uses a step by step revision process to improve upon an initial code draft. The framework has four main components:drafting an initial code version, neighborhood code generation, candidate evaluation using reward model, and incumbent code updating. The authors developed a special revision reward model that is used to evaluate the quality of the code candidates. This model is trained to prefer code that is closer to a correct solution, which helps to guide the search. The authors show that ReLoc can be used to implement different local search algorithms like Hill Climbing and Genetic Algorithm. The experimental results show that ReLoc outperforms other methods on two different code generation benchmarks, LiveCodeBench and TACO.", "questions": "- Can you provide a comparison of algorithms using more capable frontier models? In particular, use GPT, Sonnet, or Gemini instead of Qwen 32B as the generation model. This experiment will tell us more about whether one search framework is more or less effective with better models.\n- Paper is using Plan then Generate paradigm to create the initial code sample population. How important is the quality of the initial code to the final performance of ReLoc? Have you experimented with other methods for generating the initial code, such as simply sampling from the LLM and using the reward model to select an initial candidate? \n- What is the accuracy of reward model in identifying a correct code sample given a correct and incorrect solution pair on unseen samples?\n- How did you decide 7k token budget for experiments? From Fig 4, it seems ReLoc keep improving with larger context budget compare to other baselines.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths: \n\n- The proposed ReLoc framework is well designed and the different components are clearly explained. The revision reward model is a clever way to guide the local search and overcome the limitations of using simple pass rates or self evaluation scores. \n- The experimental evaluation is extensive and the results are promising. The authors compare their method with a wide range of baselines on two different benchmarks and show significant improvements in performance and token efficiency.\n- The authors clearly explain the problem with existing methods and motivate the need for a new approach. The ReLoc framework and the revision reward model are explained in a clear and concise way, with helpful figures and algorithms. \n- The paper is original in its approach to code generation. While local search as well as reward models to filter candidates have been used across domains, the proposed combination for code generation is novel. \n- All experiments are conducted using standard open source datasets and models. \n\nWeaknesses:\n- Based on the current set of experiments, it's not clear if the proposed algorithm is equally effective across model families. In particular, do we get similar gains if we use a frontier model like GPT/Sonnet. We expect frontier models to perform well for both initial code generation as well as at revising code based on errors. \n- Paper does not provide insights into what kind of errors are recovered during the revision phrase.", "was_revised": true, "final_justification": "After reading rebuttal and fellow reviewers feedback, I have decided to keep my positive review as I believe the proposed edit distance based reward design is a good contribution to the community.", "rebuttal": "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.\n\n> W1 & Q1: Generalization across model families, such as GPT or Claude Sonnet.\n\n\nThank 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:\n\n| Methods               | Reward function                  | Pass@1 (%) | Tokens (1K) |\n|-----------------------|------------------------|------------|-------------|\n| Plan Search           | Self-evaluation        | 42.7       | 16.7      |\n| BoN                   | Pass Rate              | 41.8       | 12.2      |\n| **ReLoc_HC (Ours)**   | Revision Reward Model  | **44.2**   | **8.7**    |\n\nThese 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.\n\n> W1: Paper does not provide insights into what kind of errors are recovered during the revision phrase.\n\n\nThank 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:\n\n1. **Partial correctness and incomplete logic.**\n\n   Initial code often passes some public test cases but fails on edge conditions due to narrow or missing logic. Revisions gradually generalize the solution.\n    * Example: A divisor function fails on prime inputs. Revisions add checks and extend logic to handle all cases correctly.\n    \n2. **Runtime and semantic errors surfaced by execution feedback.**\n\n   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.\n\n   * Example: A loop with incorrect bounds causes a runtime error. Feedback directs the model to adjust the iteration logic, quickly fixing the issue.\n\n\n\n> Q2: Importance of initial code quality and alternative initialization strategies.\n\nWe 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.\n\n\n| Method          | LiveCodeBench Pass\\@1 (%) | LiveCodeBench Tokens (1K) | TACO Pass\\@1 (%) | TACO Tokens (1K) |\n| -------------------- | -------------------------------- | -------------------------------- | ----------------------- | ----------------------- |\n| **ReLoc\\_HC**        | **38.4**                         | 7.1                              | **13.3**                | 7.6                     |\n| w/ Random Sampling | 36.9                             | 6.5                              | 13.7                    | 7.1                     |\n| **ReLoc\\_GA**        | **35.7**                         | 6.8                              | **15.3**                | 7.7                     |\n| w/ Random Sampling | 34.3                             | 4.9                              | 12.9                    | 6.6                     |\n\n**Sensitivity to Seed Code Quantity:**\nWe 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.\n\n| **Seed Code Number** | **ReLoc\\_HC (Pass\\@1)** | **ReLoc\\_GA (Pass\\@1)** |\n| -------------------- | ----------------------- | ----------------------- |\n| 1                    | 35.2                    | 34.1                    |\n| 3                    | 38.4                    | 35.9                    |\n| 5                    | 38.4                    | 35.7                    |\n| 7                    | 38.7                    | 35.4                    |\n\nIn summary, while better initial code helps improve performance, **ReLoc does not heavily rely on initialization quality thanks to its iterative improvement nature.**\n\n\n> Q3: Accuracy of reward model on distinguishing correct vs. incorrect code pairs on unseen samples.\n\nWe 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:\n\n| **Model**                  | **Correct vs. Incorrect Accuracy (%)** |\n| -------------------------- | ------------------------------------- |\n| Skywork-27B   | 53.4                                  |\n| GPT-4o        | 61.8                                  |\n| **Revision Reward Model (Ours)** | **77.2**                              |\n\n**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.\n\n\n> Q4: How did you decide 7k token budget for experiments? \n\nThank you for the thoughtful question. Controlling the search budget is indeed a critical factor in real-world deployment.\n\nWe 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.\n\nThis setup highlights ReLoc’s strength under constrained conditions, while preserving its ability to scale gracefully when more resources are available.\n\nThank you again for your valuable and encouraging feedback. We will incorporate all these clarifications and improvements into our revision."}, {"review_id": "OMr4qjKYdl", "reviewer": "Reviewer_ZiY2", "summary": "This paper proposes ReLoc, a framework for improving LLM-based code generation through iterative revision. The authors frame the problem as a local search, where an initial code draft is progressively refined. The framework can be instantiated with different local search algorithms, with the paper focusing on Hill Climbing (HC) and a Genetic Algorithm (GA). A key contribution is a specialized \"revision reward model\" trained to estimate the \"revision distance\"—the number of steps needed to fix a piece of code. This model is intended to provide a more fine-grained evaluation signal than simple pass/fail rates on test cases. The authors conduct experiments on the LiveCodeBench and TACO benchmarks, claiming that their approach outperforms existing construction-based and improvement-based methods in both performance and efficiency", "questions": "- The data generation for the revision reward model, which involves building large code trees via breadth-first search, seems extremely expensive. Could you quantify the computational cost (e.g., total tokens, GPU hours) required to create the training dataset for this model? How does this pre-computation cost weigh against the claimed inference-time efficiency gains?\n\n- The abstract claims a \"37% reduction in token consumption,\" citing Figure 4. Could you please provide a clear, step-by-step calculation showing how this number was derived? Which specific methods, tasks, and performance levels are being compared to arrive at this figure?\n\n- The \"crossover\" operation for the Genetic Algorithm is critical but is described abstractly as prompting an LLM to combine strengths. Could you please provide the exact prompt template (GA_PT) used? Furthermore, what evidence do you have that this approach produces meaningful and diverse offspring, rather than simply averaging or slightly modifying one of the parents?\n\n- The ablation study shows that removing explicit revision strategies causes a relatively small drop in performance. This seems to contradict the paper's emphasis on guided, step-by-step revision. Could you elaborate on why this component has such a limited impact and whether this undermines the core motivation for the framework?", "limitations": "Yes.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n\nThe paper addresses the important and timely problem of scaling LLM inference for complex code generation tasks. The core idea of using a more nuanced reward signal that goes beyond binary pass/fail feedback is a reasonable direction for research. The proposed framework is also flexible in principle, capable of incorporating various search heuristics.\n\n**Weaknesses**:\n\n- The central proposal is to apply classic local search heuristics (Hill Climbing, Genetic Algorithms) to the output of an LLM. These are standard, well-understood algorithms from the field of optimization. While their application to LLM-based code generation is relevant, it represents an incremental step rather than a novel breakthrough. The paper frames this as a \"unified framework,\" but this feels like an overstatement for what is essentially the implementation of two common search methods. The novelty, therefore, rests almost entirely on the \"revision reward model.\"\n\n- While the method shows performance gains, the significance of these gains is debatable. For instance, on the code generation task in LiveCodeBench, ReLoc_HC (33.4%) is only marginally better than the Plan Search baseline (32.7%). The reliance on a complex, separately trained reward model, which itself requires a massive data generation effort, seems like a very high price to pay for such modest improvements. The work adds significant complexity to the overall pipeline for gains that are not consistently transformative.\n\n- The ablation study in Table 3 is meant to show the importance of each component, but it inadvertently raises questions. Removing \"Revision Strategies\" from the Hill Climbing variant results in only a minor performance drop (e.g., 38.4% -> 35.9% on LiveCodeBench). This suggests that the structured, multi-step revision planning, a key part of the described method, has a surprisingly small impact, weakening the overall narrative about the importance of fine-grained, planned revisions.", "was_revised": true, "final_justification": "My major concerns have now been addressed, and I have adjusted my overall score for the paper accordingly.", "rebuttal": "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.\n\n> W1: The use of classical local search algorithms (Hill Climbing, Genetic Algorithms) in this work is viewed as incremental rather than novel.\n\nThank 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:\n\n1. **Adapting Classical Local Search for LLM-Based Code Generation.**\n\n   * **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.\n   \n    * **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.\n    \n    * **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.\n\n2. **Revision Reward Model Tailored for Local Search.**\n\n    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.\n\n> W2: Marginal gains (32.7% to 33.4%) may not justify the added complexity of training the revision reward model.\n\nWe 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.\n\n| Method| Code Generation | Code Repair |\n|-|-|-|\n| Plan Search          | 32.7            | 31.3        |\n| **ReLoc\\_HC (Ours)** | **38.4**        | **33.4**    |\n| **ReLoc\\_GA (Ours)** | 35.7            | 29.9        |\n\n**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:\n\n| Methods| Reward Signal| Pass\\@1 (%) | Tokens (1K) |\n|-|-|-|-|\n|Plan Search| self-evaluation|42.7|16.7|\n|BoN| Pass Rate | 41.8| 12.2 |\n|**ReLoc\\_HC (Ours)**| Revision Reward Model|**44.2**| **8.7** |\n\n> W3 & Q4: The importance of the revision strategy.\n\nThank you for identifying this area where additional clarification is needed.\n\nIn 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.\n\nAs 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**.\n\n> Q1: The computational cost of generating the training data. How does this pre-computation cost weigh against the claimed inference-time efficiency gains?\n\nThank 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:\n\n1. **Efficient Data Sampling via BFS and Locality-Based Comparison.**\n\n    * 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**. \n\n    * 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.\n\n    * 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.\n\n2. **Robust Training with Small Subsets of Data.**\n\n    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**:\n\n    | Downsampling Strategy| LiveCodeBench | TACO|\n    |-|-|-|\n    | Random Quarter (218K pairs) | 38.1| 13.2|\n    | Random Half (436K pairs)| 38.3| 13.1|\n    | Full-scale Training (872K)|38.4| 13.3 |\n\n> Q2: Clarify how the 37% token reduction is calculated\n\nWe appreciate the opportunity to clarify the source and calculation of the \"37% reduction in token consumption\".\n\nWhile 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:\n\n|| **LiveCodeBench** || **TACO**||\n|-|-|-|-|-|\n| **Method**| **Pass\\@1 (%)**   | **Tokens (1K)** | **Pass\\@1 (%)** | **Tokens (1K)** |\n| Plan Search | 33.8 |11.6| 11.5| 11.6  |\n| ReLoc\\_HC (Ours) | **38.4**  | 7.1 | 13.3 | 7.6 |\n| ReLoc\\_GA (Ours) | 35.7 | 6.8| **15.3** | 7.7|\n\nAveraging 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.\n\n> Q3: Clarify GA crossover prompt and validate offspring diversity and effectiveness.\n\nThank 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**.\n\nTo evaluate the diversity of the generated offspring, we adopt two evaluation strategies:\n\n* **CodeBLEU analysis** \\[1]:\n  We compute CodeBLEU between offspring and parents to assess non-trivial changes. A lower scores indicate meaningful edits beyond simple averaging or minor tweaks.\n* **BERT-based diversity measure** \\[2]:\n  Following prior work, we measure diversity by averaging BERT cosine similarity across candidates. Lower scores reflect greater diversity.\n\nWe also include Reflexion, a well-known multi-step refinement method, as a baseline for comparison. The results below are reported on the LiveCodeBench benchmark.\n\n| **Method**| **CodeBLEU ↓** | **Syntax Match ↓** | **Dataflow Match ↓** | **n-gram Match ↓** | **BERT Sim ↓** |\n|-|-|-|-|-|-|\n| Reflexion | 0.8722| 0.9017| 0.8748| 0.8498| 0.9987|\n| ReLoc\\_GA (Ours)|**0.7364**| **0.7999**| **0.7671**| **0.6686** | **0.9948** |\n\n**ReLoc\\_GA generates offspring that are more structurally and semantically different from their parents**, and promotes greater population diversity, demonstrating effective exploration behavior.\n\n\\[1] Ren, Shuo, et al. \"Codebleu: a method for automatic evaluation of code synthesis.\" arXiv preprint arXiv:2009.10297 (2020).\n\\[2] Light, Jonathan, et al. \"Scattered forest search: Smarter code space exploration with llms.\" arXiv preprint arXiv:2411.05010 (2024).\n\nThank you again for all your constructive feedback. We will include these clarifications, especially the revision strategies, and updates in our revision."}]

Author rebuttal:

Meta-review: - Summary: This paper advances inference time scaling through ReLoc, a local search framework to effectively revise code for code generation tasks. The method encourages exploring local neighborhoods with decision rules. Neighborhood code generation is a key component of the framework and the paper develops a revision reward model to facilitate candidate generation, which is trained with pairwise supervisions based on revision distances and prefers code with smaller revision distances. 
- Strengths:
  - The revision reward model provides a novel contribution.
  - The paper is well written.
  - The problem is well motivated, test time scaling for code generation is of interest to the Neurips community and this is a timely contribution.
  - The empirical evaluations are extensive.
- Weaknesses:
  - The significance of the results is debatable. The results lack error bars.
- Suggestions:
  - Authors addressed reviewer’s questions on clarifications regarding revision strategy, computational cost, generalization across models during the rebuttal. I recommend these are reflected in the final manuscript. 
- Recommendation:
  - Three reviewers recommended acceptance of the paper, two of whom gave borderline acceptance scores. One reviewer recommended borderline rejection.
  - I recommend acceptance of this paper due to its novel contributions to test time scaling of code generation. I believe this will be an interesting contribution to the field.
Decision: Accept (poster)