- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies whether a Transformer can execute backtracking tree search over continuous thought vectors, and under what training conditions such execution can be learned. The authors analyze noisy depth-H tree environments, compare single-path procedures with reward-ordered DFS, construct a one-attention-layer Transformer that exactly executes DFS over continuous thoughts, and provide learning guarantees for on-policy imitation learning and teacher forcing. They also compare raw feedback with full write-back, arguing that the latter prevents error accumulation and yields more robust execution guarantees.
Critical strengths
1.Clear problem formulation. The paper formalizes search history as a token sequence and distinguishes path success, goal success, and closed-loop correctness. This is a useful conceptual framing.
2.The theoretical narrative is coherent. The paper covers necessity (backtracking), existence (exact executor), learnability (on-policy), and limitations/robustness (teacher forcing and full write-back).
Critical weaknesses
-
The experimental scope is too narrow to support the paper’s broader claims.
Experiments are conducted only on a synthetic binary-tree environment () with depths . There are no experiments on larger branching factors, different noise levels, reward-gap distributions, budgets, architectures, or training-set sizes. For a paper making claims about Transformers learning to execute tree search, this empirical scope is insufficient. -
The experimental conditions do not satisfy the theoretical conditions.
Table 3 reports maximum training errors that exceed the full-write-back theoretical threshold by factors of 5.43–17.07. Thus, the successful models in the experiments do not satisfy the sufficient condition of Theorem 5. The experiments therefore do not validate the mechanism guaranteed by the theorem; they only show that full write-back performs better in this particular setting. The gap between theory and experiments is not adequately discussed. -
The advantage of full write-back is only pronounced at .
At , raw feedback and full write-back perform very similarly. The main difference appears at . The paper uses this to argue for the robustness of full write-back, but the empirical evidence is thin, and there is no analysis of why the difference emerges near this depth. -
No real or semi-real search task.
All experiments are on synthetic trees. While synthetic environments are acceptable for a theory paper, the paper’s claims concern “Transformers executing search,” and at least one symbolic search, planning, or algorithmic task would help establish external validity.
Questions for authors
Questions
-
Experimental scope: The experiments only cover a synthetic binary tree () with . Can the authors justify why this is sufficient to support broader claims about Transformers learning to execute tree search? Would the conclusions hold for larger branching factors, different noise levels, or different training-set sizes?
-
Theory–experiment mismatch: Table 3 shows maximum training errors exceed the full-write-back threshold of Theorem 5 by 5.43–17.07×. Since the successful models do not satisfy the theorem’s sufficient condition, how should readers interpret the empirical results relative to the theoretical guarantee? Can the authors clarify whether the observed success is actually due to the mechanism analyzed in Theorem 5?
-
Depth-dependent advantage: Full write-back is only clearly better at ; at , the two protocols perform similarly. Can the authors explain why the difference emerges near this depth, and provide additional evidence (e.g., error-growth diagnostics or intermediate-depth experiments) for the claimed robustness of full write-back?
-
External validity: All experiments are on synthetic trees. Since the paper’s claims concern “Transformers executing search,” can the authors provide at least one symbolic search, planning, or algorithmic task to show the conclusions are not specific to the synthetic binary-tree setting? If not, can they more carefully delimit the empirical claims?
3 comments
The authors' response adds valuable new evidence. However, the sufficiency-condition gap between theory and experiments is only clarified, not closed. I will therefore maintain my score.
Thank you for the follow-up. The error tolerance of Theorem 5 is a sufficient condition, not a necessary one, and the models of the main experiment reach high path success outside it. We agree that the connection between the theory and the experiments would be stronger if these models met the tolerance. Lemma F.1 applies to these models directly: under full write-back, one-step restoration is necessary and sufficient for reproducing the teacher's trace (this characterization holds for any model), and part (e) gives a lower bound on their path success from held-out one-step predictions (Appendix G.3). We hope this is useful for the final discussion.
Thank you for the review. The paper's main contribution is theoretical, along the narrative you summarize. Its learning guarantees cover ERM and any model that meets a stated fitting accuracy, and the experiments have a supporting role: they test whether standard optimization, for which no such accuracy is proved, learns to execute the search, and how well the trained models execute it under the two storage protocols.
W1 and Q1. Experimental scope.
The general cases are covered by the theory: the execution and learning guarantees hold for every depth and every fixed branching factor. The experiments are narrower, as you point out, and on their own they do not support broad claims; the revised text limits the empirical claims to the binary trees tested.
In the revision we extended the experiments where we could, in training-set size, noise level and number of updates (Section 6, Appendix G; ten seeds each). The main experiment now uses 16384 teacher traces instead of 4096. At H = 8, raw-feedback path success rises from 49.9% with 512 teacher traces to 94.9% with 16384 and changes by less than 2 points across the ambiguity levels 0.1, 0.2 and 0.3; the two protocols differ by less than 1.5 points in all of these settings. The number of updates is reported under Q3. The selection budget and the architecture are unchanged, and a systematic study of larger branching factors is left for future work.
W2 and Q2. Trained models and the condition of Theorem 5.
The path success observed under full write-back is, on all but three of the 163,840 model-instance pairs we checked, exact reproduction of the teacher's trace, and this is equivalent to the restoration of every one-step prediction, the step that Theorem 5 uses. The models of the main experiment do not, however, meet the theorem's sufficient condition.
The equivalence is new in the revision (Lemma F.1); it needs no error tolerance and holds for any model: under full write-back, a rollout reproduces the teacher's stored trace if and only if every one-step prediction on the teacher's prefixes is restored to its target token. Theorem 5 uses this restoration step after bounding the prediction error. New Appendix G.3 tests the equivalence on the trained models: the implementation agrees with it on all of these pairs, whereas under raw feedback the same one-step condition does not prevent failures (Q3). The experiments thus test the mechanism that separates the two protocols, instead of only showing that full write-back performs better.
What remains open is the sufficient condition: the models of the main experiment do not meet the tolerance of Theorem 5, so the theorem does not certify them, and its tolerance and rate are untested. The main text now says so.
W3 and Q3. Why the difference appears at H = 10.
Our reading is that under raw feedback the errors of the stored predictions accumulate, whereas full write-back removes the accumulated error whenever a prediction is restored to its target. This agrees qualitatively with Theorems 4(a) and 5: the error that the guarantee tolerates under raw feedback shrinks with the horizon, and under full write-back it does not.
The diagnostics you ask for support this reading in the main experiment (Appendix G.3). While a raw rollout is still on the teacher's path, the largest deviation of its predictions from those on the teacher's prefix has median 0.001, 0.003, 0.032 and 0.623 at H = 4, 6, 8, 10. At H = 10, the raw rollout then leaves the teacher's path even when every one-step prediction on the teacher's prefixes is restored, and more often on traces with more returns: on 0.5% of the instances with no return and on 56.3% of those with at least seven (new Table 8; eight of the ten models show a similarly large increase).
The depth at which the difference appears is not fixed (new Table 12): with fewer updates it appears at H = 8 (8.8 points after 2,500 updates), and with more updates it shrinks at H = 10 (from 24.8 points after 10,000 updates to 6.3 after 60,000). At the intermediate depth H = 9 (not in the paper), it is below half a point. The theorems do not predict the depth or number of updates at which it appears.
W4 and Q4. External validity.
We followed your second suggestion and delimited the empirical claims: the revised paper limits them to the synthetic binary environments of Setting 1 and states that other search tasks are not tested, so transfer to symbolic search or planning is open. We added no external task; the experiments use the family in which the theorems are proved because their purpose is to test the storage mechanism under standard training.