Pith. sign in

REVIEW 3 major objections 14 references

When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression

T0 review · 3 major / 0 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Download PDF Read on arXiv ↗

Pith's one-line read Reasoning hallucinations in decoder-only Transformers arise from two training-time graph mechanisms: Path Reuse early and Path Compression late.

desk verdict Clean temporal story of Path Reuse then Path Compression on synthetic graphs; useful framing, but the causal claim for compression is still correlational. read the letter →

arxiv 2604.03557 v1 submitted 2026-04-04 cs.AI

Xinnan Dai , Kai Yang , Cheng Luo , Shenglai Zeng , Kai Guo , Jiliang Tang This is my paper
classification cs.AI
keywords reasoninghallucinationsdecoder-onlyTransformerspathreusecompressionunderlyinggraphintrinsicextrinsicnext-tokenprediction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that next-token prediction in decoder-only Transformers can be understood as search over an underlying directed graph of entities and relations. Contextual (intrinsic) reasoning is search on a sampled subgraph; context-free (extrinsic) reasoning uses memorized structure in the full graph. Under this view, two mechanisms produce reasoning hallucinations. Early in training, or with sparse data, the model reuses edges already learned from the underlying graph and ignores the given context (Path Reuse). Later, frequent multi-step paths are collapsed into shortcut edges, especially when high-out-degree nodes and community bridges are bypassed (Path Compression). Both emerge under ordinary next-token training on synthetic graphs and on language stories derived from them, and the same picture is used to reinterpret the reversal curse, degree-driven reasoning bias, and why some fine-tuning recoveries fail. The claim matters because it ties fluent but unsupported answers to concrete training dynamics rather than treating them as opaque output errors.

What carries the argument

Underlying reasoning graph (Definition 3.1): nodes are atomic entities or intermediate states; directed edges are valid transitions. Intrinsic reasoning is constrained search on a sampled subgraph; extrinsic reasoning is search on the memorized full graph. Path Reuse and Path Compression are the two failure modes of that search during training.

What would settle it

Train a decoder-only model from scratch on a fully enumerated path corpus from a known graph (or on language stories whose ground-truth graph is known), track exist/local/global accuracy and the uncompressed-path ratio over epochs, and check whether early errors systematically reuse underlying edges outside the given context and later errors systematically create non-edges that jump to high-out-degree or k-hop neighbors; if those patterns do not appear, or appear only under the synthetic setup and not under real language, the two-mechanism account fails.

Watch

Extended reading notes

Core claim

Reasoning hallucinations are not a single failure mode. They arise from Path Reuse in early or underfit training, when memorized underlying-graph edges override contextual constraints, and from Path Compression in later overfit training, when multi-hop paths collapse into k-hop shortcuts that favor high-out-degree nodes and skip community bridges. These two mechanisms jointly explain intrinsic and extrinsic reasoning failures under next-token prediction.

Load-bearing premise

The paper rests on the idea that knowledge learned from language can be treated as a directed entity graph with query-invariant edges, and that synthetic random graphs plus generated stories are faithful enough proxies for real pretraining.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 0 minor

Summary. The paper models next-token prediction in decoder-only Transformers as search over an underlying directed entity-relation graph (Defs. 3.1–3.2), distinguishing intrinsic reasoning (constrained search on a sampled subgraph) from extrinsic reasoning (memorized paths). It argues that reasoning hallucinations arise from two training-stage mechanisms: Path Reuse, in which early underfitting reuses memorized underlying edges that violate contextual constraints (§4; AccExist vs AccLocal gap), and Path Compression, in which later overfitting collapses multi-step paths into shortcut k-hop edges, preferentially toward high out-degree nodes (§5; accuracy rise-then-fall, hop-error bias, out-degree statistics). Supporting evidence includes controlled ER/SBM synthetic path corpora, architecture/depth ablations, an App. B mixture-of-random-walks sketch, language-story and DocRED extensions (§6.1, App. D), SFT vs PPO recovery (§6.2), and reinterpretations of the reversal curse and reasoning distribution bias (§6.3).

Significance. If the two-mechanism account holds, the paper offers a useful unified training-dynamics explanation of when intrinsic vs extrinsic reasoning hallucinations emerge, with concrete metrics (Exist/Global/Local Acc, Uncompressed Ratio R) and falsifiable structural predictions (community bridges, out-degree bias). Strengths include fully enumerated synthetic search spaces, multi-seed tabulated results (Table 3), architecture comparisons (LLaMA/Qwen/Mixtral), and an explicit (if simplified) analytical model in App. B. The finetuning recovery contrast and the link from synthetic graphs to language sequences are practically relevant for diagnosing unfaithful multi-step reasoning. Even if the causal story is only partially identified, the empirical phase structure (early global reuse, late shortcut formation) is a contribution that can guide evaluation and training design.

major comments (3)
  1. §5.1–5.2 and App. B (Assumption B.2, Props. B.3–B.4): The central Path Compression claim is that late-stage shortcut formation is a structural consequence of next-token prediction approximating a mixture of multi-step transitions. The reported patterns (Fig. 3a–d: accuracy degradation, rising 3-hop errors, rising normalized out-degree of predicted nodes) are clear and reproducible under the stated protocol, but they remain correlational. The design trains for many epochs on a fixed, fully enumerated multi-hop path corpus with no control that holds multi-hop co-occurrence / frequency statistics fixed while removing the incentive or opportunity to form non-edges (e.g., 1-hop-only supervision, path-shuffled co-occurrence matched baselines, or edge-existence constraints at train time). Without such an identification check, late degradation is also consistent with ordinary frequency overfitti
  2. Defs. 3.1–3.2 and §6.1 / App. D: The unified story treats an underlying directed graph with query-invariant relations as an adequate model of knowledge acquired from language, and treats ER/SBM path corpora plus Gemini-generated stories (and a small DocRED probe) as faithful proxies for real pretraining dynamics. The language-story and DocRED results are directionally consistent (early peak uncompressed ratio, later compression) but much smaller in scale and more observational than the synthetic path experiments. The manuscript should either (i) substantially strengthen the real-data evidence (larger models/corpora, explicit controls for entity frequency and narrative co-occurrence) or (ii) clearly scope the causal claims to synthetic graph search and present the language/DocRED sections as suggestive transfer rather than confirmation of the same mechanism in large-scale pretraining.
  3. §6.3 (Reversal Curse / Reasoning Distribution Bias): These subsections re-interpret known phenomena via path compression and degree bias without new controlled experiments under the paper’s own protocol. As discussion they are fine; as currently written they read as supporting applications of the main theory. Either add a minimal directed-cycle / degree-skew experiment that isolates the predicted asymmetry, or move these claims to a clearly labeled speculative discussion so they do not over-extend the empirically supported core.

Circularity Check

0 steps flagged · score 1.0 of 10

No load-bearing circularity: Path Reuse/Compression are empirical training-dynamics observations with independently defined metrics; App. B is a post-hoc explanatory sketch, not a forced derivation.

full rationale

The paper's central claims are observational: under next-token training on enumerated paths from ER/SBM graphs (and later language stories), early stages show AccExist high while AccLocal lags (Path Reuse), and later stages show accuracy degradation with rising k-hop and high-out-degree errors (Path Compression). Metrics (AccLocal/Exist/Global in App. A; Uncompressed Ratio R = predicted/ground-truth length) are defined from graph validity and path length, independent of the named mechanisms. App. B posits a mixture-of-transitions model (Assumption B.2) and derives sufficient conditions for shortcut preference (Props. B.3–B.4); this is an after-the-fact hypothesis that does not fit parameters to force the observed degradation, nor does it redefine the empirical quantities. No uniqueness theorems, self-citation chains, or fitted-input-as-prediction steps underwrite the main results. Minor author-related citations (e.g., Dai et al.) appear only in related work and are not load-bearing. The derivation chain is therefore self-contained empirical science plus optional modeling; circularity score remains near zero.

Assumptions & free parameters 3 free parameters · 4 assumptions · 3 invented entities

The central claim rests on modeling next-token prediction as search over a postulated underlying entity-relation graph, on the claim that synthetic ER/SBM graphs and story-converted paths are adequate proxies for language pretraining, and on the observational definitions of Path Reuse and Path Compression. Experimental free parameters (community counts, pin/pout, train ratios, depth) modulate severity but are not fitted to force the qualitative claim.

free parameters (3)
  • SBM community count / pin / pout
    Chosen by hand to control community structure and thereby the severity of path compression; different settings produce different accuracy-drop magnitudes.
  • train-sample fraction / train ratio
    Explicitly varied (e.g., 0.1 %, 20 %, 50 %) to induce underfitting versus overfitting regimes that define Path Reuse and Path Compression.
  • model depth (6–24 layers) and architecture family
    Varied to test robustness of compression; shallower models show less compression, but the qualitative claim is independent of any single depth.
assumptions (4)
  • domain assumption Knowledge expressed in language is organized as an underlying directed graph of entities (nodes) and invariant relations (edges).
    Stated in §3 / Def. 3.1 and used as the foundation for both intrinsic and extrinsic reasoning throughout the paper.
  • domain assumption Next-token prediction in a decoder-only Transformer implements (approximate) path search / multi-step transition on that graph.
    Core modeling premise introduced in the introduction and formalized in §3; inherited from prior synthetic-graph work but treated as given.
  • domain assumption A context edge-list samples a subgraph that should constrain search (intrinsic); a bare source-target query relies on memorized structure (extrinsic).
    Definitions in §3.1 that partition the two hallucination regimes.
  • ad hoc to paper Learned transition probabilities approximate a convex combination of multi-step random-walk matrices (mixture model).
    Assumption B.2 in App. B used to derive the shortcut-hallucination condition; not independently verified.
invented entities (3)
  • Path Reuse
    purpose: Name the early-training failure mode in which memorized global edges override contextual subgraph constraints.
    Defined observationally from the gap between Exist/Global Acc and Local Acc in §4; no independent external measurement protocol beyond the paper’s metrics.
  • Path Compression
    purpose: Name the late-training failure mode in which multi-hop paths collapse into non-existent shortcut edges, preferentially to high-out-degree nodes.
    Defined from accuracy drop, k-hop error bias, and rising normalized out-degree of predicted nodes in §5; again internal to the experimental metrics.
  • Uncompressed Ratio R
    purpose: Quantify how much of the ground-truth path length is preserved in model predictions.
    R = predicted path length / ground-truth path length; introduced in §5.2 as a diagnostic, not an externally validated quantity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression." pith.science (2026). https://pith.science/paper/2604.03557

@misc{pith2026260403557,
  author       = {Pith},
  title        = {Pith review of: When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2604.03557}},
  note         = {Machine review of arXiv:2604.03557}
}
read the original abstract

Reasoning hallucinations in large language models (LLMs) often appear as fluent yet unsupported conclusions that violate either the given context or underlying factual knowledge. Although such failures are widely observed, the mechanisms by which decoder-only Transformers produce them remain poorly understood. We model next-token prediction as a graph search process over an underlying graph, where entities correspond to nodes and learned transitions form edges. From this perspective, contextual reasoning is a constrained search over a sampled subgraph (intrinsic reasoning), while context-free queries rely on memorized structures in the underlying graph (extrinsic reasoning). We show that reasoning hallucinations arise from two fundamental mechanisms: \textbf{Path Reuse}, where memorized knowledge overrides contextual constraints during early training, and \textbf{Path Compression}, where frequently traversed multi-step paths collapse into shortcut edges in later training. Together, these mechanisms provide a unified explanation for reasoning hallucinations in LLMs and connected to well-known behaviors observed in downstream applications.

Figures

Figures reproduced from arXiv: 2604.03557 by the authors.

Figure 1
Figure 1. Reasoning Hallucinations from Underlying Graph Struc￾tures. (a) Building up the underlying graph for the implicit knowl￾edge structure (b) In intrinsic reasoning, the model reuses common paths and hallucinates a direct relation (John → Scott) instead of the correct reasoning provided in context (John → Kim → Scott). (c) In extrinsic reasoning, long reasoning chains (David → John → Kim → Scott) are compressed into sh… view at source ↗
Figure 2
Figure 2. Training evolution in conditional reasoning. (a) Accuracy trajectories under a 20% training set. The persistent gap between global and local accuracy indicates the emergence of hallucinations. (b) Accuracy trajectories under a 0.1% training set. Hallucinations persist and cannot be resolved by simply increasing the number of training steps. The zoomed-out view further shows that, at later stages of training, the Exi… view at source ↗
Figure 3
Figure 3. Path Compression. (a) Accuracy degradation during training across graph settings. (b) Errors are biased toward k-hop neighbors. (c) Path-compression hallucinations via implicit k-hop edge creation. (d) Accumulation of high–out-degree nodes in erroneous predictions. We generate the underlying graphs using the Stochastic Block Model (SBM), with 1,000 nodes and varying num￾bers of communities, as well as different intr… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Error Understanding. (a) Prediction errors decrease as the out-degree of the start nodes increases. (b) Path compression reveals a tendency to bypass bridge nodes, directly jumping across communities. Further, we analyze the behavior of the model when its accuracy begi…
Figure 6
Figure 6. Figure 6: Example of change a reasoning path from underlying graph to a story. corporates a mixture-of-experts design). While the overall trends are consistent across architectures, subtle differences emerge in their training dynamics. Specifically, Mixtral achieves its highest …
Figure 8
Figure 8. Figure 8: Accuracy improvement (∆ACC) during finetuning with SFT and PPO. The original Acc are 0.8527, 0.753, 0.6787 at epoch [1][3][6]. (a) SFT finetuning shows unstable recovery behavior, es￾pecially at later pretraining stages. (b) PPO finetuning consistently achieves higher …
Figure 9
Figure 9. Figure 9: Path compression in knowledge graph data. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_9.png]
Figure 10
Figure 10. Figure 10: Underlying graphs with 0.01 pout [PITH_FULL_IMAGE:figures/full_fig_p015_10.png]
Figure 11
Figure 11. Figure 11: Underlying graphs with 0.02 pout [PITH_FULL_IMAGE:figures/full_fig_p015_11.png]
Figure 12
Figure 12. Figure 12: Underlying graphs with 0.03 pout 15 [PITH_FULL_IMAGE:figures/full_fig_p015_12.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

14 extracted references · 7 linked inside Pith

  1. [1]

    Hallulens: Llm hal- lucination benchmark.arXiv preprint arXiv:2504.17550,

    Bang, Y ., Ji, Z., Schelten, A., Hartshorn, A., Fowler, T., Zhang, C., Cancedda, N., and Fung, P. Hallulens: Llm hal- lucination benchmark.arXiv preprint arXiv:2504.17550,

    arXiv

  2. [2]

    Theoretical lim- itations of multi-layer transformer.arXiv preprint arXiv:2412.02975,

    Chen, L., Peng, B., and Wu, H. Theoretical lim- itations of multi-layer transformer.arXiv preprint arXiv:2412.02975,

    arXiv

  3. [3]

    T., Nachum, O., Vempala, S

    Kalai, A. T., Nachum, O., Vempala, S. S., and Zhang, E. Why language models hallucinate.arXiv preprint arXiv:2509.04664,

    arXiv

  4. [4]

    Understanding the effects of rlhf on llm generalisation and diversity

    Kirk, R., Mediratta, I., Nalmpantis, C., Luketina, J., Ham- bro, E., Grefenstette, E., and Raileanu, R. Understanding the effects of rlhf on llm generalisation and diversity. arXiv preprint arXiv:2310.06452,

    arXiv

  5. [5]

    Agenthallu: Benchmarking automated hallucination attribution of llm- based agents.arXiv preprint arXiv:2601.06818,

    Liu, X., Yang, X., Li, Z., Li, P., and He, R. Agenthallu: Benchmarking automated hallucination attribution of llm- based agents.arXiv preprint arXiv:2601.06818,

    arXiv

  6. [6]

    M., Alghisi, S., and Riccardi, G

    Mousavi, S. M., Alghisi, S., and Riccardi, G. What does loss optimization actually teach, if anything? knowledge dynamics in continual pre-training of llms.arXiv preprint arXiv:2601.03858,

    arXiv

  7. [7]

    Progress measures for grokking via mechanistic interpretability.arXiv preprint arXiv:2301.05217,

    Nanda, N., Chan, L., Lieberum, T., Smith, J., and Stein- hardt, J. Progress measures for grokking via mechanistic interpretability.arXiv preprint arXiv:2301.05217,

    arXiv

  8. [8]

    Llms know more than they show: On the intrinsic representation of llm halluci- nations

    Orgad, H., Toker, M., Gekhman, Z., Reichart, R., Szpektor, I., Kotek, H., and Belinkov, Y . Llms know more than they show: On the intrinsic representation of llm halluci- nations. InThe Thirteenth International Conference on Learning Representations. Power, A., Burda, Y ., Edwards, H., Babuschkin, I., and Misra, V . Grokking: Generalization beyond overfit...

    arXiv

Show all 14 references
  1. [9]

    Rawte, V ., Chakraborty, S., Pathak, A., Sarkar, A., Tonmoy, S. T. I., Chadha, A., Sheth, A., and Das, A. The troubling emergence of hallucination in large language models- an extensive definition, quantification, and prescriptive remediations. InProceedings of the 2023 Confer...

    2023

  2. [10]

    Benefits and pitfalls of reinforce- ment learning for language model planning: a theoretical perspective.arXiv preprint arXiv:2509.22613,

    Wang, S., Shen, Y ., Sun, H., Feng, S., Teng, S.-H., Dong, L., Hao, Y ., and Chen, W. Benefits and pitfalls of reinforce- ment learning for language model planning: a theoretical perspective.arXiv preprint arXiv:2509.22613,

  3. [11]

    Emergent abilities of large language models

    Wei, J., Tay, Y ., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Met- zler, D., et al. Emergent abilities of large language models. arXiv preprint arXiv:2206.07682,

    arXiv

  4. [12]

    The best instruction-tuning data are those that fit.arXiv preprint arXiv:2502.04194, 2025a

    Zhang, D., Dai, Q., and Peng, H. The best instruction-tuning data are those that fit.arXiv preprint arXiv:2502.04194, 2025a. Zhang, Y ., Li, Y ., Cui, L., Cai, D., Liu, L., Fu, T., Huang, X., Zhao, E., Zhang, Y ., Chen, Y ., et al. Siren’s song in the ai ocean: A survey on hal...

    2024

  5. [13]

    Evaluation Metrics Notation.LetG= (V, E)denote the backbone graph with|V|=N

    10 When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression A. Evaluation Metrics Notation.LetG= (V, E)denote the backbone graph with|V|=N. Each conditional reasoning query is defined as q= (s, t,C),(1) where s, t∈V are the source a...

  6. [14]

    D. Real-World Connections Our assumption is that LLMs will set up the inner knowledge graph while learning the data from language sequences; therefore, we take the DocReD dataset (Yao et al., 2019), which has both documents and a manually extracted knowledge graph. We train a ...

    2019

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.