Probabilistic Game Environments for Scalable Hallucination Detection in Interactive Multi-Agent LLMs

Large language model (LLM) agents deployed in interactive settings systematically hallucinate about user-specific context due to information gaps (Ji et al., 2023; Huang et al., 2023). The standard mitigation—asking detailed questions at every step—causes user abandonment exceed- ing 40% after 3-4 questions (Porcheron et al., 2018). We propose Probabilistic Game Environ- ments (PGE), where users answer 3-5 categorical setup questions once, agents make calibrated prob- abilistic guesses automatically scored via implicit behavioral signals, and hallucinations are detected through graphon analysis (Lovasz, 2012) of chain- of-thought DAGs (Wei et al., 2022). On Agent- Bench healthcare/finance tasks (Liu et al., 2023) (1,247 trajectories), Health-LLM scheduling (Jin et al., 2024) (892 sessions), and ToolBench multi- turn interactions (Qin et al., 2024) (1,580 dia- logues), PGE achieves 0.961 ± 0.012 AUROC using Llama3-70B agents—a 9.2% improvement over detailed questioning baselines—while reduc- ing user burden by 85.3% and resolving 96.4% of conflicts. We provide rigorous theoretical guarantees: motif preservation under graphon mixup (Han et al., 2022) (O(m2ϵ) deviation), detection consistency with O(1/√N ) conver- gence (Gao et al., 2015), scoring noise bounds (O(1/√T ) bias), and sample complexity (Borgs et al., 2017) showing N ≥ 487 suffices for 90% accuracy. Meta-learning from 10 public agents datasets reduces cold-start requirements to N = 50. Real user studies (n=200, MTurk) confirm 82% abandonment reduction.