# Graph Evidence Is Not Enough: Diagnosing Native Decoder Use in Graph-Augmented LLMs

arXiv: https://arxiv.org/abs/2608.30437 · HTML: https://mlsanity.com/paper/2608.30437/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 38 references that are in the map.
- First posted on arXiv 31 Aug 2026.

## Builds on (most cited first, 24 of 24)

- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Neural Text Generation with Unlikelihood Training](https://mlsanity.com/paper/1908.04319/) (2019)
- [LLaGA: Large Language and Graph Assistant](https://mlsanity.com/paper/2402.08170/) (2024)
- [Retrieval-Augmented Generation with Graphs (GraphRAG)](https://mlsanity.com/paper/2501.00309/) (2024)
- [Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs](https://mlsanity.com/paper/2404.07103/) (2024)
- [A Survey of Graph Meets Large Language Model: Progress and Future Directions](https://mlsanity.com/paper/2311.12399/) (2023)
- [GRAG: Graph Retrieval-Augmented Generation](https://mlsanity.com/paper/2405.16506/) (2024)
- [A Survey of Large Language Models for Graphs](https://mlsanity.com/paper/2405.08011/) (2024)
- [GOFA: A Generative One-For-All Model for Joint Graph Language Modeling](https://mlsanity.com/paper/2407.09709/) (2024)
- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [Graph Foundation Models: A Comprehensive Survey](https://mlsanity.com/paper/2505.15116/) (2025)
- [Promoting Graph Awareness in Linearized Graph-to-Text Generation](https://mlsanity.com/paper/2012.15793/) (2020)
- [G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning](https://mlsanity.com/paper/2505.18499/) (2025)
- [GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets](https://mlsanity.com/paper/2406.16176/) (2024)
- [GraphOmni: A Comprehensive and Extensible Benchmark Framework for Large Language Models on Graph-theoretic Tasks](https://mlsanity.com/paper/2504.12764/) (2025)
- [What Breaks Knowledge Graph based RAG? Benchmarking and Empirical Insights into Reasoning under Incomplete Knowledge](https://mlsanity.com/paper/2508.08344/) (2025)
- [SEMMA: A Semantic Aware Knowledge Graph Foundation Model](https://mlsanity.com/paper/2505.20422/) (2025)
- [Toward Graph-Tokenizing Large Language Models with Reconstructive Graph Instruction Tuning](https://mlsanity.com/paper/2603.01385/) (2026)
- [Graph Tokenization for Bridging Graphs and Transformers](https://mlsanity.com/paper/2603.11099/) (2026)
- [ROGRAG: A Robustly Optimized GraphRAG Framework](https://mlsanity.com/paper/2503.06474/) (2025)
- [Leveraging LLM-GNN Integration for Open-World Question Answering over Knowledge Graphs](https://mlsanity.com/paper/2604.13979/) (2026)
- [Revisiting Graph-Tokenizing Large Language Models: A Systematic Evaluation of Graph Token Understanding](https://mlsanity.com/paper/2605.03514/) (2026)

## Abstract (arXiv)

Graph-augmented large language models often assume that graph evidence produced by external computation and placed in the input can be used by the native decoder. We test this assumption with HopQA, a deliberately bounded diagnostic that asks for the shortest-hop distance between two query nodes. Because the answer is a small integer and the target is purely topological, failure cannot be dismissed as open-ended generation or ambiguous evaluation. Yet existing graph-augmented baselines still fail on this setting, showing that providing graph evidence is not the same as making it usable. We introduce an intervention triangle with three matched conditions: readable graph evidence, shuffled graph evidence, and no-graph input. This separates evidence inclusion, structural readability, and decoder-usable topology. Guided by this diagnosis, we present S2GE as an instance showing that diagnosis-driven interface design can improve native decoder usability. S2GE uses query-aware sampling, endpoint and proximity-based ordering, and structure-preserving alignment. Across DBLP, Biomedical, GoodReads, and PubMed, S2GE achieves strict exact-match scores of 36.5%, 57.8%, 76.6%, and 52.0%, improving over the strongest native-generation baseline by 53.5 points on average. The interventions further reveal harmful-shuffle, shuffle-robust, and no-graph-saturated regimes.