PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Antonis Antoniades, Albert Örwall, Kexun Zhang, Yuxi Xie, Anirudh Goyal, William Wang

arXiv:2410.20285v6cs.AI

TL;DR

Current LLM software agents often follow linear processes that limit backtracking and adaptation on complex repository-level tasks. SWE-Search combines MCTS, hybrid quantitative and qualitative value feedback, and multi-agent debate; it achieves a 23% relative improvement across five models over standard open-source agents.

  • Problem

    Current LLM-based software agents often struggle with complex, long-horizon software tasks because linear processes limit backtracking and exploration of alternatives.

    Source: §1 · p. 1

  • Method

    SWE-Search combines flexible agent state transitions, MCTS, quantitative and qualitative Value Agent feedback, and Discriminator Agent debate for adaptive repository-level problem solving.

    Source: §1 · p. 2, §3.2 · p. 4, §3.3 · p. 5

  • Results

    23% relative performance improvement across five models over standard open-source agents was achieved on SWE-bench-lite.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Search-based software agents can improve performance with increased inference-time compute and support more adaptive reasoning in complex software engineering tasks.

    Source: §5 · p. 10

    The value function sometimes misses critical decision points and undervalues effective strategies, limiting consistent solution identification.

    Source: §4.2 · pp. 9–10

Abstract

from arXiv · show

Software engineers operating in complex and dynamic environments must continuously adapt to evolving requirements, learn iteratively from experience, and reconsider their approaches based on new insights. However, current large language model (LLM)-based software agents often follow linear, sequential processes that prevent backtracking and exploration of alternative solutions, limiting their ability to rethink their strategies when initial approaches prove ineffective. To address these challenges, we propose SWE-Search, a multi-agent framework that integrates Monte Carlo Tree Search (MCTS) with a self-improvement mechanism to enhance software agents' performance on repository-level software tasks. SWE-Search extends traditional MCTS by incorporating a hybrid value function that leverages LLMs for both numerical value estimation and qualitative evaluation. This enables self-feedback loops where agents iteratively refine their strategies based on both quantitative numerical evaluations and qualitative natural language assessments of pursued trajectories. The framework includes a SWE-Agent for adaptive exploration, a Value Agent for iterative feedback, and a Discriminator Agent that facilitates multi-agent debate for collaborative decision-making. Applied to the SWE-bench benchmark, our approach demonstrates a 23% relative improvement in performance across five models compared to standard open-source agents without MCTS. Our analysis reveals how performance scales with increased inference-time compute through deeper search, providing a pathway to improve software agents without requiring larger models or additional training data. This highlights the potential of self-evaluation driven search techniques in complex software engineering environments.

1 INTRODUCTION

SWE-Search addresses the non-linear, iterative demands of software engineering with flexible exploration, feedback-driven MCTS, and collaborative debate. On SWE-bench-lite, it achieves a 23% relative improvement across five models over standard open-source agents.

1 INTRODUCTION

  • SWE-Search combines flexible exploration, MCTS planning, Value Agent feedback, and Discriminator Agent debate to support adaptive software engineering decisions.The framework is designed to replicate adaptability, iterative learning, and collaborative decision-making.Source: §1 · p. 2
  • The SWE-Agent transitions among planning, searching, and editing, enabling backtracking and strategy adaptation as new information emerges.This flexible state space is intended to mirror engineers’ dynamic revision of their approach.Source: §1 · p. 2
  • MCTS balances exploration and exploitation, while the Value Agent supplies utility estimates and qualitative feedback for iterative decision refinement.The feedback loop uses past experiences to improve decisions during complex solution searches.Source: §1 · p. 2
  • The Discriminator Agent uses multi-agent debate and judge evaluation to compare candidate solutions and select more robust outcomes.This component mirrors collaborative engineering deliberation over competing approaches.Source: §1 · p. 2
  • 23% relative performance improvement across five models over standard open-source agents demonstrates SWE-Search’s benchmark advantage on SWE-bench-lite.The benchmark tests repository-level issue resolution by generating patches that fix failing tests.Source: §1 · p. 2

2 RELATED WORK

Prior work applies search and autonomous agents to non-linear reasoning and repository-level software tasks, but existing approaches vary in flexibility, design specificity, and computational cost. SWE-Search builds on these directions with MCTS for software engineering search.

Search methods

  • MCTS explores and statistically evaluates branches without requiring dedicated evaluation heuristics for every state, supporting non-linear reasoning in complex tasks.The paper contrasts MCTS with breadth-first, depth-first, and A* search strategies.Source: §2 · p. 2

Software Agents

  • Repository-level agents typically localize relevant files and code before implementing fixes for real-world GitHub issues, as evaluated by SWE-bench.Existing systems include SWE-agent, OpenDevin, CodeAct, Agentless, and tool-augmented approaches.Source: §2 · pp. 2–3
  • Prior software-agent methods range from simple localization-and-repair pipelines to hand-designed search interfaces, while repeated sampling can produce high result variance.These differences motivate more general search-based agent designs.Source: §2 · p. 3

3 METHODOLOGY

SWE-Search combines dynamic planning, value-based self-feedback, and deliberative selection in a multi-agent framework for repository-level software tasks. Its design formalizes adaptive exploration through MCTS, trajectory-aware evaluation, flexible action transitions, and debate over candidate solutions.

3 METHODOLOGY

  • SWE-Search combines a dynamic planning framework, a Value Agent, a modified MCTS search algorithm, and a Discriminator Agent for software engineering tasks.The components jointly support exploration, utility estimation, iterative feedback, and final solution selection.Source: §3 · p. 3

3.1 PROBLEM FORMULATION

  • The SWE agent models repository work as context-dependent state transitions and seeks to maximize cumulative reward over trajectories that depend on historical states and actions.The formulation includes state, context, action, value, transition, initial-state, and context-distribution components.Source: §3.1 · pp. 3–4

3.2 SWE-SEARCH FRAMEWORK AND ACTION AGENT

  • Flexible transitions from planning to any state, plus discretionary creation and execution of tests, let the Action Agent backtrack and adapt its trajectories as new information appears.Tests are incorporated into the value function and subsequent decisions, while fail-to-pass tests remain concealed.Source: §3.2 · pp. 4–5

3.3 VALUE (FUNCTION) AGENT

  • The Value Agent evaluates full state-action trajectories with a utility estimate and natural-language explanation, then feeds that feedback into re-expansion and subsequent Action Agent decisions.The explanations expose strengths and limitations of Search, Edit, and Plan states and support iterative refinement.Source: §3.3 · p. 5

3.4 SEARCH ALGORITHM

  • Modified UCT selection balances exploitation and exploration with early depth bonuses and late depth penalties, while consecutive low rewards trigger abandonment of poor strategies.The heuristic is chosen instead of language-model node selection for interpretability and efficiency, and it supports flexible backtracking.Source: §3.4 · pp. 5–6

3.5 DISCRIMINATOR AGENT

  • The Discriminator Agent compares up to five candidate solutions through structured multi-agent debate, improving final selection accuracy from 73% for the value function to 84%.The comparison is intended to surface implementation trade-offs that similar value estimates may miss.Source: §3.5 · pp. 6–7, Figure 2 · p. 7

4 EXPERIMENTS

SWE-Search is evaluated on SWE-bench Lite using controlled baselines, flexible search, iterative feedback, state-specific value prompts, and deeper inference-time search. It improves resolution across models while exposing both the benefits and remaining limitations of value-guided search.

4.1.1 SWE-SEARCH SURPASSES ALL CORRESPONDING BASE AGENTS AND ENABLES SMALLER, OPEN SOURCE MODELS TO APPROACH GPT-4O

  • 23% relative improvement across five models over the baseline agent establishes SWE-Search’s main SWE-bench Lite result.The comparison uses Table 1 and includes consistent gains across all five models.Source: §4.1.1 · p. 8, Table 1 · p. 8

4.1.2 SEARCH ENABLES AGENTS TO MAKE BETTER USE OF MORE FLEXIBILITY

  • Flexible state transitions improve autonomous trajectory correction, but the modest 1.4% gain also reflects a risk of infinite loops.Moatless-Adapted allows Plan to transition to any state, unlike strict transition rules, but lacks high-level loop mitigation.Source: §4 · p. 7, §4.1.2 · p. 8

4.1.3 IMPACT OF HINDSIGHT FEEDBACK ON AGENT PERFORMANCE

  • Hindsight feedback drives re-expansion when an initially completed trajectory misses test coverage, leading to new tests, edits, and successful resolution.Feedback also increases action diversity when re-expanding parent nodes.Source: §4.1.3 · p. 8

4.2 IMPORTANCE OF COMPREHENSIVE STATE INFORMATION FOR VALUE FUNCTION PERFORMANCE

  • State-specific prompts correct value-function undervaluation by helping it interpret action intent within Searching, Planning, and Editing states.Without these prompts, effective file-location actions received low rewards despite contributing to later success.Source: §4.2 · p. 9, Figure 4 · p. 9
  • Increasing search iterations consistently raises resolved issues, while the value function selects the correct solution 73% of the time and the discriminator reaches 84%.The experiments cap each node at three expansions and total search at 100 iterations; improved solution identification remains needed.Source: §4.2 · pp. 9–10

5 DISCUSSION AND CONCLUSION

SWE-Search combines MCTS with qualitative feedback and improves software-engineering agents over baseline models. Its search performance scales with increased inference-time compute, while future work targets broader applications and resource scaling.

  • SWE-Search integrates Monte Carlo Tree Search and qualitative feedback, improving performance over different baseline models.Source: §5 · p. 10
  • Search-based approaches can scale performance with increased inference-time compute, supporting problems that require greater computational resources.Source: §5 · p. 10
  • Future research should examine computational scaling and apply software-agent search to a broader range of complex use cases.Source: §5 · p. 10

B ADDITIONAL IMPLEMENTATION DETAILS

Moatless-Adapted extends a linear agent framework with tree-structured states, reversible code changes, and containerized test execution. These mechanisms support backtracking and repeated evaluation in repository-level tasks.

C MCTS HYPERPARAMETERS

The study’s MCTS implementation uses configurable hyperparameters, with default values defined by its settings class and implementation.

  • Table 2 lists the MCTS hyperparameters used in the implementation.Source: Table 2 · p. 18
  • MCTS performance can be fine-tuned for specific problem domains or computational constraints by adjusting its hyperparameters.Source: C MCTS HYPERPARAMETERS · p. 18

D ABILITY OF MCTS TO ESCAPE UNPRODUCTIVE LOOPS VS. BASELINE

The example contrasts a baseline agent trapped in repetitive, unproductive actions with SWE-Search terminating such trajectories through Value Agent recognition.

  • The base agent can become stuck performing repetitive actions that do not advance the solution and lead to dead-ends.Source: Figure 6 · p. 19
  • In the example, the base agent repeatedly implemented incorrect tests that continued returning errors.Source: Figure 6 · p. 19
  • SWE-Search’s Value Agent recognizes the unproductive trajectory and terminates it quickly, as illustrated by Node 73.Source: Figure 6 · p. 19

E MODEL INSTANCE RESOLUTION UNIQUENESS

Models resolve complementary subsets of issues across SWE-bench-lite repositories, with no single model dominating every issue and library.

  • Different models resolve distinct issue subsets across five SWE-bench-lite codebases, indicating complementary strengths.Source: E MODEL INSTANCE RESOLUTION UNIQUENESS · p. 20
  • Figure 7 maps repositories by columns and issues by rows, marking each model’s successful resolutions while leaving unresolved issues white.Source: Figure 7 · p. 20
  • No single model dominates across all issues and libraries.Source: Figure 7 · p. 20

F ABILITY OF VALUE FUNCTION TO DISCERN SUCCESSFUL TRAJECTORIES

This section examines how the value function assesses software-engineering trajectories and completion confidence. It covers the evidence, criteria, and structured state transitions used to evaluate progress, correctness, testing, and alternative approaches.

F ABILITY OF VALUE FUNCTION TO DISCERN SUCCESSFUL TRAJECTORIES

G VALUE FUNCTION PROMPTS

  • The search-action prompt evaluates problem alignment, search parameters, retrieved context, and identified code, producing an integer reward from -100 to 100.The evaluation also considers whether the combined search action and code effectively address the problem and whether improvements are possible.Source: G VALUE FUNCTION PROMPTS · pp. 22–23
  • The plan prompt assesses correctness, editing mistakes, test results, historical progress, and repetitive actions when judging whether a trajectory solves the issue.It uses the problem statement, file context, action history, executed action, full Git diff, and test results as evaluation inputs.Source: G VALUE FUNCTION PROMPTS · p. 24
  • The RequestMoreContext prompt rewards relevant, necessary, specific, efficient requests that demonstrate contextual understanding and advance problem solving.Its scale ranges from 100 for crucial missing information to -50 to -100 for fundamentally irrelevant requests.Source: G VALUE FUNCTION PROMPTS · pp. 26–27
  • The edit prompt requires verifying solution quality, accurate code modifications, test coverage, and possible alternative approaches, heavily penalizing missing tests.It also asks the evaluator to identify and explain incorrect actions.Source: G VALUE FUNCTION PROMPTS · p. 27
  • The evaluation prompt supplies the problem statement, file context, action history, completion reasoning, full Git diff, and test results to assess the agent’s assertion of completion.The evaluator is instructed to identify syntax errors, incorrect modifications, unintended changes, and remaining work.Source: G VALUE FUNCTION PROMPTS · p. 28
  • The reward scale ranges from -100 to 100 and reflects confidence that the solution is most optimal, with no unresolved issues or pending tasks, while requiring updated or added tests.Failure to update or add necessary tests should be heavily penalized.Source: G VALUE FUNCTION PROMPTS · pp. 28–29
  • The rubric distinguishes solutions that are fully correct and thoroughly tested, solutions with minor issues, and solutions that are partially implemented or incomplete, with scores of 100, 75–99, and 0–74, respectively.A score of 100 denotes a thoroughly tested solution requiring no further changes. Scores of 75–99 indicate minor issues or optimization opportunities, while 0–74 indicates partial or incomplete implementation with significant issues.Source: G VALUE FUNCTION PROMPTS · p. 28

H MOATLESS TOOLS STATE RIGIDITY

  • Moatless-tools v0.0.2 enforces a rigid search → identify → plan → edit transition sequence for agents.The transition system is intended to keep tool access predictable and prevent conflicts while maintaining system integrity.Source: H MOATLESS TOOLS STATE RIGIDITY · p. 29, §H.2 · p. 30

H.1 STATE TRANSITION SYSTEM

  • The transition system accepts optional parameters for edit-prompt token limits, global parameters, and state-specific parameters.These parameters configure the behavior of edit operations and individual states.Source: §H.1 · p. 29

H.2 STATE FLOW

  • The state graph allows SearchCode to advance to IdentifyCode or PlanToCode, IdentifyCode to revisit searching or proceed through relevance decisions, and DecideRelevance to trigger searches or planning.The listed transitions define the system’s directed state flow, including progression when search and identification work is complete.Source: §H.2 · pp. 29–30

I COST ANALYSIS

SWE-Search incurs higher computational costs than Moatless-Adapted because search-based exploration evaluates multiple solutions.

  • Search-based exploration of multiple solutions results in higher computational costs for SWE-Search than Moatless-Adapted.Source: I COST ANALYSIS · p. 30
  • Table 3 compares API costs in USD between Moatless-Adapted and SWE-Search across different models.Source: Table 3 · p. 30

J COMPUTE-MATCHING ANALYSIS

The compute-matching analysis documents how SWE-Search is compared with matched baselines, while the interactive demo exposes search states and the discriminator’s solution-selection process.

J COMPUTE-MATCHING ANALYSIS

K INTERACTIVE DEMO

  • The interactive demo represents each search node as a state/action pair and exposes LLM interactions, value outputs, context, file changes, and test results.Source: K INTERACTIVE DEMO · p. 30

L DISCRIMINATOR DEBATE PROMPTS

  • The debate conclusion synthesizes prior evaluations and reports a final explanation and chosen solution ID without referencing individual participants.Source: L DISCRIMINATOR DEBATE PROMPTS · p. 31
  • The discriminator debate evaluates multiple candidate Git patches for completeness, correctness, and efficiency, then selects and explains the most appropriate solution ID.Source: L DISCRIMINATOR DEBATE PROMPTS · p. 31

Related papers

Loading 2410.20285v6…