# Guided Search Strategies in Non-Serializable Environments with Applications to Software Engineering Agents

arXiv: https://arxiv.org/abs/2505.13652 · HTML: https://mlsanity.com/paper/2505.13652/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 33 of its 41 references that are in the map.
- First posted on arXiv 19 May 2025.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)
- LLM agents and tool use / [Software engineering coding agents](https://mlsanity.com/agents/software-engineering-coding-agents/)

## Builds on (most cited first, 30 of 33)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering](https://mlsanity.com/paper/2405.15793/) (2024)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Large Language Models Can Self-Improve](https://mlsanity.com/paper/2210.11610/) (2022)
- [Executable Code Actions Elicit Better LLM Agents](https://mlsanity.com/paper/2402.01030/) (2024)
- [Agentless: Demystifying LLM-based Software Engineering Agents](https://mlsanity.com/paper/2407.01489/) (2024)
- [Training Software Engineering Agents and Verifiers with SWE-Gym](https://mlsanity.com/paper/2412.21139/) (2024)
- [Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning](https://mlsanity.com/paper/2410.08146/) (2024)
- [AutoCodeRover: Autonomous Program Improvement](https://mlsanity.com/paper/2404.05427/) (2024)
- [Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning](https://mlsanity.com/paper/2405.00451/) (2024)
- [Agent Q: Advanced Reasoning and Learning for Autonomous AI Agents](https://mlsanity.com/paper/2408.07199/) (2024)
- [Tree Search for Language Model Agents](https://mlsanity.com/paper/2407.01476/) (2024)
- [Controlled Decoding from Language Models](https://mlsanity.com/paper/2310.17022/) (2023)
- [SWE-Search: Enhancing Software Agents with Monte Carlo Tree Search and Iterative Refinement](https://mlsanity.com/paper/2410.20285/) (2024)
- [GLoRe: When, Where, and How to Improve LLM Reasoning via Global and Local Refinements](https://mlsanity.com/paper/2402.10963/) (2024)
- [SWE-Fixer: Training Open-Source LLMs for Effective and Efficient GitHub Issue Resolution](https://mlsanity.com/paper/2501.05040/) (2025)
- [OVM, Outcome-supervised Value Models for Planning in Mathematical Reasoning](https://mlsanity.com/paper/2311.09724/) (2023)
- [Learning and Planning in Complex Action Spaces](https://mlsanity.com/paper/2104.06303/) (2021)
- [Interpretable Contrastive Monte Carlo Tree Search Reasoning](https://mlsanity.com/paper/2410.01707/) (2024)
- [Lingma SWE-GPT: An Open Development-Process-Centric Language Model for Automated Software Improvement](https://mlsanity.com/paper/2411.00622/) (2024)
- [Multi-step Problem Solving Through a Verifier: An Empirical Analysis on Model-induced Process Supervision](https://mlsanity.com/paper/2402.02658/) (2024)

## Built on by (most cited first, 10 of 10)

- [Training Long-Context, Multi-Turn Software Engineering Agents with Reinforcement Learning](https://mlsanity.com/paper/2508.03501/) (2025)
- [When Agents go Astray: Course-Correcting SWE Agents with PRMs](https://mlsanity.com/paper/2509.02360/) (2025)
- [Understanding Automated Program Repair Agents Through the Lens of Traceability: An Empirical Study](https://mlsanity.com/paper/2506.08311/) (2025)
- [FALAT: Tracing Failures in LLM Agent Trajectories via Dependency-Guided Search](https://mlsanity.com/paper/2606.00765/) (2026)
- [EGSS: Entropy-guided Stepwise Scaling for Reliable Software Engineering](https://mlsanity.com/paper/2602.05242/) (2026)
- [RepoLaunch: Automating Build and Management of Code Repositories across Languages and Platforms](https://mlsanity.com/paper/2603.05026/) (2026)
- [ORACLE-SWE: Quantifying the Contribution of Oracle Information Signals on SWE Agents](https://mlsanity.com/paper/2604.07789/) (2026)
- [Mid-Harness: Scaling Actions Between Model and Harness for Terminal Agents](https://mlsanity.com/paper/2609.39982/) (2026)
- [One Tool Is Enough: Reinforcement Learning for Repository-Level LLM Agents](https://mlsanity.com/paper/2512.20957/) (2025)
- [SWE-Critix: Post-Training Generalist Verifiers for Assessing Coding-Agent Trajectories](https://mlsanity.com/paper/2610.13356/) (2026)

## Abstract (arXiv)

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.