Don't Make the LLM Read the Graph: Make the Graph Think
For researchers building multi-agent LLM systems, this paper provides actionable insights on when and how to incorporate belief graphs, revealing that architectural integration matters more than graph content.
The paper investigates whether explicit belief graphs improve LLM performance in cooperative multi-agent reasoning, finding that integration architecture determines their value: as prompt context they are decorative for strong models, but when gating action selection they become structurally essential. Key results include 100% vs 20% success on 2nd-order Theory of Mind when graphs gate actions, and identification of 'Planner Defiance' where Llama 70B overrides correct recommendations 90% of the time.
We investigate whether explicit belief graphs improve LLM performance in cooperative multi-agent reasoning. Through 3,000+ controlled trials across four LLM families in the cooperative card game Hanabi, we establish four findings. First, integration architecture determines whether belief graphs provide value: as prompt context, graphs are decorative for strong models and beneficial only for weak models on 2nd-order Theory of Mind (80% vs 10%, p<0.0001, OR=36.0); when graphs gate action selection through ranked shortlists, they become structurally essential even for strong models (100% vs 20% on 2nd-order ToM, p<0.001). Second, we identify "Planner Defiance," a model-family-specific failure where LLMs override correct planner recommendations at partial competence (90% override, replicated N=20); Gemini models show near-zero defiance while Llama 70B shows 90%, and models distinguish factual context (deferred to) from advisory recommendations (overridden). Third, full-game evidence confirms inter-agent conventions (+128% over baseline, p=0.003) outperform all single-agent interventions, and individual belief-graph components must be combined to produce gains. Fourth, preliminary scaling analysis (N=10/cell, exploratory) suggests graph depth has diminishing returns: shallow graphs provide the best cost-benefit ratio, while deeper ToM graphs appear harmful at larger player counts (-1.5 pts at 5-player, p=0.029).