acceptodds
Withdrawn from ICLR 2027

How Transformers Learn Compositional Reasoning on Trees: A Theory

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Compositional reasoning on trees is a fundamental form of structured multi-step computation: each internal node must identify its ordered children among many tokens, retrieve the appropriate operation, compose multiple intermediate values, and propagate the result upward. These branching dependencies make treestructured Chain-of-Thought (CoT) reasoning substantially harder to analyze than chain-structured CoT, where each step follows a single dependency. We develop a theory of how transformers learn and generalize tree-structured CoT reasoning. We formulate compositional reasoning as bottom-up computation on trees and introduce a multi-head attention transformer with fixed calibrated semantics that jointly performs ordered child selection and function retrieval. Under independently injected identities and an equicorrelated token dictionary, gradient descent from zero reduces exactly to margin dynamics and converges under a positive drive floor. The effective step is governed by token conditioning, with explicit structural and semantic dependence in the iteration budget. We further prove a generalization bound for unseen larger and deeper trees using an execution expansion and a training-loss barrier. Experiments on language models and deep transformers further support these theoretical predictions.

Primary area:
learning theory
Keywords:
Chain-of-Thought, training dynamics, generalization, compositional tasks

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_hSmyOpenReview ↗
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 σ4(B)\sigma^4(B). 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 gh>0∀h∈Ag_h > 0 \forall h \in A and 0<α≤1/Ld0 < \alpha \leq 1/L_d. 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 (d≥M≥Vd \ge M \ge V), which sets the maximum number of tree nodes at the embedding dimension dd. In addition, for complete bb-ary trees, the test loss bound in Theorem 4 scales as O((V′)4M2ϵb2Wmin⁡)\mathcal{O}\left(\frac{(V')^4 M^2 \epsilon}{b^2 W_{\min}}\right). The test node count grows as V′=Θ(bK′)V' = \Theta(b^{K'}), therefore the required training loss tolerance ϵ\epsilon decreases exponentially with test depth K′K'.

Questions for authors

Q1. The query and key matrices are merged into a single bilinear matrix BhB^h 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 WqW^q and WkW^k as in transformers?

Q2. Can you prove that condition P in Theorem 3 holds for complete trees of depth K≥3K\ge 3, 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?

Reviewer_1JJxOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This primarily theoretical paper studies how transformers learn compositional reasoning on trees through chain-of-thought. Each internal node must select its ordered children, retrieve its function and propagate the result upward. The authors model this with a multi-head attention layer followed by a fixed calibrated semantic module. The contributions are: (i) an expressivity result showing that there exists learnable weights such that one attention layer can route each node to its children and its function code; (ii) an optimization result showing that GD from zero converges under certain conditions, with a step size that depends on the minimum singular value of the token Gram matrix; (iii) a generalization bound showing transfer of small training loss to larger test trees.

Critical strengths
  • The paper is well motivated and addresses an important problem. Existing theory on tree-structured compositional reasoning mostly offers expressivity results. This paper asks whether gradient descent can learn such reasoning and whether the learned model generalizes to unseen tree structures.
  • The introduction is very clear. It frames the work as a theoretical account of compositional generalization in tree-structured problems through optimization and structural generalization.
Critical weaknesses

The paper is primarily theoretical, so clarity of notation/statements is essential. As written, the paper is inaccessible to most readers and to the general ICLR audience. I noted several issues in clarity and presentation:

  • The notation is heavy and the text relies on a lot of jargon, e.g. "hard slot," "height schedule," "drive floor," and "null witness."
  • Important equations are hard to follow, in particular (4) and the preceding paragraph and (6).
  • The theorem statements are hard to parse; naming the variables so the reader does not have to go back and forth to recall the notation would help.
  • Theorems 2 to 4 are close to impossible to understand for a general ML audience.
  • Beyond the proofs, the paper should state the takeaway of each theorem in plain English. There are brief takeaways but they should be extended substantially.

My second main concern is related to the meaningfulness of the results.

  • Given the fixed semantics and fixed value functions, the work is a theoretical analysis of attention rather than of transformers. This message should be made more clear in the paper.
  • I appreciate the generalization bound (thm. 4), but this bound is not informative, since one cannot tell whether it is small or large in practical settings (this could be more of an issue of notation/theorem interpretation as pointed out above; happy to discuss during the rebuttal phase).
  • The generalization bound depends on the number of internal nodes, which is unfavorable for larger trees and does not separate the impact of tree height from tree width. A more granular analysis in a low-dimensional setting would be welcome, e.g., low-dimensional data or trees with automorphisms.
  • The numerical results, especially those related to the generalization bound, are insufficient to illustrate the theory. They are limited in scope and show nothing beyond height dependence.
  • A minor note, but which should perhaps be acknowledged as a limitation, is that high dimensionality/full rank is required almost everywhere, raising the question of how informative the results are in realistic regimes. E.g.: the number of heads must match the maximum number of children; the identity vocabulary must be large, with dd (the dimension of the node identity tokens) ≥M\geq M (the number of possible injective identities), i.e., dd must grow with tree size.
Questions for authors
  • Why is the number of heads equal to the maximum number of children? Is this needed for the analysis? What happens with fewer heads?
  • In Section 2.2, what is "slot"? Is it the positional encoding or the value at the node?
  • The paragraph preceding (4) is hard to follow. Please elaborate on the fixed semantic module and the attention pools.
  • In (4), why does the function head score xx against xx while the child heads score yy against xx?
  • What is ht\mathrm{ht} in (6)?
  • What is (P) in Theorem 3?
  • How large is the bound in (18) for concrete tree sizes? Can you discriminate between the dependence on tree height and width?

Suggestions

  • Name the variables in the theorem statements and add a plain-English discussion of each result.
  • Cite canonical references on compositional generalization, e.g. Andreas et al.
  • A motivating application with the key tree structure, carried throughout the paper, would help. It would also help to explain how the lack of guarantees for such problems hinders current approaches. Even a brief description of relevant datasets or experiments could address this.

Minor notation points

  • In (4), add a space before the parentheses (currently it reads as a Boolean variable that is part fo the equation)
  • Shouldn't the attention matrix in (5) be SS instead of AA?
Reviewer_xePTOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies attention routing for bottom-up computation on trees. Under a fixed semantic module and specific assumptions, it analyzes gradient descent and generalization to larger trees.

Critical strengths

The paper studies learning dynamics rather than expressivity alone. The exact reduction to margin dynamics and the structural generalization argument are interesting.

Critical weaknesses

Writing and problem formulation The presentation is difficult to follow. It often reads as a sequence of local descriptions. The connections between the task, model, training objective, and theoretical claims are not made clear. Section 2 introduces the tree and architecture, but does not first give a self-contained statement of the learning problem. The reader must reach Section 4.1 to find the training objective and the explicit statement that every internal value is supervised. Several specific issues interrupt the reading:

  • Definitions appear out of order. On p. 4, the paper uses N_c in the arity bound before defining it as the maximum number of children later in Section 2.1.
  • The position notation is incomplete. Section 2.1 uses l_n in the relation encoder before clearly defining it. The text later introduces q_l and slot(m), but does not explicitly connect the position index, its encoding, and the slot function.
  • The forward computation is split across sections. Equation (5) defines the concatenated attention output. Equation (6) then uses proposed semantic outputs Z-tilde_i. Their connection is described in words, while the explicit semantic rule is deferred to Appendix E. This makes the main-text forward pass hard to reconstruct.
  • The output target is introduced late. Section 2 discusses reaching the root. Equation (9) later supervises every internal value. The distinction between predicting the root and predicting the full computation should be stated at the start.
  • Symbols change meaning. The relation encoder is denoted by rho on p. 4. On p. 7, rho denotes the number of active heads. The symbol v_n also shifts from a node value to its encoded vector between pp. 3 and 4.
  • The tree depth is not introduced where it is needed. Section 2.2 says “After k steps” before explicitly identifying k as the tree depth in Proposition 1.

I believe the paper requires major revision before submission. The structure and presentation need to be substantially reorganized. The title is broader than the results. The model learns routing. The composition functions, tree structure, and execution schedule are supplied. This scope should be clear in the title and contribution statements. Convergence from zero requires a positive drive floor, not just a nondegenerate token dictionary. The certified examples concern specific height-two Boolean trees. The paper should explain more clearly which deeper task families satisfy this condition. Figure 4(a) does not test greater tree height: both training and test trees have realized height four. Figure 4(b) reports teacher-forced prediction loss rather than free-running answer accuracy. These limitations are disclosed, but the experiments still provide limited direct evidence for the main generalization claims.

Questions for authors

I believe the paper requires major revision before submission. See the discussion above.

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

Related papers

Discussion (0)

Sign in to comment.