TacoMAS: Test-Time Co-Evolution for Dynamic Multi-Agent Systems

Multi-agent systems (MAS) have become a promising paradigm for tackling complex tasks. Recent studies have investigated self-evolving MAS that automatically improve agent capabilities and communication structures. However, existing approaches either learn a topology that remains fixed during inference or adapt only one of topology and capability at test time. We investigate jointly adapting both dimensions at different time scales: agent capabilities should evolve rapidly to respond to emerging subtasks, whereas topology should change more gradually to maintain coordination stability. Inspired by a stylized replicator-mutator model, we propose TacoMas, a test-time co-evolution framework for dynamic MAS. TacoMas casts MAS inference as online graph adaptation, in which nodes correspond to agents with role-specific capabilities and edges represent their communication topology. During inference, a fast capability loop updates agent expertise based on trajectory-level feedback, while a slower meta-LLM-driven topology loop evolves the MAS through agent birth-death operations, including edge editing, agent addition, and agent removal. Experiments across four benchmarks show that TacoMas consistently outperforms nearly 20 multi-agent baselines, with an average improvement of 13.3 percentage points over the strongest baseline.