A Spectral Theory of Distortion in LLM Graph Reconstruction: Sharp Bounds and Empirical Characterization

TL;DR

The paper establishes tight mathematical bounds on Wasserstein distance between Laplacian spectra in LLM graph reconstructions using edge count changes. It shows that spectral distortion reveals whether edits are one-sided (additions or deletions only) or mixed (both additions and deletions), even when total edge count remains unchanged. Empirical analysis of 135 reconstructions identifies distinct editing behaviors across models.

Why It Matters

Current evaluation methods for LLM graph reconstruction rely on aggregate metrics that obscure the nature of model edits. This work reveals hidden editing patterns—such as simultaneous hallucination and deletion—that standard metrics fail to detect, enabling more nuanced model comparison and debugging.

Key Findings

• The Wasserstein distance between Laplacian spectra is bounded above and below by scaled edge count differences, with equality holding only for one-sided edits.
• A positive residual between the upper and lower bounds indicates mixed editing behavior, detectable even without access to raw graph data.
• Three open-weight models exhibit distinct editing policies: one copies input, another attempts completion with high hallucination, and a third balances both, a distinction invisible to aggregate distortion measures.