- 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 , the change is not significant, especially for large enough, but it is for , and then what is the takeaway from that? Certainly, having to produce a function extracting from the couple 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 could have been connected to the bound on , 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
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.
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/log2n) 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.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) from 0.06 to 98.51. Keeping the invalid weights fixed and swapping the values changes it only from 98.67 to 98.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) in the worst case over n-node DAGs. The construction uses dk=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 f and g 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 f and g, and how does the threshold work? Both f and g can be any functions from the node set V to R. For a transition from the previous node p to the current node i, f assigns a score to p alone and g assigns a score to i alone. The rule compares their sum f(p)+g(i) with one threshold τ, shared by all node pairs. Scores at or above τ 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,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−1 with the mean weight on the other intermediate nodes at positions 3,…,q−2. For example, at q=5, we compare the weight at position 4 with the weight at position 3. 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 1 means the previous node receives the same attention as an average other intermediate node. Figure 1 uses this ratio to compare baseline and +x models on correct paths.