Skip to content

BOAD: Discovering Hierarchical Software Engineering Agents via Bandit Optimization

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

Why this paper was selected

Bandit optimization discovers hierarchical SWE agent architectures automatically

Ask a follow-up

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

💬 Ask ChatGPT✦ Ask Claude

TL;DR

BOAD frames the discovery of multi-agent hierarchies for software engineering (SWE) as a multi-armed bandit (MAB) problem, where each arm is a candidate sub-agent and rewards reflect hindsight-judged helpfulness. Using UCB-driven exploration plus LLM-as-a-judge credit assignment, it automatically assembles orchestrator–sub-agent pipelines that generalize significantly better than single-agent or manually designed systems on real-world GitHub issue resolution.

Problem

Existing SWE agents use a monolithic single-agent design that forces the model to retain all prior context in one reasoning chain. This introduces spurious correlations between irrelevant context and task-specific patterns, causing poor generalization to out-of-distribution (OOD) issues (as seen on SWE-bench-Live vs. SWE-bench-Verified). Manually designed multi-agent systems are brittle because human-intuited role decompositions frequently misalign with actual LLM behavior. Automatic multi-agent design is hindered by (1) a combinatorially large design space and (2) noisy credit assignment — a sub-agent's individual contribution is hard to isolate within a team.

Method

BOAD models the agent hierarchy as a Semi-MDP (SMDP): a top-level orchestrator selects temporally extended "options" (sub-agents), each of which executes a sequence of primitive tool calls until its sub-task completes, then returns control. Sub-agent discovery proceeds in three interacting mechanisms:

UCB bandit over a sub-agent archive. An archive \(\Gamma\) of candidate sub-agents is maintained. At each round \(t\), the algorithm selects the top-\(K\) sub-agents by Upper Confidence Bound: $\(\text{UCB}_\omega(t) = \hat{\mu}_\omega(t) + \sqrt{\frac{2 \ln t}{n_\omega(t)}}\)$ and evaluates the team \(\Omega_t\) on a small design set (12 issues, one per repository).

Chinese Restaurant Process (CRP) archive expansion. New sub-agents are generated by prompting an LLM with probability \(\theta / (\theta + |\Gamma_{t-1}|)\) each round, keeping diversity while shifting toward reuse as the archive grows. A warm-up stage (\(W=4\) rounds) rewrites each new sub-agent's docstring into a precise input/output spec so the orchestrator can invoke it correctly.

Hindsight credit assignment via LLM-as-a-judge. Rather than attributing team success/failure to each member (free-rider problem), an LLM judge scores each sub-agent's trajectory contribution as a binary label \(\ell_\omega(\tau) \in \{0,1\}\). The performance score is: $\(u_\omega = \frac{1}{|\mathcal{T}_\omega^t|} \sum_{\tau \in \mathcal{T}_\omega^t} \ell_\omega(\tau)\)$ This decouples individual credit from team outcome, providing a denser and less noisy training signal.

At evaluation time, the two sub-agents with the highest helpfulness scores are used with the discovered orchestrator. The backbone model is Seed-OSS-36B-Instruct; Claude-4 is used only for design generation and judging.

Key Contributions

  • Formulation of multi-agent hierarchy discovery as a MAB problem, reducing the combinatorial search space to linear in the number of sub-agents.
  • Hindsight credit assignment via LLM judge that avoids free-rider bias and provides denser reward signal than binary task success.
  • CRP-based dynamic archive expansion preventing premature convergence while controlling diversity.
  • Empirical finding that manually designed sub-agents from prior work hurt performance, motivating automated discovery.
  • First demonstration of generalization improvements on long-horizon interactive SWE tasks via automatically discovered hierarchical multi-agent systems.

Results

  • SWE-bench-Live (OOD, 300 instances): 20.0% resolved — ranked 2nd on the leaderboard at time of evaluation with a 36B model, a 63% relative improvement over the same model using default SWE-agent tools (≈12.3% baseline), and outperforming GPT-4o, Claude 3.7 Sonnet, DeepSeek-V3, GLM-4.5-Air.
  • SWE-bench-Verified (500 instances): 53.12% resolved — a 13.4% absolute gain over default SWE-agent, surpassing GPT-4o, Claude 3.5 Sonnet (OpenHands), DeepSeek-R1, DeepSeek-V3, and setting a new SotA among sub-70B models.
  • vs. Evolutionary baseline (same evaluation budget): BOAD achieves 20.0% vs. 17.0% on SWE-bench-Live; BOAD's Claude API cost is less than half due to sub-agent reuse across rounds.
  • Adding manually designed sub-agents from prior work lowers performance on both benchmarks.
  • Bandit loop converges in ≈20 rounds (≤7 hours on 1×H100 node with 56-core CPU machine).

Limitations

  • Design set is only 12 instances (one per repo); sub-agent quality may be sensitive to this sample's representativeness.
  • LLM-as-a-judge credit assignment introduces its own noise and potential systematic biases not evaluated in depth.
  • The warm-up and archive generation pipeline uses a proprietary model (Claude-4), introducing an external dependency for the design phase.
  • Optimization runs ≈12 hours; scaling to larger design sets or more rounds is expensive.
  • Sub-agents discovered by BOAD are opaque; the paper does not provide a detailed qualitative analysis of what task decomposition was found beyond noting it differs from human intuition.
  • Results on SWE-bench-Live are on a "lite" split (not full 300), which may not fully reflect leaderboard standing.

Relevance to Agentic AI / LLM Agents

BOAD directly addresses the open problem of automated multi-agent architecture search for long-horizon, tool-using agents — a major bottleneck in scaling agentic systems beyond manually engineered pipelines. Its insight that human-designed role decompositions can hurt LLM agents (because LLM behavior diverges from human intuitions about sub-task boundaries) is a significant empirical result that challenges the design philosophy of most current multi-agent frameworks. The MAB formulation for sub-agent discovery is a principled, budget-aware alternative to evolutionary or gradient-based meta-optimization, directly applicable to any agentic domain with expensive evaluation loops. The hindsight credit assignment scheme addresses a fundamental credit assignment challenge shared by any hierarchical agent system, making it relevant beyond SWE to domains like robotics planning, web navigation, and scientific discovery workflows.