How Transformers Learn Compositional Reasoning on Trees: A Theory

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.