REVIEW 8 cited by
Representational Strengths and Limitations of Transformers
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
Representational Strengths and Limitations of Transformers
read the original abstract
Attention layers, as commonly used in transformers, form the backbone of modern deep learning, yet there is no mathematical description of their benefits and deficiencies as compared with other architectures. In this work we establish both positive and negative results on the representation power of attention layers, with a focus on intrinsic complexity parameters such as width, depth, and embedding dimension. On the positive side, we present a sparse averaging task, where recurrent networks and feedforward networks all have complexity scaling polynomially in the input size, whereas transformers scale merely logarithmically in the input size; furthermore, we use the same construction to show the necessity and role of a large embedding dimension in a transformer. On the negative side, we present a triple detection task, where attention layers in turn have complexity scaling linearly in the input size; as this scenario seems rare in practice, we also present natural variants that can be efficiently solved by attention layers. The proof techniques emphasize the value of communication complexity in the analysis of transformers and related models, and the role of sparse averaging as a prototypical attention task, which even finds use in the analysis of triple detection.
Forward citations
Cited by 8 Pith papers
-
Structure Before Collapse: Transient semantic geometry in next-token prediction
Semantic geometry emerges transiently early in next-token prediction training before collapsing to Neural Collapse symmetry in synthetic settings with latent semantic factors.
-
How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers
Transformers need depth scaling as the product of ceil(k/s) and log n terms for k-hop pointer chasing under cache size s, with a conjectured lower bound, proved upper bound via windowed pointer doubling, and an adapti...
-
Keyless Attention: Value-Space Routing and Value-Only Caching for Efficient Transformers
Keyless Attention eliminates the key projection in transformers via value-space routing, cutting KV cache size by 50% with competitive or superior performance on language modeling and zero-shot benchmarks.
-
A Sharper Picture of Generalization in Transformers
PAC-Bayes applied to low-sharpness flat minima yields non-vacuous generalization bounds for boolean functions whose Fourier spectra are sparse and low-degree, with parameters estimable by property testing.
-
A Sharper Picture of Generalization in Transformers
Sparse low-degree Fourier spectra allow flat minima in transformers for boolean functions up to context-length sparsity, enabling non-vacuous PAC-Bayes generalization bounds via an idealized low-sharpness learner.
-
H$_2$O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models
H2O evicts non-heavy-hitter tokens from the KV cache using a dynamic submodular policy, retaining recent and frequent-co-occurrence tokens to reduce memory while preserving accuracy.
-
Keyless Attention: Value-Space Routing and Value-Only Caching for Efficient Transformers
Keyless Attention eliminates the key projection, computing softmax(QV^T)V and reducing KV-cache memory by exactly 50%, with comparable or better performance on small-scale models.
-
Keyless Attention: Value-Space Routing and Value-Only Caching for Efficient Transformers
An attention variant that uses values as keys reduces KV-cache memory by 50% and shows roughly comparable perplexity on small-scale training runs.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.