Lost in Serialization: Invariance and Generalization of LLM Graph Reasoners

The paper presents a systematic analysis of the invariance and generalization capabilities of Large Language Model (LLM) graph reasoners, revealing that these models exhibit sensitivity to graph serialization variations such as node reindexing and edge reordering. A novel decomposition of graph representations is introduced, alongside a comprehensive benchmarking suite and new spectral tasks to evaluate model robustness. Findings indicate that while larger non-fine-tuned models demonstrate greater robustness, fine-tuning can reduce sensitivity to node relabeling but may increase sensitivity to structural variations, highlighting the complexities of training LLMs for graph reasoning tasks.