Don't Make the LLM Read the Graph: Make the Graph Think

Computer Science > Artificial Intelligence arXiv:2604.23057 (cs) [Submitted on 24 Apr 2026] Title:Don't Make the LLM Read the Graph: Make the Graph Think Authors:Yuqi Sun, Tianqin Meng, George Liu, Yashraj Panwar, Lakshya Chaudhry, Munasib Ilham, Aman Chadha View a PDF of the paper titled Don't Make the LLM Read the Graph: Make the Graph Think, by Yuqi Sun and 6 other authors View PDF HTML (experimental) Abstract: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). Comments: main body has 9 pages, 4 figures, under review for COLM 2026 conference Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2604.23057 [cs.AI] (or arXiv:2604.23057v1 [cs.AI] for this version) https://doi.org/10.48550/arXiv.2604.23057 Focus to learn more arXiv-issued DOI via DataCite (pending registration) Submission history From: Yuqi Sun [view email] [v1] Fri, 24 Apr 2026 22:56:19 UTC (1,054 KB) Full-text links: Access Paper: View a PDF of the paper titled Don't Make the LLM Read the Graph: Make the Graph Think, by Yuqi Sun and 6 other authorsView PDFHTML (experimental)TeX Source view license Current browse context: cs.AI < prev | next > new | recent | 2026-04 Change to browse by: cs References & Citations NASA ADSGoogle Scholar Semantic Scholar export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv (What is alphaXiv?) Links to Code Toggle CatalyzeX Code Finder for Papers (What is CatalyzeX?) DagsHub Toggle DagsHub (What is DagsHub?) GotitPub Toggle Gotit.pub (What is GotitPub?) Huggingface Toggle Hugging Face (What is Huggingface?) ScienceCast Toggle ScienceCast (What is ScienceCast?) Demos Demos Replicate Toggle Replicate (What is Replicate?) Spaces Toggle Hugging Face…

This excerpt is published under fair use for community discussion. Read the full article at arXiv.org.