Skip to content

SWE-Search: Enhancing Software Agents with Monte Carlo Tree Search and Iterative Refinement

🕒 Published (v1): 2025-01-01 · Source: ICLR · Venue: ICLR 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

SWE-Search wraps a software-engineering agent inside a Monte Carlo Tree Search loop, augmenting node evaluation with an LLM-based Value Agent that emits both a numeric score and a natural-language explanation used as hindsight feedback on re-expansion. Applied to SWE-bench Lite, it yields a 23% average relative improvement over the underlying linear agent across five models with no additional training.

Problem

LLM-based software agents execute tasks as linear, non-backtracking trajectories. When an initial approach fails on long-horizon repository-level tasks (debugging, refactoring), these agents cannot explore alternative branches or incorporate evaluation feedback mid-trajectory, causing them to cycle in unproductive states.

Method

SWE-Search models the agent's decision process as a search tree \(M = (S, C, A, V, P, p_0, \rho)\) where states are code-context snapshots and edges are typed actions (Search, Plan, Edit). Four components interact:

  1. Action Agent (Moatless-Adapted): operates a two-tier action hierarchy with a git-like commit-tree for cheap state backtracking; the Plan state is ungated so it can transition to any other state type.
  2. Value Agent: given the full trajectory prefix, outputs a tuple \((v_t, \varepsilon_t) = V(s_{t,\tau}, a_{t,\tau}, \{s_i\}_{i<t}, \{a_i\}_{i<t})\) — a scalar utility and a natural-language explanation. \(\varepsilon_t\) is injected as hindsight feedback when the parent node is re-expanded.
  3. Modified MCTS: node selection uses a UCT variant $\(UCT(s,a) = V(s,a) + C\sqrt{\frac{\ln N(s)}{N(s,a)}} + \alpha e^{-\beta(d-1)} - \gamma\sqrt{d}\)$ where the depth bonus \(\alpha e^{-\beta(d-1)}\) encourages early breadth and the penalty \(-\gamma\sqrt{d}\) prunes over-deep paths. Consecutive low-reward nodes are abandoned heuristically. Language models are deliberately excluded from the selection step.
  4. Discriminator Agent: takes up to five candidate solutions, runs a structured multi-agent debate, and selects the final patch; raises solution-selection accuracy from 73% (value function alone) to 84%.

Key Contributions

  • A multi-agent MCTS harness for repository-level software engineering requiring no model fine-tuning.
  • A hybrid value function producing both numerical scores and natural-language explanations repurposed as re-expansion feedback.
  • A modified UCT with depth-dependent exploration bonus and penalty tailored to software engineering search dynamics.
  • Empirical scaling analysis showing resolve rate increases monotonically with MCTS search depth (inference-time compute).
  • Discriminator via multi-agent debate as a post-search selection stage, improving top-1 selection by 11 percentage points over the value function.

Results

  • Overall: 23% mean relative improvement over Moatless-Adapted across five models on SWE-bench Lite (300 instances).
  • GPT-4o: 25.7% → 31.0% (+17% relative); Qwen-2.5-72B: 18.0% → 24.7% (+27%); DeepSeek-V2.5: 16.3% → 21.0% (+22%); Llama-3.1-70B: 13.6% → 17.7% (+23%); GPT-4o-mini: 13.0% → 17.0% (+24%).
  • Discriminator raises solution-selection accuracy from 73% to 84% on cases with multiple candidates.
  • Value agent qualitative feedback (hindsight) is a larger driver of gains than the quantitative score alone (ablation referenced in Fig. 4a but full numbers truncated in provided text).

Limitations

  • Maximum 3 expansions per node and 100 total iterations cap; performance ceiling under this budget is unclear.
  • MCTS overhead substantially increases inference-time compute and latency compared to single-trajectory agents.
  • Evaluation limited to SWE-bench Lite (300 instances); generalization to the full 2,294-instance benchmark not reported in the provided text.
  • Value agent achieves only 73% accuracy in solution evaluation, leaving substantial noise in the search signal.
  • Fail-to-pass tests are withheld, so the agent must discover test coverage independently; this introduces variance not present in setups that expose test oracles.

Relevance to Harnesses / Meta-Harnesses

SWE-Search is a concrete meta-harness: it wraps an existing base agent (Moatless-Adapted) with an outer control loop (MCTS) and two auxiliary agents (Value, Discriminator) without modifying the base agent's internals. The architecture directly instantiates the meta-harness pattern of separating execution, evaluation, and selection into distinct, composable roles. The hindsight-feedback mechanism — where the evaluator's natural-language output is fed back into the actor's context on re-expansion — is a template for self-improving harnesses that iterate over a fixed underlying model. The inference-time compute scaling result (deeper search = higher resolve rate) reinforces the case that harness-level orchestration is a viable substitute for model scaling.