# A Capacity-Based Rationale for Multi-Head Attention

arXiv: https://arxiv.org/abs/2509.22840 · HTML: https://mlsanity.com/paper/2509.22840/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2025.

## Built on by (most cited first, 3 of 3)

- [Singular Vectors of Attention Heads Align with Features](https://mlsanity.com/paper/2602.13524/) (2026)
- [Attention-based representations for multi-task computation](https://mlsanity.com/paper/2608.04243/) (2026)
- [Abstention and Noise Filtering: Two Missing Primitives of Softmax Attention](https://mlsanity.com/paper/2609.22005/) (2026)

## Abstract (arXiv)

We study the capacity of the self-attention key-query channel: for a fixed budget, how many distinct token-token relations can a single layer reliably encode? We introduce Relational Graph Recognition, where the key-query channel encodes a directed graph and, given a context (a subset of the vertices), must recover the neighbors of each vertex in the context. We measure resources by the total key dimension DK = h,dk. In a tractable multi-head model, we prove matching information-theoretic lower bounds and upper bounds via explicit constructions showing that recovering a graph with m' relations in dmodel-dimensional embeddings requires DK to grow essentially as m'/dmodel up to logarithmic factors, and we obtain corresponding guarantees for scaled-softmax attention. This analysis yields a new, capacity-based rationale for multi-head attention: even in permutation graphs, where all queries attend to a single target, splitting a fixed DK budget into multiple heads increases capacity by reducing interference from embedding superposition. Controlled experiments mirror the theory, revealing sharp phase transitions at the predicted capacity, and the multi-head advantage persists when adding softmax normalization, value routing, and a full Transformer block trained with frozen GPT-2 embeddings.