PaperlayerView exact revision on arXiv

Source-linked AI summary

BOAD: Discovering Hierarchical Software Engineering Agents via Bandit Optimization

Iris Xu, Guangtao Zeng, Zexue He, Charles Jin, Aldo Pareja, Dan Gutfreund, Chuang Gan, Zhang-Wei Hong

arXiv:2512.23631v2cs.LGcs.AI

TL;DR

Long-horizon, out-of-distribution software engineering tasks remain challenging for LLM agents, and automated discovery of effective agent hierarchies faces costly evaluation and credit-assignment challenges. BOAD uses bandit optimization to discover helpful sub-agents, and the authors report stronger benchmark performance than single-agent and manually designed systems.

  • Problem

    LLMs struggle with long-horizon, out-of-distribution SWE tasks, while discovering effective agent hierarchies is difficult because evaluations are costly and team outcomes obscure individual sub-agent contributions.

    Source: §1 · p. 1, §4 · p. 4, §4.2 · p. 6

  • Method

    BOAD treats each candidate sub-agent as a bandit arm, rewards helpfulness in collaboration, and uses trajectory-based LLM judging to assign credit.

    Source: §1 · p. 2, §4.2 · p. 6

  • Results

    Automatically discovered sub-agents with a customized orchestrator outperform single-agent and manually designed multi-agent systems on SWE-bench-Verified and SWE-bench-Live; BOAD resolves 20.0% of SWE-bench-Live issues.

    Source: §5.2 · p. 7, §6 · p. 10

  • Takeaways & Limitations

    The experiments support automatically discovered hierarchical multi-agent systems as an approach that improves performance on challenging, long-horizon SWE tasks.

    Source: §6 · p. 10

    Discovered sub-agents transfer across models only partially, and unconditionally accepting their outputs can propagate errors.

    Source: §6 · p. 10

Abstract

from arXiv · show

Large language models (LLMs) have shown strong reasoning and coding capabilities, yet they struggle to generalize to real-world software engineering (SWE) problems that are long-horizon and out of distribution. Existing systems often rely on a single agent to handle the entire workflow-interpreting issues, navigating large codebases, and implementing fixes-within one reasoning chain. Such monolithic designs force the model to retain irrelevant context, leading to spurious correlations and poor generalization. Motivated by how human engineers decompose complex problems, we propose structuring SWE agents as orchestrators coordinating specialized sub-agents for sub-tasks such as localization, editing, and validation. The challenge lies in discovering effective hierarchies automatically: as the number of sub-agents grows, the search space becomes combinatorial, and it is difficult to attribute credit to individual sub-agents within a team. We address these challenges by formulating hierarchy discovery as a multi-armed bandit (MAB) problem, where each arm represents a candidate sub-agent and the reward measures its helpfulness when collaborating with others. This framework, termed Bandit Optimization for Agent Design (BOAD), enables efficient exploration of sub-agent designs under limited evaluation budgets. On SWE-bench-Verified, BOAD outperforms single-agent and manually designed multi-agent systems. On SWE-bench-Live, featuring more recent and out-of-distribution issues, our 36B system ranks second on the leaderboard at the time of evaluation, surpassing larger models such as GPT-4 and Claude. These results demonstrate that automatically discovered hierarchical multi-agent systems significantly improve generalization on challenging long-horizon SWE tasks. Code is available at https://github.com/iamxjy/BOAD-SWE-Agent.

1 INTRODUCTION

BOAD organizes software engineering agents hierarchically and uses bandit optimization to discover helpful sub-agents. The paper reports improvements over single-agent and manually designed multi-agent systems on SWE-bench benchmarks.

1 INTRODUCTION

  • Real-world SWE issues remain difficult for LLMs, especially outside the training distribution, while single reasoning chains can retain irrelevant context that introduces spurious correlations.The authors hypothesize that this context can contribute to overfitting and poorer out-of-distribution performance.Source: §1 · p. 1
  • Hierarchical agents divide work into sub-tasks, while an orchestrator delegates to reusable sub-agents that capture task-invariant skills across different tasks and contexts.Examples of SWE sub-tasks include bug reproduction, fault localization, code modification, and validation.Source: §1 · pp. 1–2
  • Automating hierarchy discovery is difficult because the design space grows combinatorially and team-level success or failure gives a noisy, coarse signal about each sub-agent’s contribution.Human-designed decompositions can also fail to align with how LLM agents actually reason and behave.Source: §1 · p. 2
  • BOAD uses a bottom-up search: it evaluates individual sub-agents in teams, estimates helpfulness from their behavior, and treats each sub-agent as a bandit arm rewarded by helpfulness.An LLM judge assesses contribution during problem-solving trajectories, providing a signal beyond binary team success or failure.Source: §1 · p. 2
  • BOAD consistently outperforms single-agent and manually designed multi-agent systems on SWE-bench-Verified, and its 36B system ranks second on SWE-bench-Live.The Live issues are more recent and out of distribution; the ranking is reported as of the time of evaluation.Source: §1 · p. 3

2 RELATED WORKS

Prior SWE multi-agent systems often rely on manually specified roles and coordination, while automated approaches have optimized single agents or fixed workflows. This work instead targets automatically learned multi-agent coordination.

2 RELATED WORKS

  • Earlier SWE systems manually assigned sub-tasks to agents and designed their orchestrators, requiring substantial engineering and yielding only marginal gains.Other systems used multiple agents or models to generate patches and an aggregator to select a final solution.Source: §2 · p. 3
  • Single-agent optimization refines prompts or scaffolds for one agent, whereas this work studies specialized agents coordinating across sub-tasks.Source: §2 · p. 3
  • Workflow-optimization methods use predefined functions or agent graphs, but SWE tasks call for fine-grained coordination that can adapt to intermediate outcomes and new information.Source: §2 · p. 3
  • Prior automated multi-agent generation often assumes fixed ordering or parallel aggregation; BOAD targets coordination for costly, long-horizon SWE interactions.Source: §2 · p. 3

3 PRELIMINARIES

The preliminaries model software engineering agents as tool-using systems in sequential decision processes. They introduce temporal abstraction through sub-agent options and bandits for decisions under limited evaluation budgets.

3 PRELIMINARIES

  • An SWE agent interacts with a repository through tools, and the MDP formulation represents observations, actions, trajectories, and terminal patch rewards.The stated terminal reward is 1 if the submitted patch passes all tests and 0 otherwise.Source: §3 · pp. 3–4
  • In the SMDP formulation, the orchestrator selects a sub-agent option that executes a sequence of actions until termination, reducing decision frequency and simplifying planning.Source: §3 · p. 4
  • A multi-armed bandit models repeated arm selection with stochastic rewards under a fixed interaction budget, capturing decisions when only a limited number of trials are available.Source: §3 · p. 4

4 METHOD: BANDIT OPTIMIZATION FOR AGENT DESIGN (BOAD)

BOAD frames sub-agent discovery as a multi-armed bandit problem to make costly SWE-agent design search more tractable and assign value to individual collaborators. It combines archive expansion and exploration–exploitation with hindsight-based credit assignment.

4 METHOD: BANDIT OPTIMIZATION FOR AGENT DESIGN (BOAD)

  • BOAD treats each candidate sub-agent as a bandit arm, selecting subsets under an orchestrator to reduce wasted evaluations in costly SWE tasks.The approach addresses a vast, initially unknown design space and ambiguous credit for team outcomes.Source: §4 · p. 4

4.1 AGENT DESIGN AS A MULTI-ARMED BANDIT PROBLEM

  • Each round selects K archived sub-agents, instantiates an orchestrator, evaluates the team, and propagates feedback to participating agents.The initial archive is generated by an LLM, and a warm-up rewrites docstrings to specify inputs and outputs for orchestrator use.Source: §4.1 · pp. 4–5
  • UCB ranks sub-agents by observed performance plus an optimism bonus, favoring strong candidates while exploring under-sampled ones.The first term uses empirical mean performance; the second rewards under-sampled sub-agents.Source: §4.1 · p. 5
  • A Chinese Restaurant Process dynamically adds distinct sub-agents, with new-agent probability decreasing as the archive grows.The expected number of distinct sub-agents after T rounds grows as O(θ log T).Source: §4.1 · p. 5

4.2 HINDSIGHT CREDIT ASSIGNMENT

  • Hindsight credit assignment addresses free-riding by using an LLM judge to label whether each sub-agent’s actions helped, even when the team ultimately fails.Each agent’s score is the empirical average of its binary helpfulness labels across evaluated trajectories.Source: §4.2 · p. 6

5 EXPERIMENTS

BOAD improves SWE-bench results with Seed-OSS-36B-Instruct; ablations and trajectory analysis examine design choices, coordination trade-offs, and failure modes.

5.1 SETUP

  • Evaluation covers VERIFIED (500 instances) and LIVE (300); a disjoint 12-issue VERIFIED design set limits design-time compute, while LIVE tests newer, out-of-distribution issues.Each benchmark instance includes a GitHub issue, repository-specific container image, and executable test harness.Source: §5.1 · pp. 6–7

5.2 MAIN RESULTS

  • At equal patch evaluations, evolutionary search reaches 17.0% versus BOAD’s 20.0% on LIVE, while same-iteration Claude API cost is more than double.BOAD reuses sub-agents across iterations.Source: §5.2 · pp. 7–8
  • 20.0% on LIVE (ranked second at evaluation) and 53.12% on VERIFIED; gains over default SWE-agent are 63% and 13.4%, respectively.Both results use Seed-OSS-36B-Instruct.Source: §5.2 · p. 7, Table 1 · p. 8
  • BOAD consistently reduces input tokens while total tokens are comparable—and lower on LIVE—despite communication overhead.The analysis defines total tokens as average input plus output tokens per issue, and max input tokens as average maximum input length per instance.Source: Table 2 · p. 8, §5.2 · p. 8

5.3 ABLATION STUDIES AND ANALYSIS

  • On LIVE, two agents peak at 60/300 (20.0%); smaller and larger teams trail, while final-archive agents and helpfulness-based selection outperform their respective alternatives.The compared alternatives use the initial archive and individual success-rate ranking.Source: §5.3 · p. 9
  • Customized orchestration reaches 60/300 (20.0%) versus 50/300 (16.7%); prompt-only tuning falls short, and discovered agents transfer to Claude 3.7 Sonnet with smaller gains.The transfer gains are smaller than those achieved with Seed-OSS-36B-Instruct, the model used for sub-agent optimization.Source: §5.3 · pp. 8–10

5.4 QUALITATIVE ANALYSIS OF SINGLE- VS MULTI-AGENT OUTCOMES

  • Qualitatively, hierarchical systems produce shorter localized patches and better multi-site coverage, constraining edit scope and reducing omissions or unrelated edits.The single agent often over-edited unrelated regions or missed necessary locations in multi-site fixes.Source: §5.4 · p. 10
  • In a minority of cases, erroneous sub-agent outputs mislead the orchestrator; without intermediate validation, it has limited ability to recover from upstream errors.The authors identify lightweight verification, such as span cross-checks or invariant tests, as a promising mitigation.Source: §5.4 · p. 10

6 DISCUSSION & CONCLUSION

BOAD discovers hierarchical SWE-agent systems by treating their design as sequential online decision-making. Automatically discovered sub-agents with a customized orchestrator outperform single-agent and manually designed systems on both SWE-bench-Verified and SWE-bench-Live, while transfer across models is partial and handoff errors remain a concern.

6 DISCUSSION & CONCLUSION

  • Automatically discovered sub-agents with a customized orchestrator outperform single-agent and manually designed multi-agent systems on SWE-bench-Verified and SWE-bench-Live.BOAD formulates hierarchical multi-agent design as a sequential, online decision-making problem.Source: §6 · p. 10
  • Discovered sub-agents transfer across models only partially, limiting how broadly their designs carry over unchanged.Source: §6 · p. 10
  • Failure cases include error propagation when orchestrators unconditionally accept sub-agent outputs.Source: §6 · p. 10

ETHICS STATEMENT

The study addresses coding-agent risks by running experiments in isolated Docker containers and emphasizes responsible oversight against deliberate misuse and unintended consequences.

ETHICS STATEMENT

  • Experiments ran in Docker containers to isolate and sandbox agent commands, reducing the potential for harmful commands to affect real user devices.Source: ETHICS STATEMENT · p. 11
  • The implementation builds on the SWE-Agent framework, follows its curated protocols and licensing requirements, and relies on official releases or APIs for models and tools.Source: ETHICS STATEMENT · p. 11
  • Real-world deployment should include responsible auditing and oversight to mitigate deliberate misuse and unintended consequences.Source: ETHICS STATEMENT · p. 11

REPRODUCIBILITY STATEMENT

For reproducibility, the authors use official model releases or APIs, document BOAD implementation and prompt design, and plan to release code, data, and prompts.

REPRODUCIBILITY STATEMENT

A.1 PROMPT TEMPLATES

The appendix presents prompt templates for refining and generating subagents, constructing orchestrator plans, and evaluating subagent contributions. Together, these templates define workflows for coordinating tools and assessing subagent usefulness.

A.1.1 PROMPT TEMPLATE FOR REFINING SUB-AGENT DURING WARMUP STAGE

  • The warmup refinement prompt evaluates trajectories for discoverability, reliability, and usefulness, then targets the fields implicated by observed problems.It distinguishes discovery or context-passing issues from subagent behavior issues when choosing which fields to edit.Source: §A.1.1 · p. 16
  • Refinements should be surgical, general, and limited to clearly identified problems, with only changed fields returned in an updates dictionary.The prompt requires preserving existing style and capabilities and avoiding codebase-, project-, or domain-specific assumptions.Source: §A.1.1 · p. 16

A.1.2 META AGENT PROMPTS

  • The new-subagent prompt favors novel, broadly applicable, token-efficient tools for correctness-focused workflow subtasks, each taking one string context argument.It asks the designer to specify supported workflow steps and expected outputs, and to avoid overlap with existing subagents except for efficiency improvements.Source: §A.1.2 · p. 17
  • Generated subagent templates must define the role, task instructions, and outputs while preserving base-template structure and using YAML literal blocks.The prompt requires copying the supplied system template except for specified placeholders and producing compact, consistently formatted templates.Source: §A.1.2 · pp. 17–18
  • The generated subagent instructions enforce a narrow assigned role, require exactly one function call, and direct the agent to submit results when finished.The template also specifies the required function-call format and parameters.Source: §A.1.2 · p. 18

A.1.3 CUSTOM ORCHESTRATOR PLAN PROMPT

  • The orchestrator prompt asks for a systematic workflow that integrates subagents where valuable and minimizes steps and token use.It treats the supplied subagent names and descriptions as the authoritative source for tool purposes.Source: §A.1.3 · p. 19
  • Custom orchestrator plans should contain 3 to 7 purposeful numbered steps, use “Use the <name> subagent to ...” for subagent phases, and end by deleting created test or temporary files and submitting changes.Source: §A.1.3 · p. 19

A.1.4 PROMPT TEMPLATE FOR CHECKING IF A SUB-AGENT WAS HELPFUL IN A GIVEN INSTANCE

  • The helpfulness evaluator judges whether a subagent was called, supplied useful contributions, advanced the solution, and completed its task as intended.It considers positive evidence such as output reused by the main agent and negative evidence such as irrelevant results, execution errors, or inefficient repeated calls.Source: §A.1.4 · p. 20
  • The evaluator excludes contributions that do not help produce the correct patch, and requires a YAML helpfulness judgment with a brief evidence-based explanation.A valid-looking report is insufficient if the trajectory did not achieve the claimed result, such as actually testing the code.Source: §A.1.4 · p. 20

A.1.5 ORCHESTRATOR-ONLY PROMPT

  • The orchestrator-only prompt frames repository work as understanding a problem, implementing changes, and validating the solution efficiently.Its embedded task requests minimal changes to non-test files, says not to modify tests, and requires the agent to create and follow a plan.Source: §A.1.5 · pp. 20–21
  • The plan prompt encourages learning from sampled historical templates when available, while otherwise inviting novel workflows and requiring actionable numbered steps.Plans target Python repositories and PR-based problem solving, emphasize focused exploration, specify tool usage, and end with submission.Source: §A.1.5 · p. 21

A.2.1 BOAD TOP 2 DISCOVERED SUB-AGENT CONFIGURATIONS FOR SEED-OSS-36B-INSTRUCT

The configurations divide SWE work into bounded sub-agent roles, from structuring issue reports and mapping code to editing and validating fixes. The issue analyzer also supplies reproduction criteria, success conditions, and an investigation plan.

A.2.1 BOAD TOP 2 DISCOVERED SUB-AGENT CONFIGURATIONS FOR SEED-OSS-36B-INSTRUCT

  • The issue analyzer structures issue details into reproduction steps, success conditions, and a systematic investigation plan.Its analysis also includes a problem summary, technical details, and risk assessment.Source: §A.2.1 · p. 21
  • The code navigator maps relevant files, functions, classes, and dependencies while leaving repository state unchanged.It outputs code relationships and relevant snippets based on the supplied issue context.Source: §A.2.1 · p. 22

A.2.2 ALL BOAD DISCOVERED SUB-AGENTS

The appendix describes BOAD and evolutionary-baseline sub-agent results, manually designed configurations, design-set-size comparisons, and evolutionary-baseline costs. It reports similar sub-agent performance across design-set sizes and higher per-iteration API costs for evolution than BOAD.

A.2.2 ALL BOAD DISCOVERED SUB-AGENTS

  • BOAD’s reported sub-agent statistics include generation iteration, selection count, and final hindsight helpfulness rate.The statistics cover sub-agents discovered over 100 BOAD iterations; Table 4 is sorted by experiment number.Source: §A.2.2 · p. 22, Table 4 · p. 22

A.2.3 ALL EVOLUTION DISCOVERED SUB-AGENTS

  • Among evolutionary-discovered agents, issue analysis and localization agents have higher average helpfulness than test analyzer (0.167), dependency resolver (0.250), or config manager (0.000).Issue analyzer averages 0.968, code navigator 0.917, and issue reproducer 0.817; the test analyzer depends on earlier localization and patch steps.Source: §A.2.3 · p. 23

A.2.4 MANUALLY DESIGNED SUB-AGENT CONFIGURATIONS

  • The manually designed configurations specify separate localization, editing, testing, and error-reproduction roles.Their instructions ask agents to report relevant files, code changes, verification results, or reproduction outcomes.Source: §A.2.4 · pp. 23–24

A.3.1 EFFECT OF DESIGN-SET SIZE

  • Across design sets of 6 and 24 problems, discovered sub-agents achieve similar performance.The sets were sampled from six unique SWE-Bench-Verified problems; Table 6 compares performance by design-set size.Source: §A.3.1 · p. 25, Table 6 · p. 25

A.4.1 IMPLEMENTATION DETAILS FOR EVOLUTIONARY BASELINE

  • The evolutionary baseline generates three sub-agents sequentially, then constructs an orchestrator and evaluates the bundle on the design set.It uses BOAD’s prompts and the same warm-up and orchestrator-construction procedures.Source: §A.4.1 · p. 25

A.4.2 API COST COMPARISON WITH BOAD

  • $2.33 per evolutionary iteration versus $0.96 per BOAD iteration; evolution costs more because it mutates the orchestrator–sub-agent bundle at each iteration.Both methods require Claude calls for prompt proposals and LLM-as-judge scoring.Source: §A.4.2 · p. 25

Related papers

Loading 2512.23631v2…