Phase Transition for Budgeted Multi-Agent Synergy

• URL: http://arxiv.org/abs/2601.17311v1
• Date: Sat, 24 Jan 2026 05:32:50 GMT
• Title: Phase Transition for Budgeted Multi-Agent Synergy
• Authors: Bang Liu, Linglong Kong, Jian Pei,
• Abstract summary: Multi-agent systems can improve reliability, yet under a fixed inference budget they often help, saturate, or even collapse.<n>We develop a minimal and calibratable theory that predicts these regimes from three binding constraints of modern agent stacks.
• Score: 41.486076708302456
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-agent systems can improve reliability, yet under a fixed inference budget they often help, saturate, or even collapse. We develop a minimal and calibratable theory that predicts these regimes from three binding constraints of modern agent stacks: finite context windows, lossy inter-agent communication, and shared failures among similar agents. Each leaf agent is summarized by a compute-performance scaling exponent $β$; communication is captured by a message-length fidelity curve $γ(m)$; dependence is captured by an effective shared-error correlation $ρ$; and a context window $W$ imposes hard fan-in limits that make hierarchy necessary. For binary success/failure tasks with majority aggregation, we prove a sharp phase transition for deep $b$-ary trees with correlated inputs and lossy communication: a single scalar $α_ρ$ (combining $γ(m)$, $ρ$, and fan-in $b$) determines whether weak signal is amplified to a nontrivial fixed point or washed out to chance. In the amplifying regime, we derive an organization exponent $s$ and show that budgeted synergy, i.e., outperforming the best single agent under the same total budget, occurs exactly when $s>β$, yielding closed-form compute allocation rules and explicit budget thresholds. We further characterize saturation via a mixing depth and provide a conservative clipped predictor that remains accurate across growth and saturation. A continuous-performance warm-up gives closed-form risks for star, chain, and tree organizations, making correlation- and communication-induced floors explicit and exposing the core design trade-offs in a smooth setting. Finally, we validate the predicted phase boundaries in controlled synthetic simulations and show how the same mechanisms explain the dominant bottlenecks reported in recent large-scale matched-budget studies of LLM agent-system scaling.

Related papers

• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Descent-Guided Policy Gradient for Scalable Cooperative Multi-Agent Learning [14.185814237633958]
  Descent-Guided Policy Gradient (DG-PG) is a framework that constructs noise-free per-agent guidance gradients.<n>We prove that DG-PG reduces gradient variance from $(N)$ to $mathcalO(1)$, preserves the equilibria of the cooperative game, and achieves agent-independent sample complexity.
  arXiv  Detail & Related papers  (2026-02-23T17:45:08Z)
• Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning [19.98996237281175]
  We introduce $texttGMFS$, a $textbfG$raphon $textbfM$ean-$textbfF$ield $textbfS$ubsampling framework for scalable cooperative MARL with heterogeneous agent interactions.<n>By subsampling $$ agents according to interaction strength, we approximate the graphon-weighted mean-field and learn a policy with sample complexity.<n>We verify our theory with numerical simulations in robotic coordination, showing that $textttGMFS$ achieves near-optimal performance
  arXiv  Detail & Related papers  (2026-02-18T05:34:07Z)
• Socially-Weighted Alignment: A Game-Theoretic Framework for Multi-Agent LLM Systems [17.658093330392052]
  We propose a game-theoretic framework that modifies inference-time decision making by interpolating between an agent's private objective and an estimate of group welfare.<n>We show that SWA induces a critical threshold $*=(n-)/(n-1)$ above which agents no longer have marginal incentive to increase demand under overload.
  arXiv  Detail & Related papers  (2026-02-16T05:17:58Z)
• Information Fidelity in Tool-Using LLM Agents: A Martingale Analysis of the Model Context Protocol [69.11739400975445]
  We introduce the first theoretical framework for analyzing error accumulation in Model Context Protocol (MCP) agents.<n>We show that cumulative distortion exhibits linear growth and high-probability deviations bounded by $O(sqrtT)$.<n>Key findings include: semantic weighting reduces distortion by 80%, and periodic re-grounding approximately every 9 steps suffices for error control.
  arXiv  Detail & Related papers  (2026-02-10T21:08:53Z)
• Mechanism-Based Intelligence (MBI): Differentiable Incentives for Rational Coordination and Guaranteed Alignment in Multi-Agent Systems [0.0]
  I introduce Mechanism-Based Intelligence (MBI), a paradigm that reconceptualizes intelligence as emergent from the coordination of multiple "brains", rather than a single one.<n>It provides a provably efficient, auditable and generalizable approach to coordinated, trustworthy and scalable multi-agent intelligence grounded in economic principles.
  arXiv  Detail & Related papers  (2025-12-22T22:22:13Z)
• Improved High-probability Convergence Guarantees of Decentralized SGD [74.39742894097348]
  We show that $mathttDSGD$ converges in HP under the same conditions on the cost as in the mean-squared error (MSE) sense.<n>Our improved analysis yields linear-up in the number of users, demonstrating that $mathttDSGD$ maintains performance in the HP sense.
  arXiv  Detail & Related papers  (2025-10-07T17:15:08Z)
• The Alignment Bottleneck [0.0]
  We model the loop as a two-stage cascade $U to H to Y$ given $S$, with cognitive capacity $C_textcog|S$ and average total capacity $barC_texttot|S$.<n>It pairs a data size-independent Fano lower bound proved on a separable codebook mixture with a PAC-Bayes upper bound whose KL term is controlled by the same channel via $m, barC_texttot|S$.
  arXiv  Detail & Related papers  (2025-09-19T12:38:30Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization.<n>We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution.<n>Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  Online gradient descent (OGD) is well known to be doubly optimal under strong convexity or monotonicity assumptions. In this paper, we design a fully adaptive OGD algorithm, textsfAdaOGD, that does not require a priori knowledge of these parameters.
  arXiv  Detail & Related papers  (2023-10-21T18:38:13Z)
• Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities [12.104551746465932]
  We investigate safe multi-agent reinforcement learning, where agents seek to collectively maximize an aggregate sum of local objectives while satisfying their own safety constraints. Our algorithm converges to a first-order stationary point (FOSP) at the rate of $mathcalOleft(T-2/3right)$. In the sample-based setting, we demonstrate that, with high probability, our algorithm requires $widetildemathcalOleft(epsilon-3.5right)$ samples to achieve an $epsilon$-FOSP.
  arXiv  Detail & Related papers  (2023-05-27T20:08:35Z)
• Utilizing Redundancy in Cost Functions for Resilience in Distributed Optimization and Learning [1.8414221462731502]
  This paper considers the problem of resilient distributed optimization and machine learning in a server-based architecture. The system comprises a server and multiple agents, where each agent has a local cost function. We consider the case when some of the agents may be asynchronous and/or Byzantine faulty.
  arXiv  Detail & Related papers  (2021-10-21T02:41:19Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.