PaperlayerView exact revision on arXiv

Source-linked AI summary

TacoMAS: Test-Time Co-Evolution of Topology and Capability in LLM-based Multi-Agent Systems

Chen Xu, Yicheng Hu, Ruizi Wang, Xinyu Lin, Wenjie Wang, Dongrui Liu, Fuli Feng

arXiv:2605.09539v1cs.CL

TL;DR

Existing multi-agent systems often keep topology fixed or adapt topology and capability at the same pace, limiting effective test-time evolution. TacoMAS co-evolves both through fast capability updates and slower topology changes, achieving a 13.3% average improvement over the strongest baseline across four benchmarks.

  • Problem

    Existing methods either keep communication topology fixed at inference or adapt topology and capability without the fast–slow coordination needed for stable joint evolution.

  • Method

    TacoMAS jointly adapts agent capabilities rapidly through execution feedback and communication topology slowly through meta-LLM-guided edge and agent edits during inference.

  • Results

    13.3% average improvement over the strongest baseline across four benchmarks, with TacoMAS achieving the best performance on all datasets.

  • Takeaways & Limitations

    Test-time inference in multi-agent LLM systems can be treated as task-conditioned co-evolution of capabilities and topology rather than a static forward pass.

  • Takeaways & Limitations

    The capability loop alone cannot add or remove agents or repair missing communication channels, so it may plateau under a fixed topology.

Abstract

from arXiv · show

Multi-agent systems (MAS) have emerged as a promising paradigm for solving complex tasks. Recent work has explored self-evolving MAS that automatically optimize agent capabilities or communication topologies. However, existing methods either learn a topology that remains fixed at inference time or adapt only the topology or capability during inference. We empirically and theoretically show that effective test-time evolution requires jointly adapting both axes, but on different time scales: capabilities should update rapidly to handle emerging subtasks, while the topology should evolve more slowly to preserve coordination stability. We then introduce TacoMAS, a test-time co-evolution framework for dynamic MAS. TacoMAS formulates MAS inference as a task of online graph adaptation, where nodes represent agents with role-specific capabilities and edges define their communication topology. During inference, a fast capability loop updates agent expertise using trajectory-level feedback, while a slow meta-LLM-driven topology loop performs agents' birth-death operations on MAS, including edge edit, agent addition, and agent removal. We further show that this fast-slow design drives MAS evolution toward a task-conditioned stable equilibrium. Experiments on four benchmarks demonstrate that TacoMAS outperforms nearly 20 multi-agent baselines, achieving an average improvement of 13.3% over the strongest baseline. The codes are released at https://github.com/chenxu2-gif/TacoMAS-MultiAgent.

1. Introduction

TacoMAS addresses the need for dynamic multi-agent coordination by jointly adapting agent capabilities and communication topology at different time scales during inference. Its fast-slow co-evolution design is theoretically motivated and empirically achieves a 13.3% average improvement over the strongest baseline across four benchmarks.

  • Motivation: Complex tasks such as software engineering, retrieval-intensive analysis, and long-horizon planning require multiple specialized agents coordinating across interdependent subtasks.Multi-agent systems provide a natural solution when a single agent cannot reliably solve these problems.
  • Limitations of prior work: Existing methods either keep learned topologies fixed at inference or evolve only communication topology or agent capabilities, limiting adaptation to unseen coordination demands.The introduction identifies joint optimization of both aspects as essential for realizing MAS collaboration.
  • Fast-slow principle: Updating topology and capability at the same pace can destabilize global coordination, motivating rapid capability adaptation alongside slower topology evolution.For example, a verifier may need to strengthen checking capability quickly while preserving evidence flow by avoiding simultaneous rewiring.
  • TacoMAS: TacoMAS uses a fast capability loop and a slow meta-LLM-driven topology loop to co-evolve agent expertise and graph structure during each query’s inference.The topology loop periodically proposes birth-death updates involving a small set of edge and agent edits, while the capability loop uses execution outcomes and task contribution.
  • Results: 13.3% average improvement over the strongest baseline is achieved across four benchmarks, with TacoMAS outperforming nearly 20 MAS baselines and attaining the best performance on all datasets.The benchmarks cover financial problem analysis, web browsing, Minecraft-style planning, and workplace task execution.

2. Related Work

Related work progresses from hand-crafted role-specialized multi-agent teams to automated offline search and test-time evolution, but existing approaches retain frozen inference artifacts or adapt only one update axis.

  • Multi-agent LLM systems: Multi-agent LLM systems address tasks requiring specialized roles and inter-agent coordination, including long-horizon software development, financial analysis, and multi-step planning.Early frameworks coordinate hand-crafted teams of role-specialized agents.
  • Training- / Offline-evolving multi-agent systems: Offline-evolving systems automate workflow or agent search, but the resulting multi-agent artifact remains frozen at inference.The passage identifies offline workflow/agent search and modular agent-design search as two dominant families.
  • Test-time evolving multi-agent systems: Test-time evolving systems update the multi-agent system during each instance, yet existing methods commit to a single update axis.Topology-only methods modify communication structure or agent selection while keeping agent prompts and tool policies fixed.

3. Method: TacoMAS

TacoMAS models inference as online co-evolution of agent capabilities and communication topology, updating capabilities every round and topology every K rounds. Its fast loop refines agent expertise from trajectory feedback, while its slow loop performs bounded structural edits to agents and edges.

  • Test-time evolution: TacoMAS represents the evolving MAS as a directed agent graph G_t=(T_t, Φ_t), separating topology T_t=(V_t,E_t) from agent capabilities Φ_t.The graph is indexed by execution round t during online inference for each query.
  • Asynchronous co-evolution: Capabilities update every execution round using trajectory feedback, whereas topology updates only after K rounds to preserve coordination stability.The fast operator F_C adapts reasoning and tool-use strategies, while the slow operator F_T waits for agents to reach their performance ceiling under the current topology.
  • Capability evolution: The fast capability loop evaluates each agent’s trajectory and writes evolution signals back into its capability state through a meta-judge and meta-LLM diagnostic coach.The trajectory includes reasoning steps, tool-use outcomes, and outgoing messages; evaluation provides a numerical contribution score and textual justification.
  • Capability evolution: A replicator-style abstraction amplifies high-contribution behaviors and suppresses erroneous or marginal patterns, with the meta-LLM update assumed to align statistically with this dynamic.The formulation uses team mean contribution and update strength η, while the assumption permits nonnegative noise slack ϵ_noise.
  • Topology evolution: Every K rounds, the slow meta-LLM proposes topology changes that add or remove agents and communication edges to address bottlenecks that capability refinement cannot resolve.Birth expands functional capacity, death removes consistently low-contributing agents, and edge edits repair information flow; edit budgets B_V and B_E limit structural volatility.
  • Algorithm and termination: The procedure initializes G_0 with |V_0|=5 and terminates when the global score reaches τ, the round budget R is exhausted, or the meta-LLM detects convergence.Topology updates are triggered after K rounds when the score s_t is below τ, subject to the edit budget.

4. Theoretical Analysis

TacoMAS is analyzed as a two-time-scale replicator–mutator process: a fast capability loop improves strategies under the current topology, while a slow topology loop applies structural mutations. Under bounded-noise and biased-edit assumptions, their joint update contracts toward a noise-controlled neighborhood of stable, high-performing configurations, enabling escape from topology-induced plateaus.

  • Fast capability loop: The fast capability update amplifies above-average contributions and suppresses below-average ones, improving local reasoning strategies under a fixed communication topology.Its expected update increases team-average contribution when contribution variance is nonzero, but it cannot add or remove agents or repair communication channels.
  • Slow topology loop: The slow topology loop periodically applies bounded birth–death and edge edits that mutate agent support and communication structure.The topology-edit assumption requires each proposed edit to improve the best achievable team contribution with probability p > 1/2.
  • Joint dynamics: Together, the loops form a replicator–mutator process in which capability adaptation reaches a local plateau before topology mutation changes the organization when that plateau is insufficient.The distance function L(Φ, T) measures distance to locally stable, high-performing configurations.
  • Convergence: Under bounded contribution noise and biased topology edits, the joint update contracts expected distance to the stable configuration set up to a noise-controlled neighborhood.The result explains why slow topology mutation can escape topology-induced plateaus that the fast capability loop alone cannot overcome.

5. Experimental Results

Across four reasoning benchmarks, TacoMAS achieves the best accuracy against 20 multi-agent baselines. Its gains arise from test-time co-evolution that adapts capabilities quickly and topology more slowly, with computation allocated according to task difficulty.

  • Main results: TacoMAS achieves the best accuracy across all four benchmarks, outperforming 20 multi-agent baselines spanning fixed, offline-evolved, per-instance, and within-instance methods.The benchmarks cover finance, browsecomp-plus, plancraft, and workbench, while baselines use the same LLM backend and dataset-specific tools unless otherwise stated.
  • Evolution trajectory: During inference, TacoMAS removes unhelpful roles, adds missing capabilities, and strengthens useful communication paths to form an instance-specific division of labor.On a finance trace, a “link research” role is deleted and a “data research” role is added after 3 rounds of slow update.
  • Fast/slow update schedule: The default fast/slow schedule performs best because rapid capability adaptation addresses local failures while slower topology changes preserve coordination stability.Topology updates that occur too frequently destabilize trajectories, whereas freezing topology prevents full specialization.
  • Difficulty-adaptive evolution: TacoMAS performs more slow updates on higher-expert-time finance instances, allocating additional computation from trajectory feedback rather than uniformly increasing reasoning depth.The expert-time annotation is never observed by the model.
  • Computational cost analysis: Increasing inference cost alone does not guarantee better performance: SelfOrg uses many LLM calls but plateaus, whereas TacoMAS continues improving with more evolution rounds.Calls denotes the mean number of LLM calls per instance.
  • Initial agent count: Performance is non-monotonic in initial team size: too few agents restrict role diversity, while too many increase coordination complexity, dilute bounded edits, and raise inference cost.A moderate initial team best balances role diversity, coordination stability, and compute.

6. Conclusion

TacoMAS frames inference as two-time-scale co-evolution, rapidly refining agent capabilities while slowly adapting communication topology. Its joint dynamics contract toward a task-conditioned stable region, supporting inference as a temporal co-evolution process rather than a static forward pass.

  • Framework: TacoMAS jointly refines agent capabilities rapidly and communication topology slowly within each task instance.The framework formulates inference as a two-time-scale online adaptation process.
  • Theory: Its joint dynamics connect to a replicator-mutator process and contract toward a task-conditioned stable region.
  • Implication: Inference-time computation in multi-agent LLM systems should be viewed as temporal co-evolution rather than a static forward pass.

A. Full Proofs … A.3. Lyapunov Function Construction

The appendix formalizes the replicator–mutator analysis, models capabilities through role frequencies, and establishes fitness ascent under frozen topologies. It then constructs a bounded joint Lyapunov function combining topology distance and fitness suboptimality.

  • A. Full Proofs: At round t, the agent graph is G_t = (T_t, Φ_t), with topology T_t = (V_t, E_t) and capability collection Φ_t = {ϕ_v,t}.The meta-judge produces contribution scores c_v,t, whose team mean is used in the analysis.
  • A. Full Proofs: The analysis uses replicator step η > 0, slow-update interval K ≥1, bounded noise, and finite-state assumptions.Contribution noise satisfies |ζ_v,t| ≤ ϵ almost surely, while expected fitness is bounded and Lipschitz.
  • A.1. Population-Frequency View: Each capability ϕ_v,t is treated as a positive scalar aggregating an agent’s prompt, memory, and tool inventory into multiplicative influence.The analysis converts these capabilities into an induced role-frequency vector and population-game expected fitness.
  • A.2. Replicator Dynamics under a Frozen Topology: With topology T fixed, continuous-time replicator dynamics perform Shahshahani gradient ascent on team-average fitness.The resulting team-average fitness is a Lyapunov function for the continuous flow.
  • A.2. Replicator Dynamics under a Frozen Topology: The discrete-time update has a normalized form because the empirical mean c̄_t cancels in the exponent ratio.A second-order Taylor expansion in η under bounded noise yields discrete-time fitness ascent with a variance gain, noise penalty, and O(η^2) error.
  • A.3. Lyapunov Function Construction: For query q, locally optimal configurations pair a role-frequency vector π* with a topology T* maximizing team-average fitness locally.The construction also defines a topology distance and a per-topology fitness ceiling.
  • A.3. Lyapunov Function Construction: The joint Lyapunov function combines topology distance to the optimal set with the gap between per-topology fitness ceiling and current fitness.Both summands are bounded, so the joint Lyapunov function is bounded.

A.4. Proof of Proposition 1

The proof applies the fast-step bound with topology fixed, requiring η small enough to control the O(η^2) remainder. A stronger inequality shows the update is biased toward improvement when active agents have unequal expected fitnesses.

  • Proof of Proposition 1: The proof applies (15) at T = Tt because topology remains fixed during one fast step.This establishes the stated bound for the fast capability update.
  • Proof of Proposition 1: The stated bound holds when η is small enough that O(η^2) ≤ηϵ.This is the regime of interest specified in the proof.
  • Proof of Proposition 1: The η Varπt( f ) term is strictly positive whenever expected fitnesses differ across active agents, biasing the update toward improvement.This conclusion follows from the stronger inequality (14).

A.5. Proof of Theorem 2 · A.6. Two-Time-Scale Justification

The proof analyzes K fast capability steps followed by one slow topology update, bounding their combined Lyapunov change and convergence behavior. The two-time-scale interpretation treats fast dynamics as quasi-stationary under a frozen topology before each slow update.

  • A.5. Proof of Theorem 2: Each slow-update cycle consists of K fast steps followed by one topology update, with the topology unchanged throughout the fast phase.The proof defines the role frequency immediately before the slow update after the K fast steps.
  • A.5. Proof of Theorem 2: During the fast phase, iterating the update for K steps and using Varπt(f) ≥0 yields a Lyapunov bound.Because T is fixed, the topology-dependent distance remains unchanged during these fast steps.
  • A.5. Proof of Theorem 2: Each slow edit obeys |∆V| ≤BV and |∆E| ≤BE, while improving the best achievable team contribution with probability p > 1/2.Each edit changes d(T, A) by at most 1, enabling a biased random-walk argument with γ := 2p −1 > 0.
  • A.5. Proof of Theorem 2: The topology update changes the optimal welfare by a bounded amount controlled by the edit budget, through Lipschitz continuity on the finite topology lattice.The proof introduces a constant C > 0 and bounds the welfare change after mapping the role distribution onto the new topology.
  • A.5. Proof of Theorem 2: Combining fast and slow bounds produces a per-cycle contraction with noise from score noise, meta-controller slack, topology drift, and discretization.The aggregate term is ˜ϵ = ϵmeta + Kη2ϵ + η C (BV + BE) + γ η M + O(Kη3).
  • A.5. Proof of Theorem 2: Unrolling the cycle inequality over N slow cycles and applying log(1 −γ) ≤−γ establishes the stated transient convergence requirement.The proof concludes by recasting the result as the per-step contraction in Theorem 2.
  • A.6. Two-Time-Scale Justification: For K sufficiently large, fast dynamics track a quasi-stationary distribution under the frozen topology, while slow updates use time-averaged fast trajectories.The fast-phase Lyapunov increment formalizes this two-time-scale separation, with each fast step changing L by at most O(η2ϵ).

B. Limitations

TacoMAS’s centralized evolution controller may bottleneck on long or highly decomposable tasks, while clearing scratch memory between instances prevents reuse of structural discoveries.

  • Controller scalability: A single meta-controller LLM may become a bottleneck on very long or highly decomposable instances.It observes the full execution trajectory and proposes both capability and topology updates, which keeps evolution simple and centralized.
  • Controller scalability: When tasks split into multiple sub-task clusters, the controller may miss fine-grained coordination failures after summarizing too much local information.
  • Cross-instance memory: Clearing scratch memory between instances prevents reuse of useful structural discoveries, despite preserving task independence and avoiding cross-query leakage.Related tasks may repeatedly rediscover role decompositions, verifier–searcher communication patterns, or tool-use strategies.

C. Additional Experimental Details and Results · C.1. Baseline Details

The experiments compare TacoMAS with 20 baselines spanning fixed, offline-evolved, per-instance graph, and within-instance adaptation regimes. These baselines use shared dataset-specific tools and base LLMs unless otherwise stated, while TacoMAS jointly evolves topology and capabilities.

  • C.1. Baseline Details: 20 baselines are grouped by adaptation time scale for comparison.All methods use the same dataset-specific tools and base LLM unless stated otherwise.
  • C.1. Baseline Details: Fixed-topology baselines include single-agent, independent multi-agent, complete-graph, leader-worker, and leader-subcluster designs.The compared methods are SAS, MAS-Independent, MAS-Decentralized, MAS-Centralized, and MAS-Hybrid.
  • C.1. Baseline Details: Offline-evolved baselines optimize workflows or agent designs before deployment and freeze them during inference.This group comprises MetaGPT, AFlow, AgentSquare, EvoAgentx, and ADAS.
  • C.1. Baseline Details: Per-instance graph-design baselines generate or select a graph for each query, then keep it fixed throughout execution.The group includes AgentVerse, ARG-Designer, MaAS, MetaAgent, SwarmAgentic, MetaGen, and EvolveRouter.
  • C.1. Baseline Details: Within-instance evolution baselines adapt during inference along only one axis: personas, communication topology, or memory and skills.ChatDev-Puppeteer selects fixed personas, SelfOrg rewires a communication DAG with fixed prompts, and CORAL updates memory and skills with implicit topology.
  • C.1. Baseline Details: TacoMAS jointly evolves topology and capabilities during inference, distinguishing it from the one-axis within-instance baselines.This comparison positions TacoMAS as the method that adapts both axes rather than selecting personas, rewiring topology, or updating skills alone.

C.2. Evolution Traces on Other Datasets … D. All Prompts

Across datasets, TacoMAS shows adaptive topology evolution: harder tasks need more slow updates, graph changes mainly rewire edges, and stopping behavior reflects difficulty. The appendix details the empirical checks, case studies, and prompts governing meta-controller, agent, judge, dataset, and output behavior.

  • C.2. Evolution Traces on Other Datasets: Figures 5–7 trace topology changes from the initial centralized graph through one slow update and three updates or convergence across remaining datasets.Additions are green and removals are red dashed.
  • C.3. Assumption Verification: The average round-to-round manipulation-intensity increment is positive across datasets, supporting Assumption 1’s predicted non-decreasing trend despite noisy fluctuations.Retrieval-heavy datasets are noisier, while plancraft shows a clearer upward tendency; the positive mean is consistent with fast-phase equilibrium before slow updates.
  • C.4. Slow-Update Counts / C.5. Fine-Grained Breakdown: Easier datasets usually terminate with no or one slow update, whereas harder datasets, especially finance, more often consume the full slow-update budget.Per-subcategory analysis likewise finds that harder metadata-defined subcategories generally require more slow updates.
  • C.6. Stop Reasons: The budget-exhausted fraction increases with dataset difficulty, making TacoMAS’s stopping behavior an unsupervised difficulty signal.Instances otherwise stop by reaching the answer-quality threshold.
  • C.7. Graph Densification: Node counts remain relatively stable while edge counts grow consistently, indicating that TacoMAS mainly rewires existing agents rather than spawning many new ones.This pattern supports the bounded-edit design.
  • C.8. Case Study: finance Instance 17: In a hard finance case, repeated slow updates remove failing retrieval agents and add specialized search roles until a 10-K disclosure enables answer verification.The initial graph repeatedly cited secondary sources instead of primary filings.
  • C.9. Contrast Case: finance Instance 8: In an easier finance case, one slow update removes an irrelevant calculator and adds a named-figure extraction researcher, after which the relevant margins are retrieved and compared.The contrast shows that evolution budget is spent according to instance requirements.
  • D. All Prompts: The appendix specifies TacoMAS’s prompts and JSON interfaces: the meta-LLM receives task, graph, agent traces, and scores, then emits bounded birth-death, edge-edit, feedback, rationale, and time-control fields.Fast agents self-critique after each round; judges return rubric or contribution scores; dataset templates define task-specific tools and submission formats; the released schema records graph differences and capability deltas.
Loading 2605.09539v1…