# Lost in Serialization: Invariance and Generalization of LLM Graph Reasoners

arXiv: https://arxiv.org/abs/2511.10234 · HTML: https://mlsanity.com/paper/2511.10234/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 12 of its 43 references that are in the map.
- First posted on arXiv 13 Nov 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 12 of 12)

- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [One for All: Towards Training One Graph Model for All Classification Tasks](https://mlsanity.com/paper/2310.00149/) (2023)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [GraphText: Graph Reasoning in Text Space](https://mlsanity.com/paper/2310.01089/) (2023)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [Performance Metrics (Error Measures) in Machine Learning Regression, Forecasting and Prognostics: Properties and Typology](https://mlsanity.com/paper/1809.03006/) (2018)
- [G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning](https://mlsanity.com/paper/2505.18499/) (2025)
- [GL-Fusion: Rethinking the Combination of Graph Neural Network and Large Language model](https://mlsanity.com/paper/2412.06849/) (2024)
- [GraphSOS: Graph Sampling and Order Selection to Help LLMs Understand Graphs Better](https://mlsanity.com/paper/2501.14427/) (2025)

## Built on by (most cited first, 6 of 6)

- [Detecting Differences Is Not Understanding Structure: Large Language Models Fail at Graph Isomorphism](https://mlsanity.com/paper/2606.09484/) (2026)
- [The Illusion of Replacement: Rethinking Specialized Machine Learning Models in the Foundation Model Era](https://mlsanity.com/paper/2608.28980/) (2026)
- [When Vision Meets Graphs: A Survey on Graph Reasoning and Learning](https://mlsanity.com/paper/2609.03816/) (2026)
- [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026)
- [PetriBench: Benchmarking LLM Reasoning over Dynamic State Spaces](https://mlsanity.com/paper/2609.19883/) (2026)
- [The Communication Bottleneck: A Round-Trip Study of Tree-Structured Expression Serialization in Language Models](https://mlsanity.com/paper/2609.21509/) (2026)

## Abstract (arXiv)

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.