Reproduce “Attention-based representations for multi-task computation” on OpenResearch

About this paper

Daniel Hsu, Mingyue Xu

Researchers from Columbia and Purdue Universities established that a single attention head requires resources (embedding dimension or precision) growing as sqrt(n) for simultaneously computing minimum and maximum values, whereas two heads need only O(log n) resources. They also derived a fundamental trade-off D × H ≥ T for computing symmetric Boolean functions with threshold degree T, where D is the post-processing polynomial degree and H is the number of attention heads.

Key insights

• Single attention heads face fundamental limitations and require significantly higher resources (embedding dimension, precision, or norm) to simultaneously support multiple tasks like minimum and maximum computation compared to multi-head alternatives.
• A fundamental trade-off exists between the number of attention heads (H) and the degree (D) of the post-processing polynomial for computing symmetric Boolean functions, with their product needing to be at least the function's threshold degree (T).
• The value vector dimension for computing symmetric Boolean functions with a multi-head attention layer and polynomial threshold function does not necessarily need to be large, as constructions achieve the D × H ≥ T bound with dimension O(min{D, log H}).

Summary by alphaXiv.