Multi-Turn Code Generation Through Single-Step Rewards
Authors: Arnav Kumar Jain
Gonzalo Gonzalez-Pumariega
Wayne Chen
Alexander M Rush
Wenting Zhao
Sanjiban Choudhury
Venue: ICML 2025 spotlightposter (2025)
Keywords: Code Generation
Language Models
Reinforcement Learning
Primary area: deep_learning->large_language_models

Abstract: We address the problem of code generation from multi-turn execution feedback. 
Existing methods either generate code without feedback or use complex, hierarchical reinforcement learning to optimize multi-turn rewards.
We propose a simple yet scalable approach, $\mu$CODE, that solves multi-turn code generation using only single-step rewards.
Our key insight is that code generation is a one-step recoverable MDP, where the correct code can be recovered from any intermediate code state in a single turn.
$\mu$CODE iteratively trains both a generator to provide  code solutions conditioned on multi-turn execution feedback and a verifier to score the newly generated code.
Experimental evaluations show that our approach achieves significant improvements over state-of-the-art baselines. 
We provide analysis of the design choices of the reward models and policy, and show the efficacy of $\mu$CODE at utilizing the execution feedback.

Multi-Turn Code Generation Through Single-Step Rewards
Arnav Kumar Jain 12
Gonzalo Gonzalez-Pumarieg Wayne Chen Alexander M Rush"
Wenting Zhao 1 Sanjiban Choudhury f3
Abstract
2023; Ni et al., 2024). However, these struggle to iteratively correct errors over multiple turns. Multi-turn approaches, on the other hand, rely on complex reinforcement learning (RL) (Gehring et al., 2024a; Kumar et al., 2024b; Zhou et al., 2024) to optimize long-term rewards. While effective in principle, these methods suffer from sparse learning signals which makes learning inefficient.
We address the problem of code generation from multi-turn execution feedback. Existing meth- ods either generate code without feedback or use complex, hicrarchical reinforcement learning to optimize multi-turn rewards. We propose a sim- ple yet scalable approach, PCODE, that solves multi-turn code generation using only single-step rewards. Our key insight is that code generation is one-step recoverable MDP, where the correct code can be recovered from any intermediate code state single turn. μCODE iteratively trains both generator to provide code solutions con- ditioned on multi-turn execution feedback and a verifier score the newly generated code. Ex- perimental evaluations show that our approach achieves significant improvements over the state- of-the-art baselines. We provide analysis of the design choices of the reward models and policy, and show the efficacy of μCODE at utilizing the execution feedback. Our code is available here.
Our key insight is that code generation is one-step recov- erable Markov Decision Process (MDP), implying that the correct code can be recovered from any intermediate state in a single step. This allows us to greedily maximize a one- step reward instead of relying on complex multi-step reward optimization. As a result, this reduces the problem from re- inforcement learning, which requires exploration and credit assignment, imitation learning, where the model simply learns to mimic correct code, leading to more stable and efficient training process.
We propose μCODE, a simple and scalable approach for multi-turn code generation from execution feedback. Dur- ing training, μCODE follows an expert iteration (Anthony et al., 2017) framework with local search expert, enabling iterative improvement of both the generator and the expert. The process begins by rolling out the current code genera- tor to collect interaction data with execution feedback. A single-step verifier is then trained on this data and utilized to guide a local search expert in refining the code and gen- erating training labels. Finally, the generator is fine-tuned using these labels. Given recent trends of test-time scaling in generating high quality solutions (Brown et al., 2024; Snell et al., 2024; Wu et al., 2024), μCODE also uses the learned verifier for inference-ting scaling. Here, μCODE samples trajectories; at each step, jCODEE picks the best code solution ranked by the learned verifier.
1. Introduction
Software engineers often iteratively refine their code based on execution errors. common strategy for machine code generation is thus repair code using execution feedback at test time (Chen al., 2024; Wang et al., 2024b; Zhao et al., 2024). However, prompting alone is insufficient as it cannot teach how to recover from all possible errors within a limited context.
We need to train models that can learn from execution feed- back during training. Existing approaches fall into either single-turn or multi-turn settings. In the single-turn setting, methods either train without execution feedback (Zelikman et al., 2022) or perform one-step corrections (Welleck et al.,
The key contributions of this work are as follows:
1. A novel framework, μCODE, for training code genera- tors and verifiers through multi-turn execution feedback. We add theoretical analysis of performance bounds using the property of one-step recoverability for this task.
'Equal contribution 'Mila- Quebec AI Institute Universitéé de Montréal 'Comell University. Correspondence to: Amav <arnav- kumar @ mila.quebee.. Gonzalo <gg387 @od.
2. We propose a multi-turn Best-of-N (BoN) approach for inference-time scaling and present benefits of learned verifier to select the code solution at each turn.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
3. Our approach μCCDD outperforms leading multi-turn

---

Multi-Tune Code Generation Through Single-Step Rewards
Prompt (x)
Code generation is "one-tepp recoverable" MDP
def is (s): return == sl::-1]
"Check the given string
palindrome"
$1
Turn
(11)
def is ls
$2
Turn 2
83
Turn 3
return s = s1-1]
(52)
def is palanndoreelss::
(ya)
def is_ Landroinne
is_pa ii_dpalinrooee "aaprmmee"""cccaa===assssss is (tariidddronettsst="======= (01)
return s10) = s1::-11
return sl::-11
(s_ppalindromll""" (02)
Sa_paainrooeee"""" "a"= (0g)
1s_ is_palindrone ("bob")==TTru
(a)
Rollout generator x0
Aggregate data 9
Relabel 9 with
Train Verifier
Expert x
Train Generator
R Rølx, y)
x [s)
Local search with R
1/2
y3
$2 Y2 $3
$2
8
(b)
Figure 1. (a) We define the task of multi-ture turn code generation where for initial problem z, the generator me provides solution yi. This solution is evaluated with the public test to get execution feedback o₁. At a turn 6, the generator is conditioned on the history to generate solution y/ (. 2. Mcx). The rollout ends when the turn limit is reached the public tests pass upon which the solution is exccuted on private tests. Since, the agents can generate the optimal solution at any turn, this is a 1-step recoverable process. (b) Training loop of our method μCODE- which comprises of generator and learned verifier. During each itcration, rollouts are collected using no and we train a verifier Rs to rank candidate solutions for prompt. The verifier R& is then used to construct local expert and relabel the collected rollouts. Lastly, the generator fine-tuned with this expert dataset.
approaches on MBPP (Austin et al., 2021), Hu- manEval (Chen et al., 2021) and CodeContests (Li et al., 2022a) benchmarks. Our ablations show that learned ver- ifiers aid in learning better generators and show promis- ing scaling law trends with higher inference budgets.
where the state is the interaction history S, { Vı, .I...., 1t- Oc-13 where 81 = {x), and the ac- tion is the code snippet yı- The oracle reward defined as R(*,, v.) R(x,, ye) = C(x, ye) if ye passes all public and private tests (terminating the episode), or 0 otherwise.
During training, given a dataset of problem prompts D, the goal is to find generator To (ve (r. y1, .1.... Ut-1, 0z-1), that maximizes the cumulative discounted reward R(xx, W:):
2. Background
In multi-turn code generation, an agent iteratively refines a program to maximize its correctness on private test cases. Given an initial problem prompt x, at each turn 6, the agent generates complete code snippet Ye and executes it on set of public tests. The outcomes from these tests serve as observations that guide subsequent refinements. This process continues until the agent generates a code snippet yt that passes all public tests, at which point the episode terminates, or until the maximum number of turns is reached without success. The first successful code, Mr is then evaluated on private tests to compute the correctness score Clz, Vi) E {0, 1].
T
un)
max EewDD. N9
Σ
7 "R(,, R
(1)
where 7 E [0, 1) is the discount factor. As shown in Eq. 1, the objective optimizes for a policy to generate the correct solution with few turns as possible. However, at any step t, the agent generate the correct code solution ye y* such that C(x,, y²) (as shown in Fig. (a)) one-slep recoverable process. In the following section, we describe μCODE, a simple and scalable framework that leverages the one-step recoverability and reduces the problem of rein- forcement learning to imitation learning.
We model this as Markov Decision Process (MDP),
2

---

Multi-Turn Code Generation Through Single-Step Rewards
Algorithm 1 μCODE: Training
inference time, the verifier is used for multi-turn BoN (3.4) for efficient search. The learned verifier has two distinct advantages over process reward functions typically used in multi-turn RL: (1) It is conditioned only on the initial prompt and the current solution, and is not dependent on previous states (2) It is trained via supervised learning on oracle reward labels. We explore two different losses:
input Initial generator To, multi-turn code environment E, and max iterations M
M. do 1: for iteration i = ....M
2: Rollout generator To in multi-turn environment &
to collect datapoints D; <- {xx, St, Vt. o+))}
3: Aggregate data D - D D.
4: Train a verifier Rg (c, y) on D
Binary Cross-Entropy loss (BCE): The nominal way to train the verifier is to directly predict the oracle reward labels (Cobbe et al., 2021) as given by:
5: Construct a local search expert using verifier
(1) = arg D(ar) 80 R(x, u) + Ro,,
6: Relabel data D with m (2) to get D
7: Train rá with fine-tuning (FT) D
-B (xx..)))) log Rig (2x LBCE (6) -
(2)
8: end for
- - r) log
v)l
output Best generator To and verifier RS
Bradley Terry Model (BT): Since the goal of the verifier is to relatively rank code solutions rather than predict absolute reward, we create a preference dataset and then train with a Bradley Terry loss (Ouyang et al., 2022). For every prompt 2, we create pairs of correct y* (where 1) and incorrect y (where r = 0) code and define the following loss:
3. CCDDE: Multi-turn Code Generation
We propose μ.CODE, a simple and scalable algorithm for multi-turn code generation using execution feedback. uCODE follows an expert iteration (Anthony et al., 2017) framework with a local search expert. μCODE iteratively trains two components a learned verifier Rs to score code snippets (Section 3.2), and a generator Ty imitate local search with the verifier (Section 3.3). This iterative process allows the generator and expert to bootstrap off each other, leading to continuous improvement. At inference time, both the generator and verifier are used as BoN search to select and execute code (Section 3.4). Finally, we analyze the performance of μCODE in Section 3.5.
CBr(Ø) =
(a .v (oollogg(RRozz,)) Ro D).
(3)
where o.) the sigmoid function. We hypothesize that BT is strictly easier to optimize as the verifier has to only focus relative performance. This is also consistent with obser- vations made for training process reward models, where the advantage function is easier to optimize than the absolute Q function (Setlur et al., 2024).
3.3. Training Generator
μCODE comprises generator Ta trained to produce code so- lutions conditioned on the initial problem and execution ob- servations from previous turns. Given a dataset 'D ,CCDE iteratively trains the generator to find the optimal code solu- tion labeled using the local expert over the learned verifier. For this step, μCODE extracts all code solutions from D for every problem x. An expert is then created by picking the best solution, y², which achieves the highest score using the learned verifier (x. y) when combined with the output of oracle verifier R(x, y) and is given by
3.1. The μCODE Algorithm
Algorithm/ 1 presents the iterative training procedure. At an iteration i, the current generator To is rolled out in the multi-turn code environment & to generate interaction data D; <- {(E, $t. Vt. r.)). Every turn in D, includes the prompt æ, interaction history St, code generated y/ and the correctness score from the oracle verifier Fe = R(z, Vi). This data is then aggregated D + D D D, The learned verifier R is trained on the aggregated data D. An expert is created using Ri to perform local search to find the optimal action πं. (x) arg maX)e R2, (2, y). where D(x) are all the code completions for given prompt The expert o: (x) relabels the data DD with the optimal action. The generator Th is then trained via fine-tuning (FT) on D. This process iterates M times, and the best generator and verifier pair on the validation dataset are returned.
y² = Tx (1) = arg max Bo R(. v) + BL (x v), (4) DED(2)
where 30= = 1.0 and BL = 0.1 denote the weights for oracle and learned rewards. Note that for creating the training dataset, we also use the ground labels from oracle verifier as they are available to the agent. The combination of both ver- ifiers yielded better performance in our experiments. Using this expert dataset, we relabel D with the optimal solutions:
3.2. Training Verifier
D. [(x St, bn) (z, st) ~ DD,
(5)
The learned verifier provides dense scores to code solutions for a given problem. At train time, this is used by the expert to perform local search to obtain optimal code. At
where D. represents the expert dataset. The generator ne is then trained via fine-tuning (FT) on this expert dataset D..
3

---

Multi-Turn Code Generation Through Single-Step Rewards
Algorithm 2 WCODE: Inference loop
Definition 3.1 (One-Step Recoverable MDP). A MDP
input Generator Te, learned verifier Rg, turn limit T, num- ber of rollouts N, public tests, and private tests
M (S, (S, R. 7) with horizon T is one-step recover- able if the advantage function of the optimal policy n², de- fined as (s a) = Q" (s. (s), is uniformly bounded for all (s, i.e. -1 S A (s. S 0.
1: Set 81 = 1=
2: while true do
3: Generate N rollouts {w]) Jn=1 T-(())))
4: Choose best solution y = arg max, (T, vE
Code generation is one-step recoverable MDP. Multi- turn code generation satisfies one-step recoverability be- cause the optimal policy n² (ys|s;) depends only on the problem prompt and not the interaction history &t (I,, 01,..,.... ;/-1, :,---.. 0t-1). Since the correctness of a code snippet y1 is fully determined by z, the optimal Q-function satisfies (st, (()),))) = R(E, 9r), where R(x, yt) E {0, 1). The optimal value function is (*;)s) = maxy. R(x, so the advantage function simplifies to A (7 ye)
5: Execute i to get execution feedback ot
6: if vi passes public tests or = T then
7: break;
8: end if
9: Update state 81+1 {st: yf, o and increment t
10: end while
output Return y to execute on public and private tests
R(z, y1) - maxy/ R(x, v/) S.
3.4. Inference: Multi-turn Best-of-N
Code generation enables efficient imitation learning. There are two challenges to applying interactive imitation learning (Ross et al., 2011: Ross & Bagnell, 2014) - (1) Existence of expert policies or value functions, and (2) Recoverability of expert from arbitrary states. First, for code generation, the expert is simply the one-step reward maximizer arg max, R(z, y). We can efficiently estimate (I, v) to compute the expert, without needing to com- pute value function backups. Second, even if the learner fails to imitate the expert at any given state, the expert can perfectly recover from the next state. This results in the best possible performance bounds for imitation learning, which we formalize below.
At inference time, the goal is to generate a code solution with a fixed inference budget- - denoting the number of times generators can provide one complete solution. In this work, we propose to leverage the learned verifier to improve search and code generations over successive turns with multi-turn Best-of-N (BoN). To achieve this, μCODE uses a natural extension of BoN to the multi-turn setting. At each turn, the generator produces N one-step rollouts fur' y ~ (-(ss)) and the learned verifier picks the most promising code solution among these candidates using
Vr = arg max Pegh (vr, v(*)
(6)
Theorem 3.2 (Performance bound for μCODE). For a one- step recoverable MDP M with horizon T, running N itera- tions of μCODE yields at least one policy such that
The selected code 3f is executed in the environment over public tests to obtain the execution feedback or This solu- tion and the feedback is provided as context to the generator at the next turn to repeat this procedure. The search ends once yf passes all public tests or when the turn limit is reached. Consequently, even if R.).) grants high score to a code solution, inference continues until the solution has successfully cleared all public tests, thus mitigating potential errors by (-). The final response yi is then passed through the oracle verifier to check its correctness. Algorithm describes our propose procedure of multi-turn BoN search. We found it beneficial to use the reward model trained with samples of the latest generator Te (see Table I).
J( - J(m) s O(T(c + (NN)).
(7)
where n² is the expert policy, e is the realizability error, and (NN) is the average regret.
Proof is in Appendix A.1. The bound (cT)) much better than the worst-case scenario of O(eT²) for unrecoverable MDPs (Swamy al., 2021). Thus, μCCDE exploits the structure of multi-turn code generation to enable imitation learning, bypassing the need for hierarchical credit assign- ment. More generally, this analysis suggests that for any task where the optimal action is bistory-independeee and re- coverable in one step, reinforcement learning can be reduced to efficient imitation learning without loss of performance.
3.5. Analysis
iCode effectively treats multi-turn code generation as an interactive imitation learning problem by collecting roll- outs from leamndd policy and re-labeling them with expert. It circumvents the exploration burden of generic reinforcement learning which has exponentially higher sam- ple complexity (Sun et al., 2017). We briefly analyze why this problem is amenable to imitation learning and prove performance bounds for pCODE.
4. Experiments
Through our experiments, we aim to analyze (1) How does
PCODE compare to leading state-of-the-ar methods? (2)
Does a learned verifier facilitate training a better generator? (3) Can the use of learned verifier improve multi-turn BoN

---

Multi-Turn Code Generation Through Single-Step Rewards
search inference time? (4) Does the test-time search show scaling law trends? (5) Which loss function works better for learning verifier for μCODE?
Method
A.ama-3.2-1B
Llama-3.1-88
N
MBPP HE
MBPP
IEE
CC
Single-Tur
4.1. Setup
Instruct
1
35.1
25.6
52.1
59.8
3.6
RFT
1
35.7
34.1
53.7
54.9
Models. The generator model in μCODE is initialized with 3.2--B--II-tBttt or Llama-3. 1arma--.--SB-Imae I-8B-Instruct (Dubey et al., 2024). The learned verifiers are initialized with the same models as generators and have randomly initialized linear layer to predict a scalar score (Stiennon et al., 2020).
Multi-Turr
Instruct
1
35.1
31.1
60.3
59.7
4.8
+BoN
5
47.3
35.7
69.7
62.9
13.8
RFT
1
31.1
31.7
58.9
61.2
7.2
+BoN
5
46.7
34.1
68.4
62.8
14.9
Datasets. We conduct experiments on MBPP (Austin et al., 2021) and HumanEval (Chen al., 2021) where the agent needs to generate code solutions in Python given natural language descriptions. We train the methods on the MBPP training set which comprises 374 problems and evaluate on the MBPP test set and HvmanEval (HE) dataset which have 500 and 164 problems. We also compare meth- ods on the DeepMind CodeContests dataset (CC, Li al. (2022a)) where train on 1000 problems sampled from the training set and evaluate on the 165 problems in the test set. We further describe the prompts and the split of public and private tests in Appendix C.1 and C.2. For training, we trained RFT and μCODE for 2 iterations in MBPP and HumanEval datasets and for iteration on CodeContests.
cCODE
1
37.9
35.4
62.1
60.9
7.9
+BoN
5
51.1
41.5
70.6
63.8
16.3
Table 1. Comparison of our method μCCODE with baselines across MBPP, HumanFval, and CodeContests datasets. N = 1 denotes generating solutions with 0 temperature. The Best-of-N (BoN) accuracy is computed with N candidate solutions at each where the public tests and learned verifier are used for selection. We observe that μCODE outperforms competing methods based Llama-3.2- 1--2-IIIIInstru and Llama-3.1 ----aa....------ii-i-
models. The best performance for each dataset and model-sized is highlighted in bold and similar performances (within 1 1%) are underlined.
sample with a temperature of 0.7.
Baselines. We compare μCODE with single and multi-
4.2. Results
turn baselines. For single and multi-turn settings, we re- port metrics with Llama-3.2-1B Instruct and Llama-3.1- 1- 8B-Instruct as base models. We also compare with re- jection finetuning (RFT) where we collect multiple roll- outs and filter trajectories with a correct solution for fine- tuning (FT). For multi-turn RFT, given a positive rollout f2. V1, 01.... yr, or), ) the model is finetuned over all the sub-trajectories {st, De. D For the multi-turn BoN search at inference time, we used the verifier learned from the last iteration for μCODE and trained a verifier with gen- crated rollouts for the base and RFT models. Lastly, for multi-ture tulti BoN search at inference time, we pick the best code solution with hybrid approach where solution pass- ing public tests is preferred followed by ranking solutions with learned verifier.
In Table 1, we compare our proposed algorithm μCODE with the baselines. We first evaluate the generators using code generated via greedy sampling for each problem (BoN with N 1). Our approach μCODE outperforms RFT across both benchmarks with IB-sized model demonstrating the efficacy of using one-step recoverability and learned verifiers. To highlight, our method μCODE with the 1B model outperforms baselines by 2.2 % and 1.3% on MBPP and Human datasets. Interestingly, the performance of RFT drops when compared to the base Instruct model for the multi-turn setting which can be attributed to the fact that finetuning dataset consists of sub-trajectories with incorrect code solution non-terminal steps. For the 8B-sized variant, we observe similar trends where we see that all algorithms benefit from the multi-turn BoN search at inference time. Additionally, #CODE performs better than both single and multi turn baselines across benchmarks.
Metrics. We evaluate the methods by comparing the BoN accuracy. The generator is allowed upto = 3 turns and the final solution is used for evaluation over private tests. The BoN@ I evaluates the agent producing the solution in the first attempt and is obtained via greedy decoding with a temperature of 0. The BoN accuracy measures the ability of verifiers to leverage test-time compute by generating N candidate solutions in parallel at each turn. At each turn, the verifier ranks N = 5 solutions (unless stated otherwise) provided by the generator. For the BoN performance, we
With more inference budget and multi-tur BoN search at test-time, where the learned verifier and outcomes public tests are used to select the best solution at each turn, observe that every method performs better with the test-time search procedure by upto 13%. For the IB-sized mod- els, our method μCODE significantly outperforms baselines by 4.4% on MBPP and by 5.8% on Humaneval datasets. For the 8B-sized variant, PCODE performs better than the
5

---

Multi-Turn Code Generation Through Single-Step Rewards
baselines across datasets. On the more challenging task of CodeContests, all methods benefit from the BoN search and observe performance gains of upto 2x. On this benchmark, μCODE outperforms the RFT and base model baselines by 1.4%. We further investigate these trends with a Qwen model in Appendix B. and additional unit tests on MBPP and HvlanEval benchmarks Appendix B.2.
Approach
Llama-3.2-1B
Llama-3.1-80
MBPP
HI
MBPP
HE
Base
Random
31.7
24.6
58.0
57.9
LV
30.3
29.4
62.5
61.0
PT
46.4
33,4
68.4
60.7
PT+LV
47.3
35.7
69.7
62.9
4.3. Analysis
RFT
Random
31.1
27.4
58.9
57.7
To delve deeper into the improvements, we conduct a component-wise ablation study where we I) check the effect of one-step recoverability and the learned verifier for creat- ing the local expert (4.3.1), 2) compare different verifiers for multi-turn BoN search test-time (4.3.2), 3) test the efficacy of agents at utilizing execution feedback (4.3.3), 4) assess scaling behaviors at inference time with number of candidate generations (N) at each turn (4.3.4), and 5) study different loss functions to train the verifiers (4.3.5).
LV
33.2
29.6
62.2
61.3
PT
46,8
36.8
67.4
61.4
PT+LV
46.7
36.5
68.4
62.8
CODE
Random
37.5
31.5
61.5
58.4
LV
43.3
36.5
64.8
60.6
PT
49.4
39.7
69.4
61.4
PT+LV
51.1
41.5
70.6
63.8
1. WHAT MAKES GOOD GENERATOR PCODE?
Table 3. Comparing BoN with different ways of picking solutions at each turn for multi-tur BoN search using the IB sized model. The hierarchical approach of using public test and learned veri- fier (PT+LV) outperforms picking solutions with only using either public tests (PT) the learned verifier (LV). The best performance for each dataset and model-size is highlighted in bold and similar performances (within 1%) are underlined.
Method
One-step
Verifier
MBPP
HE
RFT
X
Oracle
46.7
36.5
RFTLV
X
Learned
49.0
38.9
μCODEov
V
Oracle
48.2
38.0
cCODELV
Learned
48.5
39.1
μCODE
Both
51.1
41.5
benefits relabeling. The performance similar for the setting where the learned verifier used. To leverage the best both worlds, ,CODE uses linear combination of scores from learned and oracle verifier for relabeling which outperforms each variant by around 2%.
Table Comparison of using learned verifier (LV) and relabeling with one-step recoverability (One-Step) with the IB-sized model. We observe that FT with the learned verifier RFT performs better than FT with the oracle verifier scores RFT. Morcover, μCODE performs best when from both verifiers are used for relabeling.
4.3.2. DOES LEARNED VERIFIER AID BON SEARCH?
Firstly, we compare different verifiers for training to demon- strate the benefits of using dense rewards obtained from learned verifiers. The RFT baseline uses the oracle verifier to filter trajectories and does not relabel subsequences for FT. In this experiment, we compare RFT RFTLy where the learned verifier selects the top K rollouts for each prompt ranked via the learned verifier for FT. We use K = 3 in our experiments. We observe in Table 2 that finetuning with the learned verifier outperforms the RFT baseline. In contrast to RFT, which lacks training data for prompts with no correct solutions, RFTLy effectively trains the generator to ascend dense rewards obtained from the learned verifier.
We study the effect of different verifiers for ranking the candidate solutions to pick the best solution for multi-turn BoN search at inference time. We test with Random strategy where the policy randomly picks from the N solutions. We compare using the outcomes public tests (PT) that picks any solution that passes the public test. Note that this involves evaluating all generated solutions at every turn with all the given public tests. We also compare to selecting a solution based on scores obtained via the learned verifier only (LV). This is crucial as certain applications such priv- ileged information like public tests are not available and the agents can benefit from learned verifiers to improve search during inference. Lastly, we compare with the combination of public tests and using the dense scores obtained from the learned verifier to break ties at each turn (PT+LV).
Secondly, we present the advantages of relabeling subtra- jectories with our insight of one-step recoverability. We extend the baselines with our proposed relabeling strategy described in Sec. 3.3. We call these methods μCODEOO (80 = 1, 3 = 0) and CODELY (8o = 0. B = 1) de- pending on the verifier used for relabeling. Table 2 shows that WoODEov outperforms the baseline RFT presenting the
In Table 3, we compare the baselines and μCODE with dif- ferent verifiers at inference-tine time. We observe that LV outper- forms Random strategy which shows that learned verifier
6

---

Multi-Turn Code Generation Through Single-Step Rewards
HumanEval
MBPP
MBPP (POMDP)
50
50
BoN
45
45
45
40
40
40
35
35
1
2
4
5
1
2
3
4
5
6
3
5
6
Turn
Turn
Turn
Instruct
RFT
cCode
Figure 2. Compares the BoN performance each (with 6 turns) HumanEval, MBPP datasets. We also present results partially observable version of MBPP where we remove the public tests from the prompt to test the efficacy of methods at incorporating execution feedback- MBPP (POMDP). We observe that all methods improve performance with more turns on MBPP and HumanEval datasets. However, MBPP (POMDP) the performance drops at first turn and μCODE closes the gap with performance on MBPP compared to baselines demonstrating its ability to incorporate execution feedback to improve code solutions each turn.
indeed selects better solutions amongst the candidates. Fur- thermore, using the outcome of public tests (PT) performed better than using learned verifiers (LV) and performs sim- ilarly on the HumanEval datset for 8B-sized models. We believe that this gap can be further reduced by learning more powerful verifiers with larger datasets. Interestingly, the hi- erarchical approach (PT+LV) that uses the learned verifier to break ties on the outcomes of public tests performs best across methods and datasets. We hypothesize that using learned verifiers is beneficial in two scenarios. Firstly, if multiple solutions pass the public tests, then the learned verifier filter out incorrect solutions which may not pass private tests. Secondly, if all candidate solutions are incor- rect, then the learned verifier chooses the most promising solution at each turn. This is crucial as picking a better solution with the learned verifier can lead to more relevant feedback for recovering the true solution.
BoN accuracy over this evaluation dataset for pCODE. and the baselines. We observe that the performance first turn drops for all methods by upto 13%. With the execution feedback each turn, &CODE improves the code solutions leading to gains of 15.9 % from turn I to turn 6 and matches its performance the MBPP dataset. In contrast, the base model and RFT were unable to close this gap in this partially observable setting and performed worse by around 6% that the MBPP dataset. This demonstrates the ability μCODE to recover better code solutions each turn by utilizing the execution feedback each turn, trend not observed for the Instruct model and the RFT baselines.
4.3.4. DOES μCODE SCALE WITH INFERENCE BUDGET?
MBPP
HumanEval
52
4.3.3. CAN 2CODE UTILIZE EXECUTION FEEDBACK?
BoN
40
We evaluate the ability of the trained generator utilize execution feedback and improve the code response across turns. We report the BoN accuracy till a turn which denotes the accuracy of obtaining a correct solution within turns. Note that the agents were trained with rollouts upto 3 turns and we report results with turns for this experiment. In Fig. 2 (left and middle), we present the results with IB- sized models where observe that BoN accuracy improves with successive turns across the benchmarks.
40
36
7
11
1
11
N
Figure 3. Test-time scaling with different values candidate so- lutions N at each turn. The candidate solutions are obtained from IB-sizdd generator μCODE. We observe that BoN per- formance improves with larger values of N on both datasets.
To further understand if μCODE learns to utilize execution feedback, we curated another test dataset from MBPP where we removed the sample unit tests provided in the prompt, and call MBPP (POMDP). Removing public unit test information from the prompt makes the information from execution feedback essential and is similar partially observable MDP setting. In Fig. 2 (right), we compare the
In the multi-turn setting, the number of candidate solutions rise exponentially with the number of turns. To avoid this, CCOEE uses the learned verifier during inference to select the most promising candidate among N candidates at each turn, leading to a linearly increasing number of calls to the generator. In this experiment, we study the inference- time scaling behaviors of pCODE where we scale the num-

---

Multi-Tura Code Generation Through Single-Step Rewards
ber of candidate generations N each turn. Figure 3 plots the BoN with different values of N (1 S N I 11). With more inference time budget, we observe that the perfor- mance improves with larger number of candidates at each turn on both datasets. The BoN accuracy plateaus with N 2 for HumanEval dataset where for MBPP dataset we still observe some performance gains with larger N.
the top solutions, the last two snippets are similar the candidates from the previous turn. However, the top ranked solution is novel solution and is more accurate the gen- erated code learns to extract single digit and multiply it. With the execution feedback, μCODE generates 2 correct responses- y/ and y and learned verifier chooses one of them compared to the incorrect response y/.
4.3.5. LOSS FUNCTION FOR VERIFIER
5. Related Work
As described in 3.2, compare against different loss fune- tions for training the verifier. For this experiment, we first generate multiple single step rollouts and label them via oracle verifier. Given oracle labels, we train verifiers with two loss functions - BCE and BT. During inference, the learned verifier picks the best ranked solution among the N solutions provided by the generator. Similar to (Cobbe et al., 2021), we report the BoN plot with different values of N obtained by first sampling N candidate solutions, choosing the top-ranked solution using the learned verifier, and then evaluating the solution against public and private tests. We calculate this metric over multiple samples for each value of N. Figure 4, we observe that the verifier trained with BT loss consistently outperforms the verifier trained on BCE loss on both MBPP and HumanEval.
Prompting To Solve Multi Step Tasks A common frame- work for tackling multi-step tasks with LLMs is prompting- based agentic systems. Self-Debugging (Chen et al., 2023b) asks the L.MM to iteratively improve code by providing exe- cution feedback while CodeT (Chen et al., 2022) asks the LLM to generate test cases. AlphaCodium (Ridnik et al., 2024) first reflects on input instructions, generates and fil- ters from multiple code generations, and finally iterates on public and self-generater test cases. MapCoder (Islam et al., 2024) incorporates four agents to generate example prob- lems, plans and code, and then perform debugging. How- ever, prompting -ased agents yield limited improvements.
Training LLMs for Multi Step Tasks Some work has explored explicitly training crities or reward models for multi-step reasoning tasks. In the coding domain, CodeRL (Le et al., 2022) trains token-level critic to aid in code generation and to perform inference-time search. CodeRL's mechanics are similar to our method, but their generator is not trained for multi-step: CodeRL trains a "code repairer" which conditions on one erroneous code completion while our generator incorporates multiple. ARCHER (Zhou et al., 2024), which frames multi-step tasks via two-level hierar- chical MDP, where the higher level MDP considers comple- tions as actions and the lower level MDP considers tokens as actions. Another line of work utilizes Monte Carlo Tree Search (MCTS) methods for training: rStar-Math (Guan et al., 2025) trains a policy preference model to boost small LMs' math abilities to match or exceed large reasoning- based LMs and ReST-MCTS (Zhang al., 2024) trains a process reward model (PRM) similarly to Math-Shepherd (Wang et al., 2024a). Although /CODE'S BoN search re- sembles a tree search, our key insight that multi-step code generation resembles a one-step recoverable MDP allows us to collect training trajectories much more efficiently. Fi- nally, some work has explored using verifiers only during inference time. In "Let's Verify Step by Step" (Lightman et al., 2023), the authors demonstrate that PRMs trained on erroneous math solutions annotated by humans outperform outcome reward models for filtering multiple inference time generations. Meanwhile, AlphaCode (Li et al., 2022b) trains a test generator to evaluate multiple code solutions.
MBPP
HumanEval
42-
42
39-
39
BoN
36
36
33
33
30
30
2
B
16
32
2
8
16 32
N
N
BCE
BT
Figure 4. Comparison between BCE and BT loss function for train- ing the verifier. We train the verifiers on samples generated by the base model (Llama-3.2-1) IB- 1.22-IB-Instruct Instruct). The learned verifier then ranks the candidate solutions from hase model and the BoN per- formance of selected solution is reported. The verifier trained with BT loss performs better incrcasing value of N.
4.3.6. QUALITATIVE RESULT
Figure 5 presents a qualitative example of multi-turn Best- of-N search with pCODE. Through this example, we demon- strate the advantages of dense scores from the learned veri- fier at facilitating efficient search across turns. We generate N 5 code solutions at each turn and show the top 3 ranked solutions using the dense scores. At the first turn, we observe that the last solution oî is less accurate than the other solutions yf and yf- The top ranked solution is used to collect the environment feedback. upon which the generator comes up with N new candidate solutions. Upon
Other works omit learning a critic or reward model alto-
8

---

Multi-Turn Code Generation Through Single-Step Rewards
"Calculate the product of the unit digits of two integers"
sultiplx(o,
wutttplyce,
auunit, digit (nn(
product str scr(product)) unit..lghtt Ln(CrofucL.St((-I)
)
str_h strio)
product unit. diglt (euinit_dight f_int 8:10 neturn prodact unit digit
uiLt dight product
return diit
int(xtr_al af-13) ([-()
reture urt... mig.t...oooccctt
del multiplaia, bi: prodict & raturn Lniggi
def multiply(a, b): product à 6
sulciplyia, unit
Y2
product_.str str(prodict)
)3
anit disit
unit_áigit inteprodact unt-_figtt
unitdiigtt dnit
Turn 1
def maltiplela, blt
product aiwl siglt product unit protuct a
Turn 2
product
anit_dipit product init_
Turn 3
Y3
de raltiplyie, bl:
n,str cetrriatttttteer or
recurn initt_stri sntte.str)
Figure 5. A qualitative example of multi-turn BoN search using dense rewards obtained via the learned verifier in pCODE. Here, we show the top 3 ranked solutions each turn / where Ra( vi) 2 Rx( u/') for < j. We observe that the learned verifier selects the better solution (in orange) at each turn. The selected solution is passed to public tests to retrieve execution feedback for the generator to improve the next code solution. The selected solution each turn is better than the last (less errors highlighted in yellow), with the final solution passing all tests. Note that there are 2 correct solutions at the final turn.
gether. In the coding domain, RLEF (Gehring et al., 2024b) derives rewards only on the executor's 's result on test cases and syntax checkers, and PPOCoder (Shojaee et al., 2023) additionally considers semantic and syntactic alignment, generated via data flow graphs and abstract syntax trees re- spectively, with a reference solution. The "oracle" rewards in these methods may not be informative for training, and in the case of PPOCoder, require complex constructs. We empirically show that having reward model is beneficial by comparing μCODE against the RFT baseline. Meanwhile, SCoRe (Kumar et al., 2024a) splits training into a "genera- tor" and "correction" phase, thus restricting the total number of turns to 2. RISE (Qu al., 2024) generates recovery steps via more powerful LLM or by selecting sampled comple- tion via the oracle rewards. Both methods are less efficient than μCODE, which doesn't it require generating corrections beyond generating training trajectories. Finally, FireAct (Chen et al., 2023a) and LEAP (Choudhury& & Sodhi, 2024) FT ReAct style agents while RL4VLM (Zhai et al., 2024) and GLAM (Carta et al., 2024) studies training LLMs with interactive environment feedback.
generalize to models of larger scales. Additionally, we train models on MBPP, whose training set has only 374 examples. However, we hypothesize that more training examples will lead to better performance. Finally, our datasets are only in Python, and our findings might not generalize to other programming languages.
Impact Statement
The proposed method for training code agents has the po- tential to streamline software development processes by automating routine coding tasks, thereby reducing human labor and accelerating production timelines. However, these advances will also introduce bugs, which can propagate scale if proper quality control is in place.
Acknowledgements
AJ is supported by Calcul Québec, Canada Ex- cellence Research Chairs (CERC), and Fonds de Recherche du Québec (FRQ) scholarship (DOI assigned: http:///oo.org1106777//////
program. The authors also grateful to Mila (mila.quebee) IDT and Digital Re- search Alliance of Canada for computing resources. AMR is supported in part by NSF CAREER #2037519 and NSF #2242302. SC is supported in part by Google Faculty Research Award, OpenAl SuperAlignment Grant, ONR Young Investigator Award, NSF RI #2312956, and NSF FRR#2327973.
6. Conclusion
We present PCODE, a simple and scalable method for multi- turn code generation through single-step rewards. ,CODE models code generation as one-step recoverable MDP and learns iteratively improve code with a learned verifier to guide the search. Experimental results demonstrate that cCODE outperforms methods using oracle verifiers by large margin. We acknowledge the following limitations of this paper. Due to limited budget, we were only able to train models with up to eight-billisn parameters. It is possible that the conclusions made in this paper do not
References
Anthony, T., Tian, Z., and Barber, D. Thinking fast and slow with deep learning and tree search, 2017. URL

---

Multi-Turn Code Generation Through Single-Step Rewards
https: wwt..oogg///oo.o..o 08439.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L.,, Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110. 1416,, 2021.
Austin, J., Odena, A., Nye, M., Bosma, M., Michalewski, H., Dohan, D., Jiang, E., Cai, C., Terry, M., Le, Q. et al. Program synthesis with large language models. arXiv preprint arXiv:2108.077 07732, 2021.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle,
A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21777 2024.
Brown, B., Juravsky, J., Ehrlich, R., Clark, R., Le, Q. V., Ré, C., and Mirhoseini, A. Large language monkeys: Scaling inference compute with repeated sampling, arXiv preprint ar XXiv:2407.21787 2024.
Gehring, J., Zheng, K., Copet, J., Mella, V., Cohen, T., and Synnaeve, G. Rlef: Grounding code ilms in execution feedback with reinforcement learning. arXiv preprint arXiv:2110.02089 2024a.
Carta, T., Romac, C., Wolf, T., Lamprier, S., Sigaud, O., and Oudeyer, P.-Y. Grounding large language models in interactive environments with online reinforcement learning, 2024. URL https::/ peatps://arxiv..oo org/orggaoooo abs/ 2302. 02662.
Gehring, J., Zheng, K., Copet, J., Mella, V., Cohen, T., and Synnaeve, G. Rlef: Grounding code lims in execu- tion feedback with reinforcement learning, 2024b. URL https: /ata/aaiiivv.///..///.aa/.//iiiv org/ /210 02089.
Chen, B., Zhang, F., Nguyen, A., Zan, D., Lin, Z., Lou, J.-G,, and Chen, W. Codet: Code generation with gener- ated tests, 2022. URL ptttps://arxvva org/ abs/ 2207. 10397.
Guan, X., Zhang, L. L., Liu, Y., Shang, N., Sun, Y., Zhu, Y., Yang, F., and Yang, M. rstar-math: Small Iims can master math reasoning with self-evolved deep thinking, 2025. URL wttphhtt///// aaxiv.iiv www.i.www.......aaa........oow
Chen, B., Shu, C., Shareghi, E., Collier, N., Narasimhan, K., and Yao, S. Fireact: Toward language agent fine- tuning, 2023a. URL https:://arxt org. abs/ 0310.05915
Islam, M. A., Ali, M. E., and Parvez, M. R. Mapcoder: Multi-agent code generation for competitive problem solving, 2024. URL https: https://arxiv..e /ttp:////xxvv..og/abb. 2405 11403.
Chen, M., Tworek, J., Jun, H., Yuan, Q., de Oliveira Pinto, H. P., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., Ray, A., Puri. R., Krueger, G., Petrov, M., Khlaaf, H., Sastry, G., Mishkin, P., Chan, B., Gray, S., Ryder, N. Pavlov, M., Power, A., Kaiser, L., Bavar- ian, M., Winter, C., Tiller, P., Such, F. P., Cummings, D., Plappert, M., Chantzis, F., Barnes, E., Herbert- Voss, A., Guss, W. H., Nichol, A., Paino, A., Tezak, N., Tang, J.. Babuschkin, I., Balaji, S., Jain, S., Saunders, W., Hesse, C., Carr, N., Leike, J., Achiam, J., Misra, V., Morikawa, E., Radford, A., Knight, M., Brundage, M.. Murati, M.. Mayer, K., Welinder, P., McGrew, B., Amodei, D., McCandlish, S., Sutskever, I., and Zaremba, W. Evaluating large language models trained on code, 2021.
Kakade, S. and Langford, Approximately optimal ap- proximate reinforcement learning. Proceedings of the Nineteenth International Conference on Machine Learn- ing. pp. 267-274, 2002.
Kumar, A., Zhuang, V., Agarwal, R., Su, Y., Co-Reyes, J. D., Singh, A., Baumli, K., Iqbal, S., Bishop. C., Roelofs, R., Zhang, L. M., McKinney, K., Shrivas- tava, D., Paduraru, C., Tucker, G., Precup, D., Behba- hani, F., and Faust, A. Training language models to self-correct via reinforcement learning, 2024a. URL https: wwwpsiiv.oog/aeoo 2409. 12917.
Kumar, A., Zhuang, V., Agarwal, R., Su, Y., Co-Reyes, J. Singh, A., Baumli, K., lqbal, S., Bishop. C., Roelofs, R., et al. Training language models to self-correct via reinforcement learning, arXiv preprint arXiv:2409.12917 2024b.
Chen, X., Lin, M.. Schärli, N., and Zhou, D. Teaching large language models self-debug, 2023b. URL https: 05128.
//arxiv. org//bgg///soo abs/abaaaa// 0512202..............1.121122881
Chen, X., Lin, M., Schärli, N., and Zhou, D. Teaching large language models to self-debug. The Twelfth International Conference on Learning Representations, 2024. URL https::/...............t http///ppeeeeeeeeeeeeeeeeee wtwperewwwwwieeeeeeeeeeeeee forum? Id=KuPixIqPic
Le, H., Wang, Y., Gotmare, A. D., Savarese, S., and Hoi, S. C. H. Coderl: Mastering code generation through pretrained models and deep reinforcement learning, 2022. URL https::///// /tt//aaavvv////////a//eeee/aaaia wttp://pgaabaa........./
Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J., Leblond, R., Eccles, T., Keeling, Gimeno, F, Dal Lago, A., Hubert, T., Choy, P., de Masson d' A'Atumee C., Babuschkin, I., Chen, X., Huang, P.-S,, Welbl, J., Gowal,
Choudhury, S. and Sodhi, P. Better than your teacher: Lim agents that learn from privileged ai feedback, 2024. URL https: //axxiv.. wwwg/org/oo... abs/////// 22100...... 05434.
10

---

Multi-Turn Code Generation Through Single-Step Rewards
S., Cherepanov, A., Molloy, J., Mankowitz, D., Suther- land Robson, E., Kohli, P., de Freitas, N., Kavukeuoglu, K., and Vinyals, O. Competition-level code generation with alphacode. arXiv preprint 2mXiv:2203.07880 2022a.
learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 627-635. JMLR Workshop and Conference Proceedings, 2011.
Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J.. Leblond, R., Eccles, T., Keeling, J., Gimeno, F., Dal Lago, A., Hubert, T., Choy, P., de Masson d' Autume, C., Babuschkin, I., Chen, X., Huang, P.-S., Welbl, J., Gowal, S., Cherepanov, A., Molloy, J., Mankowitz, D. J., Sutherland Robson, E., Kohli, P., de Freitas, N., Kavukcuoglu, K., and Vinyals, O. Competition- level code generation with alphacode. Science, 378 (6624):1022-1097, December 2022b. ISSN 1095-9203. doi: 10.1 10.11126/scieecceaay111333 URL http: /tpp//xxx// doi. org 10. 1tt...116/cccccc abg.l abq1158.
Setlur, A., Nagpal, C., Fisch, A., Geng, X., Eisenstein, J., Agarwal. R., Agarwal, A., Berant, J., and Kumar, Re- warding progress: Scaling automated process verifiers for Ilm reasoning. arXiv preprint arXiv:2410.081 2024.
Shojaee, P., Jain, A., Tipimeni, S., and Reddy, C. K. Execution- based code generation using deep reinforce- ment learning, 2023. URL https: http:///xxvvvrrr.. abs 22t//231..2 13816
Snell, C., Lee, J., Xu, K., and Kumar, A. Scaling Ilm test- time compute optimally can be more effective than scal- ing model parameters. arXiv preprint arXiv:2408.03:: 2024.
Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I,, and Cobbe, K. Let's verify step by step, 2023. URL https: //arxiv. org/ aba 20050.
Stiennon, N., Ouyang, L., Wu, J., Ziegler, D., Lowe, R., Voss, C., Radford, A., Amodei, D., and Chris- tiano, P. F. Learning to summarize with human feedback. In Larochelle, H., Ranzato, M., Had- sell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, vol- ume 33, pp. 3008-3021. Curran Associates, Inc., 2020. URL httpp::/pproceedingg .ew.oooceeeeinnn..eeee.s.e...ee. cc/ pappaapr___i htc//pppee_fiileeepppeee//2//2/2 1 1E388665522093005666666688883 pdf.
Muennighoff, N., Liu, Q., Zebaze, A., Zheng, Q., Hui, B., Zhuo, T. Y., Singh, S., Tang, X., von Werra, L.,, and Long- pre, S. Octopack: Instruction tuning code large language models. arXiv preprint arXiv:2308.00 07,24, 2023.
Ni, A., Allamanis, M., Cohan, A., Deng, Y., Shi, K., Sutton, C., and Yin, P. NExt: Teaching large language models to reason about code execution. In Forty-first International Conference on Machine Learning, 2024. URL ht tps: //openreview net / forum? www
Sun, W., Venkatraman, A., Gordon, G. J., Boots, B., and Bagnell, J. A. Deeply aggrevated: Differentiable imita- tion learning for sequential prediction. In International conference on machine learning, pp. 3309-3318, PMLR, 2017.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R. Training language models to follow instructions with human feedback, 2022. URL https: //a //arxiv. org/ abs/ / 2203. 02155.
Swamy, G., Choudhury, S., Bagnell, A., and Wu, S. Of moments and matching: A game- theneetthcortic framework for closing the imitation gap. In International Conference Machine Learning. pp. 10022-1008 PMLR, 2021.
Qu, Y., Zhang, T., Garg, N., and Kumar, A. Recursive in- trospection: Teaching language model agents how to self- improve, 2024. URL https:/ /t///aaxivv//. org/ /bs/ 2407. 18219.
Wang. P., Li, L., Shao, Z., Xu, R. X., Dai, D., Li, Y., Chen, D.,. Wu, Y., and Sui, Z. Math- Kath-sheppherd Ver- ify and reinforce lims step-by-step without human notations, 2024a. URL https: http//axvvvvo//// /abs/ 2312 08935.
Ridnik, T., Kredo, D., and Friedman, I. Code generation with alphacodium: From prompt engineering to flow en- gincering, 2024. URL https: / www.aaa.vvvo....a...aa...a...... org/ abs/ 1401.08500.
Wang, X., Chen, Y., Yuan, L., Zhang, Y., Li, Y., Peng, H., and Ji, H. Executable code actions elicit better LLM agents. In Forty-first International Conference on Ma- chine Learning, 2024b. URL httttt::s//ppeeeeeeeeeeeee net/ forum? ii j=JJBBXXAfFa
Ross, S. and Bagnell, J. A. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint arXiv: 1406.5979, 2014.
Ross, S., Gordon, G., and Bagnell, D. A reduction of imita- tion learning and structured prediction to no-regret online
Welleck, S., Lu, X., West, P., Brahman, F,, Shen, T., Khashabi, D., and Choi, Y. Generating sequences

---

Multi-Tura Code Generation Through Single-Step Rewards
by learning self-correct. In The Eleventh In- ternational Conference on Learning Representations, 2023. URL httta:::/ppeeeeveee.netttt 1d-hH36JeCZDa0.
Wu, Y., Sun, Z., Li, S., Welleck, S., and Yang. Y. Infer- scaling laws: An empirical analysis of compute- optimal inference for problem-solving with language models. arXiv preprint trXiv:2408.00720 2024.
Zelikman, E., Wu, Y., Mu, J., and Goodman, N. Star: Boot- strapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35:15476-15488 2022.
Zhai, Y., Bai, H., Lin, Z., Pan, J., Tong. S., Zhou, Y., Suhr, A. Xie, S., LeCun, Y. Ma, Y., and Levine, S. Fine- tuning large vision-language models decision-making agents via reinforcement learning, 2024. URL https: //a //axxiv.. t/arxiv.org////ooeee........ abs 2405 10292.
Zhang, D.. Zhoubian, S., Hu. Z.. Yue, Dong, and Tang, J. Rest-mets*: Llm self-training via process re- ward guided tree search, 2024. URL https: /arxiv. org/ abs//ab/// 2abs/240e 2406. 03816. 6.
Zhao, W., Jiang, N., Lee, C., Chiu, T., Cardie, C., Gallé, M., and Rush, A. M. CommitO: Library generation from scratch. arXiv preprint arXiv:2412.01
2024.
Zheng, L., Yin, L., Xie, Z., Sun, C., Huang, J., Yu, C. H., Cao, S., Kozyrakis, C., Stoica, Gonzalez, J. E., Bar- rett, C., and Sheng. Y. Sglang: Efficient execution of structured language model programs, 2024. URL https: pettss///arxive org/ abs/abss///111 07104.
Zhou, Y., Zanette, A., Pan, J., Levine, S., and Kumar, A. Archer: Training language model agents via hierarchical multi-turn rl. arXiv preprint arXiv:2402.1 /9446, 2024.
12

---

Multi-Turn Code Generation Through Single-Step Rewards
A. Proofs
A.I. Proof of Theorem 3.2
The proof relies on two important results.
The first is the Performance Difference Lemma (PDL) (Kakade Langford, 2002) which states that the performance difference between any policies can be expressed the sum of advantages.
(( - J(x')
Σ Es
Σ AT (st
(8)
where 5, dā is the induced state distribution by and AT (st, ar) Q (0ts ae) V (st) the advantage w.r.t n².
We apply the PDL between the expert x" and the learner I
- J [Tx
Σ B Ba Σ
(se, (ar(0))))) m(aelss))
where the result follows from (E., A (s,,,, (x)=T* (at|st) =0
According to the one-step recoverable MDP definition, -1 s (²) S for all (s, Hence we can bound the performance difference as
J(T)) - J(x)
Σ E Barnd
Σ (st, (a|s)) (( (als;))
T
< [|A4(,.))
B Be / (1(hh) T (11s))l
(Holder's Inequality)
1=1
Ra (1((8))) (-1s))]l
(One step recoverability)
The second result we use us from interactive imitation learning DAGGER (Ross et al., 201 1) that reduces imitation learning to no-regret online learning. DAGGER shows that with n² as the expert teacher guarantees that after N iterations, it will find least one policy
Exwar (+]s) n" (+|s)]l < Eg-ar Tolas (-|s) x (.(ss)l1 ((N)
(10)
where ((N) is the average regret, and dl is the time average distribution of states induced by policy n, Telass is the best policy in policy class.
Plugging this in we have
J(TT)- (TT)= <
Egsdy (+1ss) nT (-1s:)llz
1=1
Es Eardy [[Te000 n (+(s:))l + 7(N) From (10)
1=1
$ ( + (NN))
13

---

Multi-Turn Code Generation Through Single-Step Rewards
B. Additional Results
B.1. Qwen Model
Method
MBPP
HE
Instruct
53.8
64.5
+ BBNN
60.9
70.3
RFT
57.0
66.6
+BoN
58.0
71.3
μCODE
59.0
70.5
+oN
63.1
74.0
Table Comparison of our method μCODE with baselines across MBPP, HumanEval using the Qwen-2.5-1.5B. ---.------.S model.
B.2. Additional private tests
Method
N
MBPP+
HE+
Instruct
43.2
25.7
+BoN
5
49.9
31.9
RFT
1
44.3
26.7
+BoN
5
50.0
34.3
CoDDE
1
48.7
32.4
+BoN 5
55.1
40.0
Table Comparison of method μCODE with baselines across MBPP+, HumanEval+ using the Jlama-3.--B--nnttmuee model. MBPP+ and HumanEval+ introduce 35x and 80x more tests than their original counterparts respectively. Note that MBPP+ has higher score than MBPP because there are 30% fewer problems
C. Hyperparameters
Model
Generator
Verifier
Training Epochs
2
2
Learning Rate
10-7
10-6
Batch Size
32
64
Max seq length
4096
2048
Table 6. Hyperparameters for SFT and RM training.
C.O.1. TRAINING PARAMETERS
Table 6 contains hyperparameters for training the generator and reward model on both models 1-aama-.1--8--nsttttte and Llama-3.22 3.2---..1111 B-- Insttructt and datasets (MBPP and HumanEval), We perform 2 iterations of training with μCODE, starting from the base model each iteration. All training IB models with 48 GB of memory per GPU or 4 H100 GPUs for 8B models with 80 GB of memory per GPU.
machines with either 4 RTX 6000 Ada Generation GPUs for
C.0.2. INFERENCE PARAMETERS
We use SGLang (Zheng et al., 2024) to serve our models for inference. Greedy experiments use temperature 0 with flags disable-radix-caae -max-rumman rwwnrnn-nnnuuuueeeee I to ensure deterministic results while BoN search experiments use a temperature of 0.7. All experiments are capped to 1000 tokens per completion per turn.
14

---

Multi-Turn Code Generation Through Single-Step Rewards
C.I. Prompts
C.I.I. SINGLE STEP PROMPT
Immediately below is the prompt template generate code completion in single-stor step method or generate the 1st step in multi-step method. Below the prompt templates examples of the code prompt and public tests for HumanEval, MBPP, and CodeContests.
Single Step Prompt
Write a Python funct on implementation for the following prempt:
\prompt\)
Your code should satisfy these test3:
\ttes\)
Please follow the following instruction::
Reason about the problem and any base cases before writing the code.
You must return the implementation code in the following format:
"python
<CODE GOES HERE>
You must only return single code bleck since we only parse the first code block.
Do not include any tests in your code will run the suite and return any error feedback.
Include relevant import statements.
HumanEval Prompt Example
from typing import List
def has_close elements (numbers: List/f threshold: flcat) -> bool:
*** Check if in given list of numbers, are any two numbers closer to each other
than
given threshold.
>>> has_close_elements ( [[1.0, 2.0, 3.0), 0.5)
False
>>> ses_cclos__elementc [[1.0, 2.8, 3.0, 4.0, 5.0, 2.01, 0.3)
True
HumanEval Test Example
def check (has_closs_eeeeeentt
assert has_close_eeemmnt emmntts ([1.0, 2.0, 3.0], 0.5) False
assert has_close_el ements ([) ([1.0, 2.8, 3.0, 4.0, 5. 2.01, 0.3) -- True
check chas_ latas_coos_eeeeees_eeeee elements)
MBPP Prompt Example
Write function to find the minimum cest path to reach (m, n) from (0, 0) for the given cost matrix cost II [] and positien (n, n) in cost[]
15

---

Input Multi-Tury Code Generation Through Single-Step Rewards
MBPP Test Example
assort min_cost ([[1, 31, 14, 21,
11,
5,
311
2)
assort cos_ ([[2, 3, 4], 15, 31 12, 6, 411
2)
assert mos_ ([[3, 4, 51, [6, 10, 41
13
7,
511,
2,
2)
16
CodeContests Prompt Example
Provide Python solution for the follcwing competiti programming question:
Mr. Chanek has an array a of n integers. The prettiness value of is denoted as:
$$$ (11\sigma_(1111 (n) (1=)gma_(--1)"mm) (gged(a_i, a_)) Aedot \ged 1
where (x, y) denotes the greatest common divisor (GCD) of integers x and y.
In other words, the prettiness value of array is the tetal sum of Aged a_i Aedot \ged j) for all pairs (i, 5).
Help Mr. Chanek find the prettiness value of a, and output the result modulo 10"9 + 7!
The first line contains an integer n (2 Aleq Aleq 10"5).
The second line contains integers a,,, 2,,, a (1 Aleq a \leq 10"5).
Output
Output integer denoting the prettiness value of module 10"9 7.
Example
Input
6 2 1 4
Output
77
Your code should be enclosed triple backticks like so: "python YOUR CODR, HRRR ",, Use the backticks for your code only.
CodeContests Test Example
Input fed through stdin and output checked against stdout
('input': : ('54554 59286 71521 84428 60278\n', '2\n83160 83160)n') ), 'output': ['1027150'n', '415800'nn')
1.2. FEEDBACK PROMPT
Immediately below is the prompt template for how provide feedback in multi-step methods. The feedback only consists of executor eтror traces, and we provide an example from HumanEval.
16

---

Multi-Turn Code Generation Through Single-Step Rewards
Multi- Multi-Step Feedback Prompt
Feedback:
\(feedback\) }
HvmanEval Multi-Step Feedback Prompt
Traceback (most recent call last):
File "test.py" line 18, in <module> assert has close elements (11.0, 2.0, 3.01, 0.5) = False
AssertionError
C.2. Public Private Tests
We choose a public-private test split for HumanEval and MBPP to ensure that naively passing the public tests does not guarantee private test success. For HumanEval, we use a single test from the code prompt's docstring as the public test and the remaining tests along with the official suite as private tests. For ease of parsing, we utilize processed version of HumanEval, HumanEvalPack (Muennighoff al., 2023). For MBPP, public test, and the remaining tests and any "challenge test list" tests private tests.
a single test from the official test suite the
17


Reviews:
[{"review_id": "fDGgBX4x2F", "reviewer": "Reviewer_vyX7", "summary": "This paper addresses code generation from multi-turn execution feedback. The authors propose uCode a simple and scalable approach that solves multi-turn code generation using only single-step rewards. The key insight is that code generation is a one-step recoverable MDP. uCode trains both a generator and a verifier. Experiments show improvement against StAR.\n\n\n## update after rebuttal: Thank you for your answer. I have increased my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback. We are glad that you found the paper well structured and our experiments thorough. We address your questions below.\n\n> Investigate other LLMs that are not Llama, and include larger models.\n\nWe investigate the performance of the Qwen-2.5-1.5-Instruct model, Multi-STaR and $\\mu$Code at Pass@3 and BoN@3 metrics on MBPP and HumanEval datasets. Below, we present the table and show that $\\mu$Code outperforms the baselines.\n\n### MBPP\n| Algorithm         | Pass@3 | BoN@3 |\n| :---------------- | :------: | :------: |\n| Qwen-2.5-1.5-Instruct    |53.8|60.9\n| Multi-STaR  |57.0|58.0\n| $\\mu$Code   |**59.0**|**63.1**\n\n### HumanEval\n| Algorithm         | Pass@3 | BoN@3 |\n| :---------------- | :------: | :------: |\n| Qwen-2.5-1.5-Instruct    |64.5|70.3\n| Multi-STaR  |66.6|71.3\n| $\\mu$Code   |**70.5**|**74.0**\n\nOur experiments are restricted to models that can be trained on 4 x A100 GPUs with 80 GB memory each and training of larger models greater than 8B requires more GPU memory. We expect $\\mu$Code should scale to larger models with more compute. \n\n> Investigate the performance when the turn limit is above 3. > Same with the \"training\" time following algorithm 1.\n \nIn the paper, we ran BoN search for a turn limit of 3. We present the results with a turn limit of 6 below (with the 1B-sized model used in Table 1). Note that the model is trained with a turn limit of 3. $\\mu$Code achieves the best performance on both datasets across most turn limits. This highlights the versatility of $\\mu$Code at generalizing to larger turn limits at test-time. Additionally, our results show that $\\mu$Code achieves the largest gains per turn, suggesting it is better at incorporating execution feedback and improving code solutions across turns. This experiment validates that $\\mu$Code is performant with more turns during evaluation. We believe that training with a higher turn limit could further improve the performance.\n\n### MBPP\n| Algorithm         | T=1 | T=2 | T=3 | T=4 | T=5 | T=6\n| :---------------- | :------: | :------: | :------: | :------: | :------: | :------: |\n| Llama-3.2-1B-Instruct        |39.2|41.5|43.1|44.0|45.0|45.5|\n| Multi-STaR  |**39.4**|40.9|41.4|41.9|42.2|42.7|\n| $\\mu$Code   |38.1|**43.9**|**46.6**|**48.8**|**50.1**|**50.9**|\n\n### HumanEval\n| Algorithm         | T=1 | T=2 | T=3 | T=4 | T=5 | T=6\n| :---------------- | :------: | :------: | :------: | :------: | :------: | :------: |\n| Llama-3.2-1B-Instruct        |34.8|35.6|36.6|38.0|38.4|38.6|\n| Multi-STaR  |36.8|36.8|37.2|37.8|38.2|38.2|\n| $\\mu$Code   |**38.2**|**45.7**|**48.4**|**50.6**|**51.0**|**51.4**|\n\n> Fundamentally, the only baseline used is STaR.\n\nWe point the reviewer to our response to Reviewer QsKU where we have provided an additional baseline: Rejection Fine-tuning with a learned verifier, or RFT (LV). Here, we select the top trajectories ranked using the learned verifier for a prompt and finetune at each iteration. This is similar to the Multi-STaR baseline, where the learned verifier is used to filter trajectories instead of the ground truth reward. We observed that $\\mu$Code performs better than RFT (LV) baseline.\n\nBest regards,\\\nThe Authors", "claims_and_evidence": "1. Novel framework\n- Yes\n2. multi-turn best-of-n approach that utilizes a learned verifier at inference time\n- Yes (although it does not seem necessarily novel)\n3. theoretical analysis \n- Yes\n4. Experiments on MBPP and Human Eval\n- Yes\n5. Analysis\n- Yes", "methods_and_evaluation_criteria": "The main idea is that one-step recoverable MDP implies that a correct code can be recovered from any intermediate state in a single step. uCode follows an expert iteration framework with a local search expert. It trains iteratively two components: a learned verified and generator. At inference time, both are used as best-of-n search.\n\nFirst, uCore needs a dataset that is created using the current generator. The verifier is trained on the aggregated dataset. An expert is constructed and the dataset is re-labeled. Finally, the model is fine-tuned using the dataset. Repeat as many time until convergence. The training part is sound. At inference, the authors propose multi-turn best-of-N. At each turn, the generator produces N one-step rollouts and the verifier selects the most promising one and is executed in the environment to obtain the feedback. The process is repeated.\n\nFinally, the theoretical analysis is sound.", "theoretical_claims": "Yes the one in section 3.5", "experimental_designs_or_analyses": "The models are Llama-3.2-1B instruct or 8B instruct. I would recommend the authors to also investigate other LLMs that are not Llama, and include larger models. Turn limit = 3. Datasets and metrics used are the standard ones. Fundamentally, the only baseline used is STaR. I would encourage the authors to include another model.\n\nOther than that, the experiments are well executed and the analysis are sound!", "relation_to_broader_scientific_literature": "I am not familiar with the literature.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Overall, well-written paper and well structure. Easy to read and follow. The methodology is sound, and the experiments as well. I would encourage the authors to include another baseline investigate the performance when the turn limit is above 3.", "other_comments_or_suggestions": "No", "questions_for_authors": "What are the performance with another LLM that is not Llama? Same with bigger model.\nCould you provide a performance analysis with different turn limits (> 3)?\nSame with the \"training\" time following algorithm 1, and cost/efficiency.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nY57FyNBU8", "reviewer": "Reviewer_hcVQ", "summary": "The paper introduces $\\mu$-Code, a scalable approach for multi-turn code generation that utilizes single-step rewards. It treats code generation as a one-step recoverable MDP, allowing correct code recovery from any intermediate state, and integrates a generator and verifier to iteratively train the system. The approach demonstrates substantial improvements over existing methods like STaR, with a detailed analysis of reward models and policy design choices.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback and are glad that you found our approach simple and theoretical justification insightful. We address your questions below.\n\n> I would like to see a more in-depth discussion regarding this claim, rather than treating it merely as a basic assumption.\n\nFor the task of code generation, there are two major sources of errors: 1) syntax errors and 2) algorithmic errors. For (1), we expect gradual improvement because fixing the errors should lead to a better solution at the next turn. However, the change might not be gradual for (2) when the approach is incorrect. In this scenario the agent might have to modify the algorithm and as pointed out by the reviewer can be difficult to recover from. Since, the task of code generation is one-step recoverable, this allows $\\mu$Code to relabel with a better solution and thereby recover from harder scenarios. In the paper, we provided the theoretical justification to support this claim in Theorem 3.2 (Section 3.5) and our experiments demonstrate the efficacy of $\\mu$Code. Below, we present an example where $\\mu$Code successfully resolves an algorithmic error.\n\n**Prompt**: Write a function to calculate the height of the given binary tree.\n\n**Turn 1**\n```\ndef max_height(root):\n    if root is None:\n        return 0\n    \n    queue = [(root, 1)]\n    \n    while queue:\n        node, height = queue.pop(0)\n        if node is None:\n            return height\n        queue.append((node.left, height + 1))\n        queue.append((node.right, height + 1))\n        \n    return -1\n```\n\n**Turn 2**\n```\ndef max_height(root):\n    if root is None:\n        return 0\n    \n    left_height = max_height(root.left)\n    right_height = max_height(root.right)\n    \n    if left_height > right_height:\n        return left_height + 1\n    else:\n        return right_height + 1\n```\nNote that the first solution takes an iterative approach and is incorrect because the function returns as soon as any leaf node is reached. However, the code solution at next iteration switches from an iterative to a simpler recursive approach and is correct.\n\n> Reproducibility\n\nWe will be releasing the codebase, model checkpoints and hyperparameters with the final version of the paper.\n\n> Can the method described in this paper be extended to scenarios beyond code generation to construct trajectories?\n\nYes, our method can be extended to any tasks where the correct solution can be generated in a single step (one-step recoverability). An application is theorem proving, where the the agent needs to write proof of theorems and the solution can be verified using external tools [1,2].\n\n> Could you consider using the additional tests introduced by HumanEval+ and MBPP+ as a private test set?\n\nWe thank the reviewer for bringing this up. In the submitted version, we used the HumanEval and MBPP datasets with its own set of public and private test split. Below, we provide comparison where private tests include the additional tests provided in MBPP+ and HumanEval+. We report results with the same model 1B-sized model checkpoints used to report results in Table 1 and present the results on Pass@3 and BoN@3.\n\n### MBPP+\n| Algorithm              | Pass@3 | BoN@3 |\n| :---------------- | :------: | :------: |\n| Llama-3.2-1B-Instruct        |43.2| 49.9 \n| Multi-STaR  |44.3| 50.0\n| $\\mu$Code   |**48.7**| **55.1**\n\n### HumanEval+\n| Algorithm              | Pass@3 | BoN@3 |\n| :---------------- | :------: | :------: |\n| Llama-3.2-1B-Instruct        |25.7| 31.9\n| Multi-STaR  |26.7| 34.3\n| $\\mu$Code   |**32.4**| **40.0**\n\nWe observe that $\\mu$Code outperforms baselines Multi-STaR by 5.1% and 5.7% on BoN@3 on MBPP+ and HumanEval+ datasets. Note that the numbers for MBPP are higher than what is reported in Table 1 because MBPP+ comprises of 378 problems as compared to 500 problems in the MBPP dataset.\n\n> Bigger benchmark \n\nWe conduct an experiment on CodeContests dataset and show that $\\mu$Code outperforms Llama-3.1-8B-Instruct and MultiSTaR. The experiment is discussed in the response to Reviewer QsKU, where we show **1.6%** performance gain over Multi-STaR at BoN@3.\n\n> Most of the reported results in Table 1 for HumanEval do not yield integers when multiplied by 164.\n\nWe are using a temperature of 0.7 for sampling to report our metrics. Because of the smaller dataset size, we observed variance in the results and resorted to generating 15 rollouts for each prompt. We report the mean scores in Table 1 and the values in Table 1 will be a multiple of .6 / 15 = 0.04. In the revised version, we plan to add the standard error with the mean results for clarity.\n\nBest Regards,\n\nThe Authors\n\n### References\n[1] STP: Self-play LLM Theorem Provers with Iterative Conjecturing and Proving, Dong el al. 2025.\n\n[2] Learning Formal Mathematics From Intrinsic Motivation, Poesia et al., NeurIPS 2024.", "claims_and_evidence": "I believe that most of the claims are well supported by experiments and theory. One debatable point is whether multi-turn code generation can be considered a one-step recoverable MDP. In a reasonable trajectory, each step is usually a gradual improvement over the previous one, for example, correcting the error in the last step. If a step is significantly wrong, it is difficult for the next step to directly recover to the correct code. I would like to see a more in-depth discussion regarding this claim, rather than treating it merely as a basic assumption.", "methods_and_evaluation_criteria": "- For the methodology section, I did not identify any issue and believe it makes sense for the problem and aligns with the one-step recoverable MDP assumption. \n\n- For the experiments, HumanEval and MBPP are somewhat outdated at present. I recommend that the authors use Evalplus' HumanEval+ and MBPP+. Additionally, utilizing more practical code generation benchmarks such as BigCodeBench could further enhance the robustness of the paper.", "theoretical_claims": "I did not check the proof for the theoretical claims since I am not an expert on RL. The explanation of the theorems makes sense for me.", "experimental_designs_or_analyses": "The experimental results are puzzling. HumanEval consists of 164 problems, and when measuring the pass rate, each problem is either correct or incorrect, meaning the metric must be a multiple of 1/164 ≈ 0.6%. However, most of the reported results in Table 1 for HumanEval do not yield integers when multiplied by 164. Given that the paper does not provide the code, this raises concerns about the validity of the reported results.", "relation_to_broader_scientific_literature": "The method described in this paper may be extended to scenarios beyond code generation to construct trajectories.", "essential_references_not_discussed": "I did not identify essential references not discussed.", "other_strengths_and_weaknesses": "Strengths: \n\n- The proposed method is simple and reasonable, fitting well with the one-step MDP assumption.\n- The authors conducted solid theoretical analysis of the proposed method, deriving a performance bound.\n- The writing is good and easy to follow.\n\nWeaknesses:\n\nThe paper does not appear to provide source code or explicitly commit to releasing it (unless the reviewer has overlooked this information). The absence of publicly available code could impact the reproducibility of the results and weaken the work's value to the broader research community.", "other_comments_or_suggestions": "The paper contains many typos. I suggest the authors thoroughly proofread the paper again.\n\n- Algorithm 1, line 2: {(x, st, yt, ot))} -> {(x, st, yt, ot)}; line 4: trained on -> on\n\n- Line 200 (right): during training?, -> during training?", "questions_for_authors": "- In Appendix A.2, the authors manually divided the test cases for HumanEval and MBPP. Could you consider using the additional tests introduced by HumanEval+ and MBPP+ as a private test set?\n\n- Can the method described in this paper be extended to scenarios beyond code generation to construct trajectories?\n\n- During the inference phase, if the verifier is not used and instead only the public test is used to select the best solution, will the performance change?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FP2wpBKXPZ", "reviewer": "Reviewer_QsKU", "summary": "The paper introduces an approach, $\\mu\\mathrm{CODE}$, for multi-turn code generation using single-step rewards. Unlike existing methods that rely on reinforcement learning, $\\mu\\mathrm{CODE}$ considers code generation as a one-step recoverable Markov Decision Process (MDP), allowing for iterative improvement through imitation learning. The method iteratively trains a generator and a verifier, where the verifier provides feedback to guide the generator in refining code solutions. Experimental results on MBPP and HumanEval datasets demonstrate that $\\mu\\mathrm{CODE}$ outperforms existing methods such as STaR.\n\n## update after rebuttal\nI appreciate the rebuttal by authors. However, my concerns were not well addressed.\n1. While the paper claims that multi-turn RL methods suffer from sparse learning signals which makes learning inefficient, it fails to provide any comparative experimental evidence.\n2. The authors claim that when using sparse rewards, the agent could not updated for responses where it did not generate any correct solution. But in this scenario, the verifier cannot receive effective training, therefore the continuous signals could also be quite biased. Using answers with the highest reward labeled by the verifier but actually incorrect as SFT labels could be potentially harmful.\n3. I appreciate that the authors have provided more experimental results.\n\nIn summary, I would like to raise my score to weak reject.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful feedback and are glad that you found the paper well organized. We are grateful for your questions and comments, and respond to your questions below.\n\n> While the paper claims that RL methods are inefficient, it fails to provide comparative experimental evidence.\n\nMost approaches for finetuning LLM agents via RL rely on rule-based verifier like execution feedback in code or correctness in math problems. Such signals are sparse and credit assignment due to long-term rewards is challenging in multi-turn tasks. We propose $\\mu$Code that leverages a learned verifier to provide dense signals and also uses the one-step recoverability property for better credit assignment. \n\n*Sparse Rewards:*\nLet's consider a scenario where the agent is trained over the outcome of code execution. In such a setting, the reward can be either 0 or 1 denoting failure or success. When a correct solution is observed, an RL algorithm like PPO would increase the likelihood of this response. However, the agent is not updated for responses where it did not generate any correct solution for the prompt while sampling, and thereby the completions are discarded. This makes outcome based RL inefficient as the model updates relies on generating a correct solution, and exploration to a correct solution can be challenging. In many RL applications, this is mitigated with a dense reward signal, and $\\mu$Code leverages a learned verifier for training. The generator is updated to predict solutions with the highest reward and with training should climb uphill this reward function. To demonstrate the benefits, we compare Multi-STaR^2 which is similar to $\\mu$Code and performs relabeling with the sparse and ground truth reward (in Table 1 of the paper), and observed that $\\mu$Code trained with dense rewards performed better.\n\n*Long-term Rewards*:\nDuring RL training, the agent is trained to optimize the long-term rewards of the trajectories in multi-turn tasks. With the insight of one-step recoverability, we propose to relabel trajectories and improve credit assignment. To show this, we propose a baseline, Rejection Fine-Tuning, where we finetune the agent with the top rollouts ranked via the learned verifier (and call it RFT (LV)). We did a hyperparameter search over different number of top rollouts for this baseline and found picking top 6 solutions from 15 rollouts worked best. We observe that RFT (LV) does not perform well when compared with $\\mu$Code.\n\n### MBPP\n| Algorithm   | Pass@3 | BoN@3      |\n| :---| :------: | :------: |\n| Llama-3.2-1B-Instruct        | 37.3    | 42.7\n| RFT (LV)    | 30.6    | 37.1\n| $\\mu$Code   | **42.2**    | **47.2**\n\n### HumanEval\n| Algorithm   | Pass@3 | BoN@3      |\n| :-----------| :------: | :------: |\n| Llama-3.2-1B-Instruct        | 31.5    | 32.9\n| RFT (LV)    | 27.0    | 38.6\n| $\\mu$Code   | **40.0**   | **45.5**\n\n> Verifier annotations may contain inherent biases.\n\nWe agree that the agent can exploit the inaccuracies within the learned verifier. This happens because the distribution of reponses from the generator shifts with training and the learned verifier can return inaccurate reward values. To account for the covariate shift, $\\mu$Code updates the learned verifier after every iteration. Since the ground truth reward is already known (from the execution feedback), the verifier is updated using the oracle outcome. We would like to highlight that the learned verifier in $\\mu$Code is trained with the concatenated dataset from prior iterations. In our experiments, we also observed that updating the verifier across iterations is beneficial for learning. \n\nWe additionally present emperical results with the generator of $\\mu$Code and the learned verifier at the last iteration vs the learned verifier at iteration 0 (on rollouts from Instruct model). We observe upto 2% drops in performance on BoN@3 when using the verifier trained on Instruct rollouts vs the verifier updated with rollouts from current generator.\n\n| Verifier    | MBPP     | HumanEval|\n| :-----------| :------: | :------: |\n| LV (Iter 0)   | 46.8    | 42.5 \n| LV (Iter 2)   | **48.1**    | **44.5**\n\n\n> The conclusions, therefore, warrant further validation on more comprehensive datasets.\n\nWe conduct an experiment with the CodeContests dataset. We curated a 1K-sized dataset with randomly selected problems from the training set of CodeContests. We use Llama-3.1-8B-Instruct and compare with MultiSTaR and $\\mu$Code which were trained for 1 iteration on 4 X A100 GPUs with 80GB memory. We report the Pass@3 and BoN@3 results on the test set in CodeContests with 165 problems. We observe that $\\mu$Code outperforms Multi-STaR by 1.6% on BoN scores showing the applicability of $\\mu$Code to more challenging benchmarks.\n\n| Method  | Pass@3 | BoN@3 |\n| :---- | :----: | :----: |\n| Llama-3.1-8B-Instruct        |   4.4      | 7.4\n| Multi-STaR  |   6.8      | 10.3\n| $\\mu$Code   |   **8.2**      | **11.9**\n\nBest Regards,\n\nThe Authors", "claims_and_evidence": "No. \n\n1. While the paper claims that RL methods are inefficient, it fails to provide comparative experimental evidence.\n\n2. In the proposed iterative training process, the generator is trained on the verifier's annotated optimal results rather than the ground truth validated through actual code execution. This approach appears methodologically questionable, as verifier annotations may contain inherent biases. The rationale behind this design choice remains unclear.\n\n3. The study's conclusions are drawn from experiments conducted exclusively on MBPP, a relatively small dataset of only several hundred samples. This limited scope, essentially amounting to a toy dataset, raises concerns about the robustness and generalizability of the findings. The conclusions, therefore, warrant further validation on more comprehensive datasets.", "methods_and_evaluation_criteria": "No.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "Not related.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Other Strengths: This paper is mostly well-written and clearly organized.", "other_comments_or_suggestions": "No.", "questions_for_authors": "Please refer to the content in Claims And Evidence.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oCTDPcq8IZ", "reviewer": "Reviewer_6VTR", "summary": "This paper tackles the task of multi-turn (MT) code generation by introducing $\\mu$-Code, an *expert iteration* process to alternate between training a generator (which produces candidate code solutions $y$ conditioned on past history $s$) and training a verifier ($R(x, y)$ which scores these solutions). This is motivated by the observation that MT code generation is a one-step recoverable MDP, as a correct solution could be produced conditioned on any history. Experiments of 3-turn code generation on 2 benchmarks, MBPP and HumanEval, show that it performs better than the MT baseline (fine-tuning on the correct MT trajectories): 1. training using a learned verifier performs better than using an oracle verifier ($\\mu$-Code v.s. Multi-STaR$^2$ and Multi-STaR). 2. learned verifier could better guide the MT code generation process in the multi-turn BoN (conditioned on a history, do N rollout out, and select the highest score as the current prediction) process.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. We are glad the reviewer found the idea of one-step recoverability interesting. We respond to the questions below.\n\n> Results on POMDP setting.\n\nThis is an interesting ablation as for many prompts, some unit tests are present in the $x$. To evaluate the agents without this information in prompt, we removed the unit tests from the prompt $x$ in the test set of MBPP dataset and report the turn-wise BoN@3 score. We observe that the performance drops for all algorithms. We also observe that the performance gains for $\\mu$Code is significantly higher than baselines across turns, demonstrating the efficacy of our proposed approach at leveraging execution feedback.\n\n| Algorithm              | Turn 1 | Turn 2 | Turn 3 |\n| :---------------- | :------: | :------: | :------: |\n| Llama-3.2-1B-Instruct        |24.3|29.4|32.6\n| Multi-STaR  |25.2|30.3|32.3 \n| Multi-STaR^2|22.8|26.8|27.4 \n| $\\mu$Code   |**27.3**|**37.2**|**41.5** \n\n> Other benchmarks beyond MBPP and HumanEval\n\nWe evaluate the methods on the CodeContests dataset and is discussed in the response to Reviewer QsKU. We show that $\\mu$Code outperforms Multi-STaR by 1.6%.\n\n> The results in Table 2 where $\\mu$-Code-R is worse than $\\mu$Code.\n\nTo generate the dataset for training $\\mu$Code-R, we concatenate the datasets used to train $\\mu$-Code and MultiSTaR^2. We believe a better way of merging might lead to reduce this gap in performance and plan to add an additional analysis in the next version.\n\n> Whether $\\mu$Code works for Iteration number >= 3.\n\nIn Table 1, we observe a performance drop with $\\mu$Code on the MBPP dataset and observe improvements on HumanEval with training iterations. Given the simplicity of our approach, we believe more iterations would be needed for scaling to more challenging datasets and we leave this investigation for future research.\n\n> Theoretical claims\n\nWe thank the reviewer for pointing this out. Using the reward function defined in Section 2 (L100) to take values of either 0 or 1, we have updated the paper with the $-1 \\leq A*(s,a) \\leq 0 $ in Definition 3.1, L218 and L733.\n\n> Whether StaR/Multi-StaR setting is closer to the original StaR  or Rejection Sampling Finetuning.\n\nThe Multi-STaR baseline used in the paper is similar to the Rejection Sampling Finetuning defined in [2]. We plan to change the name of Multi-STaR to RFT for more clarity, and also change Multi-STaR^2 to RFT-R to denote RFT with relabeling.\n\n> Is the new policy for iteration N is always fine-tuned from the base model?\n\nIn this work, we followed a similar strategy as [1] for fine-tuning the base model at every iteration. \n\n> In Eq(3), how are the correct/incorrect pairs constructed?\n\nThe dataset for training the verifier was obtained through a sampling process. For each prompt, a pair of correct and incorrect response was obtained and we generated 16 pairs for each prompt.\n\n> In Eq(5), do you do the relabelling for all the problems?\n\nYes, $\\mu$Code relabels all the problems even if there are no correct solutions to that problem. This is similar to how RL training would happen with a dense reward function, where the agent is updated to increase the likelihood of the response with higher reward values and climb uphill on the reward function with updates. $\\mu$Code relabels the trajectories with solutions with higher reward values for fine-tuning. \n\n> What are the sizes of the datasets for each variants in Table 2 or other statistics of the dataset? \n\nAt each iteration, the size of the dataset for $\\mu$Code is the total number of rollouts as we relabel every trajectory. For the Multi-STaR^2, we relabel ~70% of the rollouts denoting the fraction of prompts with at least one positive trajectory. The dataset for $\\mu$Code-R is obtained by concatenating the two datasets. We ran hyperparameter tuning on the number of epochs to account for different sized datasets but finetuning with 2 epochs performed best.\n\n> Reproducibility:\n\nWe will be releasing the codebase and the model checkpoints with the paper. We provide details of important hyperparameters for training $\\mu$Code below: \n| Hyperparameter | Generator | Verifier |\n| :---------------- | :------: | :------: |\n| Training Epochs        |2|2|\n| Learning Rate          |5$e^{-7}$|1$e^{-6}$| \n| Batch Size             |32|64| \n| Max Sequence Length    |8192|2048|\n\n\n> Essential References Not Discussed\n\n[2] is a very interesting work that studies different CoT approaches and execution feedbacks. We have added [2] in references as the Multi-STaR baseline is similar to the Rejection Sampling Finetuning method described in [2]. \n\nBest Regards,\n\nThe Authors\n\n### References\n[1]  Qu et al.,Recursive Introspection: Teaching Language Model Agents How to Self-Improve, NeurIPS 2024\n\n[2] Zheng et al., What Makes Large Language Models Reason in (Multi-Turn) Code Generation?,  ICLR 2025", "claims_and_evidence": "The claim that a learned verifier’s single-step reward is sufficient for multi-turn code generation is well motivated by the proposed one-step recoverable MDP formulation. The authors use the learned verifier to pick top candidates to relabel the dataset. They provide empirical improvements over STaR-like baselines (which use correct completions as fine-tuning data) in training time and show that the learned verifier could be combined with public test information to further boost the BoN performance. The authors also provide single-turn baselines in Table 1 for solid comparison.\n\nHowever, the lack of experiment details/hyperparameters makes it difficult to assess whether the comparison is sound: I'm in particular concerned with the experiment results that:\n\n1. The performance drops in general from Iter 1 to Iter 2 on MBPP for $\\mu$-Code and on both MBPP and HumanEval for Multi-StaR$^2$. Therefore, it remains a question whether the proposed expert iteration process works for Iteration number >= 3.\n\n2. The results in Table 2 where $\\mu$-Code-R is worse than $\\mu$-Code is counter-intuitive and more explanation from the authors on the reason behind or on the experiment setting is highly appreciated.\n\nAlso, as the authors discuss in the limitations, apart from limited resources for larger experiments, it remains unclear whether the claims could extend to:\n1. other benchmarks beyond MBPP and HumanEval, essentially, where the public tests information is not fully presented in the prompt $x$, making the information from execution feedback essential (in a Partially-Observable MDP setting). \n2. a larger expert iteration number (>= 3).", "methods_and_evaluation_criteria": "The authors train on MBPP training set and evaluate on MBPP test set and HumanEval. This is a valid choice given the size of the model that the authors experiment on (1B & 8B). The authors report pass@3 and BoN@3 to report multi-turn (here 3-turn) performance. The authors include single-turn performance in Table 1, which I found solid for strengthening the comparison.", "theoretical_claims": "The authors propose the one-step recoverable MDP and prove the performance bound. I have checked the proof in Appendix B. The proof seems correct in general, but I have some questions/comments regarding the definition and the details in the proof.\n\n- The transition from L733 ($A^*(s, a) \\le 1$) to what is used in L740 (I understand that the authors want to use $||A^*(.,.)||_{\\infty} \\le 1$). This is not that correct because, in principle, $A^*(s, a)$ could be negative and below -1, and the absolute value could be bigger than 1.\n\n- In my opinion, the definition in L206: \"MDP is one-step recoverable if the advantage function of the optimal policy, defined as $A^*(s, a) = Q^*(s, a)−V^*(s)$, is uniformly bounded for all (s, a), i.e. $A^*(s, a) \\le 1$\" is very artificial and is not really the definition. Rather, this should an implication from what the authors argue (from L211 to L213) that \"MDP is one-step recoverable if the optimal policy depends only on the problem prompt $x$ but not the interaction history\" and I would further argue that:\n\n1. The definition is not correct in its current form.\n2. The implication should have a tighter bound. But more importantly, it has nothing to do with the \"one-step recoverability\"; it's generally true and trivial for any MDP.\n\nFor my point 1, we can construct a toy MDP environment, which is according to the current definition and is not one-step recoverable MDP. We allow 4 states $s_0 (initial), s_1, s_2 (terminal), s_3 (terminal)$. There are only 2 possible deterministic transitions:\n1. $s_0, a_0$ gives $s_2$, reward 1.\n2. $s_0, a_1$ gives $s_1$, reward 0, and $s_1, a_2$ gives $s_3$, reward 2. \n\nIf this is one-step recoverability, the optimal policy should only depend on the initial state (L211) but not the history. However, the optimal policy here should pick the trajectory of $s_0, s_1, s_3$, and, therefore, is history-dependent. And we have (assuming here discount factor $\\gamma$ is 1):\n\n1. $A^*(s_0, a_0) = 1 - 2 = -1 \\le 1$\n2. $A^*(s_0, a_1) = 2 - 2 = 0 \\le 1$\n3. $A^*(s_1, a_2) = 2 - 2 = 0 \\le 1$ \n\nwhich satisfies perfectly the current definition, which states that all $A^*$ should be smaller than or equal to 1.\n\nFor my point 2, $V^*(s) = max_a Q^*(s, a)$ by definition and it's direct that $A^*(s, a) = Q^*(s, a) - V^*(s) = Q^*(s, a) - max_a Q^*(s, a) <= 0 < 1$. Therefore, the claim that $A^*(s, a) \\le 1$ is trivial, true for any MDP, and it's not even a good bound. Unless the authors want to say that it's negatively bounded as well in the current setting.\n\nI think one way to fix all these is to *rewrite the definition*, **and** put $-1 \\le A^*(s, a) \\le 0$ (the -1 is environment specific, which is from the range of R = 0 or 1) in the definition instead of $A^*(s, a) \\le 0$. In all, the definition still looks interesting if all my points above are properly addressed.", "experimental_designs_or_analyses": "Questions about the experimental details remain for correctly assessing the experiment results:\n\n1. Understanding the baseline setting: The StaR https://arxiv.org/pdf/2203.14465 describes 2 steps to construct a dataset for finetuning: 1. Filtering Chain-of-Thought based on the final correct answer. 2. Conditioned on the correct answer, let the model generate Chain-of-Thought. While what the authors described as StaR in the paper (L258-260) is only doing a variant of the Step 1 above, i.e., rejection sampling and fine-tuning. This is closer to what is referred to as Rejection Sampling Finetuning, i.e., rollout from the models and fine-tuning on the correct ones (in https://arxiv.org/abs/2307.09288 and https://arxiv.org/abs/2308.01825 for single-turn setting in code/math reasoning domain). The description of Multi-StaR (L260), i.e., fine-tuning on correct multi-turn rollout, is very similar to the multi-turn Rejection Sampling Finetuning in https://arxiv.org/abs/2410.08105. It remains a question about whether the authors' StaR/Multi-StaR setting is closer to the original StaR involving Chain-of-Tought re-ordering and boostrapping or closer to the above Rejection Sampling Finetuning.\n\n2.  I'm in particular curious about the drop of performance from Iter 1 to Iter 2 in Table 1. Could the author provide any insight? In the training loop of the expert iteration L7 in Algo 1, new policy for iteration N is always fine-tuned from the base model (iteration 0), or it's iteratively fine-tuned from the policy of last iteration (iteration N - 1)?\n\n3. In Eq(3), how are the correct/incorrect pairs constructed? Are you doing a full catesian product of correct x incorrect solutions or there're some sampling processes? \n\n4. In Eq(5), do you do the relabelling for all the problems, even if there's no correct solutions to that problem?\n\n5. What are the sizes of the datasets for each variants in Table 2 or other statistics of the dataset, e.g., distribution of trajectories with different turn number, distribution of the correct/incorrect trajectories in the relabelled dataset for $\\mu$-Code? It remains unclear why $\\mu$-Code-R is better than $\\mu$-Code to me despite more correct trajectories are added.", "relation_to_broader_scientific_literature": "- https://arxiv.org/pdf/2405.17503 maintains a search tree and uses Thompson Sampling to choose the multi-turn history to condition on in the multi-turn code generation.\n- https://arxiv.org/abs/2410.08105 compares different chain-of-thought strategies in multi-turn code generation, and the described multi-turn Rejection Sampling Finetuning is also related to what the authors describe in L259 about the Multi-StaR.", "essential_references_not_discussed": "I encourage the authors to include https://arxiv.org/abs/2410.08105, in which the authors compare different chain-of-thought strategies in multi-turn code generation, and the described multi-turn Rejection Sampling Finetuning is also related to what the authors describe in L259 about the Multi-StaR.", "other_strengths_and_weaknesses": "Overall, I have mixed feelings about the manuscript, on one hand the strengths are clear:\n1. The one-step recoverable MDP formulation is interesting and intuitive.\n2. Performance gain through extensive baseline comparison. Especially the Multi-StaR$^2$, which I see as the most important ablation of the whole proposed pipeline by replacing the learned verifier with the oracle verifier but still keeping the relabelling process. However, it could benefit from more discussion about the source of the performance gap. I only find text from L310-312 for this comparision.\n\nOn the other hand, I'm not fully convinced by some of the results, along with the following weaknesses, for which I would need more clarification from the authors to recommend an acceptance:\n1. Questions remain regarding my comments on the theoretical part above.\n2. A lot of experiment details are missing and would be great if the authors could clarify my questions above on the experimental designs part.\n3. Reproducibility: It would be great at least to discuss the experiment setting, such as hyperparameters.", "other_comments_or_suggestions": "Please see above.", "questions_for_authors": "Please see the above comments. Overall, I remain positive about the manuscript. I would consider revising my recommendation if the following concerns and confusing are addressed:\n\nMajor:\n1. Theoretical and Experimental Design.\n2. Intuition and more explanation on why $\\mu$-Code-R is worse than $\\mu$-Code.\n\nMinor:\n1. The other questions on the Claim part, namely the discussion on whether the claims could be extend to iteration >= 3 or POMDP.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: In this paper, the authors propose a new approach to improve multi-turn code generation using single-step rewards. Specifically, they formulate the code generation as a one-step recoverable MDP, where the correct code solution can be generated from any intermediate state in a multi-turn trajectory. A generator is trained to generate code solutions using multi-turn execution feedback and a verify is used to score the generated code. 

There are some minor concerns raised by the reviewers: 
- The authors limited the experiments to Llama models with max turns up to 3 on HumanEval and MBPP. The authors added additional results in the rebuttal to extend the experimental setup (larger number of turns, results on other benchmarks) 
- Missing details of experimental configuration in the main paper. For reproducibility, the authors responded with additional information on the training setup and they will release the codebase and model checkpoints. 

Overall, the proposed method is well motivated with sound techniques, demonstrated by comprehensive experimental results. I suggest the authors review all the feedback and improve their paper accordingly.
Decision: Accept (spotlight poster)