acceptodds
Under review as a conference paper at ICLR 2027

Learning When to Abort in Transformer Planning: A Mechanistic Study

Abstract

Planning does not by itself imply the ability to recognise errors, but recognising errors can improve planning capacity. In this paper, we study this phenomenon in Transformer planning. To analyze the inner mechanism, we follow the approach of Wang et al. (2024) and abstract planning as path-finding in graphs. In this setting, we train the model to detect the error of invalid transitions, i.e., after the model generates a next node that is not adjacent with the current node, the model should then generate a special abort token x. For expressiveness, we construct a Transformer with feed-forward width for any fixed graph with node set . It can detect all possible invalid transitions, and select a valid next node if the prefix is valid. We then propose a worst-case lower bound on feed-forward width, which makes the detector's linear width near-optimal up to logarithmic factors. In trained models, we demonstrate that invalid-transition detection increases previous-node attention, and most of the valid–invalid separation locates in the feed-forward network's output. This accords with our theoretical insights. Finally, we use this error detection to improve the model's performance: at inference, generating the abort token x will directly cause an external procedure to discard the attempt and restart from the original prompt. Experiments show that error detection combined with retry improves model's planning reliability on graphs, Countdown, and mazes.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Transformer Planning, Interpretability, Reasoning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_zcvNOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors introduce a training procedure to teach the model to produce abort tokens when it is detecting an error in the sequence (for instance, a graph path that does not exist). Their work then shows some theoretical bounds on the model capacity, and demonstrate that, empirically, the mechanism can be beneficial, even with single-shot attempts.

Critical strengths
  • The paper is rigorous and rather precise in its presentation, and overall quite clear.
  • The ideas are well executed in their own respective parts (theory and experiments).
  • The proposed theoretical results are quite interesting in their characterisation of expressivity required for transformers to solve graph tasks.
Critical weaknesses
  • Prop 4.1: perhaps it eluded my attention, but I don’t think f and g are qualified (what kind of functions are they? any?), and I think neither is the thresholding. I am not saying it is not obvious, but I think it would make the first read clearer to make the statement more precise immediately. It is not a big deal, but a little sentence clarifying exactly what is meant can be helpful.
  • At the same time, the above proposition is not particularly novel, so, it is perhaps good to keep this really short. I understand that it can motivate some of the following findings. (Also, note the “Thus, …” twice.)
  • For 5.1, it would also be good to have the ratio quantity spelled out, I believe, while it is understandable. The additional space a camera ready provides could be used towards that end
  • In general, I struggle to see the contribution of 5.1: for d=120d=120, the change is not significant, especially for nn large enough, but it is for d=384d=384, and then what is the takeaway from that? Certainly, having to produce a function extracting from (...,uk,uk+1)(..., u_k, u_{k+1}) the couple (uk,uk+1)(u_k, u_{k+1}) requires attending to those last two… But what follows from this? Removing the attention to the previous node similarly reduces the probability of emitting the stop token, but what’s the conclusion to take from that? Similarly, removing the FFN breaks the model… and? I don’t think there is an establishment between the theoretical mechanism and the one examined empirically, really, and even if there were, I must admit that I am missing the point. I do not know what to do with this. Perhaps it is my lack of understanding of mechanistic approaches/interpretability, etc. The authors should clarify the motivation behind the experiment and the theory, and also how the two relate in their paper. I think 5.2 is much clearer in this regard. It could be a matter of writing more than the contribution itself.
  • I feel that the experiments with varying dd could have been connected to the bound on rr, even if the theorem proves sufficiency not necessity.
  • Overall, I think the paper finds a series of theoretical results that are somewhat interesting, and show that empirically training on stopping planning works in some instances, but there is little connection, from what I read, between the two, and I fail to understand the takeaway, beyond that training on a signal to recognise errors can be helpful.
Questions for authors
  • Can the authors establish more explicit connections between their theoretical findings and their experimental results?
  • What are the key takeaways beyond the possible helpfulness of an abort token?

Feel free to refer to the weaknesses to answer the questions more thoroughly.

Overall, I think the paper is sound, but I fail to see the true insight behind this. I would be happy to revise my score given convincing discussion.

2 comments

We thank the reviewer for these helpful comments.

1. Can the authors establish more explicit connections between their theoretical findings and their experimental results?

(Question 1; Weaknesses 4 and 5.)

Thm. 2 shows that one Transformer layer can select the next node and check the step it just took. Both computations use the graph's edges: planning uses the current node's outgoing edges and reachability to the target; the abort decision uses the edge from the previous node to the current one. Prop. 1 shows that adding separate scores for the two nodes is insufficient. In fact, the model uses the QK dot product to combine information from both nodes.

Our original result, Thm. 3, gives a lower bound of r=Ω(n/log⁡2n)r=\Omega(n/\log^2 n) on the FFN width for a ReLU detector on separate one-hot node inputs. The new experiments show why we also need to study attention. Across six graphs, the main head's QK score distinguishes matched valid and invalid transitions before the FFN, with AUROC 0.9960.996. Each pair differs only in the previous node, and the current node can still reach the target. Keeping the valid prefix's value vectors fixed and using the invalid prefix's attention weights raises mean P(x)P(x) from 0.060.06\\% to 98.5198.51\\%. Keeping the invalid weights fixed and swapping the values changes it only from 98.6798.67\\% to 98.5198.51\\%. The abort response follows the weights. Direct logit attribution places most of the difference in the abort logit in the FFN output.

Therefore, we also added a construction in App. A.1 that uses one head's QK score to check the last step and retains next-node selection in the same layer. Thm. 4 shows that exact detection by thresholding one head's QK score at fixed positions requires a head dimension of dk=Ω(n)d_k=\Omega(n) in the worst case over nn-node DAGs. The construction uses dk=O(n)d_k=O(n), matching that order.

2. What are the key takeaways beyond the possible helpfulness of an abort token?

(Question 2; Weaknesses 4 and 6.)

We have two takeaways. First, when the oracle (of checking validity) is too costly or not available, we can teach the planner to catch its own errors using the error trajectories and train the model to emit the abort token after an invalid step. Second, we believe that planning and checking for the same task are very similar, and thus using one model is more time- and space-efficient than using separate models to do this. That is, including planning and checking validity in the same model does not reduce single-shot validity significantly even in small graph models. Meanwhile, it can improve overall performance without an oracle checking each step by retry.

We use graph path-finding to study the above phenomenons. Our theory shows how one Transformer layer can select the next node and check the preceding transition together. Our experiments show that retrying on the abort token actually improves validity across tasks.

3. What functions ff and gg does Prop. 1 allow, and how does thresholding work? How is the attention ratio in Sec. 5.1 computed?

(Weaknesses 1 and 3.)

Weakness 1. What are ff and gg, and how does the threshold work? Both ff and gg can be any functions from the node set VV to R\mathbb{R}. For a transition from the previous node pp to the current node ii, ff assigns a score to pp alone and gg assigns a score to ii alone. The rule compares their sum f(p)+g(i)f(p)+g(i) with one threshold τ\tau, shared by all node pairs. Scores at or above τ\tau can be labeled valid and scores below it invalid, or the labels can be reversed. Prop. 1 rules out both choices for the four transitions in its statement.

Weakness 3. How is the attention ratio computed? For each model, we feed in 3,000 correct held-out paths. For each query position q=5,6,7,8q=5,6,7,8, we use the current node as the query and average the attention weights over the two heads and the paths that contain that position. We compare the weight on the previous node at position q−1q-1 with the mean weight on the other intermediate nodes at positions 3,…,q−23,\ldots,q-2. For example, at q=5q=5, we compare the weight at position 44 with the weight at position 33. We average the previous-node weights over the four query positions. We separately average the mean weights on the other intermediate nodes over those same positions. The attention ratio is the first average divided by the second. A ratio of 11 means the previous node receives the same attention as an average other intermediate node. Figure 1 uses this ratio to compare baseline and +x+x models on correct paths.

I thank the authors for their response. While I am still slightly pessimistic on the significance of the contribution, the reviewers have addressed my concerns quite well, and I believe that the takeaway is now much clearer. I shall raise my score to a 3.

Reviewer_ujfNOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The setting is a fixed random graph with nodes as opaque tokens, as in the ALPINE and taxi-map studies which are focused on whether next token prediction yields world models. One difference is that the input are not just positive traces, but both positive and negative. Error trajectories label 82–93% of all non-edges, so the training data nearly spell out the adjacency matrix, and the abort token amounts to memorizing that table. On random graphs nothing else seems to be possible: seen edges carry no information about unseen ones. If so, the theory shows that such a lookup is representable.

Critical strengths
  • The paper is clear and careful, with honest controls and a consistent account across theory, mechanism and experiments.
  • The comparison with Self-Backtracking, and the Blocksworld result with a pretrained 0.6B model, are useful empirical data points.
Critical weaknesses
  • It is unclear what the reader is supposed to learn from the paper. The findings are expected: a model memorizes a largely supervised edge table; checking (p, i) needs a nonlinear interaction of p and i, so it attends to p and combines in the FFN; and rejecting flagged samples improves sampled outputs. The theory and the mechanism confirm these expectations rather than revealing how transformers recognize planning errors.
  • Generalization is not tested. Only (s, t) pairs are held out. Detection is never measured on non-edges absent from the error examples, nor on true edges absent from the training paths (false aborts).
Questions for authors
  1. What is the detection accuracy on non-edges that never appear as error examples, and how often does the model abort on true edges never seen in training paths?

  2. Given random graphs with opaque node tokens, in what sense can detection be more than memorization, and which of your claims would you expect to carry over to domains where validity follows from rules over states?

3 comments

We thank the reviewer for these comments. We have added an evaluation of non-edges absent from abort training and clarified what the fixed-graph analysis reveals about error recognition.

1. What is the detection accuracy on non-edges that never appear as error examples, and how often does the model abort on true edges never seen in training paths?

(Question 1; Weakness 2.)

Firstly, all true edges in our graphs occur in the correct training paths.

In our follow-up experiment, the models detected invalid transitions they had never seen as training errors. They also rarely flagged a valid edge they had seen during training.

We took the same valid held-out prefixes and appended three kinds of next nodes. We chose candidates that were outside the prefix, were distinct from the target, and could still reach it. We then checked how often xx was the most likely next token (App. B.2, Table 5).

Last transitionxx is the most likely next token
Non-edge never used as a training error98.66±0.1398.66\pm0.13\\%
Non-edge used as a training error99.66±0.0199.66\pm0.01\\%
Valid edge0.008±0.0010.008\pm0.001\\%

The rates are averaged within each group for each prefix, then across prefixes and six graphs. The model detects nearly all such non-edges within the same graph, even without direct abort supervision on those pairs.

2. Given random graphs with opaque node tokens, in what sense can detection be more than memorization, and which of your claims would you expect to carry over to domains where validity follows from rules over states?

(Question 2; Weakness 1.)

Graph path-finding is an abstraction of rule-based planning. In other domains, the task rules also define an adjacency relation between states. There is an edge from one state to another if a legal action takes the first to the second. For example, in Blocksworld, nodes are block configurations and edges are legal moves. A plan leads from the initial configuration to one that satisfies the goal. In Countdown, a state records the available numbers, including any repeats. A legal operation removes two operands and inserts their correct result, giving an edge to the new state. A solution follows these edges until only the target remains.

In both tasks, we can check a single step to label an error trajectory. We therefore expect the same training and retry procedure to carry over to other rule-based domains where individual steps can be checked. In Countdown, the procedure improves harness validity by 8.2±0.98.2\pm0.9 percentage points over the baseline at ρ=1\rho=1. In Blocksworld, it improves Qwen3-0.6B-Base's harness validity by 6.8±0.66.8\pm0.6 percentage points over a baseline trained for the same number of updates. These all accord with our claims.

3. What is the reader supposed to learn from the paper?

(Weakness 1.)

First, when a validity oracle is too costly to run or is unavailable at inference, we can teach the planner to catch its own errors. We use error trajectories to train the model to emit the abort token after an invalid step. Second, planning and checking steps in the same task rely on the same rules. We therefore expect using one model for both to save time and memory compared with using separate models. That is, including planning and checking validity in the same model does not reduce single-shot validity significantly even in small graph models. Meanwhile, it can improve overall performance without an oracle checking each step by retry.

We use graph path-finding to study these ideas. Our theory shows how one Transformer layer can select the next node and check the preceding transition. Our experiments show that retrying on the abort token improves validity across tasks.

Thank you for the new results. I get the impression though that the model memorizes the edges of the graph, and can then tell when a transition is not an edge. This form of memorization, unlike the rules that you mention for Blocksworld or Countdown, does not generalize. In Blocksworld, for example, there is a different graph for each number of blocks, and one wants to generalize from some of the graphs (instances) to others. Here, it seems to me, it's memorization of the graph egdes. If this interpretation is wrong, please correct me, but I don't see that this is interesting enough. Thanks.

Thank you for clarifying your concern. We agree that the model learns the graph’s edges in our setting, but we would like to clarify why we believe studying how it uses this knowledge is meaningful. Many reasoning tasks require applying known facts and rules to new problems. Our setting studies this form of generalization through new source–target pairs in a learned graph, following ALPINE [1]. Earlier studies have also used graph tasks and Blocksworld to investigate reasoning and planning in language models [2], [3], [4].

For example, mathematical reasoning uses deduction rules to derive proofs or follows dependencies among quantities to compute answers [5], [6]. API planning similarly combines available tools into sequences that solve new requests [7]. As discussed in ALPINE, these problems can be studied through graph abstractions. The graph represents the knowledge available to the model, and a new source–target pair represents a new problem to solve using that knowledge.

Learning the graph’s edges does not provide a solution to every new source–target pair, nor does successful planning automatically imply that the model can recognize an invalid step. Understanding how a Transformer stores and uses these relations is therefore a meaningful research question. Our paper studies whether the same planner can use its learned knowledge to check its own generated steps and improve planning through abort-and-retry.

[1] Siwei Wang, Yifei Shen, Shi Feng, Haoran Sun, Shang-Hua Teng, and Wei Chen. ALPINE: Unveiling The Planning Capability of Autoregressive Learning in Language Models. Advances in Neural Information Processing Systems, 37, 2024.

[2] Ida Momennejad, Hosein Hasanbeig, Felipe Vieira Frujeri, Hiteshi Sharma, Robert Osazuwa Ness, Nebojsa Jojic, Hamid Palangi, and Jonathan Larson. Evaluating Cognitive Maps and Planning in Large Language Models with CogEval. Advances in Neural Information Processing Systems, 36, 2023.

[3] Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can Language Models Solve Graph Problems in Natural Language? Advances in Neural Information Processing Systems, 36, 2023.

[4] Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the Planning Abilities of Large Language Models: A Critical Investigation. Advances in Neural Information Processing Systems, 36, 2023.

[5] Trieu H. Trinh, Yuhuai Wu, Quoc V. Le, He He, and Thang Luong. Solving olympiad geometry without human demonstrations. Nature, 625(7995):476–482, 2024.

[6] Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeyuan Allen-Zhu. Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process. International Conference on Learning Representations, 2025.

[7] Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face. Advances in Neural Information Processing Systems, 36, 2023.

Reviewer_TuQBOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates whether a Transformer planner can learn to flag its own invalid transitions in the ALPINE graph path-finding setup by training on "error trajectories" (a valid prefix, one invalid transition p → i, and an abort token x that alone receives loss). The contributions are three-fold: (1) Theory: Proposition 1 shows additive scores f(p) + g(i) cannot detect arbitrary non-edges; Theorem 2 constructs a 1-layer, 2-head Transformer where one head retrieves p's adjacency row and |V| ReLU units compute 1[i = v]·A(p, v); and Theorem 3 proves an Ω(|V|/log²|V|) FFN width lower bound for a ReLU detector on one-hot (p, i, t). (2) Mechanistic analysis of 1-layer models showing that abort supervision shifts attention to p, ablating/swapping p eliminates the abort response, and direct logit attribution (DLA) localizes the valid/invalid separation to the FFN. (3) A restart harness that resamples when x is emitted, improving validity on graphs, Countdown, mazes, and (in the appendix) Qwen3-0.6B on Blocksworld, while outperforming adapted Self-Backtracking on Countdown.

Critical strengths
  1. Clean Problem Isolation & Rigorous: Separating next-node selection (current + target) from transition checking (previous + current) cleanly isolates local transition checking from dead-end detection (verified by showing only 37% of x labels are dead ends). The empirical protocol is thorough: 5 seeds with independent graphs, restricting interventions to target-reachable prefixes, Table 2 attention controls, a matched-exposure run, decoupled loss/decoder comparisons against Self-Backtracking, Lean/numerical checks of the theory, and candidly reporting that trained FFN units fire with the opposite polarity of Theorem 2 (activating on invalid rather than valid transitions).

  2. Simple, Low-Overhead Method That Transfers Beyond Toy Models: Training loss on x alone with a simple restart harness requires minimal overhead on graphs (1.03–1.09 draws per instance) and transfers effectively to a pretrained Qwen3-0.6B model on Blocksworld (+22.9 points overall, and +6.8 points over a compute-matched baseline), showing the approach is not restricted to 1-layer toy setups.

Critical weaknesses
  1. Ambiguity Between Attention-Based vs. FFN-Lookup Mechanisms & Mismatched Width Bound: Proposition 1 rules out additive scores to argue the FFN’s ReLU is critical, but QK attention between i and p is bilinear, not additive. The paper's own data show the main head puts 0.58 attention mass on p after an invalid step versus 0.17 after a valid one (while Fig. 6 shows correct paths barely attend to p). If the QK circuit is already scoring non-adjacency, the FFN may simply be thresholding how much p-content arrived—which would explain both the reversed firing polarity and the small number of active units (16–31). DLA and FFN-zeroing do not distinguish these mechanisms because in a 1-layer normed model that never writes x through attention, only the FFN can write a strong abort logit. Separately, Theorem 3’s lower bound assumes one-hot e_p inputs to the FFN, whereas in the Transformer construction A(p, :) is stored in head 2’s |V|×|V| value projection (and d = 4|V| + 8 already forces Θ(|V|) width), making Theorem 3 a general parameter-counting bound (n²/2 bits) rather than proof that FFN width is the architectural bottleneck.

  2. Weak/Unmatched Harness Baselines in the Main Text & Thin Empirical Scale: On graphs, the baseline harness only checks the target endpoint and almost never retries (1.01 draws), reducing the comparison to "learned detector vs. nearly no detector." Natural cheap baselines—restarting on low token probability or high entropy, likelihood-ranked best-of-N at matched draws, or a lightweight classifier head—are missing on graphs, Countdown, and mazes, while compute-matched Countdown numbers (+x uses 3.7 vs. 1.1 draws) and Blocksworld are relegated to the appendix. Moreover, mechanistic results are restricted to 1-layer models; graph gains at d = 384 are near ceiling (95–98% to 99–99.7%) while d = 120 drops ~11 points in single-shot validity; mazes use only 4 mazes × 2 runs; matched-exposure (B.3) is a single graph without error bars; and all studied domains have trivial exact external verifiers, leaving the practical use case under-motivated.

Questions for authors
  1. QK Circuit vs. FFN Lookup: Have you analyzed the QK circuit restricted to (current, previous) node pairs to see if attention scores already predict non-adjacency before the FFN? And in the unit-level analysis, do the 16–31 high-contribution units vary with the current node i (as Theorem 2 predicts), or are the same units firing across prefixes? Also, how do you reconcile Fig. 6 (little attention to p on correct paths) with Fig. 1's rising previous-node ratio—is look-back mostly content-dependent on errors?
  2. Stronger Compute-Matched Baselines: How does the +x harness compare against restarting on low token probability/high entropy and likelihood-ranked best-of-N at matched draws on graphs and mazes? How do results behave at lower sampling temperatures where baseline invalid steps are rarer?
  3. Scope of Theorems 2 & 3: How does Theorem 3 apply when adjacency bits can live in QK or value matrices rather than FFN weights? In Theorem 2 / Remark 1, Theorem 2 covers u_k ≠ t while the graph acceptance test only checks the endpoint: do error trajectories include invalid transitions into t, and how often do returned paths have an invalid final edge?
  4. Countdown Single-Shot Gains: Why does single-shot validity improve on Countdown even without retries—could this be a data-augmentation effect from extra valid prefixes in context?
  • Additional Feedback & Minor Cleanup:
    • Move the compute-matched comparison (Appendix B.4) and the Blocksworld Qwen3-0.6B experiments into the main text, as they provide the strongest practical support for the harness.
    • Scope "near-optimal width" in the abstract/intro to the specific one-hot FFN setup of Theorem 3, and motivate concrete settings where an exact external transition checker is unavailable or costly.
    • Clarify how the summary values (0.88 → 2.52) in noisy Fig. 1 are computed, add multi-graph error bars to the matched-exposure check (B.3), and briefly discuss how look-back detection extends to deeper models where "previous state" is distributed across tokens.
3 comments

We thank the reviewer for these comments.

1a. Do QK scores between the current and previous nodes predict non-adjacency before the FFN? Do the 16–31 high-contribution units vary with the current node ii, as in Theorem 2, or do the same units fire across prefixes?

(Question 1; Weakness 1.)

In our revised Sec. 5, we paired prefixes that differ only in the previous node. Both end at the same current node, which can still reach the target, but the last transition is valid in one prefix and invalid in the other. Across six graphs, the main head’s QK score between the current and previous nodes distinguishes valid from invalid transitions with a mean AUROC of 0.9960.996.

Next, we swapped attention weights after softmax and kept each prefix’s value vectors fixed. Giving the invalid prefix the valid prefix’s weights lowers the abort probability P(x)P(x) from 0.98670.9867 to 0.00120.0012. In the other direction, giving the valid prefix the invalid prefix’s weights raises it from 0.00060.0006 to 0.98510.9851. The abort response thus follows the attention weights.

Finally, we ranked FFN units by their mean contribution to the abort logit on invalid prefixes. The top ten units have a Jaccard overlap of 0.500.50 across different current nodes and 0.510.51 when we keep the current node fixed and compare two groups of prefixes ending there. The similar overlap supports reuse of the same units across nodes.

The above experiments show that the trained graph model uses QK scores to check the last transition, and the FFN turns the change in attention into an abort logit.

1b. How do you reconcile Fig. 6 (little attention to pp on correct paths) with Fig. 1's rising previous-node ratio? Does the model look back more on errors?

(Question 1; Weakness 1.)

Figs. 1 and 6 both use correct paths. In +x+x, the previous node can get less attention than the current node and more than the mean for the other intermediate nodes. Fig. 6 shows the absolute weights. Fig. 1 shows the ratio to that mean. We also took a valid prefix and changed only the previous node to make the last step invalid, keeping the current node and target fixed. The main head's attention to the previous node rose from 0.1650.165 to 0.6790.679.

2. How does the +x+x harness compare with low-probability restart, high-entropy restart, and likelihood-ranked best-of-NN at matched draws on graphs and mazes? Does the gain persist at lower sampling temperatures?

(Question 2; Weakness 2.)

Our method is independent of the decoding rules and hence can be combined with all the decoding rules suggested by the reviewer. We compare the baseline and +x+x under each rule. With low-probability or high-entropy restart, the +x+x model restarts when the confidence rule fires or when it emits xx. With best-of-NN, both models rank candidates by mean token log-probability, and +x+x discards candidates that emit xx.

At each temperature, all six conditions use the same generated-token budget per instance within each task. The tables report test validity at the largest budget tested for each task.

T=1T=1 (App. B.4, Table 7)

Each cell shows test validity as baseline → +x+x.

Task (token cap)Low-probability restartHigh-entropy restartBest-of-NN
Countdown (300)42.7% → 48.8%42.0% → 49.0%43.7% → 51.3%
Mazes (250)56.8% → 63.6%49.2% → 57.8%59.3% → 69.6%
Graphs (100)99.9% → 100.0%94.8% → 98.9%99.9% → 99.7%

T=0.5T=0.5

Each cell shows test validity as baseline → +x+x.

Task (token cap)Low-probability restartHigh-entropy restartBest-of-NN
Countdown (300)42.2% → 48.3%42.3% → 48.3%43.7% → 49.5%
Mazes (250)56.0% → 63.5%54.5% → 63.4%58.5% → 68.7%
Graphs (100)99.9% → 100.0%99.8% → 99.9%100.0% → 99.9%

Adding +x+x improves validity with all three rules on Countdown and mazes at both temperatures. On graphs, the largest gain is with high-entropy restart at T=1T=1, from 94.894.8\\% to 98.998.9\\%. At T=0.5T=0.5, graph validity is near 100100\\% for both models under all three rules.

3a. How does Theorem 3 apply when adjacency bits can live in QK or value matrices rather than FFN weights?

(Question 3; Weakness 1.)

If the attention value projection maps the previous node to its adjacency row, our original Thm. 3 covers this case. The map is linear and can be folded into the FFN's first layer at the same width. If a head checks the edge through its QK score, our new Thm. 4 asks how large that head must be for exact detection by thresholding its score at fixed token positions. Intuitively, if the head dimension is too small, the score matrix cannot represent every possible pattern of edges. In the worst case, we need dk=Ω(n)d_k=\Omega(n). With a fixed number of heads HH and r=4Hdkr=4Hd_k, the Transformer's FFN width must also satisfy r=Ω(n)r=\Omega(n).

3b. Theorem 2 covers uk≠tu_k\ne t while the graph acceptance test only checks the endpoint. Do error trajectories include invalid transitions into tt, and how often do returned paths have an invalid final edge?

(Question 3.)

Yes, the invalid transitions into tt make up less than 0.30.3\\% of training error trajectories and are rare among returned paths. We ran two additional tests to look at them more closely. When we deliberately added an invalid final edge to a held-out prefix, the model ranked the abort token xx first in 75.2±0.775.2\pm0.7\\% of cases across six graphs. With the harness, our model reduced the rate of invalid final edges among returned paths from 0.61±0.100.61\pm0.10\\% for the baseline to 0.20±0.060.20\pm0.06\\% (App. B.3, Table 6). A path can end at the target and pass the endpoint test when its last step is invalid. In this case, the model can still emit xx, which tells the harness to discard the attempt and retry.

4. Why does single-shot validity improve on Countdown even without retries? Could this be a data-augmentation effect from extra valid prefixes in context?

(Question 4.)

We construct the Countdown error trajectories as follows.

  1. Generate correct solution trajectories and split them into training and test sets.
  2. Select a trajectory from the correct training set.
  3. Keep the problem and the solution through a chosen equation's equals sign, replace that equation's result with an incorrect one, and append xx.
  4. Compute the loss only on xx for this error trajectory.

Every correct prefix in the error data therefore already appears in the correct training data for the same problem. The error trajectories supply no new correct prefixes or correct next-token labels.

A possible explanation for the gain is that the two tasks use some of the same knowledge. In graph path-finding, selecting a next node and checking the last transition before emitting xx both rely on adjacency. The adjacency probe in App. B.2 shows a slightly larger separation between edges and non-edges with abort supervision. In Countdown, arithmetic rules likewise determine both the correct result and whether a proposed result is wrong. Learning when to emit xx may therefore also help the model choose valid steps.

Reviewer_TuQBOpenReview ↗

Thank you for your response. It addresses all major concerns. some final points for improvement of the paper.

Thank you for the detailed rebuttal and the additional experiments. I appreciate that you revised the paper itself, not just the response. The new framing in the abstract, introduction and conclusion fits the evidence much better. Overall, my main concerns have been addressed:

Mechanism. The QK AUROC analysis, the swaps of attention weights vs. value vectors, and the unit-overlap analysis convincingly show that the main head’s QK score checks the transition and the FFN thresholds the result. The value-swap result is especially clear: the abort decision follows how much attention goes to the previous position, not what that node’s value vector contains.

Baselines. Table 7 (low-probability restart, high-entropy restart, best-of-N, matched token budgets, two temperatures) shows that the gains on Countdown and mazes hold across decoding rules. Theory scope. Folding the value projection into Theorem 3, adding Theorem 4 for QK detection, and limiting the “near-optimal” claim all resolve my concern.

Some smaller changes the paper would benefit from:

Main-text placement. If space allows, please move the Blocksworld/Qwen3-0.6B results and the compute-matched Countdown comparison into the main text. They are the strongest support for the method beyond one-layer models. Error bars across several graphs for the matched-exposure check (B.3) would also help.

Related work. The paper would benefit from positioning against:

GNN-based learning for planning. This covers learned heuristics (Chen et al., 2024), generalized policies (Ståhlberg et al., 2022a, 2022b, 2023) and action ranking (GABAR; Mangannavar et al., 2025). These methods assume a known action model whose successor generator rules out invalid transitions. Stating this contrast would clarify when a learned abort signal is needed, i.e., when the network writes actions itself without a symbolic successor generator.

LLM self-verification. Stechly et al. (2025) find that self-critique degrades planning performance while sound external verification helps. Explaining why trained, local abort supervision avoids this failure would strengthen the motivation.

References Chen, D. Z., Thiébaux, S., & Trevizan, F. (2024). Learning domain-independent heuristics for grounded and lifted planning. Proceedings of the AAAI Conference on Artificial Intelligence, 38(18). Mangannavar, R., Lee, S., Fern, A., & Tadepalli, P. (2025). Graph neural network based action ranking for planning. Advances in Neural Information Processing Systems 38 (NeurIPS 2025). Saparov, A., Pawar, S., Pimpalgaonkar, S., Joshi, N., Pang, R. Y., Padmakumar, V., Kazemi, S. M., Kim, N., & He, H. (2025). Transformers struggle to learn to search. International Conference on Learning Representations (ICLR 2025). Shen, W., Trevizan, F., & Thiébaux, S. (2020). Learning domain-independent planning heuristics with hypergraph networks. Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS 2020). Ståhlberg, S., Bonet, B., & Geffner, H. (2022a). Learning general optimal policies with graph neural networks: Expressive power, transparency, and limits. Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS 2022). Ståhlberg, S., Bonet, B., & Geffner, H. (2022b). Learning generalized policies without supervision using GNNs. Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning (KR 2022), pp. 474–483. Ståhlberg, S., Bonet, B., & Geffner, H. (2023). Learning general policies with policy gradient methods. Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning (KR 2023). Stechly, K., Valmeekam, K., & Kambhampati, S. (2025). On the self-verification limitations of large language models on reasoning and planning tasks. International Conference on Learning Representations (ICLR 2025).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.