Guided Search Strategies in Non-Serializable Environments with Applications to Software Engineering Agents
Authors: Karina Zainullina
Alexander Golubev
Maria Trofimova
Sergei Polezhaev
Ibragim Badertdinov
Daria Litvintseva
Simon Karasik
Filipp Fisin
Sergei Skvortsov
Maksim Nekrashevich
Anton Shevtsov
Boris Yangel
Venue: ICML 2025 poster (2025)
Keywords: RL
Planning
Test-time search
Test-time computation
Agents
LLM
Software Engineering
SWE-bench
Process supervision
Outcome supervision
Primary area: deep_learning->large_language_models
TL;DR: We apply test-time search with learned critics to LLM agents even in environments where it's not possible to fork a state by following multiple actions from it.

Abstract: Large language models (LLMs) have recently achieved remarkable results in complex multi-step tasks, such as mathematical reasoning and agentic software engineering. However, they often struggle to maintain consistent performance across multiple solution attempts. One effective approach to narrow the gap between average-case and best-case performance is guided test-time search, which explores multiple solution paths to identify the most promising one. Unfortunately, effective search techniques (e.g. MCTS) are often unsuitable for *non-serializable* RL environments, such as Docker containers, where intermediate environment states cannot be easily saved and restored. We investigate two complementary search strategies applicable to such environments: 1-step lookahead and trajectory selection, both guided by a learned action-value function estimator. On the SWE-bench Verified benchmark, a key testbed for agentic software engineering, we find these methods to double the average success rate of a fine-tuned Qwen-72B model, achieving $40.8$\%, the new state-of-the-art for open-weights models. Additionally, we show that these techniques are transferable to more advanced closed models, yielding similar improvements with GPT-4o.

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engineering Agents
Karina Zainullina" ! Alexander Golubev" 1 Maria Trofimova Sergei Polezhaev Ibragim Badertdinov I
Daria Litvintseva' Simon Karasik
Filipp Fisin Sergei Skvortsov' Maksim Nekrashevich Anton Shevtsov
Boris Yangel*
Abstract
PasegNN
Large language models (LLMs) have recently achieved remarkable results in complex multi- step tasks, such as mathematical reasoning and agentic software engineering. However, they of- ten struggle to maintain consistent performance across multiple solution attempts. One effective approach narrow the gap between average-case and best-case performance guided test-time search, which explores multiple solution paths identify the most promising one. Unfortunately, effective search techniques (c.g. MCTS) are often unsuitable for non-serializable RL environments, such as Docker containers, where intermediate environment states cannot easily saved and re- stored. We investigate two complementary search strategies applicable such environments: 1-step lookahead and trajectory selection, both guided by learned action-value function estimator. On the SWE-bench Verified benchmark, a key testbed for agentic software engincering, we find these methods to double the average success rate of a fine-tuned Qwen-72B model, achieving 40.8%. the state-of-the-art for open-weights mod- cls. Additionally, we show that these techniques are transferable to more advanced closed models, yielding similar improvements with GPT-4o.
Succoss rale.
75
Figure I. The comparison of two evaluation protocols for a GPT- 4o-based agent: P and random sampling. The x-axis shows the numher of attempts, the y-axis shows the average success rate (i.e. the percentage of correct solutions).
formance often falls short of their demonstrated potential.
To illustrate this challenge, Figure depicts the performance of reasonably capable GPT-4o-based agent (Yang al., 2024) on SWE-bench Verified (Jimenez et al., 2024) under two evaluation protocols:
Pass N: the agent makes N attempts solve each problem instance, and problem is considered solved if at least one attempt succeeds. This protocol demon- strates the model's potential capability ceiling.
1. Introduction
The rise of large language models (LLMs) has driven sig- nificant advancements across multiple domains. However, when it comes tasks requiring heavy reasoning or agentic capabilities, a major challenge persists: while the models occasionally achieve exceptional results, their average per-
Random sampling: a problem is considered solved if randomly selected solution from N attempts is correct.
This example highlights that LLMs exhibit high variance in success rate across different attempts. It is common for sequential tasks where multiple correct decisions must be chained together: even a model makes 80% individual decisions correctly, the probability of sampling a complete successful trajectory can decrease exponentially with the
'qqual contribution Nebius. Correspondence to: Boris Yangel <byangel@ nebius.com>.
Proceedings of the nnnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engincering Agents
number of required steps (i.e. 0.8* for 7 steps), depending on the ability of the model self-correct.
2. Preliminaries, Definitions, and Notation
2.1. Problem Setup and Notation
In domains that involve complex reasoning, such mathe- matical problem solving, recent work has demonstrated im- provements in performance consistency through two main approaches. Outcome Reward Models (ORMs) (Cobbe al., 2021; Mudgal et al., 2024) predict the correctness of the final answer that is then used for solution reranking. Process Reward Models (PRMs) (Lightman al., 2024; Wang et al., 2024a; Uesato et al., 2022) evaluate the cor- rectness of intermediate steps. Step-level evaluations pro- vided by PRMs can be combined into a single score for reranking, but they also enable classical search methods such as Beam Search (Setlur et al., 2024), Best-First Search (BeFS) (Koh et al., 2024). Depth-First Search (DFS) (Yao et al., 2023a), and Monte-Carlo Tree Search (MCTS) (Koc- sis & Szepesvári, 2006; Gao et al., 2024; Xie et al., 2024; Hao et al., 2023; Putta et al., 2024). Search methods im- prove consistency by systematically exploring the space of solutions instead of relying on chance.
Following (Murphy, 2024) we formalize our setting as Partially Observable Markov Decision Process (POMDP) with discounted rewards, defined by the tuple (2, (2,A, W, O, R),), where
Z is the set of environment states,
A is the set of actions,
Ω is the set of observations,
W, O, R are stochastic transition, stochastic observa- tion, and reward functions,
7 E [0, 1) is the discount factor.
Unfortunately, many agentic systems operate in non- serializable environments (formally defined in Section 2.3), where intermediate states cannot be saved, replicated, or
At each time step i, the environment is in state 2, E 2, which is not directly observable by the agent. Instead, the agent receives observation o, ~ O(o ze) and maintains its internal state 8t. defined as the history of past observations and actions 8; = (ov, ag, 01, .1....,.0 or), fer to trajectory. Based on 8t, the agent follows policy to issue an action a₂ ~ T<a 5t) E A. The environ- ment then transitions to Ze-411 W(z Re, ax) and provides reward Ft = R(2,, 4r, 21+1).
reversed. Non-serializability prevents the use of search methods that require multiple roll-outs from the same state, significantly limiting the available forms of exploration. For example, Monte-Carlo Tree Search (MCTS) becomes impossible in these settings as it relies on the ability to re-explore previously visited states.
which we also re-
Our main contributions are follows:
We introduce the notion of non-serializable RL envi- ronments, with Docker containers being one important example, and highlight the limits to the applicability of powerful guided search techniques such as MCTS to these environments.
We consider an episodic setting where each episode ter- minates upon reaching one of the terminal states 2r Zeeminal C Z. We refer to trajectories that reach a terminal state as complete trajectories, denoted 8r. In setting, we focus on sparse reward environments, where non-zero rewards are only provided at terminal states, i.e. for < T - 1 and FT-1 E 13. This reward structure naturally arises in scenarios where ground truth is provided by verifier that evaluates the entire trajectory upon episode completion. For any step t, the return-to-go defined the discounted terminal reward RG --T-t-1m TT-I-
0
We identify and systematically study two guided search methods applicable to non-serializable environments, using SWE-agent (Yang et al., 2024) on SWE-bench Verified (Jimenez et al., 2024) as testbed. Our find- ings reveal that these techniques and their combination can significantly bridge the gap between peak and av- erage agent capabilities even under non-serializability constraints. Moreover, we observe favourable perfor- mance scaling with more test-time computation.
2.2. Guided Search
Given a problem encoded using the POMDP formulation de- scribed above, we formalize guided search methods through the notion of inference operators, rules that induce the distri- bution over trajectories given an initial state. In its most gen- eral form, an inference operator is a distribution [(sT so). The most straightforward inference operator is the hase in- ference operator [[T] sp) that uses some policy π to generate complete trajectories according the following
We apply the proposed techniques on top of state-of- the-art open- weights LLM and demonstrate the best- in-class success rate of 40.8% on the SWE-bench Veri- fied.
We demonstrate that the proposed method is equally applicable to powerful proprietary models.
2

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engincering Agents
procedure:
One example of such environment is SWE-agent (Yang al., 2024), a framework for solving GitHub issues through in- teractions with Docker container. While Docker supports container checkpointing through CRIU (Checkpoin//Restore In Userspace) (CRIU community, 2019), several technical limitations prevent reliable state serialization (Andrjjausaas et al., 2024; Dash, 2022). Specifically, CRIU cannot guaran- tee consistent preservation of shared memory segments and inter-process communication channels. During its opera- tion, SWE-agent might spawn complex background process hierarchies. When restored, these processes face issues with PID reassignment and broken parent-child relationships, disrupting the normal execution flow.
ag T(a st),
2+41 W(z1 24, az),
0++1 O(o 2(+1);
(1)
S141 - (oo, ao. ao..... Or, at, ot+1)
until a terminal state 21+1
21 Zveminal is reached.
We can build other forms of inference operators I with the aim to improve upon [[T](ST] 5o) in terms of expected reward, where the expectation is taken over the stochas- ticity of the operator itself and the starting distribution of problems P:
An alternative approach to replicate an environment state 2, is to replay the action sequence (ao...., Qc-1) in a freshly initialized Docker container. However, this approach is computationally expensive as it requires to re-run all ac- tions from the beginning of trajectory, potentially including time-consuming ones such as compilation or running tests. Moreover, the transition function W(z, a) exhibits stochas- behavior due to multiple sources of non-determinism: process scheduling, inter-process communications and ac- to entropy sources like current time external systems. Consequently, executing the same action sequence multiple times may result in different state trajectories, making it impossible to reliably reproduce a specific state 2, through action replay.
EggxP, (PT + max.
(2)
Improvement can be achieved by leveraging access to the base policy æ and its statistics such as the action-value function Q= (s, a). We call inference operators that leverage action-valus functions guided search operators and denote them as I[ (5] | so). One trivial example of a guided search inference operator is operator induced by some policy improvement operator PPI n Qm) (Sutton & Barto, 1998):
I[T, Q=](s s0) A [[P Qx1] s0).
Overall, the lack of serialization ability mirrors real- world software engineering scenarios, where changes accumulate sequentially and mistakes must be mitigated within the for- ward flow of the solution process.
However, as show later, more general forms of guided search are possible.
2.3. Non-Serializable Environment
3. Guided Search in Non-serializable Environments
Definition 2.1. A non-serializable environment in the con- text of reinforcement learning (RL) is an environment, which states E Z cannot be serialized and de-serialized at an arbitrary time step f, and acting in a state changes the state in-place, potentially irreversibly.
In this section, we describe several guided search techniques applicable to non-serializable environments. We assume that we are given a base policy Taa s) and its action-value function Q= (s, a). In Section 4 we explore different ways to approximate Q (s, a) with a learned model.
Non-serializability has the following implications:
No rollbacks: once action a, is taken in state 2₁ to obtain 4++1 = W(2, at), there is no procedure to revert the environment state back to zt-
3.1. 1-step Lookahead
As discussed above, one way to build a guided search in- ference operator is by inducing it via a policy improvement operator. A well-known policy improvement operator ap- plicable non-serializable environments is 1-step looka- head (Sutton & Barto, 1998):
No state copying:
we cannot create multiple instances of 2, to obtain observations resulting from taking dif- ferent actions in this state.
No branching: methods requiring multiple unrolls from the same state (e.g. MCTS) cannot be directly applied.
PI[ Qa)(a (8) = 1 a = arg max Q (x(() e'EA
(4)
Limited forms of exploration: agent must proceed strictly forward through the transition function W.
When the action space is large, as it is the case for LLM- based agents, we can utilize its sample- version (Hu-
3

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engincering Agents
Algorithm Sample-based 1-step lookahead
Algorithm 2 Trajectory selection
1:
Input: base policy π, number of action candidates K, critic model Qx. environment E
1: Input: base policy n,, number of runs N, critic model
Qn. environment F
2: Initialize s < E.niit)
2: Initialize listOfTrajectoress +
3: repeat
3: Initialize listOfQ t-
4: Initialize listOfActions < []
4: for i == to N do
5: Initialize listOrQValues 4- |
sr f- unrollPolicy(( F)
6: for k to K do
(# ST
7: a' sample from Ta 18)
listOFTTajjecttrissaappeedddd
8: listOrQQaluess.ppeedd Q~ (s,
8: (isorovvllussapeennQ000000001100
9: listOF/Actions.appeedd a²)
9: end for
10: end for
10: 8 <- IistOTTraaecccorissssfrrr max
11: a" <- listOfActionsfarr (arg (ax(listOOQVallues))
11: return
12: s + E.step(s,cr a²)
until s terminal
14: return
date from a batch of complete trajectories. Specifically, for an almost complete trajectory 8T-1 = (0o, 00. (r......,))))) 0r-1),
bert al., 2021):
the action-value of its terminating action or-1 simplifies the trajectory reward Qa (sT-1,,,7 ar-1) PT-1-
PI[T, QxI(a (s) =
Thus, we can build an inference operator implementing the trajectory selection process in the following way:
An(3.dy).
(5)
= a
arg max
where dg ~ T(a ()..
I[r, Q+1(s 80)
The pseudocode for the sample-based version of this search procedure is presented in Algorithm 1. Notice how this search strategy eliminates the need to observe outcomes of all sampled actions df Ta s). Instead, it estimates Qr a) for each candidate action and proceeds with the one that has the highest aetion-value, guiding the trajec- tory towards more promising paths reachable by the base policy Some additional benefits of this strategy are:
Q(ST-1, Q( ar-))
(6)
arg max ey (c
where
8T 2 (on, a0,,..,, OT -1
ST-1
5 I[T[(s 50)
It is straightforward to implement this strategy top of any existing base policy and combine it with other guided search methods.
This is generalization of ORMs for arbitrary environments with sparse reward. The pseudocode for this procedure is presented in Algorithm 2. It directly attempts to close the gap between the average-case and best-case performance discussed in Section 1. Essentially, approximates the @ selection process by replacing the oracle that has access to evaluation results with learned action-value esti- mator. This strategy offers several practical benefits:
If the base policy an I.L., this strategy has minimal impact on inference costs: only increases the num- ber of generated output tokens (by factor of K, the number of action candidates), while the primary factor that influences agentic inference costs is the number of input tokens, especially in scenarios involving long trajectories.
Action candidates can be generated in parallel, reduc- ing impact on inference latency. However, one would still have to wait for the generation of the longest ac- tion candidate, and then for the estimation of its action- value.
It is agnostic to the base policy, allowing easy integra- tion with guided search based on policy improvement. Specifically, as we show in Subsection 4.2, this method can be efficiently combined with 1-step lookahead.
Multiple trajectories can be generated in parallel, mean- ing that although trajectory selection requires addi- tional computation, has minimal impact on inference latency.
3.2. Trajectory Selection
Another way to build guided search operator is to leverage the action-value function to select the most promising candi-

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engincering Agents
Table J. The effects of guided search, Verified-50.
Default
Until Submitted
Inference operator
SR (%)
SEM
SR (%)
SEM
Qwen-based policy
16.2
#1.08
22.8
#1.05
Qwen-baser policy + 1-step lookahead
26.8
+100
32.4
+0.89
Qwen-based policy + trajectory selection (N = 5)
27.2
=0.1
32.27
10.06
Qwen-based policy + trajectory selection (N 10)
31.27
#0.12
37.6
+0.04
Qwen-based policy 1-step lookahead + trajectory selection (N 5)
36.5
#0.11
39.95
#0.06
Qwen-based policy + 1-step lookahead + trajectory selection (N 10)
41.7
#0.13
44.07
#0.05
GPT-4o policy
22.0
#1.54
22.0
11.54
GPT-4o policy + 1-step lookahead
27.2
- 1.20
29.2
#1.62
GPT-4o policy + trajectory selection (N 5)
34.0
34.0
GPT-4o policy + 1-step lookahead + trajectory selection (N 5)
40.0
40.0
Table Comparison with other systems based open-weights models, SWE-bench Verified.
Method
SR (%)
Qwen-based policy + 1-step lookahead (K 8) trajectory selection (N 15)
40.8
SWE-Gym (Qwen-based policy + trajectory selection (N = =32)) (Pan et al., 2024)
32.0
SWE-Fixer (Xie et al., 2025)
30.2
Lingma Agent + Lingma- Seegga--WE-GPPP SWE-GPTT72B (Ma et al., 2024)
25.0
4. Experiments and Results
Evaluation Methodology SWE-agent's problem-solving process terminates under two conditions: when the agent issues "submit" command indicating the problem is con- sidered solved, upon encountering unrecoverable error (e.g. the L.M runs out of context). In the latter case, the accumulated changes in the workspace are treated as the generated patch. However, we observe that context ex- haustion frequently correlates with unrecoverable mistakes mid-traje vid-trajectory, leading to incorrect solutions. To enhance reliability, implement an iterative execution strategy: the agent runs repeatedly until it terminates by issuing "submit" command or reaches a maximum of 10 additional attempts. We refer to this approach, which can be viewed as a simple form of search, as until submilied regime, and use it by default in all experiments, not stated otherwise. As shown Table and Appendix E, the approach signif- icantly boosts the performance of single run, enabling better view into the effects of the techniques studied in this paper.
4.1. Experimental Setup
We utilize the SWE-agent scaffolding (Yang et al., 2024) to evaluate guided search techniques described in Section 3
on the SWE-bench Verified dataset (Jimenez et al., 2024). Our primary measure of interest is the Success Rate (SR),
defined as the percentage of problems successfully solved by the agent.
The SWE-agent scaffolding is a non-serializable environ- ment, as we argue in Section 2.3. Moreover, we choose SWE-bench because remains a challenging benchmark of practical interest, pushing LLM's abilities effectively navigate and resolve complex software engineering scenar- ios their limits. Test-time search strategies can further assist in addressing these challenges by enabling more effi- cient exploration within the constraints of con-serializable environments.
5

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engincering Agents
To better understand whether the observed performance dif- ferences statistically significant, we each experiment 10 times with distinct random seeds. We then compute the mean success rate and report it along with the standard eтrоr of the mean (SEM). This is particularly important when evaluating less capable agent policies, which exhibit higher performance variance due to inconsistent error-recovery be- havior.
100
twen-based policy
Qwen based policy lookahead
rate per Instance, %
Success rate
40
To balance comprehensive evaluation against computational constraints, created Verified-50, a dataset of 50 randomly selected problems from SWE-bench Verified. This dataset allows us to compute an unbiased estimate of the success rate on the full SWE-bench Verified together with the esti- mation error at the cost of single run on the full evaluation set. For the most promising setups, we additionally per- form evaluation on the full evaluation set. The list of issues included in Verified-50 can be found in Appendix D.
10
20
25
Instance
Figure 2. Per-instance success rate of Qwen-based policy com- puted over 15 runs.
Training Details We the majority of experiments with the LLM-based policy trained in-house. To estimate the action-value function of policy, we train separate LLM- based models that we refer to as critics.
We start by adopting the SWE-bench issue collection methodology to compile an extended set of training issues (Badertdinov et al.. 2024). Our training issue set consists of 6,500 issue-pull pull request pairs from 2,500 Python reposito- ries, carefully filtered to avoid leakage of the SWE-bench test set, and supplemented with the SWE-bench develop- ment set.
Succass race.
25-
20
10
N
We then apply a bootstrapping process to collect agent tra- jectories that we use to train the models, while simultane- ously training a capable policy. The bootstrapping process consists of repeating the following steps:
Pesigei Oven-buuad lette Inclaneed
Qparniaaed palky
Burcor Covenibueed pollcy Letpp locahhec
Randors Giarddsedd pa by
Trisdary aedoct Owion bard policy Salep Iecluhood
The cdlorryyy adiiciinn Gren bcaoo galicy
Figure 3. The dependency between success rate and the number of candidates N in trajectory selection.
1. Generate complete trajectories for all training issues using the current policy.
This bootstrapping process produced a total of 80,000 pos- itive and negative trajectories. We use these trajectories to train critic models. Since our dataset contains trajecto- ries produced by multiple policies, we incorporate policy identifiers into the critic's system prompt to condition the predicted action-value the policy being evaluated. When running action-valus prediction for policies not represented in the training data (e.g. GPT-4o), we simply pass previ- ously unseen policy identifier ("gpt-4o"" to the critic. We use LLaMA3.1 1-BBB (Dubey et al., 2024) to initialize critic training. Additional details on policy and critic training are provided in Appendices B, F and G.
2. Evaluate these trajectories and incorporate them into the dataset with a terminal reward of (if the issue is solved) (otherwise), annotating each trajectory with the corresponding policy version.
3. Update the current policy by fine-tuning on a curated subset of successful trajectories collected so far.
4. If not done, go to step 1.
use Dw (Bai et al., 2023) both the initial collection policy and as the starting point for every fine- tuning iteration. The policy produced by fine-tuning on data produced by the final bootstrapping iteration, which we refer to as Owen-based policy, is then used in the guided search experiments described below.
We
4.2. Main Results
We evaluate both search strategies - 1-step lookahead and trajectory selection as well their superposition. The
6

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engincering Agents
evaluation uses critic model trained with the best param- eters identified in Subsection 4.3, i.e. TD(0.7), for both 1-step lookahead and trajectory selection. For 1-step looka- head, we utilize the optimal search parameters identified in Subsection 4.4: policy sampling temperature 7 = 0.9 and number of candidates are presented both N and N runs when using the Qwen-based policy. For GPT-4o, trajectory selection evaluation is limited to N 5 runs without reporting SEM to reduce experimentation costs.
34
33
Trajectory selection results
32
Success rate,
31
30-
As shown in Table 1, both guided search methods, when used independently. achieve significant improvements over the base policy. When combined, they deliver 2-fold improvement success rate for both GPT-4o and Qwen- based policies, Importantly, these patterns hold consistently across both evaluation regimes: the relative ranking and magnitude of improvements remain stable whether allow- ing multiple attempts (Until Submitted) or terminating on first completion (Default). This consistency suggests that until submitted regime primarily addresses execution-level failures (such as context exhaustion) that affect all methods equally, rather than changing the core algorithmic dynamics that distinguish our guided search approaches.
0.0
0.2
0.4
0.5
0.8
1.0
A
Figure 4. The dependency between 1-step lookahead SR
and A.
31
88
Success rate,
Performance improvement on top of GPT-4o is especially notable given major challenges of this setup: relatively modest critic's base model capabilities compared to the policy, and the absence of GPT-4o-specific trajectories in the critic's training data.
28-
Additionally, evaluate the effect of 1-step lookahead per-instance success rate, presented in Figure 2 for the Qwen-based policy. Our analysis reveals that 1-step looka- head generally increases the probability of solving prob- lem, therefore boosting reliability. It can also boost very low success probabilities, allowing to start solving some instances where the base policy was consistently failing. GPT-4o policy demonstrates similar trends with the corre- sponding figure found in Appendix C.
0.86
0.88
0.90
0.92
0.94
0.96
0.98
1.00
Figure 5. The dependency between success rate and y for MC.
Unsuccessful
Successful
For trajectory selection, we also investigate the relationship between the success rate and the number of candidates, N, when applied to the base policy and when combined with 1- step lookahead. the success rate continues to rise without reaching visible plateau in the investigated range. Interestingly, N grows, the gap between the base policy and 1-step lookahead nar- rows for both N and trajectory selection setups, sug- gesting that both search methods might eventually converge to the same solutions provided enough compute. In practice, one should carefully select the appropriate values for K and N to achieve the desired trade-off between computational costs, latency, and performance.
Trajectory length
18
F
can be seen in Figure 3, N increases,
12
0.86
0.88
0.50
0.92
0.34
0.96
0.98
1.00
V
Figure 6. The dependency between trajectory length and y for MC.
We also evaluate the Qwen-based policy with 1-step looka-

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engincering Agents
Qwen based policy + 1-step lookahead, successtull
0.9
based policy step lookahead, unsuccessfull Owen-bmed policy successfull
Owen-based policy, unsuccescfull
Average critic score
Success rate. %
20
26
0.5
24
T= 0.1
0.4
T= 0.5
22
0.9
0.3
1.5
0.2
0.4
0.8
16
(relative)
Figure 7. Critic learns distinguish successfull and unsucessfull trajectories produced by Qwen-based policy.
Figure 8. Success rate of TD(0.8) critic with varying K and T.
age value estimates evolve as trajectories progress in time, demonstrating critic's ability to differentiate between suc- cessful and unsuccessful trajectories. The critic not only assigns higher values to successful trajectories average but also increases the confidence of its estimates trajecto- ries progress and additional information becomes available. Naturally, 1-step lookahead causes some amount of value hacking, leading to an increase of average values for nega- tive trajectories. This suggests that building robust critic model would require multiple iterations of active re-training adversarial trajectories found by guided search. Finally, there exists small gap between the positive and negative trajectories at the very beginning, suggesting non-tre toivialial ability to estimate problem complexity from its description.
head and trajectory selection with 15, T 0.9, and K the full SWE-bench Verified set, where it achieves 40.8% success rate (Table 2), establishing new state-of- the-art among systems using open-weights models.
4.3. Critic Model Analysis
In this section, we provide details on important aspects of training critic models, using the performance of 1-step lookahead with 4 action candidates as the benchmark.
Given our sparse reward setting, we use TD(A) (Sutton & Barto, 1998) to compute training targets. TD(A) interpo- lates between pure Monte-Carlo (MC) target estimates and lemporal-difference learning, allowing reduce target vari- at the expense of introducing bias into the estimate. Figure 4 illustrates that À= 0.7 yields the highest success rate, outperforming both Monte-Carle estimates (A = 1) and one-step TD (A = 0). This result suggests that relying exclusively on Monte-Carle estimates might be suboptimal due to high variance, and a careful search for might yield benefits similar setups.
4.4. Co-scaling of K and T for 1-step Lookahead
To better understand the trade-offs between search quality and costs, we investigate how the success rate of 1-step lookahead changes when varying the number of action can- didates K and sampling temperature T, using a TD(0.8) critic.
We further analyze how the discount factor y influences the success rate, using critic trained to predict Monte-Carlo target estimates. As can be seen in Figure 5, as approaches 1, the success rate increases. Manual trajectory investigation shows that longer temporal horizon helps the agent avoid missing critical steps (e.g. testing or issue reproduction). Figure 6 corroborates this by demonstrating that higher y values lead longer trajectories, allocating additional steps to vital yet initially unrewarded actions.
As shown in Figure 8, performance initially improves with increasing K across all temperature settings, but saturates at K = 8. where our current critic models reach their dis- criminative ceiling. However, better critic models trained on adversarial trajectories produced by critic-guided search will likely benefit from more than 8 candidates.
The temperature parameter T' exhibits different effects at different ranges of K. For lower values of K, higher tem- peratures yield better results, indicating the importance of increased exploration when fewer candidates are available. Optimal performance emerges at moderate values of both K and T, achieving an effective balance between exploration and exploitation. At high K temperature does not seem to
We additionally investigate the critic-estimnn estimmest action- values for both successful and unsuccessful trajectories, which were produced by the Qwen-based policy with and without 1-step lookahead. Figure illustrates how the aver-
8

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engineering Agents
be very important provided it is not too low and allows for sufficient exploration.
match the performance of leading proprietary models, fur- ther democratizing AL We encourage future work to fur- ther scrutinize the ethical and distributive impacts of the performane-verrus-coomppe trade-off.
5. Conclusion and Future Work
In this work, we introduce the concept of non-serializable RL environments and examine how non-serializability hin- ders the use of powerful guided search methods. This issue is of practical importance, as Docker containers com- monly used to isolate execution of automated software gineering agents are one notable example of such envi- ronments. Software engineering agents often exhibit a large gap between average-cate and best-case performance, and guided search methods can help mitigate this problem.
References
Andrijauskas, F., Sfiligoi, I., Davila, D., Arora, A., Guiang, J., Bockelman, B., Thain, G., and Würthwein, F. CRIU- checkpoint restore in userspace for computational simula- tions and scientific applications. CoRR, 0tds/2402.052444 2024. doi: 10448550AARXXV ordoi.oog//00 48550/85500/
URL https:
2402 052244 05244.
Antoniades, A., Örwall, A.,, Zhang, K., Xie, Y., Goyal, A., and Wang. W. Y. Swe-search: Enhancing software agents with monte carlo tree search and iterative refinement, CoRR, abs/2410.20285, 2024. doi: 10.48550/ARXIV. 410.20285, URL https: / /ttp://oooooooooo .tte:/11..88/55/ 48550/a rXiv. 2xiv.2410.. 22244.2..22225.
We describe two guided search techniques, 1-step looka- head and trajectory selection, that operate effectively de- spite non-serializabiltty constraints. Our empirical study on an automated software engineering benchmark, SWE- bench Verified, reveals that these simple approaches can yield a two-fold performance improvement, achieving state- of-the-art results among systems relying on open-weet weighte models. We further investigate how these methods scale with increased test-time compute and recommend strategies for training critic models to guide them.
Badertdinov, I,, Trofimova, M., Anapolskiy, Y., Abramov, S., Zainullina, K., Golubev, A., Polezhaev, S., Litvintseva, D., Karasik, S., Fisin, F,, Skvortsov, S., Nekrashevich, M., Shevtsov, A., and Yangel, B. Scaling data collection for training software engineering agents. Nebius blog. 2024.
Some interesting future directions of this work are:
Bai, J., Bai, S., Chu, Y., Cui, Z., Dang, K., Deng, X., Fan, Y., Ge, W., Han, Y., Huang, F., Hui, B., Ji, L.,, Li, M., Lin, J., Lin, R., Liu, D., Liu, G., Lu, C.,, Lu, K., Ma, J., Men, R., Ren, X., Ren, X., Tan, C., Tan, S., Tu, J., Wang, P., Wang, S., Wang. W., Wu, S., Xu, B., Xu, J., Yang. A.. Yang, H., Yang, J.. Yang, S., Yao, Y., Yu, B., Yuan. H., Yuan, Z., Zhang, J., Zhang, X., Zhang, Y., Z,Zangg, Z., Zhou, C., Zhou, J., Zhou, X., and Zhu, T. Qwen technical report. arXiv preprint 2rXiv:2309.1660
Examining whether powerful search methods imple- mented via replay-based serialization can bring perfor- mance benefits despite their lack of correctness.
Improving the robustness of replay-hased based serialization, for instance, by disallowing background processes, re- stricting access to entropy sources to reduce stochastic- ity, or detecting when replay diverges from the intended state.
2023.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. Training verifiers to solve math word problems. CoRR, ab/22110.1116 2021. URL 68.
Developing alternative approaches to correctly serial- ize and deserialize development containers.
Impact Statement
CRIU community. 2019. URL Checkpoint/restart in userspace(criu))
This work aims to improve the reliability and efficiency of LLM-based agents through guided search strategies. Our method allows to trade additional computation at inference time for higher agent performance, effectively exchang- ing money for capability. While such techniques allow to achieve better results with existing models using more computation, in the future similar methods can also deepen existing inequalities by giving well-funded actors a further advantage. Next, critic models that we train to guide the agent enable seff-verification, thus fostering safer and more reliable agentic systems. Finally, our approach may let open-weight models, when combined with guided search,
Dash, A. Understanding migration mechanisms of contain- ers using criu. Volume: 09:5, 02 2022.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A.. Goyal, A., Hartshom, A., Yang, A., Mitra, A., Sravanku- mar, A., Korenev, A., Hinsvark, A., Rao, A., Zhang, A., Rodriguez, A., Gregerson, A., Spataru, A., Rozière, B., Biron, B., Tang, B., Chern, B., Caucheteux, C., Nayak, C., Bi, C., Marra, C., McConnell, C., Keller, C., Touret, C., Wu, C., Wong, C., Ferrer, C. C., Nikolaidis, C., Allonsius,

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engincering Agents
D., Song, D., Pintz, D., Livshits, D., Esiobu, D., Choud- hary, D., Mahajan, D., Garcia- D.,, Perino, D., Hup- kes, D., Lakomkin, E., AlBadawy, E., Lobanova, E., Di- nan, E... Smith, E. M., Radenovie, F., Zhang, F., Synnaeve, G. Lee, G., Anderson, G. L., Nail, G., Mialon, G., Pang, G. Cucurell, G., Nguyen, H., Korevaar, H., Xu, H., Tou- vron, H., Zarov, I., Ibarra, A., Kloumann, I. M., Misra, I. Evtimov, I. Copet, J., Lee, J., Geffert, J., Vranes, J., Park, J., Mahadeokar, J., Shah, J., van der Linde, J., Bil- lock, J. Hong J. Lee. J., Fu, J., Chi, J., Huang, J., Liu, J., Wang. J. Yu, J., Bitton, J., Spisak, J., Park, J., Rocca, J., Johnstun, J., Saxe, J., Jia, J., Alwala. K. V., Upasani, K., Plawiak, K., Li, K., Heafield, K., Stone, K., and et al. The Ilama 3 herd of models. CoRR, https///4.22773.... 2024. doi: 10.48550/ARXIVV 220.X2XX2220072218... URL https: //doi. . wrg. 10. 48444855///0 2177.3
23.EMN.P-MMIIN6. URL https:: /ttp///oii.oo ///d/...og//// 118653/v1/20000 emn emmlp-mainn 67.
Hubert, T., Schritwieser, J., Antonoglou, I., Barekatain, M. Schmitt, S., and Silver, D. Learning and planning in complex action spaces. CoRR, abs/2104.063333.. 2021. http://aa......r/aa///04.....
URL
Jimenez, C. E., Yang. J., Wettig, A., Yao, S., Pei, K., Press, O., and Narasimhan, K. R. Swe-bench: Can language models resolve real-world github issues? In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024, OpenRe- view.net, 2024. URL https: http//pppwweee.eeoe/ee/ee httpp:://peerrreeee /
net
Koesis, L. and Szepesvári, C. Bandit based monte-carlo planning. In Fürnkranz, J., Scheffer, T., and Spiliopoulou, M. (eds.), Machine Learning: ECML 2006, 17th Eu- ropean Conference on Machine Learning, Berlin, Ger- many, September 18-22, 2006, Proceedings, volume 4212 of Lecture Notes in Computer Science, pp. 282-293. Springer, 2006. doi: 10.1007//118718221 229. URL https: //tpi://do..../// 1011.//00000110//111111122222221
Ehrlich, R., Brown, B., Juravsky, J., Clark, R., Ré, C., and Mirhoseini, A. Codemonkeys: Scaling test-time compute for software engineering, 2025. URL pottps://axet v. v. abs 14723
Gao, Z., Niu, B., He, X., Xu, H., Liu, H., andlight- light Xuming Hu, A. L., and Wen, L. Interpretable contrastive monte carlo tree search reasoning. CoRR, abs/2410.01707, 2024. doi: 10.48550/ARXIV 2410001 707. URL https::////// / /ttp///iiio//////////// org/ wwt..//.//...//////.... ...41..011 01707.
Koh, J. Y., McAleer, S., Fried, D., and Salakhutdinov, R. Tree search for language model agents. CoRR, abs/2407 0os/2407.01476, 2024. doi: 10.48550/ARXIV.2400 01476. URL https: org/ wtw.o////.....////////// 48550/arx 1v.2407.01478
Hao, S. Gu, Y., Ma, H., Hong, J., Wang, Z., Wang. D. Z., and Hu, Z. Reasoning with language model is planning with world model. In Bouamor, H., Pino, J., and Bali, K. (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Process- ing, EMNLP 2023, Singapore, December 6-10, 2023, pp. 1153-8173. Association for Computational Linguis- tics, 2023. doi: URL. www.t:tpps.......... / wttp:..org//00/ 111.11....6611111 .mnlp--mall mat.-mmain.555 507.
Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, Y. Large language models are zero-shot reasoners. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Infor- mation Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022. URL ht httpttt::ppppppppppeeeee httpppappppsseeeeeee nips cc/p aper_fflees/ppeee//22///eeeeee cclacf06ef11209911666 Atstoa9acc1taa---ssaa----------a Con perence.himl
Havrilla, A., Raparthy, S. C., Nalmpantis, C., Dwwiwddi-Ve Yu, J., Zhuravinskyi, M., Hambro, E., and Raileanu, R. Glore: When, where, and how to improve LLM reasoning via global and local refinements. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL /ttt/foor/rrtt forum? d=IH6R
Abst
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. In The Twelfth Inter- national Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL https: http::httt/sseeeeeeeee https:///pppeeeiiieeee hwtp:/iwwwiieeeeeeeeeeeeeeeeeeee net/foruu ?i ?id=v8L0pN6B0:
https: /tte:///ppeeeeeeee 06NxdB.
Huang, J., Gu, S., Hou, L., Wu, Y., Wang, X., Yu, H., and Han, J. Large language models can self- celfoieprove. In Bouamor, H., Pino, J., and Bali, K. (eds.), Proceed- ings of the 2023 Conference on Empirical Methods in Natural Language Processing, EMNLP 2023, Singapore, December 6-10, 2023, pp. 1051-1068. Association for Computational Linguistics, 2023. doi: 10.1863//V1/20
Luo, L., Lin, Z., Liu, Y., Shu, L., Zhu, Y., Shang, J., and Meng, L. Critique ability of large language models. CoRR, abs/2310.04815, 2023. doi: 10.48550/ARXIV.2 310.04815. URL https: http://.oo..o.....1/1 /arxiv.2310. 04815.
10

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engineering Agents
Ma, Y., Cao, R., Cao, Y., Zhang, Y., Chen, J., Liu, Y., Liu, Y., Li, B., Huang, F., and Li, Y. Lingma SWE-GPT:
Mastering chess and shogi by self-play with a general re- inforcement learning algorithm. CoRR, abs/1712.018155, 2017. URL http:://axxiv.rroo 1712 018 15.
open devebopmentt-rroess--ennti language model for au- tomated software improvement. CoRR, abs/241 1.00622, 2024. doi: 10.4855//RRXIV.441..000 URL https: //doi , //44///.l//00..1185555/5////////
2411.14400 00622.
Sutton, R. S. and Barto, A. G. Reinforcement learning an introduction. Adaptive computation and machine learning. MIT Press, 1998. ISBN 978-0-262-19398-6 URL https:tt//// /www.wwwwk worldcat . wtt.:ooo//oooooooooooooooooccooo 293240.
Mudgal, S., Lee, J., Ganapathy, H., Li, Y., Wang, T., Huang, Y., Chen, Z., Cheng, H., Collins, M., Strohman, T., Chen, J., Beutel, A., and Beirami, A. Controlled decoding from language models. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL https:// http://orruummooooooooo000700000 7Qa0. www.dcdbVVbbbbbcoo.o
Uesato, J., Kushman, N., Kumar, R., Song, H. F., Siegel, N. Y., Wang, L., Creswell, A., Irving, G., and Higgins, I. Solving math word problems with process- and outcome- based feedback. CoRR, abs/2211. 2022. doi: 10 Tttp:/ARXXI.2211114420 URL https: /wwii.ooooooooo///oooo////////// g/10. 1..0.48550/arkte 2211. 14275.
Murphy, K. Reinforcement learning: An overview. CoRR, abs/2412.05265,, 2024. doi: 10448550/ARXIV224422.00
265. URL https::/p//o.....t. http:::://di...// htt///doi.oo org. 4855044555555 22122. 05265.
Wang. P., Li, L., Shao, Z., Xu, R., Dai, D., Li, Y., Chen, D., Wu, Y., and Sui, 7. Math-shepherd: Verify and reinforce Ilms step-by-step without human annotations. In Ku, L., Martins, A., and Srikumar, V. (eds.), Pro- ceedings of the 62nd Anmual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), ACL 2024, Bangkok, Thailand, August 11-16, 2024, pp. Association for Computatioonal Linguitttiiiiiaaaaaiiiiiiiiiitie Linguistics, 2024a doi: 10.B653W/202A..CL-LON...13 URL https: / 1tt..ooo//....153/////0/000
Pan, J., Wang, X., Neubig, G., Jaitly, N., Ji, H., Suhr, A., and Zhang. Y. Training software engineering agents and verifiers with swe-gym. CoRR, abs/2412.221139, 2024. doi: 10.48550/ARXIV.22111
URL https: 2411.21111
//doi h/doi.org///// 10. 4 40054455a/aaaa
Putta, P., Mills, E., Garg, N., Motwani, S., Finn, C., Garg, D.,
and Rafailov, R. Agent Q: advanced reasoning and learn- ing for autonomous AI agents. CORR, abs/2408.077 109199 2024. doi: 10.48550/ARXIV w0w.:/XI.......0119199 URL https: /10 4004448555533 2408. 07199.
- -log..51 550.
Wang. X., Wei, J., Schuurmans, D., Le. Q. V., Chi, H., Narang, S., Chowdhery, A., and Zhou, D. Self- consistency improves chain of thought reasoning in lan- guage models. In The Eleventh International Confer- ence Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL https:
Schluntz, E., Biggs, S., Drain, D., Christiansen, E., Kravec, S., Rosso, F., DasSarma, N., and Chandrasekara, V. Rais- ing the bar on swe-bench verified with claude 3.5 sonnet, 2024. URL https: www. www.aaaticcc..... com/ re search/ swe-wweeebbeee sonnet.
Setlur, A., Nagpal, C., Fisch, A., Geng, X., Eisenstein, J., Agarwal, R., Agarwal, A., Berant, J., and Kumar, A.
ht////ppereeeeeeeee /ttp::// NIMMIW.
ttte/foorun 1PL1
Rewarding progress: Scaling automated process verifiers for LLM reasoning. CoRR, abs/2410.08144 2024. doi: 10. 10.48550/ARXIV.222 221.0.224000081446 URL https::///// /do///di.... org/10. 48550 arxiv 2410.2440 08146
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 Machine Learning, ICML 2024, Vienna, Austria, July 21 21-27, 2024. OpenReview.net, 2024b. URL https: / //opereeview net wwwtteetrrueeeeee www.rrmmmmmdj/o/ooeeeee
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner. N., Sutskever, I., Lilli- crap, T. P., Leach, M., Kavukcuoglu, K., Graepel, T., and Hassabis, D. Mastering the game of go with deep neural networks and tree search. Nat., 529(7587):484- 489, 2016. doi: 10. 10.1038/NATURE1600 https: http://doooooogg///// www./1.....ooo 038 naturel 6961.
Wang. Li, B., Song. Y., Xu, F. F. Tang, X., Zhuge, M., Pan, J., Song, Y., Li, B., Singh, J., Tran, H. H., Li, F,, Ma, R., Zheng, M., Qian, B., Shao, Y., Muennighoff, N., Zhang, Y., Hui, B., Lin, J., Brennan, R., Peng. H., Ji, H., and Neubig, G. Openhands: An open platform for ai software developers as generalist agents, 2024c. URL https:
URL
/ / http/axxiiivvii org aal///b//2244 2400 16741.
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai,
M., Guez, A., Lanctot, M., Sifrre, L., Kumaran, D., Grae- pel, T., Lillicrap, T. P., Simonyan, K., and Hassabis, D.
Wang. Z., Li. Y., Wu, Y., Luo, L., Hou, L., Yu, H., and Shang, J. Multi-step problem solving through a verifier:

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engincering Agents
An empirical analysis model-induced process supervi- sion. In Al-Onaizan, Y., Bansal, M., and Chen, Y. (eds.), Findings of the Association for Computational Linguis- tics: EMNLP 2024, Miami, Florida. USA, November 12-16, 2024, pp- 7309-7319, Association for Computa- tional Linguistics, 2024d. URL ht:ps: /tt///aaaaa aaclantho logy. wwg. findings emn 1p. 429.
Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K. R., and Cao, Y. React: Synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023, OpenReview.net, 2023b. URL https:t/////t... https://pppeeeeeewe.e net fore//oormmmmmo WE_vluYUL-X
Wei, J., Wang. X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, H., Le. Q. V., and Zhou, D. Chain-of- thought prompting elicits reasoning in large language models. In Koyejo, S., Mohamed, S., Agarwal, A., Bel- grave, D., Cho, K., and Oh, A. (eds.), Advances in Neu- ral Information Processing Systems 35: Annual Confer- ence on Neural Information Processing Systems 2022,
Yu, F., Gao, A., and Wang, B. Ovm, outcome-supervise value models for planning in mathematical reasoning. In Duh, K., Gómez-Adorno, H., and Bethard, (eds.), Find- ings of the Association for Computational Linguistics: NAACL 2024, Mexico City, Mexico, June 16-21, 2024, pp. 858- 118-875. Association for Computational Linguistics, 2024. doi: 10. 10..1665N.1222...ENNNSSSS......
NeurIPS 2022, New Orleans, LA, USA, November 28
URL http://///ooooooooo....116////// Findings-naacl..
December 9, 2022, 2022. URL htwp::tthh/// /ttp::://pppppree pwpppsppppssse cc /ttp://pppeeeeilleeeee/ee//2222/ d560
Zhang, Y., Ruan, H., Fan, Z., and Roychoudhury, A. Au- tocoderover: Autonomous program improvement. In Christakis, M. and Pradel, M. (eds.), Proceedings of the 33rd ACM SIGSOFT International Symposium on Soft- ware Testing and Analysis, ISSTA 2024, Vienna, Austria, September 16-20, 2024, pp. 1592-1604. ACM, 2024. doi: 10. 0001144/660022233660000 o/doi.orr/10.1100
act act-Confen Cot--ooference.e html.
Xia, C., Deng, Y., Dunn, S., and Zhang. L. Agentless: De- mystifying Ilm-based software engineering agents. CoRR,
abs/2407.01 -899,, 2024. doi: 10.48550/ARXIV224444 2240 489. URL https: / /ttp///d..ooo/////// www.doi..ooggoooee
URL https: 3680384.
.2407.000 01489.
Xie, C., Li, B., Gao, C., Du, H., Lam, W., Zou, D., and Chen, Swe-fixer: Training open-source Ilms for effec- tive and efficient github issue resolution. arXiv preprint PrXiv:2501.05040 2025.
Xie, Y., Goyal, A., Zheng, W., Kan, M., Lillicrap. T. P., Kawaguchi, K., and Shieh, M. Monte carlo tree search boosts reasoning via iterative preference learning, CoRR, abs/2405.00kl .0451,011111 2024. doi: 0048550/ARXI..20050000 451. URL https::///// https:///oiiii /ttp:///doiiooo org.10.0g11.0000 htt.a/o.g/111.10000... 40t00///000555/xi arxiv ..2405.0044 00451.
Yang, J., Jimenez, C. E., Wettig, A., Lieret, K., Yao, S., Narasimhan, K. R., and Press, O. SWE-agent: Agent- computer interfaces enable automated software engi- neering. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024. URL ht https:/ aaaii.iiiiv.//...//aaaaaaaiaavva wwexvv.org//ii.. wwg//ogg//.... 2405 15793.
Yao, S., Yu, D.. Zhao, J., Shafran, I., Griffiths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. In Oh, A., Naumann, T., Globerson, A.. Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans,
LA, USA, December 10 16, 2023, 2023a. URL http:
//papprrs.nipe.ccc/ppppe___eee httpe/ppperrraeppppaaeeeeeeeeeee / 023 022//aat//7dds992288144aadaaaa 3.70--Abstractt-Coffeeeccc html.
4ed5
12

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engineering Agents
A. Related Work
Reasoning via Prompting Large Language Models have demonstrated strong capabilities in reasoning and planning. Chain of Thought (CoT) (Wei et al., 2022) has emerged as dominant method for enabling structured reasoning in LLMs by introducing intermediate computation steps. This approach has proven particularly effective for complex tasks, requiring no modifications to model parameters. The effectiveness was further enhanced by the discovery that these behaviors can be elicited in a zero-shot manner through simple prompting techniques (Kojima et al., 2022), demonstrating LLMs' inherent capability for multi-step reasoning. However, single-path generation, even with structured reasoning, may not always yield the best solution.
To improve LLM reasoning beyond single-path generation, the simplest approach is to explore multiple solutions without learned evaluation components. Self-consistency (Wang et al., 2023) demonstrated strong performance through sampling multiple complete solutions and implementing Majority Voting over their answers. While effective, this approach relies heavily on random sampling and cannot guide the exploration process.
Reasoning via Search
Learning to Guide Search Combining search with learned value estimation has proven crucial for efficient exploration, pioneered by AlphaGo / AlphaZero (Silver al., 2016; 2017). This approach has been adapted to LLM reasoning through various search strategies: Beam Search (Setlur al., 2024), Best-First Search (Koh et al., 2024), Depth-First Search (DFS) (Yao et al., 2023a), and Monte-Carlo Tree Search (Koesis & Szepesvári, 2006; Putta et al., 2024; Xie et al., 2024; Hao et al., 2023), each offering different trade-off's between exploration breadth and depth.
The development of effective value estimators has been a key challenge in this direction. Early attempts to use LLMs directly as verifiers proved unsuitable for math reasoning (Huang et al., 2023; Luo et al., 2023). Different approaches to value estimation have emerged: some works (Wang et al., 2024a) use Monte-Carlo Tree Search (Koesis & Szepesvári, 2006), while others (Wang et al., 2024d) employ Monte-Carlo estimation using only policy roll-outs. This data can then be used to train step-level outcome-level critic models. Outcome- sutcome--uuperiseed Reward Models (ORMs) (Cobbe et al., 2021; Yu et al., 2024; Mudgal et al., 2024) predict final answer correctness for solution reranking, while Process-supervise Reward Models (PRMs) (Lightman et al., 2024; Wang et al., 2024a; Uesato et al., 2022; Havrilla et al., 2024) evaluate the validity of an intermediate step to rank and select among competing intermediate steps.
Software Engineering Agents Recent approaches to building software engineering agents can be categorized by their reliance on human priors. The first category employs manually defined workflows (Xia et al., 2024; Zhang et al., 2024; Ma et al., 2024; Ehrlich et al., 2025), breaking down complex tasks into specific subtasks and introducing ad hoc verification stages. These approaches require significant engineering effort and lack the ability to adapt to novel situations. The second category builds upon ideas from highly flexible, domain-agnostie frameworks of ReAct (Yao et al., 2023b), which introduced thought-based planning for any multi-step interaction, and CodeAct (Wang et al., 2024b), which proposed using Python code as universal action interface. SWE-agent (Yang et al., 2024) and OpenHands (Wang et al., 2024c) frameworks adapt these general-purposs purpose ideas to the software development domain, defining an agent-computer interface (ACT) that enables LLM agents to exccute arbitrary operations via shell commands.
Although agents in the second category (Schluntz et al., 2024) offer more flexibility, they face challenges in long- long-term term planning. Recent work has shown that combining such frameworks with test-time search strategies can significantly improve performance. For example, SWE-Gym (Pan et al., 2024) studies the benefits of applying outcome supervision to such agents. Our approach, built upon the SWE-agent framework, complements this work by investigating outcome supervision at a significantly larger scale, while additionally studying step-level value estimation and how the two methods can be combined. SWE-Search (Antoniades et al., 2024) leverages MCTS to search the solution space, demonstrating performance scaling with increased test-time computation. This work demonstrates that bypassing stochasticity and non-serializability issues by manually managing a limited subset of the true state (e.g. only filesystem changes in the working copy) can yield meaningful performance benefits. However, we expect this approach to run into issues when applied to scenarios where stochasticity important, such dealing with race conditions interacting with stateful external systems.
B. Training Details
We train critic models and the base policy using the hyperparameters listed in Table 3.
Critic models are trained with 1.2 loss, using TD(A) estimates of discounted reward-to-go as targets. For critic models to
13

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engincering Agents
Table 3. Hyperparameters used in experiments
Hyperparameter
Critic
Base policy
Optimizer
AdamW
AdamW
Warmup steps
7
Training steps
459
215
Learning rate value
2 10-6
4 10-6
Learning rate schedule
cosine
cosine
Batch size
128
128
Number of epochs
4
Weight decay
0.1
0.1
Sequence length
32768
32768
predict (s, a). the unembedding layer of the initial model is replaced with a linear layer that maps token embeddings scalar outputs. We add special token to the end of every agent turn, and treat the scalar predicted for this token the action-value prediction for the turn. Loss is masked for all other tokens during training. All parameters of critic models except the embedding layer are updated during training.
The base policy is trained with conventional cross-cnts cross-entropy loss to maximize the probability of training trajectories, All parameters of the base policy are updated during training, except the embedding and unembedding layers.
C. GPT-4o-based Policy Results
100
GPT-4o policy 1-step lookahead
45
Success per instance, %
80
Success rate. 96
05
20
Possgg: policy
Rasseyii policy 1:ttpp lookahoodd
Instance
Randoni policy
Random policy Listup lookanead
Vajectary selectio: polcc
Vajectory
polcy
Figure 9. 1-step lookahead improves success rate per instance for GPT-4o hase policy, adding new solved issues.
Figure The dependency between the success rate and number of candidates N in trajectory selection for GPT-4o.
We analyze the impact of 1-step lookahead on the per-instance success rate for the GPT-4o policy, as shown in Figure 9. Our results indicate that per-instance success rates generally improve across most instances.
Furthermore, we examine the relationship between the success rate and the number of candidates N used for trajectory selection, both for the base policy and when applied on top of 1-step lookahead. The results are presented in Figure 10. As N increases, the success rate continues to improve, with no clear plateau observed within the explored range.
14

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engincering Agents
GPT-40 palicy, successtull
1.0
GPT 4a palicy, unsuccessfull
GPT-4n palicy + 1 step lookahead, successfull
Fraction of submitted Instances
policy step
Average critic score
0.6
0.6
0.5
0.2
0.2
0.0
0.2
2
8
Time (relative)
Number retries before submitted
Figure 11. Critic learns to distinguish successful and unsuccessful trajectories for GPT-4o.
Figure 12. The average number of retrics it takes to generate tra- jectory that ends with "submit" for given fraction of the test set using the Qwen-based policy.
Figure 11 illustrates how critic-estimated action values evolve time for both successful and unsuccessful trajectories generated by the GPT-4o policy, with and without 1-step lookahead. The results suggest that the critie effectively differenti- ates between successful and unsuccessful trajectories. However, in the case of the GPT-4o base policy, the critic's scores remain stagnant mid-trajectee -rajerrjycttry for successful trajectories, indicating difficulty in recognizing positive steps at intermediate stages. A potential explanation for this behavior is that the critic was not trained on any opFT-4o-generated trajectories, which may have limited its ability to generalize to this setting. Some degree of value hacking is also present with lookahead.
D. Verified-50 Problems
The Verified-50 dataset, which curate from the SWE-bench Verified by randomly selecting problems, contains the following problem instances:
sympy_ssmmy-22000, djnoo0__1j
django_d django__janno-11333
natploo:1b..matpllliib-----
abango_dfango-1133, djangood@janoo-6642,
django djnngo--jan aphinx-doc
pylint-dev pylinttdew.ppyiin--6600.
sympy-sympy-13615, 1300
django Sinoo__djjngg-144255,
o/test-dev-ppteett--80,,
django_djjange-15103,
2sf_requuett==23177,
4jango-django-6611.
django_djangc--16611
sympy_sympy-11139, 5y11
9phinas-60o..shhhis-4499,,,
diango-@hjange--08800,
Ophinx--doc.aphinn--2222
django
dinngoodjano-1116566 matplotlib
pydata.xarraa-6446.
django__djeng==15388,,
django.django-115554,
pydata
xydaaa__aarray-69922, django django_djange-15881,, django.djange-1336}
sympy-symp--18852
gylnnt-devpyllnt-4466
E. Running Until Submitted
In our experiments, we employ an iterative execution strategy, in which the agent repeatedly attempts to solve the problem until it issues a "submit" command or reaches a maximum of additional attempts. We refer this approach, which can
15

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engincering Agents
be viewed simple form of search, until submitted regime. As shown in Table 4, this strategy signifieantly improves the performance of the Qwen-based policy, both with and without 1 1-step lookahead. Additionally, it increases the number of unique successfully solved instances (Pass N), calculated based on the last attempt for each instance, thereby expanding the opportunities for trajectory selection.
Figure 12 shows that the majority of Qwen-based policy solutions are submitted on the first try. However, when 3 additional attempts are allowed, the fraction of submitted solutions increases to 80%. This demonstrates that the strategy significantly boosts performance without imposing a substantial computational cost, requiring an average of 1.65 extra attempts per problem.
As shown in Table 4, in contrast to the Qwen family, the GPT-4o-based policy is not significantly influenced by the until submitted regime, with the metrics for the default regime almost matching those when running until submitted.
Table The effects running until submitted, Verified-50.
Default
Until Submitted
Inference operator
SR (%)
SEM
Pass@5 (%)
Pass@15 (%)
SR (%)
SEM
Pass@5 (%)
Pass 15 (%)
Qwen-based policy
16.2
+ 1.08
33.6
44.0
22.8
1.05
41.8
54.0
Qwen-based policy +
26.8
1.08
46.4
60.0
32.4
0..8
51.2
62.0
1-step lookahead
GPT-4o policy
22.0
1.55
46.0
22.0
1.54
46.0
GPT-4o policy 1-step
27.2
1.20
48.0
29.2
1.62
48.0
lookahead
F. Critic Base Model Sensitivity Analysis
Table The effects of varying base model for critic on performance of Qwen-based policy + 1-step lookahead, Verified-50, default regime.
Base model for critic
SR (%)
SEM
LLaMA3.1-70B
26.8
11.08
Qwen2.5-72B
22.8
+.08
LLaMA3.1-80
21.0
11.16
Qwen2.5-7B
20.2
+.08
No critic
16.2
+108
Table 5 compares crities trained starting from different base models on the task of guiding Qwen-based policy with 1-step lookahead on Verified-50. We don't perform additional hyperparameter tuning for each base model, using hyperparameters selected for LLaMa3.1 1- across all experiments.
Model size appears to be an important factor: smaller models (8B/7B) underperform (21.0% and 20.2%) compared to 70B+ models, hinting at the fact that critic performs non-trivial computations that can benefit from better representations.
In this comparison, LLaMA3.1-70B outperforms its Qwen2.5 counterpart; however, this result may partially reflect unequal hyperparameter tuning. Specifically, we performed extensive hyperparameter optimization for LLaMA3.1 1- exploring learning rates, batch sizes, and training schedules. contrast, for Qwen2.5-72B, we applied the best configuration identified
16

---

Guided Search Strategies in Non-Serializable Environments with Applications to Software Engincering Agents
Success rate.
Critic dataset size, %
Figure 13. The effects of varying training datasct size for critic performance of Qwen-based policy 1-step lookahead, Verified-50, default regime.
for LLaMA3.1-700 We recommend targeted hyperparameter tuning for the specific model family used to maximize performance of the trained critic model.
G. Sensitivity Analysis for Critic Dataset Size
Figure 13 presents a sensitivity analysis of critic performance with respect to training dataset size, with critic evaluated on SWE-bench Verified-50 using 1-step lookahead in default regime. We systematically reduce the training set size from 100% to 25% to understand how varying data sizes affect critic quality. We don't perform additional hyperparameter tuning for each dataset size, using hyperparameters optimized for the full dataset across all experiments.
As expected, critic performance tends to decline with dataset size, with the highest success rate of 26.8% + 1.08 observed when using the full dataset. The performance drop smaller subsets at least partially comes from insufficient training signal. However one other reason likely contributing to performance drop is that on smaller subsets, bootstrapped action- value estimates used in TD(A) targets simply don't have enough time to stabilize. We expect that by explicitly tuning hyperparameters for smaller datasets one can achieve better critic performance.
17


Reviews:
[{"review_id": "dTJGt54ifj", "reviewer": "Reviewer_LbVW", "summary": "This paper introduces two algorithms for guiding LLM policies in non-serializable RL environments using a learned action-value estimator (LLaMA-3-70B) as a critic. The proposed methods are: ***1-step lookahead**, which acts as a process-level reward model by selecting actions at each step, and **Trajectory Selection**, which serves as an outcome-level reward model by evaluating entire trajectories. The authors demonstrate that their test-time guided search methods can improve performance on SWE-bench Verified tasks of LLM policies (Qwen-72B-finetuned, GPT-4o).", "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 thoughtful comments and valuable feedback.\n\nRegarding the comment about the trade-off between the lookahead and the trajectory selection methods (assuming that is what the reviewer means by “best-of-N sampling strategy”), we’d like to emphasize that trajectory selection still requires a trained critic. Admittedly, this critic is not required to have process supervision abilities, which in theory can make its training more sample efficient. Therefore, we agree with the reviewer (and other reviewers who have also emphasized this point) that the paper can benefit from an ablation of data mixture size. We will train critic models on 25%, 50% and 75% of the data mixture we used and will report the performance of both lookahead and trajectory selection methods in the appendix. The corresponding models are already in the process of being trained.\n\nRegarding the question about the reasons for choosing LLaMa3 70B as the base model for training critic, they are purely historical: this was the best 70B model available at the time when this project started, which gave a reasonable balance of model size and capability. We agree that this might be confusing and the paper can benefit from an ablation on model sizes and families. We will train critic models using the same data mixture on 2 model families (LLaMa 3 and Qwen 2.5) and 2 model sizes (approx 7B and 70B) and present results in the appendix. The corresponding models are already in the process of being trained.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing empirical evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation setup are appropriate for the problem of guided search in non-serializable environments.", "theoretical_claims": "No formal proofs are provided, but the presented formulas align well with the textual descriptions and intended algorithmic behavior. I found the derivations sound and consistent with expected outcomes.", "experimental_designs_or_analyses": "The experimental design is rigorous and clearly presented. I found no methodological issues with the evaluation. In particular, the ablations and comparisons (e.g., best-of-N) are valuable for contextualizing the utility of the proposed methods.", "relation_to_broader_scientific_literature": "The paper makes a contribution by applying action-value-based test-time guidance to non-serializable RL environments, a relatively underexplored area. This complements recent work on Software Engineering Agents and extends ideas from traditional RL into new LLM application domains.", "essential_references_not_discussed": "None that I identified. The paper appears to situate itself well within the relevant literature.", "other_strengths_and_weaknesses": "Strengths:\n- The writing is clear and accessible.\n- Algorithm design is intuitive and well-motivated.\n- Empirical results are presented with care and depth.\n\nWeaknesses:\n- The reliance on training a critic using 80k labelled trajectories raises practical concerns regarding data collection and compute costs. It would be helpful to better contextualize the cost-benefit trade-off between this approach and a simpler best-of-N sampling strategy, especially given that best-of-3 GPT-4o performs comparably to the more complex guided search method in some cases (e.g., Figure 10).", "other_comments_or_suggestions": "No further suggestions or minor issues to report.", "questions_for_authors": "1. What was the rationale behind choosing LLaMA-3-70B as the critic model?\nIt would be useful to understand whether this choice was based on empirical performance (e.g., ablation over model sizes), availability, or alignment properties. Clarification here would help assess whether a smaller or less resource-intensive model could have been similarly effective.", "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": "aHEZVYurPy", "reviewer": "Reviewer_uvAg", "summary": "This paper proposes training a critic for action-value estimates for guided search in non-serializable environments (SWEbench). The high variance of LLM agents performance on this benchmark is well known, and the proposed trained  critic can address this issue while enabling inference-time scaling through guiding the search process, in 1) 1-step lookahead, 2) best-of-n trajectory selection and 3) combination of both.", "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 thoughtful comments and valuable feedback.\n\nWe thank the reviewer for pointing out the missing reference to “SWE-Search: Enhancing Software Agents with Monte Carlo Tree Search and Iterative Refinement, ICLR 2025”. We will add the reference to the related work section and discuss its connection to the present work.\n\nWe explain that “Qwen-based policy“ is a finetuned policy based on Qwen-2.5-72B-Instruct in section 4.1, paragraph “training details“. Experimenting on an open model is a necessity for this project to reduce inference costs, however experimenting on a non-finetuned instruct model is not an option: SWE-bench is a hard benchmark and current generation instruct models don’t perform too well on it out-of the box, hindering our ability to evaluate the effect of interventions we make. We agree that this aspect of the present work can benefit from a more clear presentation and will try to improve it in the final version of the paper.\n\nAll training we do is full-parameter, but it was indeed not clarified in the paper. We will add this detail to the training setup description. We believe that comparing LoRA vs full finetuning for training critics lies outside of the scope of this paper, as our method is orthogonal to fine-tuning methodology.\n\nWe agree that this work can benefit from an ablation on model sizes. We will train critic models using the same data mixture on 2 model sizes (7B and 70B) and present results in the appendix. The corresponding models are already in the process of being trained.\n\nWe also agree that the paper can benefit from an ablation of data mixture size. We will train critic models on 25%, 50% and 75% of the data mixture we used and will report the performance of lookahead and trajectory selection methods in the appendix. The corresponding models are already in the process of being trained.\n\nRegarding using off-the-shelf prompted LLM as a critic for lookahead/trajectory selection, we did experiment with such approaches but couldn’t produce a critic with performance significantly exceeding random guessing. We decided not to include these results as a baseline because it wasn’t clear if this was a skill issue on our side.", "claims_and_evidence": "The experiment results on SWEbench show that the trained critic enables doubling of performance on SWEbench verified. Analysis experiments show that 1step lookahead reduces the performance variance, and analysis of the critic model shows that it exhibits several positive properties, including scaling to more number of action candidates, better distinguishes successful and unsuccessful trajectories, and is able to reflect long-horizon value.", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "n/a", "experimental_designs_or_analyses": "i did not identify any serious issues.", "relation_to_broader_scientific_literature": "the paper is related to SWE agents and inference-time scaling.", "essential_references_not_discussed": "A missing reference on SWE agents with guided search is SWE-Search: Enhancing Software Agents with Monte Carlo Tree Search and Iterative Refinement, ICLR 2025", "other_strengths_and_weaknesses": "The paper shows strong results in a challenging domain. While verifier-based inference time scaling is an existing idea, there are few which successfully apply it to SWEbench. The paper is clearly written and easy to follow. \n\nA weakness of the paper is lack of details on training and cost details:\n- It's confusing whether the policy is finetuned or not: In table 1, is Qwen-based policy + 1-step lookahead a finetuned policy + 1-step lookahead?\n- It's unclear whether training is full-parameter or not, with cost implications as the finetuned model is on the larger side with 72B", "other_comments_or_suggestions": "- If the authors can include results for smaller models, it would demonstrate the generalizability of the proposed approach.\n- Did you try using an off-the shelf prompted LLM to do 1-step lookahead or best-of-n trajectory selection? If feasible, it would be interesting to see how this compares with the training approach.", "questions_for_authors": "- What is the \"LLM-based policy trained in-house\"? Is the base policy e Qwen-72B-Instruct or something else?\n- How important is the 80k number for the critic training data? Did you try smaller or larger training sets?\n- Do you do full-paramemter finetuning?", "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": "3sD6HiVo0f", "reviewer": "Reviewer_RSYG", "summary": "The paper introduces and formalizes the notion of a non-serializable environment. Traditional guided search techniques cannot be applied to non-serializable environments. A particular instance of a non-serializable environment is mutable software engineering environments, where it can be difficult to revisit prior states or roll back changes. \n\nThe authors study two guided search methods that are applicable to non-serializable environments (SWE-Bench-Verified). The methods are one-step-lookahead and trajectory selection using a learned critic. To train a critic, the authors construct an auxillary dataset similar to SWE-Bench and use it to generate trajectories for training a critic. Combined with one-step lookahead, the critic improves policies in the SWE-Agent scaffolding by a substantial amount.", "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 thoughtful comments and valuable feedback.\n\nRegarding the question about the reasons for choosing LLaMa3 70B as the base model for training critic, they are purely historical: this was the best 70B model available at the time when this project started, which gave a reasonable balance of model size and capability. We agree that this might be confusing and the paper can benefit from an ablation on model sizes and families. We will train critic models using the same data mixture on 2 model families (LLaMa 3 and Qwen 2.5) and 2 model sizes (7B and 70B) and present results in the appendix. The corresponding models are already in the process of being trained.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Not applicable.", "experimental_designs_or_analyses": "I checked all experiments.", "relation_to_broader_scientific_literature": "This paper is most closely related to LLM-driven search [1], process supervision for reasoning [2] and training software engineering agents [3]. LLM-driven search methods typically rely on serializable environments, and this paper studies non-serializable environments. Thus far, process supervision for LLM reason has mostly been applied only to mathematics task (and possibly simple coding tasks). Training software engineering agents is relatively new, and I'm not aware of any works that are not concurrent work that apply process supervision for training software engineering agents. \n\n\n[1] Hao, Shibo, et al. \"Reasoning with language model is planning with world model.\" arXiv preprint arXiv:2305.14992 (2023).\n[2] Lightman, Hunter, et al. \"Let's verify step by step.\" The Twelfth International Conference on Learning Representations. 2023.\n[3] Pan, Jiayi, et al. \"Training Software Engineering Agents and Verifiers with SWE-Gym.\" arXiv preprint arXiv:2412.21139 (2024).", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "I think the only weakness of the paper worth mentioning is that the paper only shows results for a single open model (Qwen-72B-Instruct). \n\nThe strength of the paper is that it addresses an important problem (non-serializable environments) by applying simple, effective methods from the RL literature. The method works, and the authors collected their own dataset to train a critic.", "other_comments_or_suggestions": "None.", "questions_for_authors": "1. Why not also try this with a SLM (7B parameters)? You could take the offline dataset you generated with the 72B model or GPT-4o and train on it. \n2. Why do you use a different LLM family for the critic?", "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": "zXHRt2tJxC", "reviewer": "Reviewer_gMAZ", "summary": "This paper investigates guided search strategies for Large Language Models (LLMs) in non-serializable environments, focusing on SWE agents. The authors identify a significant gap between the average-case and best-case performance of LLMs in complex multi-step tasks. While effective search techniques like Monte Carlo Tree Search (MCTS) exist, they cannot be directly applied in non-serializable environments (like Docker containers) where intermediate states cannot be saved and restored.\n\nThe paper proposes two complementary search strategies applicable to such environments:\n1. 1-step lookahead: Guided by a learned action-value function to select the most promising next action\n2. Trajectory selection: Selecting the most promising complete trajectory from multiple attempts\n\nWhen applied to the SWE-bench Verified, these methods doubled the average success rate of a Qwen-72B-based model, achieving 40.8% success - a new state-of-the-art for open-weights models. The techniques also showed similar improvements when applied to GPT-4o.", "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 thoughtful comments and valuable feedback.\n\nWe agree that Pass@N is the correct term for trajectory selection with oracle and will change the text and plots accordingly.\n\nWe respectfully disagree that “run until submitted” is not a fair setting for evaluation: all evaluations done in the paper have been done using this setting unless stated otherwise. The results without running until submitted have been included in the Appendix E, which shows that lookahead search still has a dramatic effect on agent performance even when not using this regime. However we agree that the presentation of results without running until submitted was incomplete and will add trajectory selection results to this section. For your reference, turning off “running until submitted“ has the following effect on trajectory selection performance:\n\n* Qwen-based policy: 22.8% → 18.1%\n* Qwen-based policy + trajectory selection (N = 5): 32.3% → 27.2%\n* Qwen-based policy + trajectory selection (N = 10): 37.6% → 31.3%\n* Qwen-based policy + 1-step lookahead + trajectory selection (N = 5): 40.0% → 36.5%\n* Qwen-based policy + 1-step lookahead + trajectory selection (N = 10): 44.1% → 41.7%\n\nWe also agree that a subset of these results should be added to table 1 for clarity. We are not certain that these results should be added to table 2, which goal is to compare our best setup to concurrent work.", "claims_and_evidence": "The main claims are well-supported by:\n\n- Theoretical framework describing non-serializability constraints and how they limit search strategies\n- Comprehensive experiments showing performance improvements on SWE-bench Verified\n- Ablation studies examining different parameters (λ values for TD learning, discount factor γ, number of candidates K, temperature T)\n- Analysis of how their methods improve per-instance success rates\n- Comparison with state-of-the-art results for open-weights models\n\nThe paper provides substantial empirical evidence showing that their proposed search strategies significantly improve performance both individually and when combined.\n\nMy only concern about these evidence was related to an experiment setting- I will elaborate on this in a later section.", "methods_and_evaluation_criteria": "The methods are sensible for the problem at hand:\n\n- Well-defined non-serializable environment framework\n- Clear implementation of 1-step lookahead and trajectory selection algorithms\n- Appropriate training of critic models using TD(λ) learning with extensive ablation that help the reader understand the importance of each components\n- Use of SWE-bench Verified for evaluation, which aligns with the software engineering focus", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "This is my only major concern on the result:\n\n> However, we observe that context exhaustion frequently correlates with unrecoverable mistakes mid-trajectory, leading to incorrect solutions. To enhance reliability, we implement an iterative execution strategy: the agent runs repeatedly until it terminates by issuing a “submit” command or reaches a maximum of 10 additional attempts.\n\nI like this paper, but I think this is not a fair setting for comparison: I would consider this as best-of-K strategy (where K is the number of re-runs) with a rule-based verifier that selects trajectories with a \"submit\" action.\n\nI would recommend the authors to also present the main experimental results in Tables 1 and 2 *without* this setting for the reader to have a clear understanding of whether it impacts the conclusion of this paper.\n \nI'd be happy to raise the score if we can observe the same performance trend **without doing until submit**", "relation_to_broader_scientific_literature": "This paper builds upon prior work in guided search for LLMs / inference-time scaling while addressing the specific challenges of non-serializable environments (e.g., specifically in software engineering).", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "- For figure 1, I would consider that number \"pass@N\" as opposed to \"best@N\"", "questions_for_authors": "N/A", "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: The paper tackles the problem of guiding LLMs in non-serialisable environments (i.e. environments where states cannot be saved, reloaded or rewound), which makes search methods like MCTS inapplicable. The key motivation here is software engineering tasks, which are run in Docker containers, where states simply cannot be rolled back.  To address this type of domain, the authors propose two guided search strategies for LLM agents: one-step-lookahead and trajectory selection using a learned critic. To train a critic, an auxiliary dataset similar to SWE-Bench is used to generate trajectories for training. These methods significantly improve performance on SWE-bench, doubling the performance of several LLMs on the benchmark. 

Reviewers all agree that the paper is well-written, thoughtful and shows impressive results on a very hard benchmark task, and so would make a strong contribution to the community. The paper could benefit from more ablation studies, which were identified during the rebuttal phase and which the authors are in the process of running. These results could further strengthen what is already a solid paper, and the authors are encouraged to include them in a finalised version.
Decision: Accept (poster)