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

• URL: http://arxiv.org/abs/2604.23057v1
• Date: Fri, 24 Apr 2026 22:56:19 GMT
• Title: Don't Make the LLM Read the Graph: Make the Graph Think
• Abstract summary: We investigate whether explicit belief graphs improve LLM performance in cooperative multi-agent card game Hanabi.<n>Through 3,000+ controlled trials, we establish four findings.
• Score: 13.277447097714395
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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).

Related papers

• X-KGRank: A Knowledge Graph RAG Framework for Explainable Recommendations via Pattern Mining and LLM Re-Ranking [0.0]
  X-KGRank is a knowledge graph retrieval framework that unifies structural collaborative filtering with LLM-based explanation.<n>We construct a heterogeneous knowledge graph of 9,762 nodes and 999,264 edges spanning three relation types (RATED, HAS_GENRE, and CO_RATED)<n>X-KGRank achieves NDCG@10 = 0.2956 and Recall@10 = 0.5371, improving over a strong popularity baseline by 17.1% on both metrics.
  arXiv  Detail & Related papers  (2026-08-03T05:56:40Z)
• When Does Few-Shot Prompting Help? A Systematic Empirical Study of Shot-Count Effects Across Model Scale, Architecture, and Output Parsing Robustness [0.0]
  Few-shot prompting, the practice of prepending a small number of input-output demonstration pairs to a query before presenting it to a large language model, is widely adopted in NLP.<n>Yet little systematic work investigates how shot count interacts with model scale, architecture, and output format compliance in classification performance.
  arXiv  Detail & Related papers  (2026-07-25T00:31:40Z)
• GraphCogent: Mitigating LLMs' Working Memory Constraints via Multi-Agent Collaboration in Complex Graph Understanding [13.356521655409422]
  Large language models (LLMs) show promising performance on small-scale graph reasoning tasks but fail when handling real-world graphs with complex queries.<n>We propose GraphCogent, a collaborative agent framework that decomposes graph reasoning into specialized cognitive processes: sense, buffer, and execute.
  arXiv  Detail & Related papers  (2025-08-17T14:28:38Z)
• Synthetic Visual Genome [88.00433979509218]
  We introduce ROBIN: an instruction-tuned with densely annotated relationships capable of constructing high-quality dense graphs at scale.<n>In total, our dataset contains 146K images and 5.6M relationships for 2.6M objects.<n> ROBIN-3B model, despite being trained on less than 3 million instances, outperforms similar-size models trained on over 300 million instances on relationship understanding benchmarks.
  arXiv  Detail & Related papers  (2025-06-09T11:09:10Z)
• G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning [58.73279333365234]
  Reinforcement Learning (RL) on synthetic graph-theoretic tasks can significantly scale graph reasoning abilities.<n>With RL on Erdos, G1 obtains substantial improvements in graph reasoning, where our finetuned 3B model even outperforms Qwen2.5-72B-Instruct (24x size)<n>Our findings offer an efficient, scalable path for building strong graph reasoners by finetuning LLMs with RL on graph-theoretic tasks.
  arXiv  Detail & Related papers  (2025-05-24T04:33:41Z)
• Compile Scene Graphs with Reinforcement Learning [69.36723767339001]
  Next-token prediction is the fundamental principle for training large language models (LLMs)<n>We introduce R1-SGG, a multimodal LLM (M-LLM) initially trained via supervised fine-tuning (SFT) on the scene graph dataset.<n>We design a set of graph-centric rewards, including three recall-based variants -- Hard Recall, Hard Recall+Relax, and Soft Recall.
  arXiv  Detail & Related papers  (2025-04-18T10:46:22Z)
• ReasonFlux: Hierarchical LLM Reasoning via Scaling Thought Templates [51.633266497799745]
  hierarchical LLM reasoning via scaling thought templates can effectively optimize the reasoning search space.<n>We introduce three innovations: (i) a structured and generic thought template library, containing around 500 high-level thought templates capable of generalizing to similar or relevant reasoning problems; (ii) performing hierarchical reinforcement learning on a sequence of thought templates instead of long CoTs; and (iii) a brand new inference scaling system.
  arXiv  Detail & Related papers  (2025-02-10T18:51:47Z)
• An Automatic Graph Construction Framework based on Large Language Models for Recommendation [49.51799417575638]
  We introduce AutoGraph, an automatic graph construction framework based on large language models for recommendation.<n>LLMs infer the user preference and item knowledge, which is encoded as semantic vectors.<n>Latent factors are incorporated as extra nodes to link the user/item nodes, resulting in a graph with in-depth global-view semantics.
  arXiv  Detail & Related papers  (2024-12-24T07:51:29Z)
• Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models [70.03602551880526]
  We introduce ProGraph, a benchmark for large language models (LLMs) to process graphs.<n>Our findings reveal that the performance of current LLMs is unsatisfactory, with the best model achieving only 36% accuracy.<n>We propose LLM4Graph datasets, which include crawled documents and auto-generated codes based on 6 widely used graph libraries.
  arXiv  Detail & Related papers  (2024-09-29T11:38:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.