The Head Complexity of Boolean Functions in Single-Layer Attention

arXiv:2609.04046 · cs.CC, cs.LG · Submitted 2026-09-03 · Read on arXiv

cs.CC, cs.LG

Submitted: 2026-09-03

Updated: 2026-09-03

Comments: 32 pages, 0 figures

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Transformer — 73× in this paper · explained in 2 episodes
• Embeddings — 7× in this paper · explained in 2 episodes
• In International Conference on Learning Representations — 6× in this paper
• Core — 5× in this paper · explained in 2 episodes
• Additivity — 2× in this paper · explained in 1 episode
• Alternation — 1× in this paper · explained in 1 episode
• Ambient Dimension — 1× in this paper · explained in 1 episode
• Attention Mechanism — 1× in this paper · explained in 3 episodes
• Empirical Methods in Natural Language Processing — 1× in this paper
• Endpoint Selection Problem — 1× in this paper
• Generalization — 1× in this paper · explained in 13 episodes
• Generative AI — 1× in this paper · explained in 2 episodes
• In-Context Learning — 1× in this paper · explained in 4 episodes
• International Conference on Machine Learning — 1× in this paper
• Interpretability — 1× in this paper · explained in 15 episodes
• Meeting of the Association for Computational Linguistics — 1× in this paper
• Pairwise Comparisons — 1× in this paper · explained in 2 episodes
• Phase Transitions — 1× in this paper · explained in 2 episodes

Sources

• Fast Attention Requires Bounded Entries
• Fundamental Limitations on Subquadratic Alternatives to Transformers
• On the Ability and Limitations of Transformers to Recognize Formal Languages
• Overcoming a Theoretical Limitation of Self-Attention
• Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth
• Theoretical Limitations of Self-Attention in Neural Sequence Models
• Lower bounds for one-layer transformers that compute parity
• Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?
• Parity, Sensitivity, and Transformers
• Strassen Attention, Split VC Dimension and Compositionality in Transformers
• Transformers Learn Shortcuts to Automata
• Memorization Capacity of Multi-Head Attention in Transformers
• The Parallelism Tradeoff: Limitations of Log-Precision Transformers
• A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
• Saturated Transformers are Constant-Depth Threshold Circuits
• In-context Learning and Induction Heads
• On Limitations of the Transformer Architecture
• Concise One-Layer Transformers Can Do Function Evaluation (Sometimes)
• Representational Strengths and Limitations of Transformers
• One-layer transformers fail to solve the induction heads task

Related papers

• Parameterized Hardness of Zonotope Containment and Neural Network Verification
• Optimal Unambiguous DNFs and Alon-Saks-Seymour
• On the Limits of Quantum Multiparty Simultaneous Communication
• Hardware-Algorithm Co-Optimization of Early-Exit Neural Networks for Multi-Core Edge Accelerators
• Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM
• Strassen's support functionals coincide with the quantum functionals