Source-linked AI summary
Can LLM Graph Reasoning Generalize beyond Pattern Memorization?
Yizhuo Zhang, Heng Wang, Shangbin Feng, Zhaoxuan Tan, Xiaochuang Han, Tianxing He, Yulia Tsvetkov
TL;DR
The paper asks whether instruction-tuned LLMs learn generalizable graph reasoning or memorize synthetic patterns, introducing NLGIFT to test transfer across synthetic shifts and real-world graph tasks. Results show partial robustness on simpler patterns but poor reasoning and real-world generalization, with post-training alignment the most promising preliminary strategy. The authors conclude that going beyond pattern memorization remains open.
Problem
Method
NLGIFT evaluates semantic, numerical, structural, reasoning, and real-world transfer using out-of-distribution tests plus Significant Transfer and Strong Recovery standards.
Source: §1 · p. 1, §2.2 · p. 4Results
Takeaways & Limitations
Post-training alignment is the most promising explored strategy, but transferable graph reasoning beyond memorized synthetic patterns remains an open research question.
Source: §1 · p. 2, §8 · p. 9Experiments use only one black-box LLM and Llama2-7B, with 4-bit quantization and QLoRA for Llama2-7B.
Source: Limitations · pp. 9–10
Abstract
from arXiv · showhide
Large language models (LLMs) demonstrate great potential for problems with implicit graphical structures, while recent works seek to enhance the graph reasoning capabilities of LLMs through specialized instruction tuning. The resulting 'graph LLMs' are evaluated with in-distribution settings only, thus it remains underexplored whether LLMs are learning generalizable graph reasoning skills or merely memorizing patterns in the synthetic training data. To this end, we propose the NLGift benchmark, an evaluation suite of LLM graph reasoning generalization: whether LLMs could go beyond semantic, numeric, structural, reasoning patterns in the synthetic training data and improve utility on real-world graph-based tasks. Extensive experiments with two LLMs across four graph reasoning tasks demonstrate that while generalization on simple patterns (semantic, numeric) is somewhat satisfactory, LLMs struggle to generalize across reasoning and real-world patterns, casting doubt on the benefit of synthetic graph tuning for real-world tasks with underlying network structures. We explore three strategies to improve LLM graph reasoning generalization, and we find that while post-training alignment is most promising for real-world tasks, empowering LLM graph reasoning to go beyond pattern memorization remains an open research question.
1 Introduction
The paper asks whether graph-tuned LLMs learn transferable reasoning or merely memorize synthetic patterns, and introduces NLGIFT to test transfer across increasingly challenging patterns. Experiments show reasonable transfer on easier patterns but severe failures on reasoning and real-world patterns, while post-training alignment is the most promising preliminary strategy.
Benchmark motivation
- NLGIFT evaluates transfer across semantic, numerical, structural, reasoning, and real-world patterns, including movement from synthetic graph problems to real-world tasks.The benchmark contains 37,000 problems and evaluates instruction-tuned models on both in-distribution and out-of-distribution data.Source: §1 · pp. 1–2
Main findings
- 75% basic transfer and 35% strong recovery on easier semantic, numerical, and structural patterns show partial but incomplete generalization.These standards distinguish statistically significant improvement over an untuned model from substantial recovery of in-distribution gains.Source: §1 · p. 2
- Reasoning patterns achieve basic generalization only 33% of the time and never achieve strong recovery.This result indicates that transferring across graph reasoning tasks is substantially harder than transferring simpler attributes or representations.Source: §1 · p. 2
- Real-world patterns achieve basic generalization in only 6% of settings, while synthetic graph instruction tuning is counterproductive in 69% of cases.The result casts doubt on whether synthetic graph data reliably improves tasks with underlying network structures.Source: §1 · p. 2
Mitigation strategies
- Code mixing, machine-generated chain-of-thoughts, and post-training alignment are explored as preliminary remedies, with post-training alignment most promising for real-world tasks.The paper concludes that going beyond memorized synthetic patterns remains an open research question.Source: §1 · p. 2
2 NLGIFT Benchmark
NLGIFT is a progressive benchmark that tests graph reasoning transfer across four synthetic tasks and five increasingly difficult pattern shifts. Its metrics distinguish significant out-of-distribution improvement from recovery of in-distribution performance.
2 NLGIFT Benchmark
- NLGIFT uses connectivity, shortest path, topological sort, and maximum flow to test whether graph reasoning transfers beyond memorized training patterns.The benchmark contains 33,000 synthetic and 4,000 realistic problems.Source: §2 · p. 3, §2.1 · p. 4
2.1 Graph reasoning patterns
- Semantic transfer changes natural-language graph representations, including adjacency, incident, graph expert, and friendship descriptions.The intended test is whether training on one representation preserves performance on another representation of the same graph problem.Source: §2.1 · p. 3
- Numerical transfer changes edge-attribute distributions among small integers, large integers, and one-decimal floats.The test examines whether models preserve graph reasoning performance when numerical scales and formats change.Source: §2.1 · p. 3
- Structural transfer varies graph size, graph-generation algorithm, and transitivity to test robustness across heterogeneous network structures.The benchmark contrasts graphs with 3–10 versus 11–25 nodes, Erdős–Rényi versus Barabási–Albert generation, and low versus high transitivity.Source: §2.1 · p. 3
- Reasoning transfer trains on one synthetic graph task and tests on the same task plus three different graph tasks.This evaluates whether models learn universal graph reasoning principles rather than task-specific patterns.Source: §2.1 · p. 3
- Real-world transfer evaluates synthetic-tuned models on multi-hop question answering and structured commonsense reasoning with implicit graph structure.The datasets include StrategyQA, Knowledge Crosswords, ExplaGraphs, and Proscript.Source: §2.1 · pp. 3–4
2.2 Generalization Metrics
- Significant Transfer requires tuned out-of-distribution performance to exceed the untuned model significantly, whereas Strong Recovery requires recovering most in-distribution performance.Performance Gap Recovered (PGR) operationalizes the stronger criterion, with λ = 0.8 used in the experiments.Source: §2.2 · p. 4
3 Experiment Settings
The experiments evaluate graph reasoning with two LLMs across numerical-transfer results and specified sampling and tuning settings.
Numerical Patterns
- For numerical patterns, easier shortest-path tasks transfer better across numerical distributions than more complex maximum-flow tasks.Source: Table 2 · p. 5
- The numerical-pattern table marks four corner cases that achieve Strong Recovery but fail Significant Transfer because zero-shot performance is low.Source: Table 2 · p. 5
- CHATGPT is fine-tuned for 3 epochs, while LLAMA2-7B uses 4-bit QLoRA for 10 epochs with batch size 4 and learning rate 1e-4.Source: §3 · p. 5
4 Results
Across graph-reasoning patterns, transfer is stronger for semantic and some numerical or structural changes than for reasoning and real-world tasks. The results also show that graph size and task complexity constrain transfer, while synthetic tuning can produce weak or negative real-world effects.
Semantic Patterns
Numerical Patterns
- For numerical patterns, shortest path transfers better than maximum flow, while large-integer and float settings yield 2.6% average in-distribution gains versus 12.1% for small integers.Source: §4 · pp. 5–6
Structural Patterns
- Graph size is the strongest structural constraint: only 2 of 8 settings achieve Strong Recovery, and training on small graphs yields average PGR below 60% on large graphs.Source: §4 · p. 6, Table 3 · p. 6
Reasoning Patterns
- Reasoning patterns achieve Significant Transfer in only 8 of 24 cases, with no Strong Recovery; average out-of-distribution gains are -12% for LLAMA2-7B and 19% for CHATGPT.Source: §4 · p. 6, Table 4 · p. 6
Real-World Patterns
- Synthetic tuning provides barely any improvement on real-world tasks, and Proscript shows an average 12.5% drop for both models after instruction tuning.Source: §4 · pp. 6–7, Figure 2 · p. 7
Mixture of Graph Tasks
- Figure 3 reports results for mixtures of graph tasks, where shortest path is the majority task and the other three tasks each receive the indicated share of training data.The figure also shows performance upper and lower bounds corresponding to in-distribution training and zero-shot conditions, respectively.Source: Figure 3 · p. 7
5 Analysis
The analysis examines how task mixtures and pretraining keyword frequency affect graph reasoning generalization. Mixing tasks can hurt the majority task, while keyword frequency is positively associated with in-distribution performance.
Mixture of Graph Tasks
- Mixing graph tasks reduced shortest-path performance by up to 43%, while connectivity and topological sort improved; maximum flow did not improve even with 25% of training data.The results suggest that mixed-task instruction tuning may not effectively improve overall graph-task performance.Source: §5 · p. 7
Frequency in Training Corpus
- Keyword frequency in the Dolma pretraining corpus was generally positively related to CHATGPT’s in-distribution performance on semantic patterns.The corpus contains 3.1T tokens and was used as an approximation because the base models’ training data were unavailable.Source: §5 · p. 7
6 Improving Graph Reasoning Generalization
The paper evaluates code mixing, machine-generated reasoning traces, and preference alignment as strategies for improving graph reasoning generalization. No method improves every setting, while DPO is the most promising but remains imperfect.
Mixing Code
- The study adds general and graph-related code instruction data to synthetic graph-training sets to test whether structured code improves generalization.The two code sources are general code instruction data and graph-related code filtered using graph keywords.Source: §6 · pp. 7–8
Results
- Table 5 compares mean in- and out-of-distribution accuracy with average recovery rate across the evaluated synthetic and real-world settings.The table reports the best result in bold and identifies DPO as preliminarily the most promising approach.Source: Table 5 · p. 8
Machine-generated Chain of Thoughts
- Machine-generated chain-of-thought training transfers filtered correct CHATGPT reasoning outputs to LLAMA2-7B for further fine-tuning.This strategy addresses the possibility that handcrafted reasoning paths differ from an LLM’s internal reasoning process.Source: §6 · p. 8
Preference Alignment
- Preference alignment uses DPO pairs formed by selecting preferred and dispreferred CHATGPT solutions according to answer correctness.The pairs are sampled from NLGIFT training sets, with around 200 DPO pairs for each task.Source: §6 · p. 8
Results
- Average performance drops 24% while average recovery rate increases 72%, and no improvement method achieves both high performance and high recovery rates.DPO achieves the highest recovery rate for synthetic patterns and the highest performance in two of four real-world tasks.Source: §6 · p. 8, Table 5 · p. 8
- DPO is preliminarily the most promising strategy, although improving graph reasoning generalization remains an open research question.The comparison covers synthetic structural and reasoning tasks together with four real-world tasks.Source: §6 · p. 8, Table 5 · p. 8
7 Related Work
Related work covers prompting, instruction tuning, graph encoders, multimodal methods, and LLM applications to graph-related tasks. This paper distinguishes itself by testing whether tuned graph reasoning transfers across patterns and to real-world tasks.
LLM Graph Learning and Reasoning
- Prior work finds preliminary graph reasoning abilities but brittleness to spurious correlations, while prompting and alternative graph encoders aim to improve performance.The cited approaches include prompt design, graph neural network encoders, instruction tuning, preference alignment, and visual modalities.Source: §7 · pp. 8–9
Real-world Graph Tasks
- Real-world graph applications use LLMs as embedding enhancers, direct predictors, or components aligned with graph neural networks.These categories cover node classification and tasks with implicit graph structures such as multi-hop knowledge QA.Source: §7 · p. 9
Position of This Work
- This work studies whether specialized instruction tuning produces transferable graph reasoning skills rather than merely memorized in-distribution patterns.The study focuses on generalization across graph reasoning patterns and implications for improving graph reasoning abilities.Source: §7 · p. 9
8 Conclusion
The paper introduces NLGIFT to evaluate graph reasoning generalization across semantic, numerical, structural, reasoning, and real-world patterns. Experiments find limited robustness beyond simple attribute changes, and post-training alignment is promising but insufficient.
Conclusion
- NLGIFT evaluates LLM graph reasoning generalization across semantic, numerical, structural, reasoning, and real-world patterns.The benchmark is presented as an evaluation suite for testing whether models move beyond memorized synthetic patterns.Source: §8 · p. 9
- LLMs are somewhat robust to semantic and numerical changes but struggle to generalize beyond synthetic reasoning patterns and benefit real-world network tasks.These findings motivate continued work beyond pattern memorization.Source: §8 · p. 9
Limitations
The study is limited by its model coverage, simulated distribution shifts, incomplete strategy effectiveness, and focus on classic graph algorithms.
Limitations
- Experiments cover only one blackbox model and LLaMA2-7B, with QLoRA and 4-bit quantization potentially affecting results.The authors leave evaluation of stronger, code-oriented, and other LLMs, as well as full-parameter fine-tuning, for future work.Source: Limitations · p. 9
- NLGIFT simulates distribution gaps by withholding one training distribution, while additional task mixtures address less clear-cut underrepresentation.This setup models blind spots in training data but does not cover every possible form of generalization gap.Source: Limitations · p. 9
- The three proposed improvement strategies are not effective in all scenarios, leaving transferable graph reasoning beyond pattern memorization unresolved.The paper identifies multimodal and neuro-symbolic approaches as possible future directions.Source: Limitations · pp. 9–10
- The study mainly evaluates classic graph and network algorithms, so its conclusions do not yet extend to tables, proofs, or code.The authors envision extending the generalization study to these other structured data types.Source: Limitations · p. 10
A Analysis (cont.)
Additional analyses show that generalization weaknesses persist across thresholds, prompting methods, and semantic or numerical shifts, while direct real-world tuning outperforms synthetic transfer.
A Analysis (cont.)
- Strong Recovery decreases as the PGR threshold λ increases, but no threshold eliminates the generalization gap between distributions.The analysis therefore treats the gap as not dependent on selecting a particular λ.Source: A Analysis (cont.) · p. 13
- Arithmetic errors account for less than half of errors; CHATGPT’s average arithmetic-error share is 2.7%, while floats and large integers are harder, especially for LLaMA2-7B.For LLaMA2-7B, error rates on floats and large integers increased by an average of 8% compared with small integers.Source: A Analysis (cont.) · p. 13
- Only 1 of 12 in-context-learning settings achieved Significant Transfer for CHATGPT, versus 5 of 12 with zero-shot prompting.Some in-context-learning results were worse than zero-shot results, reducing concern that prompting alone explains the weak reasoning transfer.Source: A Analysis (cont.) · p. 13, Table 6 · p. 13
- Qualitative semantic and numerical examples show that both models can answer correctly on one distribution but fail on another.These cases support the conclusion that graph reasoning abilities remain tied to task patterns rather than robustly transferring across them.Source: A Analysis (cont.) · pp. 13–14
- Direct instruction-tuning on in-distribution real-world data achieves the best performance across all evaluated real-world tasks.This comparison indicates a substantial gap between synthetic graph-pattern transfer and real-world graph reasoning.Source: Table 7 · p. 14, A Analysis (cont.) · p. 14
- Synthetic-to-real transfer remains weak: directly tuning on real-world problems greatly exceeds tuning on synthetic problems across varied settings.The authors conclude that using synthetic data to improve real-world graph reasoning remains an open research question.Source: A Analysis (cont.) · p. 14
B.1 Graph reasoning problems
- The benchmark covers connectivity, shortest path, topological sort, and maximum flow, each evaluated with task-specific correctness criteria.Shortest-path evaluation requires both the correct path and its length, whereas topological-sort evaluation checks node coverage and edge constraints.Source: §B.1 · p. 14
B.2 Real-world Datasets
- Real-world evaluation includes yes-or-no, multiple-choice, support-or-counter, and ordered-step tasks with deterministic or partial-credit scoring.Proscript receives partial credit from the fraction of satisfied ordering constraints.Source: §B.2 · p. 14
B.3 Dataset Statistics
NLGIFT contains 37,000 problems spanning semantic-pattern keywords and qualitative transfer analyses, with substantial computational requirements for LLaMA2-7B experiments.
B.3 Dataset Statistics
- NLGIFT contains 37,000 problems, including 4,000 real-world problems.The benchmark statistics describe how problem totals are distributed across pattern settings, tasks, mixtures, and test sets.Source: §B.3 · p. 15, Table 9 · p. 16
B.4 Keywords for Semantic Patterns
- Semantic patterns use five keywords per pattern: two describe edges and three represent nodes.The benchmark includes adjacency, incident, graph-expert, and friendship representations.Source: §B.4 · p. 15
B.5 Computational Resources
- LLaMA2-7B fine-tuning takes about 120 minutes for 500 examples over 10 epochs on one A4000 GPU, while inference takes 30–120 minutes.Inference time varies with instruction and response length, using four A4000 GPUs and 96 GB RAM for the reported setup.Source: §B.5 · p. 15
- Qualitative tables show generalization gaps for both semantic and numerical patterns, including failures even on connectivity.The captions describe these as out-of-distribution performance gaps rather than complete transfer.Source: Table 10 · p. 16, Table 11 · p. 17