Skip to content

Belief-Calibrated Multi-Agent Consensus Seeking for Complex NLP Tasks

๐Ÿ•’ Published (v1): 2025-01-01 ยท Source: NeurIPS ยท Venue: NeurIPS 2025 ยท link

Ask a follow-up

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

๐Ÿ’ฌ Ask ChatGPTโœฆ Ask Claude

TL;DR

BCCS (Belief-Calibrated Consensus Seeking) is a multi-agent framework that replaces naive voting-based consensus with a belief-aware three-state consensus judgment and theoretically-grounded collaborator/leader selection. It outperforms the best existing multi-agent methods by 1.67โ€“2.00% average accuracy on MATH and MMLU, with larger gains on harder subtasks.

Problem

Existing multi-agent consensus methods (e.g., Byzantine consensus, majority voting) judge consensus solely on agent answer agreement, ignoring each agent's confidence (belief). This causes two failure modes: (1) consensus can be declared despite high internal belief contradictions, producing unstable or suboptimal outcomes; (2) agents collaborate indiscriminately with all peers rather than selecting optimal collaborators, slowing or preventing stable convergence.

Method

BCCS operates iteratively over a MAS of n agents, each producing an answer x and a belief b (LLM output probability as a confidence proxy). Three modules run each round:

  1. Belief-Calibrated Consensus Judgment (BCCJ): Extends Byzantine consensus (>2/3 majority) with a belief ratio threshold. Full consensus requires p_b > 0.8 (dominant group's aggregate belief โ‰ฅ 4ร— conflicting group's). Partial consensus requires dominant-group aggregate belief > conflicting-group belief. Neither condition โ†’ no consensus.

  2. Collaborator Assignment (CA, for partial consensus): Identifies the most uncertain opinion group (highest entropy). Assigns the highest-belief agent from the conflicting group to guide the most uncertain agents (preventing local optima), while assigning highest-belief agents from supportive groups for all others. Conflict between groups is quantified via a belief-weighted conflict score ฯˆ combining macro-conflict (belief-weighted Jaccard complement) and micro-conflict (local consistency score difference).

  3. Leader Selection (LS, for no consensus): Selects the n_l highest-belief agents per opinion group as leaders; followers update exclusively by interacting with these leaders, driving rapid convergence per Theorem 3.3.

Theoretical proofs establish that (i) mixed supportive+conflicting collaboration guarantees stable consensus, and (ii) leaders with above-average belief accelerate convergence.

Key Contributions

  • BCCS framework with three-state belief-calibrated consensus judgment, collaborator assignment, and leader selection modules.
  • Formal theorems proving stable consensus conditions: balanced supportive/conflicting collaboration and high-belief leader selection.
  • Composite conflict score ฯˆ combining macro-level (belief-weighted Jaccard) and micro-level (local consistency gap) conflict between opinion groups.
  • Empirical validation on MATH and MMLU with ablations confirming contribution of each module.

Results

  • MATH (avg accuracy): BCCS 80.60% vs. best baseline DyLAN 78.93% (+1.67%); maximum gain on challenging subtasks: +2.23%.
  • MMLU (avg accuracy): BCCS 78.47% vs. best baseline PARSE 76.47% (+2.00%); maximum gain on challenging subtasks: +3.95%.
  • Ablation (MATH avg): Removing BCCJ โˆ’2.60%, removing CA โˆ’2.00%, removing LS โˆ’2.47%; removing conflicting-agent collaboration โˆ’1.60%; random leader selection โˆ’2.27%.
  • Scalability: Benefits persist when backbone scaled to Qwen2.5-32B and DeepSeek-R1-Distill-Qwen-32B; BCCS at 32B matches or surpasses larger-scale single-model baselines.
  • All results use Qwen2.5-7B-Instruct backbone unless noted; 7 agents, max 3 rounds, n_l=2 leaders.

Limitations

  • Evaluated only on NLP benchmarks (MATH, MMLU); not tested in embodied intelligence or tool-use agentic settings.
  • Belief is proxied by LLM output token probability, which is an imperfect calibration signal for LLMs.
  • Hyperparameters (number of agents, rounds, leaders) set empirically; no automatic tuning.
  • Gains are modest on easy tasks where single-agent baselines already converge reliably, limiting benefit over simpler methods in low-difficulty regimes.

Relevance to Agentic AI / LLM Agents

This work directly addresses a core design question in multi-agent LLM systems: how agents should decide when to accept a collective answer and whom to consult. By grounding collaborator selection and consensus termination in theoretically-justified belief dynamics (drawing from opinion dynamics literature), BCCS offers a principled alternative to ad-hoc voting schemes used in debate-style agents (MAD, GroupDebate, DyLAN). The belief-calibration mechanism is directly applicable to any MAS workflow where agents produce confidence scores alongside answers, and the three-state consensus categorization could inform routing logic in hierarchical or mixture-of-agents architectures.