The Head Complexity of Boolean Functions in Single-Layer Attention

Rajmohan Rajaraman, Ravi Sundaram, Amanuel Tesfaye

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 mode…