Lost in Serialization: Invariance and Generalization of LLM Graph Reasoners

Daniel Herbst, Lea Karbevska, Divyanshu Kumar, Akanksha Ahuja, Fatemeh Gholamzadeh Nasrabadi, Fabrizio FrascaarXiv 2025 · DOI · arXiv

Abstract

Large Language Models (LLMs) are increasingly utilized for graph reasoning, yet they lack the "permutation invariance" fundamental to Graph Neural Networks (GNNs). Because LLMs process graphs as linear text sequences (serializations), their performance is highly contingent on arbitrary choices such as node naming, edge ordering, and file syntax. This paper introduces a framework to evaluate these sensitivities across three axes of variation. The findings suggest that while fine-tuning enhances task-specific accuracy, it often renders models more brittle to formatting changes and fails to facilitate generalization to fundamentally different graph-theoretic domains, such as spectral analysis.

Introduction

In graph theory, a graph is defined by its topology, independent of how its components are labeled or the order in which its edges are listed. GNNs are architecturally designed to respect this "permutation invariance." In contrast, LLMs are sequence-to-sequence models that require graphs to be flattened into text. This "serialization" process introduces artificial order and naming conventions that do not exist in the underlying mathematical object.

This research investigates the extent to which LLMs are "lost in serialization." Specifically, it examines whether models can maintain consistent reasoning when the textual representation of a graph changes, and whether fine-tuning on combinatorial tasks (like shortest path) enables models to generalize to more complex mathematical properties.

Methodology: Decomposing Serialization

The authors propose a principled framework to analyze graph serialization by decomposing it into three primary axes of variation:

  1. Node Labeling: The specific identifiers used for nodes (e.g., integers, letters, or random strings).
  2. Edge Encoding: The structural format (e.g., edge lists, adjacency lists, or matrices) and the internal sequence of these elements (sorted vs. shuffled).
  3. Syntax: The high-level textual "style," ranging from structured formats like JSON to programming code using libraries like NetworkX or PyTorch Geometric (PyG).
The three axes of variation in graph serialization: Node labeling, Edge encoding, and Syntax.

The study evaluated a range of models, including the Qwen base models, G1 (a graph-specialized model fine-tuned from Qwen), and gpt-oss (large-scale open-weight models up to 120B parameters). Performance was measured using the Erdős Benchmark, comprising 49 topological tasks, and a newly introduced Spectral Tasks benchmark designed to test mathematical generalization.

The "Brittle Specialist" Phenomenon

A key finding of the study is the trade-off between specialization and robustness. Fine-tuned models like G1 demonstrate high accuracy on specific tasks but exhibit increased sensitivity to formatting—a phenomenon termed the "Brittle Specialist" effect. While fine-tuning helps models ignore arbitrary node names, it often causes them to overfit to the specific edge ordering or syntax encountered during training.

Comparison of output dispersion and accuracy across different model scales and task difficulties.

As shown in the results, larger models (e.g., gpt-oss-120B) tend to exhibit greater "functional invariance." Their scale allows them to handle diverse serializations more robustly than smaller, specialized models. Conversely, shuffling edge lists—which forces the model to search its entire context window rather than following a linear adjacency list—leads to significant performance degradation in fine-tuned models.

Key Insights

  • Algorithmic Difficulty: The serialization format dictates the LLM's "computational path." For instance, the PyG format, which separates source and target nodes into distant lists, requires complex mental "offsetting" that often leads to errors.
  • Positional Spillage: Models often learn heuristics based on node order. When nodes are relabeled, these "shortcuts" fail, revealing that the model hasn't truly learned the underlying graph logic.
  • Failure of Spectral Generalization: Fine-tuning on combinatorial tasks (e.g., connectivity) provides no benefit for spectral tasks (e.g., calculating eigenvalues). Models frequently resort to "assumptive heuristics," guessing common values rather than performing analytical derivations.

Conclusion

The sensitivity of LLMs to graph serialization highlights a fundamental gap between sequence-based processing and structural reasoning. To move beyond "brittle specialization," future research should focus on invariance-aware training. Rather than simply increasing data volume, training objectives should explicitly teach models that diverse textual serializations represent the same invariant graph structure.

Summary updated

BibTeX
@misc{herbst2025lost,
  author = {Daniel Herbst and Lea Karbevska and Divyanshu Kumar and Akanksha Ahuja and Fatemeh Gholamzadeh Nasrabadi and Fabrizio Frasca},
  title = {{Lost in Serialization: Invariance and Generalization of LLM Graph Reasoners}},
  year = {2025},
  eprint = {2511.10234},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.10234},
}
Figure