Lost in Serialization: Invariance and Generalization of LLM Graph Reasoners

AI summary

Overview

• Research area: Machine learning — specifically graph reasoning with Large Language Models (LLMs), and the robustness/invariance of such models to how graphs are written out as text.
• Technical level: Intermediate. Readers should be comfortable with concepts such as graphs, node permutations, Graph Neural Networks, and LLM fine-tuning. The paper's framing and conclusions are readable without deep mathematics.
• Scope in one sentence: The paper systematically measures how sensitive LLM graph reasoners are to node relabelings, different graph data structures and edge orderings, and different textual formats, and whether fine-tuning helps or hurts generalization on new spectral tasks.

What This Paper Is About

Graph Neural Networks are built to be invariant to node relabeling — the same graph in a different order gives the same answer — but LLMs read graphs as token sequences, and different orderings or formats produce different input strings. The paper asks what is actually learned when LLMs are post-trained as graph reasoners: do they become invariant to these representational choices, or do they simply specialize to the specific serialization seen in training data? It also tests whether such fine-tuned reasoners generalize to a new class of spectral graph tasks not represented in their training corpora.

Key Contributions

1. A principled decomposition of graph serializations into three factors: node labeling (how nodes are indexed), computational structure (the data structure plus the internal edge-ordering rule), and syntax (purely textual style such as JSON, NetworkX, or PyG formatting).
2. A large-scale robustness evaluation on the Erdős benchmark (Guo et al., 2025), covering 49 topological tasks over 100 graphs each (4,900 samples, excluding isomorphic_mapping) and totaling over 1.5M individual model inferences. Models compared: non-fine-tuned Qwen (3B, 7B), fine-tuned G1 (3B, 7B), and non-fine-tuned gpt-oss (20B, 120B).
3. A new spectral benchmark of 12 spectral graph-theoretic tasks on 100 graphs from the Erdős test set, grouped into Easy, Medium, and Hard, to probe generalization beyond purely combinatorial tasks.
4. An empirical finding that post-training trades one kind of sensitivity for another — reducing relabeling sensitivity but increasing sensitivity to computational structure and syntax — and an argument that fixed-format accuracy is an insufficient measure of progress.

Main Findings

• Larger non-fine-tuned models are most robust. Across the analyses, the gpt-oss models showed the steadiest behavior. Under syntax changes, gpt-oss-120B was reported as robust: barring PyG, all encodings worked equally well (88% accuracy all), while gpt-oss-20B performed best with JSON and NetworkX. gpt-oss also had the lowest cross-encoding variability (5.41% for -20B, 3.45% for -120B), versus Qwen (5.98% for -3B, 5.86% for -7B) and G1 (9.69% for -3B, 10.51% for -7B).

• Accuracy drops under node relabeling are more pronounced for G1 than for Qwen. Relabeling sensitivity was measured over N=10 random node labelings, with edges lexicographically sorted afterwards to factor out edge shuffling. The authors attribute much of this to positional regularities: for example, in bipartite_maximum_matching the ground-truth solution in Erdős always induces a contiguous bipartition ({1, ..., x}, {x+1, ..., n}), which fine-tuning could internalize, so performance drops once relabeling destroys contiguity.

• Output variability under relabeling is higher for Qwen, and correlates with task performance. Using the normalized output span averaged over numerical tasks, Qwen models generally showed higher sensitivity, typically correlating with their accuracy. The implication is that fine-tuning makes graph reasoners more "invariant" mainly by improving reasoning performance rather than by producing genuine functional invariance. One exception: in the "Challenging" category, fine-tuning lowered output variability even without a meaningful accuracy increase.

• Changes in computational structure cause persistent performance gaps. Sorted edge-lists stayed close to the Erdős baseline; adjacency-lists introduced shifts on some tasks; adjacency-matrix encodings often incurred sizable losses, hypothesized to stem from misalignment with counting tasks and description length inflated to O(n²). The largest drops occurred on edge_number and density. G1 was the most brittle, Qwen sometimes improved, and gpt-oss remained fairly steady.

• Locality in the serialization matters. Sorted edge-lists group each node's neighbors contiguously; shuffled edge-lists break this locality and force a full scan or an internal reordering. G1 was most brittle under shuffling, with the largest drops on edge-lists. Adjacency-lists preserve locality under all their symmetries and were hit comparatively mildly by shuffling. Replicating undirected edges to enforce full symmetric locality again hit G1 hardest, with edge-counting tasks most affected.

• LLMs are not format-invariant, and specialized reasoners excel mainly on formats seen in post-training. Erdős remained on average the highest-performing encoding for both G1 models (G1-7B best in 28/49 tasks). Qwen-7B preferred JSON (34% accuracy, best in 24/49 tasks). PyG was generally underwhelming.

• On spectral tasks, there is no consistent winner. G1-7B outperformed Qwen on only 7/12 tasks. Reported average sMAPE (lower is better, scale 0–100) by difficulty: Qwen2.5-3B 35.01 / 53.89 / 56.60; Qwen2.5-7B 19.73 / 50.05 / 51.31; G1-3B 30.33 / 55.74 / 59.14; G1-7B 20.80 / 49.58 / 39.95. G1-7B beat the mean baseline in 50% of tasks, with gains still limited (RelMAE in [0.6, 0.9]), and on harder problems such as eigenvector_centrality and heat_trace it was still not better than the mean baseline (RelMAE above 1.0).

• Reasoning style degrades with complexity. Manual inspection of 10% of G1-7B's generated answers showed it begins with analytical derivations (computing degrees, normalized adjacency matrices) but reverts to heuristics as complexity increases — known properties, assumed intermediate values, and structure-based approximations.

• Accuracy gains from larger models come at a latency cost. On a single H100 80GB, measured latency was 0.531 s for Qwen-3B, 0.919 s for Qwen-7B, 0.765 s for G1-3B, 1.207 s for G1-7B, 5.457 s for gpt-oss-20B, and 31.740 s for gpt-oss-120B (falling to 7.103 s on two H100s).

Methodology in Plain English

The authors take the same underlying graphs and re-write them in many systematically different ways, then check whether the models' answers change. Three knobs are turned:

1. Node labeling — nodes are randomly reindexed (10 random labelings per graph), which should not matter for a graph-level answer.
2. Computational structure — the graph is written as an edge-list, adjacency-list, or adjacency-matrix, each in a canonically sorted and a shuffled variant, plus a variant that lists every undirected edge in both directions.
3. Syntax — the same edge-list content is re-formatted as JSON, NetworkX-style code, or PyG-style code.

For every combination, they run non-fine-tuned models (Qwen 3B/7B, gpt-oss 20B/120B) and fine-tuned G1 models (3B/7B) on Erdős tasks at temperature 0 for deterministic comparison, and record accuracy differences, output variability, and per-task standard deviations. They then add 12 spectral tasks — quantities such as graph energy, algebraic connectivity, the Estrada index, spectral radius, and von Neumann entropy — and score them with sMAPE and RelMAE, where a RelMAE below 1.0 means the model beats the mean baseline. Finally, they manually classify a sample of generated answers as analytical, heuristic, or incomplete. All models were served with vLLM on NVIDIA H100 80GB accelerators, with gpt-oss-120B run on two H100s with tensor parallelism.

Why This Matters

• Impact on research: The paper argues that fixed-format accuracy is a misleading yardstick for LLM graph reasoning. If a model's score swings with node ordering, edge ordering, or formatting, benchmark numbers may reflect memorized idiosyncrasies of a dataset rather than structural reasoning. This motivates invariance-aware post-training and benchmark design, in the same spirit as permutation invariance in Graph Neural Networks.
• Real-world applications:
  • Knowledge discovery and network analysis, where the same underlying graph may be serialized differently by different tools or pipelines.
  • Scientific computation on graphs, where spectral quantities are used to analyze robustness and diffusion in real-world networks.
  • Any deployment pipeline that stores graphs in JSON but feeds models a different format than the one they were fine-tuned on.
  • Error-sensitive domains where a silent drop in accuracy caused by a harmless-looking reformatting could go unnoticed.
• Industry relevance: Teams that fine-tune small open-weight models for graph tasks as a cheaper alternative to large models should note that specialization appears to increase brittleness to format, ordering, and structure changes. Serving costs are also quantified: the more robust large models are much slower, and multi-GPU deployment only partly offsets this.

Future Directions

1. Invariance-aware post-training. Design fine-tuning objectives or data curation that teach permutation and format invariance rather than dataset-specific serialization regularities.
2. Better benchmark design. Move evaluation beyond a single fixed format, incorporating equivalence-preserving graph transformations into standard graph reasoning benchmarks.
3. Broader model and tuning coverage. The authors' limitations section notes the study could cover more LLM models and other previously proposed tuning strategies.
4. Real-world property prediction. Extend the same sensitivity analyses from synthetic benchmark tasks to real-world node- and graph-property prediction tasks.

Target Audience

Researchers and practitioners working at the intersection of LLMs and graph-structured data, including those building or evaluating graph reasoners, benchmark designers, and ML engineers deciding between fine-tuning small models versus serving large general-purpose ones. It is also relevant to readers interested in the broader question of what LLMs learn from post-training on structured, serialized inputs.

Authors’ abstract

While promising, graph reasoners based on Large Language Models (LLMs) lack built-in invariance to symmetries in graph representations. Operating on sequential graph serializations, LLMs can produce different outputs under node reindexing, edge reordering, or formatting changes, raising robustness concerns. We systematically analyze these effects, studying how fine-tuning impacts encoding sensitivity as well generalization on unseen tasks. We propose a principled decomposition of graph serializations into node labeling, edge encoding, and syntax, and evaluate LLM robustness to variations of each of these factors on a comprehensive benchmarking suite. We also contribute a novel set of spectral tasks to further assess generalization abilities of fine-tuned reasoners. Results show that larger (non-fine-tuned) models are more robust. Fine-tuning reduces sensitivity to node relabeling but may increase it to variations in structure and format, while it does not consistently improve performance on unseen tasks.