Lost in Serialization: Invariance and Generalization of LLM Graph Reasoners
This addresses robustness concerns for researchers and practitioners using LLMs in graph reasoning, though it is incremental as it analyzes existing issues without proposing a new solution.
The paper tackles the problem of LLM-based graph reasoners lacking invariance to graph representation symmetries, finding that larger models are more robust and fine-tuning reduces sensitivity to node relabeling but may increase it to other variations without consistently improving generalization on unseen tasks.
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.