Skip to content

From Self-Check to Consensus: Bayesian Strategic Decoding in Large Language Models

🕒 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

This paper proposes the Bayesian Decoding Game (BDG), a game-theoretic framework that models LLM output generation as a multistage signaling game between a generator and a verifier, converging to a σ-Separated Equilibrium to avoid both single-agent confirmation bias and multi-agent collusive error reinforcement. It requires no additional training and is model-agnostic. Smaller models augmented with BDG can outperform much larger baselines (LLaMA-13B at 78.1 on ARC-Easy vs. PaLM-540B at 76.6).

Problem

Single-agent self-reflection suffers from confirmation bias (the model reinforces its own errors), while multi-agent debate systems converge on shared incorrect answers through collusion—both at the cost of factual accuracy. Existing game-theoretic consensus methods (e.g., the Equilibrium Consensus Game, ECG) converge to Nash Equilibria that admit multiple solutions, including collusive ones, and suffer slow, oscillatory convergence via Average Recall updates.

Method

BDG formalizes LLM decoding as a multistage Bayesian signaling game with two roles: a Generator (samples candidate answers conditioned on a correct/incorrect signal) and a Verifier (judges candidates without observing the original signal). The key innovations are:

  1. σ_i-Separated Equilibrium (σ_i-SE): A Perfect Bayesian Equilibrium variant that enforces a minimum L1 distance σ_G between the generator's strategy distributions under correct vs. incorrect signals, and σ_V between verifier confidence scores—preventing arbitrary collusive consensus.
  2. Markovian Strategy Update: Each player updates their strategy using only the opponent's previous-round action (Eqs. 4–6), rather than cumulative Average Recall. This uses an exponential weighting with learning rate η_i and stiffness λ_i, and provably converges to σ_i-SE (Theorem 2).
  3. Stopping criterion: Convergence is declared when both σ-separation conditions hold and the generator and verifier preference orderings O_G = O_V agree.

For open-ended tasks, the candidate set Y is constructed via nucleus and top-k sampling. For multiple-choice tasks, Y is the given option set. No training is required; BDG operates entirely at decoding time.

Key Contributions

  • Formal proof that Nash Equilibrium in signaling games admits collusive solutions (Theorem 1), motivating the σ-Separated Equilibrium.
  • BDG framework with Markovian updates that converges to σ_i-SE 30× faster than ECG's Average Recall update.
  • Complexity reduction: O(n log n) vs. O(n²) for ECG.
  • Model-agnostic, training-free improvement applicable across LLM families and task types.
  • User study (n=183) showing BDG-guided verification improves both expert and non-expert human accuracy on mathematical assessment.

Results

  • LLaMA-13B + BDG on ARC-Easy: 78.1 vs. PaLM-540B baseline of 76.6.
  • LLaMA-13B + BDG on MMLU: 46.9, outperforming zero-shot GPT-3-175B (37.7) and LLaMA-65B.
  • LLaMA-13B + BDG on RACE-High: 60.3, outperforming LLaMA-65B (51.6) and PaLM-540B (49.1).
  • DeepSeek-7B on MMLU: BDG achieves 49.52% vs. 46.20% (ECG) and 44.07% (baseline G); +12.4% improvement stated in abstract.
  • Average improvement over baseline G: BDG +20.2%, ECG +18.2% across LLaMA-7B/13B on MMLU, ARC-E/C, RACE-H.
  • Inherent inconsistency (G vs. V disagreement): 59.7% average across benchmarks, which BDG effectively reduces.
  • BDG orthogonally combines with CoT and few-shot prompting with further gains (Tables 3–4).

Limitations

  • The game requires explicit specification of correctness/incorrectness signal branches, which assumes alignment with human intent by design—no guarantee of ground-truth factual correctness independent of the signal structure.
  • Evaluated only on LLaMA-7B/13B and DeepSeek-7B; scaling behavior to frontier-scale models is not systematically characterized.
  • Multi-agent extension (more than one generator or verifier) is mentioned as possible future work but not explored.
  • The candidate set construction for open-ended tasks (nucleus/top-k sampling) introduces a dependence on sampling hyperparameters that may affect equilibrium quality.

Relevance to Agentic AI / LLM Agents

BDG directly addresses a core failure mode of multi-agent systems—collusive consensus—with a principled game-theoretic fix applicable at inference time without retraining, making it immediately relevant to agentic pipelines that use self-consistency checks or debate-style reasoning. The Generator/Verifier separation mirrors the prover-verifier and actor-critic architectures common in agentic frameworks, but provides formal convergence guarantees absent from ad hoc implementations. The training-free, model-agnostic nature means BDG could serve as a drop-in decoding strategy for existing agent scaffolds (e.g., ReAct, reflexion loops) to improve output reliability. The result that smaller models with BDG can surpass much larger models is particularly relevant to cost-constrained agentic deployments.