- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
In this paper, the authors investigate the problem of bottom-up reasoning on trees through chain of thought. In particular, they introduce a single-layer multi-head attention block connected to a programmed semantic module. In this architecture, each reasoning step selects child values and retrieve functions for all nodes at a given tree height. Under specific conditions, gradient descent from zero reduces exactly to a one-dimensional scalar margin update for each head. The authors prove that gradient steps scale proportionally to the minimum singular value of the token dictionary . The authors also prove a generalization bound for unseen larger and deeper trees using null-witness error barriers. Finally, the authors present some synthetic experiments that corroborate the theoretical results.
Critical strengths
The problem, compositional reasoning on trees, is indeed very relevant and investigating whether classical training algorithms such as gradient descent can discover and promote this mechanism is an interesting research question. The paper is generally well-written and is easy to follow. The math appears to be sound.
Critical weaknesses
-
My main problem with this submission is its disconnection with real transformer architectures. The proposed canonical architecture is an unrealistic toy model, where a fixed, pre-programmed semantic module executes all node functions, while external hard masks define the input height and child slots. Gradient descent only learns attention routing in practice. On the other hand, real transformers must learn and execute routing, topology, and function computation jointly without any structural bias. Therefore, the title and abstract greatly overstate the scope of this work, as the theory and experiments only study isolated attention routing and teacher-forced token loss, not true transformer chain of thought reasoning.
-
Somewhat related to the previous point, the authors do not provide any evidence that the theoretical results obtained for the canonical architecture might transfer to real language model. The Qwen2.5-0.5B experiment in Figure 4b only reports teacher-forced token cross-entropy loss. Moreover, the test loss on deeper trees increases again after 200 training steps, which indicates overfitting rather than depth generalization.
-
Theorem 3 relies on the condition and . However, this condition is only verified for Boolean trees of height 2.
-
The theory shows significant dimension and depth bottlenecks. The optimization proofs require linearly independent public identity tokens (), which sets the maximum number of tree nodes at the embedding dimension . In addition, for complete -ary trees, the test loss bound in Theorem 4 scales as . The test node count grows as , therefore the required training loss tolerance decreases exponentially with test depth .
Questions for authors
Q1. The query and key matrices are merged into a single bilinear matrix and initialize it to zero. Standard transformers operate with two separate matrices for keys and queries, initialized with Gaussian or uniform distributed values. How would the results change if the bilinear matrix was factorized into and as in transformers?
Q2. Can you prove that condition P in Theorem 3 holds for complete trees of depth , or do deeper trees introduce saddle points near zero initialization?
Q3. Can you extend the empirical evaluation on real language model to show that they effectively match the theoretical results?
Q4. Does gradient descent from zero still converge to small training loss when the number of public identities exceeds the embedding dimension?