{"id":"94d72eec-452f-4730-ae82-5dc2f100d920","arxiv_id":"2502.08794","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Two-layer transformers learn shortest paths on small graphs by building embeddings that correlate with spectral decomposition of the line graph, yielding an approximate spectral path-finding algorithm.","lead":"This paper trains small transformer language models to predict shortest paths on tiny graphs and shows they learn a spectral, geometric representation of the graph. The work is a case study in reverse-engineering the internal algorithm a neural network discovers, and it yields a new approximate path-finding method.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"SLN's 99.32% accuracy relies on per-graph oracle choice of k, so the reported number is not for a fixed standalone algorithm.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing concern: SLN's accuracy depends on per-graph selection of k, and if k is chosen using test-set information, the 99.32% result is not the accuracy of a standalone algorithm. The paper's own wording in Section 6 and Figure 9 supports this concern: k is increased when needed, which implies a backward-looking search over k. The transformer accuracy result (result 1) is credible and independently supported by training/test plots and ablations, so the concern does not invalidate the empirical claim. However, the mechanistic explanation (result 3) is only as strong as the SLN evaluation. If the concrete test shows fixed-k accuracy is far below 99.32%, the paper needs a substantial revision: either specify how k is chosen without access to the answer, or present SLN as a family of algorithms with oracle-tuned k and compare the transformer against the best fixed member. Since this is currently unresolved, keeping the CONDITIONAL verdict is appropriate; no change to the reader's verdict is needed.","tokens_in":12918,"tokens_out":2856,"duration_ms":31989,"concrete_test":"Run SLN on the same 500K test set with k fixed to 1 (Fiedler vector only) and with a graph-only rule for choosing k, e.g., k = number of eigenvalues before the first large spectral gap of the normalized Laplacian of L(G), with no access to ground-truth paths. Report accuracy for fixed k in {1,2,4,8,16,32,45} and for the spectral-gap rule. If no fixed or graph-only rule approaches 99.32%, the reported accuracy must be reframed as an oracle-tuned upper bound and the mechanistic claim weakened accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 6 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.' Because 'needed' is defined by whether the path is found correctly, k is selected per graph with knowledge of the correct answer. The 99.32% figure is therefore an oracle upper bound over the family of algorithms SLN(k), not the accuracy of a specifiable or reproducible algorithm. This is load-bearing: the paper's central mechanistic claim is that the transformer implements SLN, and that comparison is only meaningful if a fixed k, or a k chosen from graph features alone, matches the transformer's accuracy. The paper provides no such fixed-k or principled-selection result. The transformer training result itself remains credible, but the SLN accuracy claim is not yet supported as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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%.","tokens_in":13096,"tokens_out":3013,"duration_ms":29442,"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":[{"comment":"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":"Section 6 and Figure 9"},{"comment":"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.","section":"Section 5.2 and Figures 5-6"},{"comment":"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.","section":"Introduction and Section 4"}],"minor_comments":[{"comment":"The phrase 'manually expecting attention maps' should read 'manually inspecting attention maps.'","section":"Appendix B.2"},{"comment":"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":"References"},{"comment":"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.","section":"Section 3"},{"comment":"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":"Figure 2 caption"},{"comment":"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":"Section 5.1"},{"comment":"The SLN algorithm is described in prose; a formal pseudocode block would make the algorithm unambiguous and easier for readers to reimplement.","section":"Section 6"},{"comment":"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.","section":"Figure 9"}],"recommendation":"major_revision","confidential_remarks":"The paper is a good fit for a mechanistic interpretability audience, and the training results and ablations are credible. The main risk is the oracle-k issue for SLN's accuracy, which must be resolved before the central claim can be accepted. I would also ask the authors to add the missing one-layer experiment and to tone down or properly qualify the grid-maximum correlation claims. If the fixed-k SLN accuracy turns out to be substantially lower, the paper's contribution would shift from 'the model implements SLN' to 'the model implements something like a spectral distance heuristic,' which is still interesting but weaker."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the two-layer training result is credible, and the hidden-dimension ablation is a genuine prediction that holds up. But the headlining SLN number is not the accuracy of a fixed algorithm. On reading Section 6 and Figure 9, the stress-test note is right: k is chosen per graph, with knowledge of whether the path is correct. That makes 99.32% an oracle upper bound over the family SLN(k), not a specifiable algorithm.\n\nWhat's real: two-layer decoder-only models learn shortest paths on connected graphs up to 10 nodes, with careful bucketing and remapping, and the failure-mode analysis (near-optimal paths) is thoughtful. The attention-head split into hcurrent and htarget is clean, and the edge-embedding correlation with the line graph Laplacian (cosine ~0.9 at 4 dims) is a nice observation even if reported as a max over a grid. The hidden-dim ablation is the strongest part: the prediction that you need hidden dimension > 45 to represent the line graph Laplacian, confirmed by 64 working and 32 failing, is exactly the kind of independent check interpretability papers should have.\n\nSoft spots, in order: (1) The k-selection issue is load-bearing. Without a fixed k or a k chosen from graph features alone, the comparison between SLN and the transformer is not meaningful. The paper needs either the accuracy of SLN with fixed k (even if lower) or an honest \"SLN with per-graph oracle k\" designation. (2) The one-layer failure claim in the intro has no experiment behind it—trivial to add. (3) The Figure 5 max-over-grid slightly oversells the correlation, but the raw values are strong enough that I don't worry about it.\n\nWho this is for: mechanistic interpretability people working on algorithmic tasks; graph reasoning folks may find the SLN idea worth thinking about. The paper is worth a serious referee, but the referee should push on the k-selection question. I'd recommend engagement with this prior to publication, not rejection—the core empirical findings are solid and the fix is straightforward.","headline":"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.","tokens_in":13556,"tokens_out":2730,"would_cite":false,"duration_ms":25057,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C85","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["shortest path","mechanistic interpretability","decoder-only transformer","spectral graph theory","line graph Laplacian","path-finding algorithm","graph embeddings","planning in language models"],"falsifier":"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.","tokens_in":12732,"feed_emoji":"🧭","tokens_out":12504,"duration_ms":106431,"temperature":0.7,"pith_summary":"This paper aims to settle a piece of the debate about whether language models can be said to plan: it trains a small decoder-only transformer from scratch on the shortest-path problem and then reverse-engineers what the network actually computes. The central claim is that a two-layer model can learn shortest paths on simple connected graphs with up to 10 nodes, and that in doing so it does not run textbook dynamic programming. Instead the model learns an embedding of edges that tracks the spectral decomposition of the graph's line graph, and it advances along the path by greedily picking the edge nearest, in that embedding space, to the target's edges. The paper extracts this behavior as an explicit approximate algorithm, Spectral Line Navigation (SLN), which reproduces the model's answers on 99.32% of held-out graphs, nearly matching the transformer's 99.42%. If correct, this gives a concrete example of a learned planning computation that is not a lookup table and can be stated as a standalone algorithm.","feed_headline":"Two-layer transformers learn shortest paths via spectral navigation","feed_subtitle":"Their hidden algorithm matches a spectral line-graph navigator on 99.32% of test graphs.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the spectral graph theory used to define the normalized Laplacian and the eigenvector embeddings of the line graph.","marker":"Chung, 1997"},{"why":"Defines the line graph construction that turns original edges into nodes for the spectral embedding.","marker":"Harary & Norman, 1960"},{"why":"Prior spectral approach to shortest paths that SLN extends by using the Laplacian of the line graph.","marker":"Steinerberger, 2020"},{"why":"Earlier mechanistic study finding a similar embedding-distance navigation algorithm on directed acyclic graphs, the closest algorithmic precedent.","marker":"Khona et al., 2024"},{"why":"Mechanistic analysis of a transformer on a multistep reasoning path task, used to distinguish per-layer iterative algorithms from the learned embedding-distance mechanism.","marker":"Brinkmann et al., 2024"},{"why":"Reference implementation used to compute the shortest paths and all-shortest-paths counts that form the training labels and evaluation.","marker":"Hagberg et al., 2008"},{"why":"Labelled enumeration algorithm used to generate the non-isomorphic graph dataset.","marker":"Mckay, 1983"},{"why":"Decoder-only transformer and attention architecture that the paper trains and interprets.","marker":"Vaswani et al., 2017"}],"fun_headline_variants":["Transformers solve shortest paths with spectral navigation","Spectral Line Navigator emerges in transformers","Two-layer transformers navigate graphs spectrally","Transformers' secret: spectral shortest paths","99.32%: transformers learn spectral pathfinding"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Transformers solve shortest paths with spectral navigation","Spectral Line Navigator emerges in transformers","Two-layer transformers navigate graphs spectrally","Transformers' secret: spectral shortest paths","99.32%: transformers learn spectral pathfinding"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000796,"raw_usage":{"total_tokens":3488,"prompt_tokens":916,"completion_tokens":2572,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":532,"completion_tokens_details":{"reasoning_tokens":2506}},"tokens_in":532,"tokens_out":2572,"duration_ms":17325,"temperature":1.0,"reasoning_tokens":2506,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T23:40:03.470469+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}