Skip to content

Back to the catalog

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

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

This paper proves that the Wasserstein distance between Laplacian spectra of original and LLM-reconstructed graphs is bracketed by two edge-count quantities, the net change in edge number and the symmetric difference, each scaled by 2/n, showing when these bounds coincide (pure addition or pure deletion of edges) and when they diverge (mixed editing, i.e. both inventing and losing edges). Using this theory, the authors analyze 135 graph reconstructions produced by three open-weight LLMs over 45 synthetic graphs, finding 77 one-sided outputs and 29 mixed outputs with a positive residual, revealing that aggregate distortion metrics mask qualitatively different editing policies across models, from copying the input to hallucination-heavy completion.

TL;DR Sharp spectral bounds show a single aggregate graph-reconstruction distance hides whether an LLM only adds/deletes edges or does both, exposing distinct editing policies across three open-weight models.
Open original ↗
Document

What it claims

An aggregate Laplacian-spectral distance (EMD, the 1-Wasserstein distance between eigenvalue distributions) can be split using four scalars you probably already log: EMD, edge-count ratio (ECR = |E′|/|E|), |E| and n. From these you get a trace excess

X = EMD − (2|E|/n)·|1 − ECR| ≥ 0

and a guarantee that min(added, deleted) ≥ nX/4. So X > 0 proves the model both hallucinated and dropped edges, without looking at which edges changed. The ¼ constant cannot be improved: a star-graph example attains it.

The paper also gives a closed form for the "model just echoed the prompt" case. If the output equals the prompted sublist of size ⌊ρ|E|⌋, then EMD = (2/n)·⌈(1−ρ)|E|⌉ ≈ (1−ρ)·average degree. That value is independent of the model and of which edges were withheld. Per-family EMD averages can therefore mostly reflect benchmark density rather than model quality.

How it works

  • Lower bound. Trace L = 2|E|, so the sum of |λ′ᵢ − λᵢ| is at least the net trace change.
  • Upper bound. Mirsky's trace-norm inequality plus ‖bₑbₑᵀ‖* = 2 gives at most 2|E△E′|/n.
  • Signs of the eigenvalue shifts. nX = 2·min(S⁺, S⁻), where S⁺ and S⁻ are the total positive and negative eigenvalue shifts. X > 0 holds exactly when the sorted spectra cross.
  • Cheaper connectivity test. Use ACR = λ′₂/λ₂. If ECR ≥ 1 and ACR < 1, or ECR ≤ 1 and ACR > 1, the edit is mixed. ACR = 0 holds exactly when the reconstruction is disconnected.
flowchart TD
  A[EMD, ECR, abs E, n] --> B[Compute X]
  B -->|X > 0| C[Certified mixed: invented and lost edges]
  B -->|X = 0| D[One-sided OR dominant mixed]
  D --> E[Indistinguishable from scalars; need edge sets]

Evidence

Benchmark. 45 synthetic graphs: 5 instances in each of 3 families × 3 sizes.

  • Stochastic block model with p_in = 0.7, p_out = 0.05, c = 3/4/5 blocks, n = 15/28/50.
  • Preferential attachment with m = 2, n = 15/30/50.
  • Rectangular lattices with n in the ranges 14–18, 27–32 and 45–50.

Task. Each model saw a shuffled 75% of the edges (ρ = 0.75, fixed seed, so every model got the same withheld set), plus n, density and average degree. It was asked to return the full edge list.

Models. Llama 3.1 8B, Mistral 7B and Qwen 2.5 7B, all run via Ollama at temperature 0 on a single Apple M4. That gives 135 outputs.

Results.

  • The bounds held on all 135 outputs.
  • 77 outputs were one-sided and 29 were certified mixed (X > 0). The paper says the three classes partition all outputs, which leaves 29 dominant-mixed.
  • Two outputs kept the edge count exactly (ECR = 1) while adding and deleting 19 and 15 edges respectively, which no single scalar reveals. Figure 1 shows the 19-edge case on an SBM graph with n = 28.
  • The parser discarded 174 (Llama), 334 (Mistral) and 1 (Qwen) candidate pairs. All but 7 were duplicates, so the hallucination counts reflect model output rather than parsing.

Model differences. The paper says the models range from returning the prompt verbatim to aggressive completion with large hallucination volume. The fetched text cuts off before the per-model breakdown, so which model does which is not shown here.

How to use it

If you already report spectral EMD for graph reconstruction, add X and the (ECR, ACR) sign test. Both are free to compute from existing logs.

Treat EMD on one-sided outputs as nothing more than a rescaled edge count. The authors keep raw responses and parsed edge lists so metrics can be recomputed. No code release, URL or licence appears in the fetched text.

Limits

The certificate only works in one direction.

  • A mixed edit can still show X = 0 (Example 9: n = 4, five edges added and one deleted, pointwise dominance).
  • An isospectral edit gives EMD = 0, X = 0, ECR = 1 and ACR = 1 despite two changed edges (Example 10, two P₄ paths).

The bound is conservative when edits overlap. It is loose whenever added and deleted edges share vertices, because the upper bound is attainable only when they don't. It lower-bounds the smaller edit side and does not recover its true size.

Narrow experimental setting.

  • Synthetic graphs only, with n ≤ 50.
  • A single keep ratio (0.75).
  • Three ~7–8B models at temperature 0.
  • Two disconnected SBM draws were redrawn.

Specific to this setup. The results apply to the combinatorial Laplacian on a fixed common vertex set, not to normalized-Laplacian spectral distances.

Truncated page. The text ends at the Measurement section, so the full per-model results were not available to this summary.

Techniques named here

  • Wasserstein distance between Laplacian spectra
  • Mixed-editing certificate

Related in research