Skip to content

From Debate to Equilibrium: Belief-Driven Multi-Agent LLM Reasoning via Bayesian Nash Equilibrium

🕒 Published (v1): 2025-06-09 23:49 UTC · Source: Arxiv · Venue: ICML 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

ECON reframes multi-LLM coordination as an incomplete-information game and targets a Bayesian Nash Equilibrium (BNE), replacing explicit inter-agent message passing with a learned belief-state mechanism. Each Execution LLM independently maintains a belief network over peer behaviors; a centralized Coordinator aggregates outputs. ECON achieves a sublinear regret bound \(O\!\left(N\sqrt{T}/(1-\gamma)\right)\) and outperforms multi-agent debate by 11.2% on average while cutting token usage 21.4%.

Problem

Multi-agent debate (MAD) frameworks force every LLM to read every other agent's output each round, producing three compounding failures: quadratic token overhead, context-window overflow at scale, and no convergence guarantee—sometimes underperforming simple self-consistency. There is no principled coordination protocol that is simultaneously efficient, scalable, and theoretically grounded.

Method

ECON models the ensemble as a Decentralized Partially Observable MDP (DEC-POMDP) \(\langle \mathcal{N}, S, A, O, P, \Omega, R, \gamma \rangle\). Each of \(N-1\) Execution LLMs maintains a Belief Network \(B_i(\tau_i^t, o_i^t; \theta_i^B)\) implemented as a GRU over local history, producing a belief state \(b_i \in \mathbb{R}^d\) and a 2-D prompt embedding \(e_i = [T_i, p_i]\) (temperature + repetition penalty) that steers the LLM's generation—the only action space. A Belief Encoder (multi-head attention over \(\{b_i\}\)) produces a group-level representation \(E\), which feeds a Centralized Mixing Network that computes a global Q-value \(Q^{tot}\) and back-propagates to refine each agent's belief network via TD loss. The Coordinator LLM issues a strategy/format prompt, collects answers, and produces the final output. Optimization uses three reward components—Action Likelihood \(r^{AL}\) (cosine similarity to coordinator output), Task-Specific \(r^{TS}\), and Collaborative Contribution \(r^{CC}\)—with dynamically adjusted weights. BNE existence is proved via Glicksberg's Fixed Point Theorem; sublinear regret follows from bounding Q-function estimation error \(\epsilon_t = O(1/\sqrt{t})\) and policy suboptimality \(\delta_t = O(1/\sqrt{t})\).

Key Contributions

  • Formal DEC-POMDP treatment of multi-LLM coordination with a proved BNE existence theorem (Glicksberg) and sublinear Bayesian regret \(O\!\left(N\sqrt{T}/(1-\gamma)\right)\) versus linear regret of MAD.
  • ECON architecture: per-agent Belief Network (GRU + MLP) → Belief Encoder (multi-head attention) → Centralized Mixing Network, replacing token-heavy message passing.
  • Prompt-embedding action space \((T_i, p_i)\) that steers frozen LLMs without any parameter fine-tuning.
  • Three-part reward (consistency, task, contribution) with gradient-updated weighting.
  • Demonstrated scalability: 3 → 9 Execution LLMs yields +18.1% performance with only moderate resource increase; supports heterogeneous model ensembles.

Results

  • Reasoning average (5 datasets, 6 LLMs): ECON +25.6% over Zero-shot CoT, +6.3% over Few-shot CoT, +10.9% over SC@64, +11.2% over ToT, +6.4% over rStar, +11.2% over MAD.
  • Token usage: 21.4% fewer tokens than 3-round MAD.
  • TravelPlanner (GPT-4-Turbo): ECON 7.2% / 9.3% final pass rate (val/test) vs. MAD 2.3% / 3.7%; vs. best leaderboard sole-planning entry (DirectGPT-4-Turbo) 4.4%.
  • Scalability: 3 → 9 Execution LLMs adds +18.1% accuracy.
  • Heterogeneous ensembles: Strong hetero (Mixtral 8Ă—22B + Qwen1.5 110B + LLaMA3.1 405B) reaches 85.46% accuracy vs. weak homo (3Ă— LLaMA3.1 8B) at 67.70%.

Limitations

  • Belief networks require an offline training phase with task-specific reward signals; pure inference-time deployment is not possible without pre-trained belief parameters.
  • The action space is extremely narrow (2-D: temperature + repetition penalty), limiting how much the belief network can actually steer a frozen LLM.
  • Coordinator quality is a bottleneck: weak coordinators with strong executors underperform the reverse configuration (Table 2 shows hetero strong-executor config at 85.46% vs. 74.24% for weak-executor hetero).
  • BNE convergence proofs rely on standard regularity conditions (continuity, quasi-concavity) that are assumed rather than verified for real LLM reward landscapes.
  • Evaluated only on open-source models and GPT-4-Turbo; no ablation isolating belief-network depth or attention heads.
  • No wall-clock latency numbers; token reduction does not imply proportional latency reduction under batching.

Relevance to Harnesses / Meta-Harnesses

ECON is directly a multi-agent orchestration harness: its Coordinator-Executor architecture is a canonical meta-harness pattern where a controller dispatches work to a fleet of worker agents and synthesizes their outputs. The belief-based coordination layer is a principled alternative to the round-robin debate loops used in most LLM harnesses, offering both a convergence guarantee and a quantified token budget, two properties rarely present in ad hoc harnesses. The framework's modular design—swappable Execution LLMs, a separable Belief Encoder, and a pluggable reward function—maps cleanly onto harness design concerns around extensibility and cost control. For anyone building multi-LLM orchestration pipelines, ECON provides a theoretically grounded template for replacing synchronous all-to-all communication with asynchronous belief aggregation.