Source-linked AI summary
Graph Evidence Is Not Enough: Diagnosing Native Decoder Use in Graph-Augmented LLMs
Xiaoyu Guo, Pengcheng Chen, Jiong Yu, Yi Lu, Yaohua Wang, Ziyang Li
TL;DR
Graph-augmented LLMs can receive graph evidence without making it usable for exact native decoding. The paper diagnoses this gap with bounded HopQA and matched interface interventions, then evaluates S2GE’s diagnosis-driven design, which improves native strict exact match across four domains.
Problem
Graph evidence may reach a native decoder without becoming usable for exact hop answers, even when the task has a bounded answer space and purely topological target.
Method
The paper uses HopQA and readable, shuffled, and no-graph conditions to diagnose graph-signal existence, evidence exposure, structural readability, and decoder use, then applies S2GE’s query-aware sampling and structure-preserving interface design.
Results
S2GE reaches native strict EM of 36.5–76.6% across four domains, while interventions distinguish harmful-shuffle, shuffle-robust, and no-graph-saturated regimes.
Takeaways & Limitations
Bounded native evaluation and graph-token interventions can distinguish exposed graph signal from decoder-usable topology and guide interface design.
Takeaways & Limitations
Numerical trends across decoder scales remain untested because the empirical results use a single LLaMA-3-8B-Instruct backbone.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper uses bounded HopQA to diagnose whether graph evidence survives the graph-to-decoder interface well enough for exact native generation. It separates graph-signal existence, evidence exposure, readability, and decoder use, then proposes S2GE as a diagnosis-driven interface design.
- Diagnostic gap: HopQA asks models to generate the shortest hop distance between two nodes from exposed graph evidence under strict exact match.Its bounded integer answer and topological target isolate graph-evidence use from open-ended generation.
- Diagnostic gap: Existing graph-augmented baselines fail on Core-HopQA despite graph evidence reaching the decoder.G-Retriever obtains 0.0±0.0% strict EM across DBLP, PubMed, Biomedical, and GoodReads, while LLaGA remains near zero.
- Diagnosis-driven interface: S2GE addresses the interface gap with query-aware sampling, role-based ordering, and adjacency-based alignment.These choices aim to keep relevant structure within the evidence budget, preserve endpoint roles, and maintain local adjacency.
- Diagnostic design: The readable/no-graph/shuffled intervention triangle separates signal existence, evidence exposure, structural readability, and native usability.The protocol combines graph controls, graph-token interventions, and adjacency transfer to distinguish where the graph-to-answer path breaks.
- Residual graph signal: Generated graph-token changes reveal helpful residue, harmful residue, and output collapse across data regimes.These residual effects expose how interface changes alter native answer states.
2 Related Work
Related work frames graph-language systems as a progression from exposing graph structure to organizing it into readable interfaces and supporting native usability. Prior work spans retrieval, graph serialization, graph tokens, prompt design, external execution, and reasoning traces.
- Visible evidence: Graph-augmented systems expose structure through graph text, graph tokens, graph-enhanced generation, and LLM-only prompting.Examples include G-Retriever’s textual subgraphs and LLaGA’s projection of graph structure into decoder tokens.
- Readable interfaces: Graph reasoning performance is sensitive to task format, prompt design, evaluation coverage, and graph linearization.GraCoRe, GraphOmni, and graph-to-text studies connect interface organization with benchmark and generation outcomes.
- Readable interfaces: Compression alone does not guarantee graph understanding in graph-tokenized language models.This motivates treating representation organization as distinct from merely exposing graph information.
- Native usability: Other systems strengthen graph reasoning with external execution, symbolic traversal, tool calls, candidate scoring, constrained decoding, or supervised reasoning traces.Graph-CoT, KG-CoT, KiRAG, and HopRAG exemplify approaches that supplement native generation with structured reasoning or retrieval pipelines.
3 Bounded Graph-Signal Diagnosis
HopQA bounds graph reasoning to shortest-hop prediction, separating graph-signal recovery from whether native decoding can use exposed evidence. The diagnosis motivates S2GE’s ordered interface conditions: sample relevant structure, make roles readable, and preserve adjacency after projection.
- Diagnostic setup: HopQA restricts answers to five hop distances, testing whether bounded graph evidence becomes an exact native-generation answer.Each query uses source and target nodes, with gold answer d_G(s,t) in {1, 2, 3, 4, 5}.
- Diagnostic setup: Graph controls compare signal recovery with ordinary generation, distinguishing graph information available outside the decoder from native decoder use.The positive signal-use gap contrasts graph-based controls with each method’s ordinary generation path.
- Scope and assumptions: The study’s single-backbone experiments characterize scale-sensitive failure only for LLaMA-3-8B-Instruct, while interface-induced information loss is treated as scale-independent.The interface-conditioned upper bound states that distinctions removed before decoding cannot be reconstructed by decoder capacity alone.
- Interface conditions: The interface is evaluated through local coverage, readable endpoint roles, and adjacency preservation in projected graph tokens.These conditions correspond to what enters the sample, how nodes are distinguished, and whether sampled neighbors remain structurally related after projection.
- S2GE design: S2GE follows the diagnostic order by using query-aware sampling, role-based perception, and adjacency-based alignment.Sampling selects bounded endpoint-conditioned evidence; ordering exposes endpoint and proximity roles; alignment encourages adjacent nodes to remain close in token space.
- S2GE design: Native generation is trained jointly with sampled-adjacency preservation while retaining standard token-level negative log-likelihood for target answers.The objective combines native answer generation with the alignment term targeting A_adj(q).
4 Experiments
Experiments evaluate native decoder usability, intervention regimes, and S2GE through Core-HopQA and auxiliary graph diagnostics. Results show strong domain variation: readable organization, evidence inclusion, and alignment matter differently across regimes, while S2GE and graph-only structure recover complementary signal.
- Experimental setup: StrictEM is the primary native-usability metric, while ParsedEM, SingleIntRate, and DominantAnswerRate audit generated output states and residual numeric traces.
- Native decoder usability: S2GE reaches 36.5–76.6% strict EM across Core-HopQA, with ∆Chance gains of +16.5, +37.8, +56.6, and +32.0 on DBLP, Biomedical, GoodReads, and PubMed.
- Native decoder usability: G-Retriever obtains 0.0±0.0% strict EM across Core-HopQA, while LLaGA remains near zero under native generation.
- Graph-token intervention diagnostics: The intervention triangle compares readable, no-graph, and shuffled graph-token conditions to separate evidence removal, organization effects, and domain-specific output states.
- Interface ablations: PubMed is shuffle-robust, whereas DBLP is harmful-shuffle; PubMed alignment removal changes StrictEM little, from 52.0 to 52.0.
- Graph-token intervention diagnostics: Biomedical is no-graph-saturated: no-graph input reaches 57.1 StrictEM versus 57.8 with readable tokens, indicating a strong task prior.
- Interface ablations: Ablations indicate that PubMed is limited by query-aware sampling, while DBLP is more sensitive to query syntax and degree cues.
- HopQA predictive validation: S2GE and Pure GNN solve overlapping but non-identical subsets, and projected S2GE tokens preserve recoverable one-hop adjacency across source-target domain pairs.
5 Conclusion
The diagnostic shows that graph evidence can reach the decoder without becoming natively usable, while S2GE improves native usability across four domains. Its outcomes vary by domain, with unreadable graph tokens harmful, residue-preserving, or no-graph-saturated.
- Five-choice HopQA separates graph-signal existence, interface readability, and native usability through strict evaluation and graph-token interventions.
- S2GE reaches native strict EM 36.5–76.6% across four domains.The reported range spans DBLP, Biomedical, GoodReads, and PubMed.
Ethics Statement
The study uses public graph benchmarks and baseline artifacts for research evaluation without collecting new personal data, conducting user studies, or exposing annotators to offensive content.
- The evaluation uses public graph benchmark and baseline artifacts only for research purposes.The materials are used according to their public releases or published descriptions, with released code and processed diagnostics designated for research use.
- The work involves no new personal data collection, user studies, or annotator exposure to offensive content.
Limitations
The limitations center on HopQA’s bounded, protocolized scope and the need for additional evaluation protocols in open-ended graph reasoning. Decoder-scale trends are also not empirically tested beyond a single backbone.
- HopQA is a controlled receiving-end probe that covers only a bounded slice of graph-language interfaces.Its single-integer answers make correctness, output validity, and fallback behavior directly measurable.
- Open-ended graph QA and path-witness generation require additional answer-equivalence and calibration protocols.
- Numerical trends across decoder scales remain empirically untested because the results use a single LLaMA-3-8B-Instruct backbone.The paper separately characterizes a fixed-interface information bound across decoder scales.
B.1 Datasets and Splits
The controlled HopQA evaluation uses four graph domains, balanced five-label splits, strict exact-match scoring, and overlap and hop-wise audits. These choices make chance baselines and output validity explicit while checking for shortcut explanations.
- Datasets and Splits: Balanced splits across five hop labels give uniform random guessing and fixed majority-label prediction an expected accuracy of 0.200.These baselines are used to compute ∆Chance in the main experimental tables.
- Datasets and Splits: Strict exact match counts only outputs that are exactly one valid integer, while ParsedEM may recover a number from otherwise invalid output.
- Datasets and Splits: All audited GoodReads overlap types are zero, and hop-wise scores are reported to check against a single-hop shortcut explanation.
C Experiment Details
The experiments audit whether graph evidence remains readable and usable across training, evaluation, and controlled interface conditions. They combine reproducible run records, frozen probes, path-witness checks, and readable, shuffled, and no-graph interventions.
- Evaluation setup: Each domain uses balanced HopQA splits with equal numbers of examples for hop labels 1 through 5.The protocol includes chance-level baselines and defines StrictEM as the primary metric, with additional diagnostic audits.
- Reproducibility: Run records store domain, seed, prediction and evaluation paths, and ordered test-ID checksums for matched evaluation.Released checkpoints and method-specific recipes are used for G-Retriever and LLaGA, while the 12-epoch S2GE schedule applies only to trainable runs.
- Diagnostic target: Frozen interface probes assess whether projected token streams preserve endpoint roles, local adjacency, and endpoint-conditioned path order.Downstream exact match also reflects decoder optimization, so the audit separates interface readability from hop-decoder adaptation.
- Reproducibility: The appendix documents formal run, optimization, generation, and control settings, including the GoodReads leakage audit and hop-wise S2GE scores.These materials consolidate the implementation and evaluation protocol.
- Diagnostic target: The path-witness diagnostic requires protocolized path existence and a witness field checked by local adjacency and endpoint progress.It evaluates structured topology recovery while keeping the task bounded.
- Interventions: Readable, no-graph, and shuffled interfaces provide shared intervention coordinates for separating domain regimes.The contrasts compare how evidence organization changes the decoder’s answer state.
D.4 Output Variables
The output audit tracks domain-specific checkpoint behaviors alongside exact match and legality. Probe discovery promotes stable generation anomalies into measurable diagnostics that are followed across checkpoints.
- Output variables: Checkpoint behavior is summarized with exact match, legal-output rate, long-digit continuation rate, single-integer output rate, and dominant-answer concentration.DBLP uses digit8; GoodReads and PubMed emphasize dominant-answer concentration; Biomedical also monitors legality and format collapse.
- Probe discovery: Probe discovery collects raw generations, measures output anomalies, compares them with gold-label distributions, and promotes the most stable anomaly to a domain probe.The selected probe is tracked jointly with exact match and legality across checkpoints.
- Role implementation: Role identifiers mark source, target, endpoint proximity, and context within each sampled subgraph.Endpoint proximity uses BFS distances and connectivity inside the bounded sample; full-graph paths, hop labels, and stored witnesses are evaluation-only.
E.1 Formal Boundary Results
The formal results characterize HopQA as a bounded graph-structure diagnostic, establish an information boundary for exposed interfaces, and define measurable output-state differences between interface conditions. Protocol audits then quantify sampling, ablation, and adjacency recoverability.
- E.1 Formal Boundary Results: Bounded HopQA queries are graph-structure functions, and all-pair hop distances determine the adjacency matrix.For distinct nodes, adjacency is equivalent to hop distance one.
- E.1 Formal Boundary Results: If two examples share the same exposed interface but have different labels, no decoder observing only that interface can be correct on both.The decoder must assign the same output distribution whenever the exposed representation is identical.
- E.1 Formal Boundary Results: Decoder scaling cannot remove ambiguity that the fixed exposed interface has already introduced.Larger decoder families may improve approximation, optimization, and output formation, but cannot recover removed distinctions.
- E.1 Formal Boundary Results: Output-state divergence is positive when two interface conditions induce different output-state distributions and zero when those distributions match.The finite output-state audit makes interface changes measurable.
- E.2 Protocols: Query-aware 1-hop sampling reaches 1.00 endpoint coverage and 0.58 path recall, while query-aware 2-hop sampling reaches 1.00 and 0.835 on 100 DBLP examples.Degree-only sampling gives 0.00/0.00; the formal alignment protocol uses λ = 0.25.
- E.2 Protocols: The ablation protocol uses PubMed for shuffle-robust interface-coordinate tests and DBLP for harmful-shuffle role/query readability stress tests.These experiments target distinct intervention regimes.
- E.2 Protocols: S2GE achieves DBLP reachability AUROC values of 0.950, 0.865, 0.861, 0.857, and 0.873 for k = 1, . . . , 5.Pure GNN gives 0.818, 0.952, 0.802, 0.722, and 0.720 on the same sequence.