Source-linked AI summary
Credit Where Credit Is Due: Contrastive Attribution Topology Search for Multi-Agent Systems
Fabian Tritthart, Tom Zehle
TL;DR
Team-level scores do not reveal which agents help or hinder, complicating the search for effective, low-cost multi-agent topologies. CATS compares traces to credit agents and updates and prunes a fixed supergraph. It improves the performance–efficiency balance on BigCodeBench, matches or beats score-only search on at least one measured axis across three domains, and its poisoned-pool test supports pruning harmful agents without establishing a security guarantee.
Problem
Team-level task scores do not identify which agents help or hinder, although topology determines agent inclusion and communication and affects accuracy and cost.
Source: §1 · p. 1Method
CATS compares candidate-team execution traces to assign per-agent credit, then updates supergraph edges and prunes weak links and agents to select a fixed team.
Source: §2 · p. 2Results
Takeaways & Limitations
The results support attribution for team optimization and pruning potentially harmful agents, but not a security guarantee.
Source: §6 · p. 4The poisoned-prompt stress test does not establish deployment safety, since an adaptive adversary could act beyond the capped transcript window or exploit the unverified attributer.
Source: §6 · p. 4
Abstract
from arXiv · showhide
An LLM multi-agent system (MAS) is only as good as the agents it chooses to trust: its accuracy and cost hinge on its topology, meaning which agents are included and how they communicate. A single task score, however, does not reveal which agents help or hinder performance. We propose Contrastive Attribution Topology Search (CATS), which searches for compact teams within a fixed supergraph of specialized agents. An LLM attributer compares execution traces across candidate topologies and assigns credit to individual agents. CATS uses these credits to update supergraph edges while progressively pruning weak edges and agents, yielding a small team for deployment. With small open-weight models and matched candidate evaluations, CATS improves mean accuracy on BigCodeBench by 5.3 percentage points over score-only heuristic search while using 54$\%$ fewer deployment tokens. On MBPP, CATS matches the strongest baselines with fewer tokens than the other searches. In a HotpotQA prompt-poisoning stress test, CATS excludes all adversarially prompted agents in all three runs, whereas random search retains some at comparable accuracy. Per-agent credit thus supports both team optimization and the pruning of potentially harmful agents.
1 Introduction
MAS topology determines which specialized agents participate and communicate, yet team-level scores obscure individual contributions. CATS uses per-agent credit to guide team construction and is evaluated on coding benchmarks and a poisoned-agent stress test.
1 Introduction
- LLM multi-agent systems divide work among specialized agents, but adding agents and messages increases token use, while task-dependent topology makes manual design difficult.The paper cites prior work suggesting collaboration can improve small models [9] [10], while manual topology design is difficult [5].Source: §1 · p. 1
- Task scores assess the team as a whole, so they can miss useful contributions in failures and unnecessary work in successes.The introduction asks whether feedback on individual agents can guide compact, effective teams.Source: §1 · p. 1
- CATS compares candidate-team transcripts to assign signed credit to agents, then updates links and prunes weak links and unreachable agents.It selects one fixed team for deployment; agent models, prompts, roles, and tools remain unchanged.Source: §1 · p. 1
- The paper reports higher mean accuracy and lower deployment-token use than score-only search on two coding benchmarks under matched candidate evaluations.It also reports that CATS excluded all poisoned agents in every HotpotQA run, while random search retained some at comparable accuracy.Source: §1 · p. 1
2 Method
CATS searches for a useful subgraph of specialized agents by sampling candidate topologies, assigning contrastive agent credits, and updating and pruning communication links.
Supergraph
- The search space is a hand-crafted complete directed acyclic supergraph whose nodes are specialized agents and whose edges encode direct communication and scheduling order.Each edge has a logit that determines its sampling probability; CATS uses heuristic credit-based updates rather than gradient descent [7].Source: §2 · p. 2
Sampling
- At each step, CATS samples K topologies by drawing edges independently, rejects graphs with unreachable nodes, and evaluates each candidate on N tasks.Candidates, tasks, and often agents run in parallel; because agents share an environment, edges are optional communication channels.Source: §2 · p. 2
Attribution
- An LLM attributer assigns each participating agent a credit from −1 to 1 by comparing candidate rollouts on the same task.It sees task scores, length-capped outputs, tool calls, and final artifact state, and operates in parallel across tasks.Source: §2 · p. 2
Update and selection
- Agent advantages center credits against the task-level mean, update fired and selected unfired incoming edges, and guide pruning of weak edges and unreachable nodes.After T steps, CATS returns the best final candidate; ties favor fewer agents and then the earlier candidate.Source: §2 · p. 2
Baselines
- The search baselines are random topology search and a score-only heuristic using CATS’s updates and hyperparameters, with scalar scores replacing agent credits.The two search baselines match CATS’s K × T candidate evaluations on the same tasks, but not compute.Source: §2 · p. 3
3 Benchmarking
CATS is evaluated with small open-weight models on BigCodeBench and MBPP over three random seeds. It improves the accuracy–deployment-token balance on BigCodeBench, performs comparably to leading MBPP baselines, and its final candidate can be more efficient than the pruned graph.
Experimental setup
- Experiments evaluate CATS on BigCodeBench and MBPP using Gemma 4 12B MAS agents and a Gemma 4 31B attributer, with four optimization steps and three random seeds.This configuration performed well in preliminary experiments excluding held-out tasks, but the authors do not claim it is optimal.Source: §3 · p. 3
BigCodeBench
- 5.3 points higher mean accuracy and 54% fewer deployment tokens than score-only heuristic search on BigCodeBench, with matched candidate evaluations.Gains hold across all three seeds, though standard deviations overlap and uncertainty remains.Source: §3 · p. 3
MBPP
- CATS performs comparably to the hand-crafted MAS and random search on MBPP, using fewer deployment tokens than other searches but more than the hand-crafted MAS.The paper notes that its MBPP baseline scores leave little headroom for accuracy gains.Source: §3 · p. 3
Final-candidate ablation
- Deploying the selected topology instead of the pruned supergraph roughly halves coding deployment tokens, with higher mean accuracy on BigCodeBench and the same accuracy on MBPP.Source: §3 · p. 3
Offline search tokens
- Including attribution, CATS uses 28% and 35% fewer mean search tokens than score-only search on BigCodeBench and MBPP, respectively, but roughly twice as many on poisoned HotpotQA.Source: §3 · p. 3
Discovered architectures
- Every selected coding team retains a draft coder, and three of six have no inter-agent edges; selected HotpotQA teams retain reader-to-submitter paths.The paper cautions that sparse coding teams may coordinate through the shared environment and do not isolate a benefit from communication optimization.Source: §3 · p. 3
4 Poisoned-Pool Stress Test
The HotpotQA stress test evaluates whether search can avoid adversarially prompted agents without being told which agents are poisoned. CATS removed all poisoned agents across three seeds, while random search retained two on average.
4 Poisoned-Pool Stress Test
- CATS retained no poisoned agents across all three seeds, whereas random search retained two on average.The search saw task scores and transcripts but no adversarial labels; CATS removed incoming edges to make poisoned agents unreachable.Source: §4 · p. 4
- The poisoned HotpotQA pool paired six adversarially prompted agents with four honest agents and included six attack types.Attacks included plan misdirection, fabricated evidence, citation spoofing, instruction hijacking, late answer overwrites, and exact-match sabotage.Source: §4 · p. 4
- Comparable task scores could mask different levels of poisoned-agent recruitment, while score-only search produced cheap but inaccurate teams.Its teams had 1, 2, and 5 agents, including one with four poisoned agents.Source: §4 · p. 4
5 Related Work
Prior work optimizes agent graphs, samples systems from supergraphs, and prunes communication. CATS adapts contrastive attribution to topology search, using LLM-judged per-agent credit while keeping agent configurations fixed.
5 Related Work
- CATS adapts contrastive attribution from prompt optimization to topology search, changing team membership and communication links while agent configurations stay fixed.Other cited approaches optimize graphs, sample query-dependent systems from supergraphs, prune communication, or derive statistical per-edge credit from relative task rewards.Source: §5 · p. 4
- GPTSwarm, MaAS, and AgentPrune establish topology optimization, supergraph sampling, and communication pruning as related research directions [15] [16].Graph-GRPO derives statistical per-edge credit from relative task rewards within groups of sampled graphs [3].Source: §5 · p. 4
- Because introspective LLM judges do not faithfully approximate leave-one-out contribution, CATS treats its credits as an optimization signal rather than a causal measure [8].Source: §5 · p. 4
6 Limitations, Responsible Use, and Conclusion
CATS converts a hand-crafted supergraph into a fixed team and supports attribution for team optimization and pruning potentially harmful agents, but not a security guarantee. The paper also limits its conclusions to the evaluated settings and identifies attribution and deployment-safety caveats.
6 Limitations, Responsible Use, and Conclusion
- Evaluations use one model family across three domains and three seeds, limiting conclusions about broader transfer and variance.High baseline scores on MBPP also leave little headroom for accuracy gains.Source: §6 · p. 4
- Attribution credits lack human validation, and their correlation with success is only a consistency check because the attributer sees system_score.The score-only baseline was not separately tuned, and credit is node-level rather than edge-level.Source: §6 · p. 4
- CATS turns a hand-crafted supergraph into a small fixed team, supporting team optimization and pruning potentially harmful agents, not a security guarantee.Source: §6 · p. 4
- An adaptive adversary could act beyond the capped transcript window or exploit the unverified attributer; tool and data permissions must remain outside the optimizer.The stress test does not establish deployment safety.Source: §6 · p. 4
A.1 Supergraphs and Graphs
- The initial supergraphs use forward edges between layers, with start edges selecting entry agents; adversarial labels in the figure are hidden from search and attribution.Source: Figure 4 · p. 6
- HotpotQA alignment labels in the agent-pool table are for post-hoc measurement only and are not read by search or attribution.A read budget of zero allows listing titles but not reading passages.Source: Table 3 · p. 7
A.2 Selected Deployment Architectures
Selected coding teams retain a draft coder with one or two other agents, while HotpotQA teams connect a reader to an answer-submitting agent and exclude poisoned roles. The appendix identifies these selected topologies and gives search and baseline context.
A.2 Selected Deployment Architectures
- Agent selection and communication are distinct decisions: some coding teams use only entry edges, yet agents can interact through a shared persisted artifact.The selected topologies are the highest-scoring step-4 candidates on the search set, and each listed edge is directed.Source: Table 4 · p. 7, §A.2 · p. 8
- Coding teams retain a draft coder with one or two other agents, while HotpotQA teams retain a second-hop reader and either a drafter or final submitter, with communication directed from reader to answer submitter.HotpotQA teams exclude poisoned roles; the coding communication patterns vary across selected teams.Source: §A.2 · p. 8
A.3 Search and Baselines
- Attribution accounted for 9–11% of coding search tokens.Source: Table 5 · p. 8
- The baseline definitions use the same task model, grader, decoding limits, and seed-specific held-out tasks.Source: Table 6 · p. 8
A.4 Evaluation Protocol
The evaluation protocol specifies field-level token caps, model and run settings, and held-out grading. Each dataset split contains 100 held-out tasks.
A.4 Evaluation Protocol
- Field caps retain the prefix, discard the tail, and append a truncation marker; agent inputs use 900/700-token caps and attributer fields use 120 tokens for coding or 150 for HotpotQA.Tool-effect logs and final summaries are exempt from field capping; the assembled attributer prompt is prefix-capped at its model limit minus the attribution field cap.Source: §A.4 · p. 9
- Seeds 13–15 control splits, randomness, topology sampling, and generation; crashes, timeouts, empty environments, and unusable results score zero.Deployment tokens count all agent-call input and output tokens per held-out task, and reported ± values are sample standard deviations over three runs.Source: §A.4 · p. 9
- Coding agents and baselines use gemma-4-12b-llmlb, while the attributer uses gemma-4-31b-llmlb; weight hashes and quantization were not exposed.Source: §A.4 · p. 9
- Each held-out set contains 100 tasks, with dataset splits and grading summarized in Table 7.Source: Table 7 · p. 9
A.5 Per-Seed Results and Additional Analyses
The section provides per-seed evaluation context and additional analyses of search dynamics, credit–success consistency, and offline search-token use.
A.5 Per-Seed Results and Additional Analyses
- Per-seed evaluations report selected-topology scores, deployment tokens, agent and edge counts, and poisoned-agent counts for HotpotQA.Table 8 groups each seed’s selected topologies on 100 held-out tasks; scores are percentages and tokens are thousands per task.Source: Table 8 · p. 9
- Figure 5 plots MBPP CATS dynamics as three-seed means with sample-standard-deviation bands.The corresponding BigCodeBench panels appear in the main paper.Source: Figure 5 · p. 9
- The credit–success consistency analysis correlates mean participating-agent credit with binary task score across candidate-task pairs and within queries.The attributer sees system_score, so the check is not independent validation; four seed-15 pairs are omitted due to an unparsed transcript.Source: Table 9 · p. 10
- Table 10 reports offline search input-plus-output tokens for 16 candidates on 100 search tasks, averaged over seeds 13–15.Totals include sample standard deviations and are separate from deployment tokens.Source: Table 10 · p. 10
B BigCodeBench Attributer Call
The BigCodeBench attributer compares execution traces and credits agents based on their contributions to the persisted code artifact. Its example illustrates how tool effects and whether changes reach the graded target shape attribution.
B BigCodeBench Attributer Call
- For BigCodeBench, contrastive attribution grades the persisted code artifact rather than agent text and exposes ordered, compact tool effects.Source: B BigCodeBench Attributer Call · p. 11
- The prompt asks the attributer to compare executions using score differences, system predictions, and measurable changes to the shared environment.Credits range from -1.0 to 1.0: positive means helpful, negative harmful, and zero neutral or unclear.Source: B BigCodeBench Attributer Call · p. 11
- Because hidden tests grade persisted code, the attributer receives each agent’s text and an ordered log of its tool calls.Only targets named in final are graded; scratch writes count only if observed and followed by a graded write, and surviving code changes receive credit.Source: B BigCodeBench Attributer Call · p. 11
- The response format requires one executions object containing four ordered items, each with agent_credits for the specified seven agents.Source: B BigCodeBench Attributer Call · p. 11
- All four example executions scored 0.0, primarily because agents struggled to align implementation with the prompt’s implied data structure.Source: B BigCodeBench Attributer Call · p. 11
- In Execution 3, the edge-case tester’s scratchpad tests had no outcome impact because no coder wrote them to the graded code target.Source: B BigCodeBench Attributer Call · p. 11