Paper recorded by Signals 4 on 2026-09-03 in cs.LG. Abstract reproduced from arXiv; link to the original below.
Published 2026-09-03 on arXiv · recorded by Signals 4 on 2026-09-04
Category: cs.LG · 机器学习 · first seen 2026-09-04
What can a single layer of self-attention compute? We study head complexity: the minimum number of attention heads required to compute a function in a one-layer attention-only model. We establish an exact hierarchy under this measure: $k$ heads compute $k$-bit parity but cannot compute $(k+1)$-bit parity. The lower bound is unconditional in the two resources a transformer might otherwise exploit