When a single language-model agent fixes a bug in a real codebase, its trace (the logged sequence of thoughts, tool calls and observations) contains recurring stretches of work. It reproduces the failure, hunts for the faulty file, edits, and checks. Multi-agent systems try to exploit this by handing each kind of work to a separate sub-agent, but the sub-agents are almost always invented by people or by a language model guessing what a good team looks like. We propose to find sub-agents in the data instead. We cut many solved and unsolved single-agent traces into segments and describe each segment by what it changes in the world: which files became known, which tests started or stopped failing, whether an edit landed. We then cluster these effect descriptions. Each cluster becomes a sub-agent with its own restricted tool set and a stopping condition read off the cluster's typical end state. We add clusters to the team only if delegating that cluster's work raises solve rate on held-out issues.
Two observations motivate this. BOAD searches for software-engineering sub-agents with a bandit over LLM-invented role descriptions. It finds that hand-designed roles from earlier systems hurt performance and that the best team has exactly two sub-agents. That second result is something a data-driven method should be able to explain. In multi-agent reinforcement learning, RODE showed that grouping actions by their predicted effect on the environment yields useful role decompositions, but only for small discrete action sets frozen after early exploration. We carry RODE's effect-based clustering into open-ended tool use, where the actions are arbitrary shell commands and edits. We use BOAD's evaluation setting to test whether mined roles beat searched ones.
Core Claim
Sub-agent boundaries that come from clustering trace segments by their effect on task state and on what happens next will beat two alternatives at equal rollout budget. The first is LLM-invented roles (BOAD). The second is clustering by surface features such as which tools were called. The same procedure also yields a principled team size. If the effect clusters are the right unit of delegation, only a few clusters should carry positive delegation value. That would offer an account, rather than a hyperparameter, for BOAD's two-sub-agent peak.
Relation to Prior Work
Three MARL papers supply the core technique, and each also limits how far it transfers.
- RODE clusters action embeddings learned by a forward model of observation and reward change. We reuse its "cluster by effect" principle. We drop its two requirements: a fixed set of primitive actions, and representations frozen after 50k steps.
- ROMA gets roles to emerge through mutual-information losses and a policy-generating hypernetwork. This requires gradients through the agents, which black-box LLM agents do not offer. We therefore take only its lesson that roles are dynamic behavioral states, not fixed agent identities.
- R3DM identifies a "history trap": roles inferred only from past behavior collapse when agents start from similar histories. Its fix is to define a role by what it predicts about the agent's future. This is the reason our segment embedding is trained to predict future task state, not to reconstruct the past segment.
On the LLM side, three papers constrain the design and one competes directly.
- CodeR argues that fixed roles and task graphs are essential. It reports 28.33% on SWE-bench Lite and drops to 10% when the structure is removed.
- BOAD finds the opposite for hand-designed roles. We read the two together as saying structure helps, but human-chosen structure is the wrong kind. Our proposal tests whether trace-derived structure is the right kind.
- De-Linearizing Agent Traces (BPOP) infers dependency graphs between steps from traces. It decomposes a workflow's ordering for a single executor and assumes static task logic. We decompose by kind of work and assign it to separate agents, which suits bug fixing, where step order varies per issue.
- TraceSIR structures traces into Thought/Action/Observation rounds for human diagnosis. We borrow its trace format, but close the loop back into agent construction.
From behavioral clustering we take the premise, demonstrated at production scale by Agentic Coding in the Wild, that agent telemetry clusters into stable archetypes. We also respond to its stated weakness: clusters there were never tied to task success. Our clusters are scored by their effect on solve rate.
Research Program
Trace collection. We run one fixed single-agent scaffold in the style of SWE-agent over SWE-bench instances outside the Verified and Live evaluation sets. Because multiple runs per issue use nonzero temperature, we expect several thousand traces with known unit-test outcomes.
State features. After each step we compute a cheap, model-free state descriptor:
- the set of files read and edited;
- whether a reproduction script exists and fails;
- the pass/fail vector of the issue's tests when they are run;
- the size of the current diff.
Segmentation and effect encoding. A step encoder embeds each step from its tool, arguments and observation summary. A hidden semi-Markov model (a model that cuts a sequence into variable-length stretches, each drawn from one of $k$ latent types) jointly segments traces and assigns segment types. The segment representation $z$ is trained to predict two quantities:
- the change in state descriptor over the segment, $\Delta s$;
- the descriptor $h$ steps later, $s_{t+h}$.
The objective is $\mathcal{L} = \lVert f(z) - \Delta s \rVert^2 + \lambda \lVert g(z) - s_{t+h} \rVert^2$, where $f$ and $g$ are small prediction heads and $\lambda$ weights the future term. The future term is the R3DM-style ingredient that keeps two segments apart when they look alike but lead to different outcomes.
Turning clusters into sub-agents. Each cluster becomes a sub-agent with three components:
- Tool set: the tools covering 95% of the cluster's calls.
- Stopping condition: a predicate on the state descriptor, learned as the cluster's most frequent end-state change (for example, "a failing reproduction exists").
- Task-description prompt: written by an LLM from the cluster's representative segments. The prompt is the only place a language model touches role design.
Choosing team size. An orchestrator (the original single agent) can delegate to any sub-agent. Clusters are added greedily, in order of delegation value: the change in solve rate on a held-out tuning split when that cluster's work is delegated rather than done inline. Adding stops when value turns non-positive.
Refreshing the clusters. To avoid RODE's frozen representations, we repeat the pipeline once on traces produced by the resulting team and check whether the clusters stay stable.
Baselines
The naive reference point is the single-agent scaffold that produced the traces, run on the evaluation sets with the same base model. Every gain is measured against it. BOAD reports that its discovered team improves out-of-distribution performance by 63% over its single-agent baseline, which tells us the size of gap a good decomposition can open.
The strongest existing method is BOAD. It reports 53.2% resolution on SWE-bench-Verified and 20.0% on SWE-bench-Live with the 36B Seed-OSS model. We will run it with the same base model, same orchestrator scaffold and same tool access. Its optimization budget is matched to ours in total agent rollouts, rather than to its original 12 tasks, because our method consumes thousands of traces. Giving BOAD equal rollouts is the fair comparison and may strengthen it. Beating BOAD means a higher resolution rate on both Verified and Live under this matched budget, with the gap exceeding seed-to-seed variance over at least three seeds. We also report peak input tokens, since BOAD found delegation cut them by up to 25%.
CodeR's hand-designed five-role team is a reference for human-designed structure. It reports 28.33% on SWE-bench Lite with GPT-4o, against SWE-agent's 18.0% there. We re-run CodeR's roles on our base model rather than comparing across models.
Three ablations isolate the key ingredient:
- Surface clustering: cluster segments by tool-call histograms and text embeddings, with no effect or future prediction.
- No future term: set $\lambda=0$, testing the R3DM claim in this setting.
- Fixed team size: use silhouette-chosen $k$ with all clusters delegated, instead of delegation-value selection.
Why not just…?
Why not just let an LLM read the traces and propose roles? This is the most serious threat. A strong model reading successful traces, TraceSIR-style, may name the same stretches of work our clustering finds, at a fraction of the engineering. We run this as a baseline. Same traces, same prompt-writing model, and the LLM proposes roles, tool sets and stopping conditions. Selection of how many roles to keep uses the same delegation-value procedure. If it matches the effect clusters, the honest conclusion is that the contribution lies in the delegation-value selection and the use of success-labeled traces, not in the clustering. The note would then be rewritten around that claim.
Why not just use BOAD's bandit search? BOAD invents roles without looking at what agents actually do, and the file reports no account of why its optimum is two sub-agents. Our matched-budget comparison settles whether data-grounded roles generalize better to SWE-bench-Live. The delegation-value curve directly tests whether a small number of clusters carries all the value.
Why not just keep one agent with a better interface or per-step tool filtering? SWE-agent shows interface design alone moves a single agent far. CodeR's ablation (22% falling to 10% without multi-agent structure) and BOAD's token reductions suggest delegation adds something beyond interface design. We additionally give the single agent our mined tool subsets as context-dependent tool filters, without delegation. If that matches the team, the mined clusters are useful but sub-agents are not.
Proposed Experiments
The main experiment compares the following systems on SWE-bench-Verified and SWE-bench-Live, three seeds each:
- the single-agent scaffold;
- BOAD;
- CodeR roles;
- LLM-proposed roles;
- the three ablations;
- our mined team.
Metrics are resolution rate, peak and total tokens, and number of delegations per issue.
Three further checks decide the claim:
- Future term and diversity: whether removing the future term lowers Live resolution and causes measurable cluster collapse, meaning two clusters with near-identical tool profiles but different outcome distributions merging.
- Team size: whether delegation value turns non-positive after two or three clusters, and whether forcing more clusters reproduces BOAD's degradation.
- Stability: whether clusters re-mined from team traces stay stable, measured by adjusted Rand index over segment assignments.
As a check that the method is not specific to software engineering, we apply the same pipeline to TextCraft. There, state descriptors are inventory contents, and TDAG reports 73.5% success against ADAPT's 52.0%. This tests whether effect-based clustering recovers useful sub-agents in a second, smaller tool space.
References
- BOAD: Discovering Hierarchical Software Engineering Agents via Bandit Optimization
- RODE: Learning Roles to Decompose Multi-Agent Tasks
- ROMA: Multi-Agent Reinforcement Learning with Emergent Roles
- R3DM: Enabling Role Discovery and Diversity Through Dynamics Models in Multi-agent Reinforcement Learning
- CodeR: Issue Resolving with Multi-Agent and Task Graphs
- De-Linearizing Agent Traces: Bayesian Inference of Latent Partial Orders for Efficient Execution
- TraceSIR: A Multi-Agent Framework for Structured Analysis and Reporting of Agentic Execution Traces
- Agentic Coding in the Wild: Characterizing GitHub Copilot Traces at Production Scale
- SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering