paper

Exact Fusion of Softmax Attention Heads Can Require Exponentially Many Atoms

arXiv:2611.02943

Abstract

Fusing independently normalized attention heads can increase the number of explicit key-value entries, or atoms, needed to preserve their output. We prove a sharp separation for : its two-atom heads use head-atom terms, whereas its minimum single-head representation has exactly atoms, even with arbitrary fixed replacement keys, scalar values, and positive masses. The same lower bound holds for every fixed uniform error below on , and the threshold is sharp. The proof uses exposed-key normal cones; exact equality on any nonempty open query domain inherits the bound. The resulting atom bound for a fixed head count is tight when that count divides . A normalized family retains its exponential exact minimum while approaching a constant on fixed-radius query balls. For pretrained-model caches, a classical affine-rank bound and a certified instance exclude exact vector preservation at a specified atom count. Learned-cache comparisons on two disjoint banks of 64 contexts show budget-dependent reversals and calibration effects.

arXiv comment9 pages, 3 figures. Code and reproducibility materials: https://github.com/usamihiroyasu/attention-head-fusion