REVIEW 10 cited by
Theoretical limitations of multi-layer Transformer
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
Transformers, especially the decoder-only variants, are the backbone of most modern large language models; yet we do not have much understanding of their expressive power except for the simple $1$-layer case. Due to the difficulty of analyzing multi-layer models, all previous work relies on unproven complexity conjectures to show limitations for multi-layer Transformers. In this work, we prove the first $\textit{unconditional}$ lower bound against multi-layer decoder-only transformers. For any constant $L$, we prove that any $L$-layer decoder-only transformer needs a polynomial model dimension ($n^{\Omega(1)}$) to perform sequential composition of $L$ functions over an input of $n$ tokens. As a consequence, our results give: (1) the first depth-width trade-off for multi-layer transformers, exhibiting that the $L$-step composition task is exponentially harder for $L$-layer models compared to $(L+1)$-layer ones; (2) an unconditional separation between encoder and decoder, exhibiting a hard task for decoders that can be solved by an exponentially shallower and smaller encoder; (3) a provable advantage of chain-of-thought, exhibiting a task that becomes exponentially easier with chain-of-thought. On the technical side, we propose the multi-party $\textit{autoregressive}$ $\textit{communication}$ $\textit{model}$ that captures the computation of a decoder-only Transformer. We also introduce a new proof technique that finds a certain $\textit{indistinguishable}$ $\textit{decomposition}$ of all possible inputs iteratively for proving lower bounds in this model. We believe our new communication model and proof technique will be helpful to further understand the computational power of transformers.
Forward citations
Cited by 10 Pith papers
-
Understanding Input Selectivity in Mamba: Impact on Approximation Power, Memorization, and Associative Recall Capacity
Mamba's S6 layer can represent Haar wavelets and solve associative recall tasks with explicit size bounds, though its memory still decays exponentially unless input-dependent time steps counteract it.
-
Learning Compositional Functions with Transformers from Easy-to-Hard Data
A transformer with O(log k) layers provably learns the k-fold permutation composition task in poly(N,k) samples with curriculum or mixed easy-to-hard data, despite an SQ lower bound requiring N^{Omega(k)} samples on h...
-
Hierarchical Domain Generalization
Over infinite domains, hierarchy-uniform domain generalization is impossible for every nontrivial hypothesis class; a length-generalization bound is a property of the length hierarchy, not a hierarchy-free guarantee.
-
Frontier Language Models Struggle to Copy: Text Can Be Better Viewed in 2D
2D-RoPE, which arranges text by line breaks into rows and columns, lets Transformers copy strings hundreds of times longer than training lengths, while standard 1D positional encodings fail on the same task.
-
The Power of Power Law: Asymmetry Enables Compositional Reasoning
Power-law data sampling creates beneficial asymmetry in the loss landscape that lets models acquire high-frequency skill compositions first, enabling more efficient learning of rare long-tail skills than uniform distr...
-
When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression
Reasoning hallucinations arise from Path Reuse (early memorized paths overriding context) and Path Compression (later multi-hop shortcuts), when next-token prediction is modeled as graph search.
-
Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently
Under hand-designed masks and task-specific activations, RL fine-tuning learns a k-sparse Boolean reasoning chain in one gradient update while SFT learns it one CoT step per update.
-
Falcon-H1: A Family of Hybrid-Head Language Models Redefining Efficiency and Performance
Falcon-H1 reports competitive benchmark scores for a 0.5B to 34B family of parallel hybrid attention/Mamba-2 models, claiming 2x to 4x parameter efficiency versus dense transformers.
-
Transformers Meet In-Context Learning: A Universal Approximation Theory
A constructive theorem shows that transformers can perform in-context learning for any Barron-type function class by combining universal features with an emulated Lasso solver.
-
Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers
The paper claims pause tokens strictly increase constant-precision, constant-depth Transformer expressivity from a subset of AC0 to AC0 (and log-precision to TC0), but the constant-precision proof is not sound as written.
Discussion (0). Sign in to comment.