Research map / Architectures and efficiency / Attention and transformers
Strassen Attention, Split VC Dimension and Compositionality in Transformers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that one-layer softmax transformers with unbounded precision cannot solve Match3, function composition, or binary relation composition via a new splitting-VC-dimension lower bound, and introduces Strassen attention (sub-cubic, n^2 space) that solves these tasks in principle and outperforms standard attention empirically.
Problem
Standard softmax transformers are known to fail on compositional and triple-interaction tasks, but prior lower bounds (communication complexity) assume low precision; the paper asks whether unbounded precision circumvents these limits and whether a scalable triple-wise attention can solve them.
Approach
Introduces splitting VC dimension, a complexity measure for Boolean functions, giving lower bounds on transformer size independent of precision; and Strassen attention, a triple-token attention whose scores decompose into pairwise dot products so it runs in sub-cubic time via matrix multiplication.
Key results
- Strassen attention and third-order attention are the only mechanisms with high accuracy across all four tasks; Strassen converges faster in training time than third-order attention on all tasks.
- On Quotient Binary Relation Composition, Strassen attention shows a clear advantage over standard and triangular attention.
- Strassen attention is implementable in O(n^omega d) time, sub-cubic, with n^2 space, versus cubic time for third-order attention.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace standard attention with Strassen attention | one-layer Transformer · Function Composition | accuracy | Helped |
| replace standard attention with Strassen attention | one-layer Transformer · Binary Relation Composition | accuracy | Helped |
| replace standard attention with Strassen attention | one-layer Transformer · Match3 | accuracy | Helped |
| replace standard attention with Strassen attention | one-layer Transformer · Quotient Binary Relation Composition | accuracy | Helped |
| replace third-order attention with Strassen attention | one-layer Transformer · Function Composition and Match3 | accuracy | Helped |
| replace third-order attention with Strassen attention | one-layer Transformer · all tasks | training time to peak performance | Helped |
| replace third-order attention with Strassen attention | one-layer Transformer · all tasks | epochs per minute | Helped |
| use triangular attention instead of Strassen attention | one-layer Transformer · Binary Relation Composition | training time | Helped |
| replace standard or triangular attention with Strassen attention | one-layer Transformer · Quotient Binary Relation Composition | accuracy | Helped |
Surprising findings
- Triangular attention outperforms all mechanisms in training time on binary relation composition, which is expected given its built-in structure.
- Third-order attention shows noticeably unstable learning dynamics on function composition and quotient binary relation composition.
Limitations
- Theoretical lower bounds apply only to standard attention with bounded size; upper bounds rely on constructions with precise positional encodings and exponentially small precision margins.
- Experiments use simplified special-case synthetic tasks with small constant-size one-layer models, not realistic language settings.
Experimental setup
Datasets: synthetic Function Composition data synthetic Binary Relation Composition data synthetic Match3 data synthetic Quotient Binary Relation Composition data
Benchmarks: Function Composition (synthetic) Binary Relation Composition (synthetic) Match3 (synthetic) Quotient Binary Relation Composition (synthetic)
Metrics: accuracy training time epochs per minute forward pass time GPU utilization memory usage
Baselines: standard softmax attention third-order attention triangular attention
Builds on: communication complexity lower bounds for transformers higher-order (third-order) attention triangular attention VC dimension
Closest papers by meaning
- Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers (ICML 2025 · similarity 0.87)
- Transformers Learn Faster with Semantic Focus (NeurIPS 2025 · similarity 0.87)
- Memorization Capacity of Multi-Head Attention in Transformers (ICLR 2024 · similarity 0.87)
- Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages (NeurIPS 2024 · similarity 0.87)
- Learning Linear Attention in Polynomial Time (NeurIPS 2025 · similarity 0.87)
- Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.