A bandit-driven method for composing specialized LLM sub-agents (BOAD) materially improves performance on challenging software-engineering tasks; a tuned 36B BOAD system placed second on the SWE-bench-Live leaderboard, outperforming larger models including GPT-4 and Claude.

Main Finding

BOAD (Bandit Optimization for Agent Design) automatically discovers hierarchical multi-agent software-engineering (SWE) systems by treating candidate sub-agents as arms in a multi-armed bandit. Using UCB-style exploration, a Chinese Restaurant Process to grow an archive, and an LLM-based hindsight credit assignment, BOAD finds compact teams of specialized sub-agents plus an orchestrator that outperform single-agent and hand-designed multi-agent systems on long-horizon, out-of-distribution SWE tasks. On SWE-bench-Verified and SWE-bench-Live, BOAD-based systems show substantial generalization gains; a 36B BOAD system ranked second on SWE-bench-Live (at evaluation time), surpassing some larger models (GPT-4, Claude). Code is released.

Key Points

• Motivation: Monolithic LLM agents retain irrelevant context across long reasoning chains, creating spurious correlations and poor OOD generalization. Human-like decomposition into specialized sub-agents (localize, edit, validate, etc.) should help.
• Hierarchical design: BOAD frames an orchestrator that selects temporally-extended sub-agents (Semi-MDP / options). Each sub-agent is a tool-like policy specialized for a sub-task.
• Automatic discovery: Instead of hand-designing agent roles, BOAD generates candidate sub-agents via LLM prompts and searches for helpful ones automatically.
• Bandit formulation: Treat each candidate sub-agent as an arm. At each round, select a subset of K arms to form a team, instantiate an orchestrator, evaluate on design instances, and update per-arm estimates.
• Exploration/exploitation: Use UCB for arm selection (empirical mean + optimism term). Dynamically expand the archive with a CRP-style generator: Pr(new) = θ/(θ + |archive|).
• Credit assignment: Use hindsight credit assignment via an LLM judge that inspects trajectories and labels whether each sub-agent’s contribution was helpful (binary ℓω(τ)). Per-sub-agent score uω is the average judged helpfulness across trajectories—this mitigates free-riding.
• Practical steps: Bootstrapping an archive via LLM prompts, warm-up stage that rewrites sub-agent docstrings into strict input/output specs (so orchestrator can call them), LLM-based orchestrator prompts to coordinate agents, evaluate on a small design set.
• Empirical outcomes: BOAD beats single-agent baselines and manually designed multi-agent systems on SWE-bench-Verified and generalizes better on out-of-distribution SWE-bench-Live. The discovered hierarchical systems show stronger OOD robustness than larger monolithic LLMs.
• Limitations noted: evaluation is expensive (long-horizon interactions), reliance on LLM judge quality, dependence on prompt-generated sub-agent quality and warm-up, and need for careful design-set selection.

Data & Methods

• Tasks / Benchmarks:
  • SWE-bench-Verified: 500 curated GitHub issue instances (frozen).
  • SWE-bench-Live: 300 continuously collected, more recent and OOD issues.
• Design set: small, diverse set for design-time evaluations (one random issue per repo; 12 instances used in main experiments).
• Agentic environment: LLM-based agents interact with code repositories via tools (browse files, run shell/tests, edit), modeled as an MDP with sparse terminal reward (1 if patch passes tests).
• Hierarchical formalism: Semi-MDP/options where orchestrator selects a sub-agent (option) which executes until termination.
• BOAD algorithm (high level):
  • Bootstrap archive Γ0 with LLM-generated sub-agent candidates; warm up docstrings to precise I/O specs.
  • For t = 1..B (budget rounds):
    • With prob θ/(θ + |Γ|) generate a new sub-agent and add to Γ; otherwise reuse.
    • Compute UCBω(t) = μ̂ω(t−1) + sqrt(2 ln t / nω(t−1)); pick top-K sub-agents by UCB.
    • Instantiate an orchestrator prompt conditioned on Ωt; evaluate (πt, Ωt) on design instances; collect trajectories.
    • For each ω appearing in trajectories, query LLM judge to produce ℓω(τ) ∈ {0,1} indicating helpfulness; set uω = average ℓω across evaluated trajectories; update μ̂ω and counts.
• Credit assignment: Hindsight LLM judge inspects full trajectory to determine per-sub-agent helpfulness (addresses co-occurrence/free-rider problems).
• Exploration control: Upper Confidence Bound selection and archive growth via CRP-style likelihood to maintain discovery vs exploitation.
• Implementation details: orchestrator and sub-agents implemented via LLM prompts/tool-calling protocol; warm-up ensures orchestrator can invoke sub-agents by parsing docstrings.
• Results summary: BOAD > single-agent and manually designed multi-agent baselines on Verified; strong OOD generalization on Live, with a 36B BOAD system placed high on leaderboard, outperforming some larger proprietary LLMs in that evaluation.

Implications for AI Economics

• Cost-efficiency and sample efficiency:
  • BOAD demonstrates that algorithmic structure (bandit-guided search + modular agents) can yield better performance than scaling model size alone. This can lower the marginal compute needed to achieve a given SWE capability, altering cost curves for applied LLM systems.
  • Bandit-based discovery reduces expensive end-to-end evaluations versus brute-force multi-agent search, improving design-time ROI for product teams.
• Returns-to-scale and model-market effects:
  • If smaller models paired with automatic hierarchical orchestration can match or exceed larger monolithic models on some tasks, this weakens pure parameter-scale returns and shifts value toward orchestration, tool ecosystems, and design-time algorithms.
  • Marketplace implications: vendors may compete by offering modular agent components, orchestrators, and agent-discovery tooling rather than just larger base models.
• Labor and task reallocation:
  • Better OOD generalization on complex SWE tasks increases the near-term automation potential for routine debugging, testing, and repo navigation—likely changing demand for certain developer activities (automation of low- to mid-skill SWE work) while increasing demand for higher-level roles (tooling/orchestration, verification, monitoring).
  • The modular agent approach suggests new complements to labor: humans supervising orchestrators, writing rubrics for LLM judges, or creating domain-specific sub-agents.
• Productization and monetization:
  • Reusable, specialized sub-agents (localizers, testers, refactors) could become tradable assets—licensed modules or marketplace components—creating new monetizable layers above base LLM APIs.
• Compute demand and externalities:
  • While BOAD can reduce per-instance inference cost by enabling smaller models to perform better, it also requires design-time evaluation (expensive), LLM-based judges, and orchestration infrastructure—possibly concentrating compute costs at development time but lowering operational costs.
  • Broader adoption may increase total demand for compute (many teams building custom orchestrations), even as per-task marginal costs fall.
• Policy and risk considerations:
  • Improved robustness on OOD tasks reduces some operational failure risk but shifts risk to agent-design errors and LLM-judge biases (misattributing helpfulness). Regulators and firms will need verification/auditing standards for automated agent pipelines in safety-critical code contexts.
• Research and market agenda for economists:
  • Study of how modular agent design affects market concentration (platform vs. orchestration/tool providers).
  • Empirical assessment of labor reallocation across developer tasks and wage effects.
  • Modeling returns to scale when gains can come from algorithmic orchestration rather than model size.

Limitations worth noting for economists and practitioners: BOAD’s effectiveness depends on quality of LLM-generated sub-agent proposals and of the LLM judge (both can be biased), design-time evaluation costs remain substantial, and the demonstrated benchmarks are SWE-specific—generality to other domains requires further validation.