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

We'd like to thank you for reviewing our paper, and recognizing the novelty of our idea.

SWE-Agent, SWE-Bench, Baselines. While we appreciate the reviewer's suggestions for additional comparisons, we note that tools like MetaGPT, ChatDev, and GPT-Engineer operate in fundamentally different settings from the SWE-bench benchmark [1,2]. Our paper builds specifically on repository-level software agents that can navigate and modify existing codebases - a distinct category from agents designed for code generation from scratch. Explaining in detail how software engineering agents work is beyond the scope of both our paper and this rebuttal. We have added Appendix H to point the reviewer to more implementation details of the base agent. We would be happy to clarify any specific aspects of the SWE-bench setting that would help contextualize our work.

Problem Definition & MCTS Operation. The search tree operates over states representing repository and test execution context, with edges representing actions that progressively build toward a solution. The agent typically starts with Search actions to locate relevant files and functions, then uses Identify to examine specific code sections, before moving to Edit states for actual modifications. Each of these actions involves complex tool usage - for example, Search requires the LLM to output structured parameters like file patterns or queries for semantic vector search, while Edit involves generating code modifications and repository git diffs. The progressive nature of the task means errors in early stages (like searching the wrong files) can derail the entire solution process, making accurate value estimation particularly important. These tool calls are managed through a standardized interface that ensures the LLM outputs remain well-structured.

Value Function & State Prompts. The effectiveness of our value function relies heavily on state-specific information and criteria, and providing the right context, such as file context, previous actions, and test outputs (Figure 1). As shown in Figure 4a, without specialized prompts, the value function fails to recognize the significance of key actions - assigning a low reward (0) to a successful code lookup action. With state-specific prompts, the same action receives an appropriate high reward (75), reflecting its importance in the solution process. This specialization allows the value function to achieve 73% accuracy in identifying correct solutions, with the discriminator further improving this to 84% (Figure 5a). The specialized prompts enable the value function to properly contextualize each state type (Search, Edit, Plan) and provide appropriate feedback aligned with the specific goals of that state. We have added the value prompts for each state in Appendix G.

The discriminator process step complements traditional MCTS approaches. While our value function achieves 73% accuracy, direct comparison between candidate solutions improves that to 84% and offers unique advantages, and we think it’s one of the strengths of using LLMs as evaluators. This is particularly valuable when evaluating multiple promising solutions that may appear similar based on value estimates alone, or are not easily discernible in isolation.

We are always available to answer any further questions that you may have.

[1] J. Yang, C. E. Jimenez, A. Wettig, K. Lieret, S. Yao, K. Narasimhan, and O. Press, "SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering," arXiv:2405.15793, 2024.

[2] C. E. Jimenez, J. Yang, A. Wettig, S. Yao, K. Pei, O. Press, and K. Narasimhan, "SWE-bench: Can Language Models Resolve Real-World GitHub Issues?," arXiv:2310.06770v3, 2024.

Thank you for your thoughtful review.

Compute Matching Baseline. We agree with the reviewer that such a baseline makes sense. We compare Moatless-Adapted pass@5 performance to that of SWE-search, which equates to the same compute over the benchmark. We observe that SWE-Search maintains strong performance compared to simple pass@n approaches, with even most models’ pass@1 outperforming the equivalent pass@5 Moatless-Adapted. This suggests our approach makes efficient use of compute resources, achieving better results through structured exploration rather than pure brute-force. We avoid running the GPT-4o benchmark due to the exorbitant cost.

Moatless-tools transitions. We refrained from providing a detailed explanation of the base agent, as that would require a separate paper by itself, but have provided more details in Appendix B. The Moatless-tools version we’re comparing with (0.0.2) doesn’t have access to all the tools at any given time. Instead it has to follow a rigid transition structure (search -> identify -> plan -> edit), please see Appendix H for the exact lines of code that implement this.

Value Function. The value function is optimizing what we refer to in the paper as the “expected utility” of each state/action. For each state type (search, identify, edit) what constitutes a good state/action is unique, and we therefore formulate specialized prompts for each state type that provide the relevant criteria, as well as detailed grading criteria for the values themselves. Appendix G aims to give a digestible overview of the structure of the prompts, but following the reviewer’s request we are adding the full system prompts for each state in the same section. As highlighted in the paper, this is one of the key insights to making this method work (Fig. 4a).

The value function does indeed perform well in terms of separating states that lead to successful vs. unsuccessful trajectories (Appendix F, Fig. 8), as also indicated by the performance of the method including outperforming pure brute-force approaches. Having said that, we agree that beyond the empirical and analytical results we share, understanding the self-evaluation capabilities of swe-agents in more detail warrants further exploration that is befitting of an entire paper by itself.

Benchmarks / Generalizability. SWE-Bench-lite is the official benchmark recommended by the SWE-Bench team.

In terms of transferability, our algorithm is indeed easily transferable to other OS agents, as none of them currently utilize search. Furthermore, the fluid nature of Moatless-Adapted agent framework we base SWE-Search on in its current state can be easily extended to incorporate tools and functionalities from other agents. One of the main novelties of the agent is the ability to build a git commit tree of repositories, in order to flexibly transition between any of them, which was a notable engineering challenge. We have attached an anonymized version of the open-sourced repository.

More benchmarks are always desirable. Still, focussing on different agent implementations would take focus away from the algorithm we propose. We contend that the consistent increase on the moatless-tools baseline is sufficient evidence of the potential of SWE-Search, and we think the OS implementation and lessons learned will be a valuable contribution to the community.

We’d like to express our appreciation for such a thorough review of our paper.

Citation. The citation was not intended to imply that MCTS was introduced by Sliver et. al, but rather that it was the first to combine it with DL approaches. Nevertheless, as big Van Halen fans, we acknowledge the reviewer’s analogy and update our citation accordingly.

Writing. Additionally, we have done an extensive review of the paper, improving and simplifying the writing, rearranging the methods section to follow a consistent and more interpretable format, removing the term general value functions and addressing all points brought up by the reviewer.

How agent works/weaknesses. Explaining how the whole agent (or any agent) implementation works in detail is very hard without diving into the codebase itself. We explain more about the core agent implementation in Appendix B. In general, the implementation is indeed quite fluid, with the agent itself deciding what to do next given definitions to a set of actions in its context. Explaining how the base agent works would need a paper of its own entirely, and we instead focus on explaining the algorithm we propose. Is there a specific point in the pipeline you’d like us to clarify further?

Limitations. An example of a current limitation is demonstrated in Figure 4a. The value functions require carefully crafted state-specific prompts to perform effectively. Getting language models to serve as reliable value functions across diverse domains (e.g., coding, web navigation) currently requires manual adaptation of these prompts. Future work should focus on automating this process, potentially enabling more general and adaptable value estimation across different task domains.

Improvement. We believe a 23% average increase across 5 models is quite significant for this benchmark (other reviewers seem to agree), nevertheless this is a matter of opinion. Virtually all the top solutions on SWE-bench were submitted after we wrote the paper, and utilize Anthropic’s new model. The moatless-tools base agent using this new model achieved a 38%, which is nearly on-par with SOTA (submitted to official benchmark). Our current results also achieve the best performance for open-source models through Qwen-72b. The highlight of our algorithm is that it's designed to be model and agent-agnostic. We intentionally kept the value function, node tree expansion, and search separate to the base agent, exactly in order to enable the algorithm to transfer to other agents (please see provided code). This took considerably more effort than hardcoding the algorithm within the base moatless tools agent.

Inference-time Scaling (479-481). Those lines point to the direction we hope the community will expand works like ours in the future. Search approaches for code essentially enable the “scaling” of swe-agents according to how extensively you want to explore the space of available solutions. Additionally, tree search gives added flexibility to an Agent, allowing it to “fail” and simply backtrack and learn from experience, essentially making the agent more open-ended. While this requires additional compute and may be overkill in some scenarios, there are domains like cybersecurity or scientific analysis where exploration far outweighs efficiency concerns - similar to how MCTS is used in Chess and Go. Beyond the scaling results in Figure 4b, we leave deeper exploration of this direction to future work, as it requires specialized benchmarks and evaluation frameworks that don't yet exist. The codebase we have open-sourced provides a foundation for exploring these directions.

Alibaba Agent. The Alibaba system uses MCTS to explore the codebase and provide potential locations that could be responsible for the issue. This information is then passed along to a code agent which generates a code patch. This second stage follows a linear structure, which is different from how our agent works, where it is allowed to flexibly expand and transition to any state/action at any point, including independent code edits, by utilizing a git commit tree.

API Costs. You raise an important point about API costs. As expected, the search-based exploration of multiple solutions results in higher computational costs. We also note that costs can be significantly reduced by using open-source models like Qwen-72b, which achieve competitive performance at a fraction of the cost of closed-source alternatives. Additionally, as we show in the compute-matching baseline, matching SWE-Search outperforms a naive baseline using the same amount of compute by executing multiple runs.

Thank you for your detailed review and acknowledging the novelty of our method and the potential significance it can have by advancing SWE-agent approaches. We'd like to offer the following information in response to your comments.

Writing. We updated the expected cumulative reward to properly index the states and actions with respect to time, and correctly formatted the conditional expectation.

The value function equation and notation has been revised for consistency throughout the paper. We now use $V(s_t, a_t)$ instead of $O_n(s_n, a_n)$ to represent the value function estimate of a state-action pair.

Actions, which are separated into action types, cause transitions to State types. These states hold all the environment variables including state of repository, potential test outputs, model context, and previous actions in the trajectory. We make this distinction more clear in the manuscript (3.2), and update equations accordingly to make this more explicit.

Changed Figure 3 -> Table 3. Figure 3 indeed demonstrates the “ideal performance” of the method. Since we conclude MCTS after 5 finished states, pass@5 is the performance of the agent if the correct solution was selected 100% of the time, when present.

Multiple runs. We appreciate the suggestion regarding multiple random seeds, but maintain our evaluation methodology is appropriate given: (1) the magnitude of improvements (mean +23%) far exceeds what could be attributed to MCTS randomness, with consistent positive deltas from +17% to +27% across five different architectures over 300 benchmark instances. The compute-matching baselines reinforce this notion. (2) software engineering benchmarks (HumanEval, MBPP, SWE-bench) traditionally focus on solve rates rather than statistical significance [1] given the binary nature of problem-solving success, and so do search approaches for other agentic tasks [2] (3) running multiple seeds would multiply computation costs without meaningfully changing the practical implications.

Q2: Since our state transitions $P : S × A × C → ∆(S)$ incorporate context information, and each state contains the relevant context from previous transitions, it would be redundant to include C explicitly in the value function. This follows standard formulations in POMDPs where the state representation is designed to be complete with respect to the information needed for decision-making.

Q3: Traditional discounting (something of the form $γ^d$) wouldn’t be able to readily encourage the types of behaviors we were looking for. For the ‘early_depth_bonus’, we wanted to give a very high bonus that quickly vanishes, while for the ‘late_depth_penalty’ we wanted to penalize depth more slowly. Thus we found the approach of separating these two easier to work with.

Q4: In the original agent, the transitions between state/action types are rigid. This provides some guardrails for the agent in order to continue along a reasonable path, concretely: search -> plan -> code -> finish. By allowing transitions between any state/action types, (for example transitioning from plan back to search) we are able to give more flexibility to the agent, but at the same time risk the agent making erroneous decisions like searching over and over again, making wrong transitions (instead of editing the right files, searching again and ending up with wrong files), or never concluding (reaching a finished state), for example by continuously introducing new edits or searches. Please see Appendix D to see an example of an agent getting stuck in these loops. We have also updated the paper to make this clearer (Section 3.2).

We are always available to answer any further questions you may have.

[1] J. Yang, C. E. Jimenez, A. Wettig, K. Lieret, S. Yao, K. Narasimhan, and O. Press, "SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering," arXiv:2405.15793, 2024.

[2] Y. Zhang, Z. Ma, Y. Ma, Z. Han, Y. Wu, and V. Tresp, "WebPilot: A Versatile and Autonomous Multi-Agent System for Web Task Execution with Strategic Exploration," arXiv:2405.15793v3, 2024.

We'd just like to conclude by thanking the reviewers and providing some final comments.

Baselines and Random Seeds

Regarding baselines, we note that there is a single baseline (Moatless) in our work. While additional baselines might be expected, the multiple LLMs in our study serve a role similar to random seeds, demonstrating that our results aren't a statistical fluke. The question of seeds remains challenging for us due to the significant computational expense involved, the minimal impact it would likely have on results, and notably, the fact that this type of analysis isn't present in other SWE-bench papers.

Benchmark Requirements

The suggestions regarding benchmarks would effectively require us to implement the algorithm with multiple agents and multiple seeds to enable apple-to-apples comparison with base agents or to outright achieve SOTA on the benchmark in order to outright claim the algorithm outperforms all submitted solutions to SWE-bench. This shifts the focus toward SOTA pursuit rather than algorithm development.

New Results, Demo, Code

We appreciate all the reviewers comments, but we wish they would have engaged in more insightful discussion with us. None of the reviewers acknowledged our code or interactive demo, which was meant to help them understand more about our implementation.

Having said all the above, we will use your feedback to improve our work. Thanks again for all your time and efforts to review our submission.