Graph Evidence Is Not Enough: Diagnosing Native Decoder Use in Graph-Augmented LLMs
2026-08-31 • Computation and Language
Computation and Language
AI summaryⓘ
The authors studied how well language models can use graph information given as input to answer questions about the shortest connections between two points. They found that just including graph data is not enough for the model to use it correctly. To investigate, they tested three setups: with normal graph info, scrambled graph info, and no graph info, showing some models struggle when the graph is scrambled or missing. They then created a new method called S²GE that organizes the graph data in a way the model can understand better, achieving much higher accuracy across several datasets.
large language modelsgraph augmentationHopQAtopological distancegraph evidencedecoder usabilityexact-match accuracyquery-aware samplinggraph structure alignmentdiagnostic evaluation
Authors
Xiaoyu Guo, Pengcheng Chen, Jiong Yu, Yi Lu, Yaohua Wang, Ziyang Li
Abstract
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 S$^2$GE as an instance showing that diagnosis-driven interface design can improve native decoder usability. S$^2$GE uses query-aware sampling, endpoint and proximity-based ordering, and structure-preserving alignment. Across DBLP, Biomedical, GoodReads, and PubMed, S$^2$GE 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.