A Spectral Theory of Distortion in LLM Graph Reconstruction: Sharp Bounds and Empirical Characterization
Why a single distortion score hides what language models get wrong about graphs
When language models reconstruct graphs, researchers usually report one summary number measuring how wrong the reconstruction is. This paper proves that number conceals crucial details: two mathematical bounds reveal whether the model only added edges, only deleted them, or did both—and when it does both, that signals the model hallucinated connections while also losing real ones. Testing three AI models on 45 graphs, the researchers found that 29 reconstructions invented and deleted edges simultaneously, even in cases where the total edge count stayed the same.
Aggregate distortion scores mask whether a language model's errors come from conservative editing or aggressive hallucination mixed with forgetting. This matters because a model that adds fake edges while dropping real ones behaves very differently from one that just copies the input, yet a single summary number treats them the same. The new bounds let researchers diagnose a model's reconstruction strategy from standard metrics alone—critical information for deciding whether the output is trustworthy.