REVIEW 3 major objections 7 minor 20 references
Spectral Journey: How Transformers Predict the Shortest Path
T0 review · 3 major / 7 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Two-layer decoder-only transformers can learn shortest paths on small graphs, and the paper identifies the learned computation as a greedy spectral navigation over the line graph's spectral embedding.
desk verdict Solid training and embedding evidence, but SLN's reported 99.32% needs a fixed k or principled k-selection before it supports the 'model implements SLN' claim. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing machinery is the spectral embedding of the line graph $\mathcal{L}(G)$: replace every edge of the original graph by a node, connect nodes when the original edges share an endpoint, then take the eigenvectors of the normalized Laplacian and use the coefficients of the $k$ smallest non-zero eigenvalues as coordinates for each edge. The model's edge-token embeddings after layer 1 resemble these coordinates, so distances in this space act as learned estimates of graph distance. Two second-layer attention heads, called $h_{\text{current}}$ and $h_{\text{target}}$ in the paper, supply the readout: they concentrate weight on edges incident to the current and target nodes, and the next node is chosen by minimizing $\|e_{\text{current},i} - e_{\text{target},j}\|_2$ over those sets. The same spectral picture yields a size prediction the paper verifies: because the line graph Laplacian for a 10-node graph has up to 45 dimensions, hidden dimensions above that threshold learn the task, while hidden dimension 32 fails.
What would settle it
Run SLN with k fixed to 1 on every test graph; if accuracy falls substantially below 99.32%, then the per-graph choice of k is doing the work and the claim that the model implements a single SLN algorithm fails.
Extended reading notes
Core claim
The paper's central claim is that the shortest-path computation learned by a two-layer decoder-only transformer is a greedy spectral navigation. Confronted with a query, the model's first layer produces representations of edge tokens that are strongly correlated with the eigenvector coefficients of the normalized Laplacian of the line graph; across 10,000 test graphs with four eigenvectors and four principal components, the cosine similarity peaks at 0.909 for the 4-head model, and pairwise embedding distances correlate at 0.92. In the second layer, dedicated attention heads emerge: one attends to edges containing the current node, the other to edges containing the target node, with sharply reduced activation on the edge leading back to the previous node. The paper argues that at each step the model selects as the next node the endpoint of the current-node edge whose spectral embedding is closest to the target-node edge embeddings. This procedure, implemented directly without the network, is Spectral Line Navigation, and it reaches 99.32% accuracy on the test set.
Load-bearing premise
The comparison between the model and SLN assumes SLN is one fixed algorithm, but the number of spectral directions used is chosen per graph; if that choice is informed by the test set, the reported 99.32% match does not establish that the model runs SLN.
Editorial extensions
If this is right
- A two-layer decoder-only transformer with even a single attention head can learn shortest paths on graphs up to 10 nodes, and increasing heads improves accuracy and robustness; the weakest category, the one-head model on 6-step paths, still sits above 95% in the interquartile range.
- Failures are not random: the model assigns probability mass to near-shortest paths, so accuracy degrades as the average length $\bar{\ell}$ of runner-up paths approaches the true shortest length $\ell^*$.
- The spectral account makes a size prediction the paper verifies: hidden dimension must exceed the line-graph Laplacian dimension, so hidden size 64 learns 10-node graphs while hidden size 32 fails, and restricting graphs to fewer edges than the hidden dimension restores learning.
- SLN is a concrete approximate shortest-path procedure that works without the network, so the transformer's behavior on these graphs can be reproduced and studied outside the model.
Reading between the lines
- The per-graph choice of $k$ in Section 6 means the reported 99.32% belongs to a family of spectral navigators rather than one fixed algorithm; running SLN with a single $k$ chosen from training graphs only would be the cleanest test of whether the transformer literally implements SLN.
- The hidden-dimension ablation implies a scaling law the paper leaves implicit: a two-layer transformer with hidden size $d$ should begin to fail once graphs contain more than about $d$ edges, because the line-graph Laplacian needs $d$ coordinates to be represented.
- If the spectral-distance mechanism holds broadly, it suggests planning in these models can be recognized geometrically, by looking for low-dimensional embeddings whose distances encode problem structure, rather than by searching for explicit iterative loops.
- A testable consequence is distributional: when several near-shortest paths exist, the model's probability spread should track the spectral distances among candidate next edges, so failure cases and SLN's margin should coincide.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper trains two-layer decoder-only transformers from scratch to predict shortest paths on small simple connected undirected graphs (up to 10 nodes), with token sequences representing edge lists, node lists, and queries. The authors report that such models learn the task with high accuracy, that their learned edge-token embeddings correlate with spectral embeddings of the line graph, and that attention heads in the second layer attend selectively to edges incident to the current and target nodes. Based on these observations, they propose an approximate spectral path-finding algorithm, Spectral Line Navigation (SLN), which greedily selects the next edge by minimizing L2 distance in a spectral embedding of the line graph, and report 99.32% test accuracy for SLN, close to the transformer's 99.42%.
Significance. The controlled experimental setting, the per-graph remapping to remove labeling symmetries, the hidden-dimension and head-count ablations, and the proposal of a concrete interpretable algorithm are strengths. If SLN were a fixed, standalone algorithm whose accuracy is genuinely comparable to the trained transformer, the paper would constitute a substantive mechanistic interpretability contribution with a novel algorithmic finding. The hidden-dimension ablation in Appendix B.1 is a particularly good example of an independent prediction derived from the proposed mechanism. However, the load-bearing comparison between the transformer and SLN is weakened by the per-graph selection of the number of eigenvectors k, as discussed below; the empirical evidence for the spectral-embedding correlation is also partly based on grid-search maxima.
major comments (3)
- [Section 6 and Figure 9] The reported 99.32% accuracy for SLN is not the accuracy of a fixed algorithm. The text states that for most graphs the Fiedler vector suffices, but 'for other graphs we needed to increase the number k of non-zero eigenvalues we consider,' and Figure 9 plots the value of k 'needed' for successful path finding. This implies k is selected per graph using knowledge of whether the path is correct, i.e., an oracle choice. The 99.32% figure is therefore an upper bound over the family of algorithms {SLN(k)} rather than the accuracy of a specifiable, reproducible algorithm. Because the paper's central mechanistic claim is that the transformer implements SLN, this comparison is only meaningful with a fixed k or with a k chosen from graph features alone. Please provide a fixed-k evaluation (e.g., k=1, 2, 3) with corresponding accuracies, or a principled selection rule, and report the resulting accuracy.
- [Section 5.2 and Figures 5-6] The correlation values reported in Figure 5 (0.928, 0.907, 0.909, 0.826) are maxima over a grid of numbers of eigenvector coefficients and PCA coefficients, which overstates the strength of the evidence that the model embeddings are correlated with the spectral decomposition. Figure 6 then computes a Pearson correlation of 0.92 using the specific (4, 4) cell selected as the maximum in Figure 5. Please report the full correlation matrix (or a representative summary) and evaluate stability across dimension choices, rather than selecting the best cell after the fact.
- [Introduction and Section 4] The Introduction states as a major result that 'two-layer models can learn to perform this task on graphs with up to 10 nodes, while one-layer models cannot.' No experiment or ablation for a single-layer transformer is presented in the paper. Since this is part of the first claimed result, please either include the one-layer training curves/accuracy or qualify the statement as an observation from pilot experiments.
minor comments (7)
- [Appendix B.2] The phrase 'manually expecting attention maps' should read 'manually inspecting attention maps.'
- [References] There are several typos in the reference list: 'Mathemetical' (Chung), 'Internation Conference' (Nanda et al.), and 'Proessing' in the Wang et al. 2024b entry.
- [Section 3] The citation to 'Mckay, 1983; Mckay' is inconsistent; the second entry appears to be a URL-only reference and should include a year or be formatted consistently as a dataset/web resource.
- [Figure 2 caption] The phrase 'the 1.5 interquartile range is above 0.95' is unclear; likely it refers to the upper whisker at 1.5 times the interquartile range, but the wording should be made precise.
- [Section 5.1] The procedure for selecting hcurrent and htarget heads is described only as 'manually inspecting activation maps'; please specify the exact criterion used to pick a head for each model size, especially for the 8-head model where multiple redundant heads exist.
- [Section 6] The SLN algorithm is described in prose; a formal pseudocode block would make the algorithm unambiguous and easier for readers to reimplement.
- [Figure 9] The caption says 'k counts needed for SLN to successfully find the shortest path'; please define 'needed' explicitly, e.g., whether k is the smallest value that yields a correct path when k is increased until success.
Circularity Check
SLN's reported 99.32% test accuracy is an oracle over per-graph k, not the accuracy of a fixed algorithm, making the main algorithmic claim partially circular.
-
fitted input called prediction
[Section 6 (Proposed Path-Finding Algorithm); Appendix B.3, Figure 9]
"We implement and run SLN on the test set and are able to achieve a final accuracy of 99.32%. We found that for most graphs (roughly 80%) using only the second smallest eigenvalue (i.e., the Fiedler vector from Section 2) for edge embeddings is sufficient. However, for other graphs we needed to increase the number k of non-zero eigenvalues we consider for edge embeddings. ... Figure 9. The log of k counts needed for SLN to successfully find the shortest path over the test set."
The integer k is not a fixed hyperparameter chosen before evaluation; it is selected per graph using knowledge of whether the shortest path was found ('k counts needed for SLN to successfully find the shortest path'). Because 'needed' is defined relative to the correct answer, the reported 99.32% accuracy is the best-case performance of the family {SLN(k)} with k chosen on the test labels, not the accuracy of a single reproducible algorithm. The paper's central comparison ('the model achieves 99.42% and SLN achieves 99.32%') therefore pits an independently trained transformer against an oracle-selected member of an algorithm family, so the SLN accuracy is fitted to the test set by construction rather than predicted.
full rationale
The transformer training result is measured independently and is not circular: two-layer decoder-only models are trained on held-out graphs and achieve high accuracy, with no fitted parameter smuggled into that evaluation. The mechanistic observations in Section 5 (attention heads attending to current/target edges, and PCA embeddings correlating with line-graph eigenvectors) are empirical measurements rather than consequences of the conclusions. The hidden-dimension ablation in Appendix B.1 is a genuine independent prediction: the authors reason that representing the line-graph Laplacian requires hidden dimension at least 45, and they confirm that hidden dimension 32 fails while 64 succeeds. There is no load-bearing self-citation chain or imported uniqueness argument. The circularity is concentrated in the SLN accuracy claim: the algorithm's free parameter k is chosen per graph after checking whether the path is correct, so the headline 99.32% is an oracle upper bound over k, not the accuracy of a fixed, reproducible algorithm. Because this number is presented as the paper's third major result and is the basis for claiming that SLN explains the transformer's behavior, the partial circularity is material. The paper would be substantially strengthened by reporting accuracy for a fixed k or for a k chosen from graph features only, without using the target path.
Assumptions & free parameters
free parameters (2)
- k (SLN eigenvector count) =
per graph, up to |E|, not specified in a fixed rule
- dimensions for spectral/PCA correlation =
4 or 7 eigenvectors, 4 or 20 PCA components (chosen as max over grid)
assumptions (3)
- standard math Low-order eigenvectors of the normalized Laplacian of a connected graph encode edge proximity (Fiedler vector and friends).
- domain assumption The residual stream embedding of an edge control token after layer 1 represents the edge that precedes it.
- ad hoc to paper A transformer needs hidden dimension larger than the number of edges to represent the line graph Laplacian for this task.
Cite this review
Pith. "Pith review of Spectral Journey: How Transformers Predict the Shortest Path." pith.science (2026). https://pith.science/paper/F5ZBIQXZ
@misc{pith2026250208794,
author = {Pith},
title = {Pith review of: Spectral Journey: How Transformers Predict the Shortest Path},
year = {2026},
howpublished = {\url{https://pith.science/paper/F5ZBIQXZ}},
note = {Machine review of arXiv:2502.08794}
}
read the original abstract
Decoder-only transformers lead to a step-change in capability of large language models. However, opinions are mixed as to whether they are really planning or reasoning. A path to making progress in this direction is to study the model's behavior in a setting with carefully controlled data. Then interpret the learned representations and reverse-engineer the computation performed internally. We study decoder-only transformer language models trained from scratch to predict shortest paths on simple, connected and undirected graphs. In this setting, the representations and the dynamics learned by the model are interpretable. We present three major results: (1) Two-layer decoder-only language models can learn to predict shortest paths on simple, connected graphs containing up to 10 nodes. (2) Models learn a graph embedding that is correlated with the spectral decomposition of the line graph. (3) Following the insights, we discover a novel approximate path-finding algorithm Spectral Line Navigator (SLN) that finds shortest path by greedily selecting nodes in the space of spectral embedding of the line graph.
Figures
Figures from the paper (6 more)
Reference graph
Works this paper leans on
-
[1]
L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al
Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774,
-
[6]
Gromov, A. Grokking modular arithmetic. arXiv preprint arXiv:2301.02679,
-
[8]
Z., Dikkala, N., Luo, E., Rashtchian, C., Wang, X., and Panigrahy, R
Hong, G. Z., Dikkala, N., Luo, E., Rashtchian, C., Wang, X., and Panigrahy, R. How transformers solve propositional logic problems: A mechanistic analysis. arXiv preprint arXiv:2411.04105,
-
[9]
Po- sition: Llms can’t plan, but can help planning in llm- modulo frameworks
Kambhampati, S., Valmeekam, K., Guan, L., Verma, M., Stechly, K., Bhambri, S., Saldyt, L., and Murthy, A. Po- sition: Llms can’t plan, but can help planning in llm- modulo frameworks. arXiv preprint arXiv:2402.01817,
-
[10]
Khona, M., Okawa, M., Hula, J., Ramesh, R., Nishi, K., Dick, R., Lubana, E. S., and Tanaka, H. Towards an understanding of stepwise inference in transform- ers: A synthetic graph navigation model. arXiv preprint arXiv:2402.07757,
-
[11]
S., Michaud, E., Tegmark, M., and Williams, M
Liu, Z., Kitouni, O., Nolte, N. S., Michaud, E., Tegmark, M., and Williams, M. Towards understanding grokking: An effective theory of representation learning. Advances in Neural Information Processing Systems , 35:34651– 34663, 2022a. Liu, Z., Michaud, E. J., and Tegmark, M. Omnigrok: Grokking beyond algorithmic data. In The Eleventh International Confere...
-
[14]
Proving test set contamination in black box language models
Oren, Y ., Meister, N., Chatterji, N., Ladhak, F., and Hashimoto, T. Proving test set contamination in black box language models. arXiv preprint arXiv:2310.17623,
-
[15]
Power, A., Burda, Y ., Edwards, H., Babuschkin, I., and Misra, V
URL https://arxiv.org/abs/2402.05862. Power, A., Burda, Y ., Edwards, H., Babuschkin, I., and Misra, V . Grokking: Generalization beyond overfit- ting on small algorithmic datasets. arXiv preprint arXiv:2201.02177,
Show all 20 references
-
[17]
Roformer: Enhanced transformer with rotary po- sition embedding
Su, J., Lu, Y ., Pan, S., Murtadha, A., Wen, B., and Liu, Y . Roformer: Enhanced transformer with rotary po- sition embedding. arxiv e-prints, art. arXiv preprint arXiv:2104.09864,
-
[18]
URL https: //transformer-circuits.pub/2024/ scaling-monosemanticity/index.html. Tian, Y . Composing global optimizers to reasoning tasks via algebraic objects in neural nets. arXiv preprint arXiv:2410.01779,
2024
-
[19]
Llama 2: Open foundation and fine- tuned chat models
Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y ., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. Llama 2: Open foundation and fine- tuned chat models. arXiv preprint arXiv:2307.09288 ,
-
[21]
org/abs/2407.20311
Full version available at http://arxiv. org/abs/2407.20311. Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y ., and Liu, T.-Y . Do transformers really perform badly for graph representation? In Ranzato, M., Beygelzimer, A., Dauphin, Y ., Liang, P., and Vaughan, J...
-
[22]
cc/paper_files/paper/2021/file/ f1c1592588411002af340cbaedd6fc33-Paper
URL https://proceedings.neurips. cc/paper_files/paper/2021/file/ f1c1592588411002af340cbaedd6fc33-Paper. pdf. A. Training Details A.1. Hyperameters Field Value layers 2 num heads {1, 2, 4, 8} hidden dim 512 MLP hidden dim 2048 vocab size 16 RoPE θ 10000.0 weight decay 0.001 op...
2021
-
[1959]
The llama 3 herd of models
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783,
-
[1960]
Learning to grok: Emergence of in-context learning and skill com- position in modular arithmetic tasks
He, T., Doshi, D., Das, A., and Gromov, A. Learning to grok: Emergence of in-context learning and skill com- position in modular arithmetic tasks. arXiv preprint arXiv:2406.02550,
-
[1983]
Gsm-symbolic: Understanding the limitations of mathemetical reasoning in large language models
Mirzadeh, I., Alizadeh, K., Shahrokhi, H., Tuzel, O., Bengio, S., and Farajtabar, M. Gsm-symbolic: Understanding the limitations of mathemetical reasoning in large language models. arXiv preprint arXiv:2410.05229,
-
[1997]
Training verifiers to solve math word problems
Cobbe, K., Kosaraju, V ., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168,
-
[2021]
Fatemi, B., Halcrow, J., and Perozzi, B
https://transformer- circuits.pub/2021/framework/index.html. Fatemi, B., Halcrow, J., and Perozzi, B. Talk like a graph: Encoding graphs for large language models,
2021
-
[2023]
Nichani, E., Damian, A., and Lee, J. D. How transform- ers learn causal structure with gradient descent. arXiv preprint arXiv:2402.14735,
-
[2024]
De Luca, A. B. and Fountoulakis, K. Simulation of graph algorithms with looped transformers. arXiv preprint arXiv:2402.01107,
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.