mathematics//compositionality

Compositionality is the principle that complex functions can be built by composing simpler ones, \(f = f_n \circ f_{n-1} \circ \cdots \circ f_1\).

Compositionality is the principle that complex functions can be built by composing simpler ones, f=fn∘fn−1∘⋯∘f1f = f_n \circ f_{n-1} \circ \cdots \circ f_1f=fn​∘fn−1​∘⋯∘f1​.

In transformers, each layer is a function, and the full model is their composition. The residual stream carries the intermediate result between compositions: each layer adds its contribution to it, and the stream accumulates the full composition.

In extended thinking, each decoding step applies the full transformer stack to a new input (the context including all previous thinking tokens). The chain of thought is a composition of compositions: nnn steps, each applying LLL layers, for n×Ln \times Ln×L total transformations.

PSPACE, the class of problems solvable with polynomial memory but potentially exponential time, gives the link to reasoning. Chain-of-thought reasoning gives the model a polynomial scratch space (the context window) to solve problems that would require exponential search without it: the thinking tokens are the polynomial workspace.

Compositionality matters for training because SFT can teach the model what compositions look like (imitating reasoning chains), but only RL can teach it which compositions are worth computing: which intermediate steps actually help.

It is like Gaussian elimination.

Solving nnn equations requires nnn elimination steps, each one simplifying the system, and no shortcut exists because each step depends on the previous one. Complex reasoning likewise requires intermediate thinking tokens, because each one changes the context for the next.