Attention-based representations for multi-task computation

• URL: http://arxiv.org/abs/2608.04243v1
• Date: Tue, 04 Aug 2026 21:52:04 GMT
• Title: Attention-based representations for multi-task computation
• Abstract summary: We establish bounds on the number of heads required in two simple and concrete multi-task scenarios.<n>In the first scenario, a vector representation is sought so that linear predictors can compute both the smallest and largest numbers in a given list.<n>In the second scenario, a vector representation is sought so that a threshold function can compute the XOR of a given string of $n$ bits.
• Score: 8.34204538904959
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-head attention layers produce vector representations that support multiple downstream tasks. We establish bounds on the number of heads required in two simple and concrete multi-task scenarios. In the first scenario, a vector representation is sought so that linear predictors can compute both the smallest and largest numbers in a given list. In this case, it is known two attention heads with small embedding dimension and bit precision level suffice. We prove that a single attention head requires exponentially higher embedding dimension or precision level. In the second scenario, a vector representation is sought so that a polynomial threshold function can compute the XOR of a given string of $n$ bits. This scenario is analogous to the first one for $n=2$, since XOR is readily computed by a linear function using a vector representation that encodes both the AND and the OR of the two bits. We observe that $n$-bit XOR requires the product of the number of heads and the polynomial degree to be at least $n$, and we construct multi-head attention layers that match this lower bound. These results generalize to arbitrary (symmetric) Boolean functions, where the bound is given in terms of the threshold degree.

Related papers

• The Head Complexity of Boolean Functions in Single-Layer Attention [2.2727733134290813]
  We study the minimum number of attention heads required to compute a function in a one-layer attention-only model.<n>We establish an exact hierarchy under this measure: $k$ heads compute $k$-bit parity but cannot compute $(k+1)$-bit parity.<n>We also establish compactness bounds for embedding dimension and numerical precision.
  arXiv  Detail & Related papers  (2026-09-03T16:22:02Z)
• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  Matrix chain multiplication is a problem in scientific computing, machine learning, and graph analysis.<n>We present emphTwo-Tower Matrix, a quantum subroutine that encodes the product $mathcalW$ of the $K$ matrices into a quantum state in circuit depth.
  arXiv  Detail & Related papers  (2026-07-14T18:42:40Z)
• Higher-Order Token Interactions via Quantum Attention [30.903467721896487]
  We introduce textbfQuantum Higher-Order Attention (QHA), a shallow, hardware-realizable quantum attention head.<n>QHA synthesizes order-$k$ token interactions inside the circuit and exposes them through a local single-qubit read-out.<n>As an application, QHA serves as a compact high-order interaction detector across three domains.
  arXiv  Detail & Related papers  (2026-06-10T05:33:12Z)
• On the Computational Hardness of Transformers [14.73362105392153]
  We show that transformers can be computed more efficiently than $LH$ independent evaluations of attention.<n>In the small embedding regime, computing $LH$ attention heads separately takes $LHN2 + o(1)$ time.<n>In the large embedding regime, one can compute $LH$ attention heads separately using $LHN+ o(1)$ arithmetic operations.
  arXiv  Detail & Related papers  (2026-03-11T21:48:43Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  We present a novel characterization of rank, grounded in the well-known Transformer architecture.<n>We show that the rank of a function $f$ corresponds to the minimum number of emphChain of Thought steps required by a single-layer Transformer.<n>We also introduce the notion of the multi-head rank that captures multi-head single-layer transformers, and perform the analysis of PAC-learnability of the classes of functions with bounded multi-head rank.
  arXiv  Detail & Related papers  (2025-01-22T16:30:58Z)
• A New Class of Algorithms for Finding Short Vectors in Lattices Lifted from Co-dimension $k$ Codes [1.8416014644193066]
  We introduce a new class of algorithms for finding a short vector in lattices defined by codes of co-dimension $k$ over $mathbbZ_Pd$, where $P$ is prime. The co-dimension $1$ case is solved by exploiting the packing properties of the projections mod $P$ of an initial set of non-lattice vectors onto a single dual codeword. We show that it is possible to minimize the number of iterations, and thus the overall length expansion factor, to obtain a short lattice vector.
  arXiv  Detail & Related papers  (2024-01-22T22:17:41Z)
• Universality of max-margin classifiers [10.797131009370219]
  We study the role of featurization maps and the high-dimensional universality of the misclassification error for non-Gaussian features. In particular, the overparametrization threshold and generalization error can be computed within a simpler model.
  arXiv  Detail & Related papers  (2023-09-29T22:45:56Z)
• Polynomial Width is Sufficient for Set Representation with High-dimensional Features [69.65698500919869]
  DeepSets is the most widely used neural network architecture for set representation. We present two set-element embedding layers: (a) linear + power activation (LP) and (b) linear + exponential activations (LE)
  arXiv  Detail & Related papers  (2023-07-08T16:00:59Z)
• On the Information Capacity of Nearest Neighbor Representations [21.915057426589748]
  The brain has an integrated architecture where computation and memory are indistinguishable. Motivated by the architecture of the brain, we propose a model of $textitassociative computation$.
  arXiv  Detail & Related papers  (2023-05-09T23:45:16Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  We study multi-agent general-sum Markov games with nonlinear function approximation. We focus on low-rank Markov games whose transition matrix admits a hidden low-rank structure on top of an unknown non-linear representation.
  arXiv  Detail & Related papers  (2022-10-30T22:58:22Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Combiner: Full Attention Transformer with Sparse Computation Cost [142.10203598824964]
  We propose Combiner, which provides full attention capability in each attention head while maintaining low computation complexity. We show that most sparse attention patterns used in existing sparse transformers are able to inspire the design of such factorization for full attention. An experimental evaluation on both autoregressive and bidirectional sequence tasks demonstrates the effectiveness of this approach.
  arXiv  Detail & Related papers  (2021-07-12T22:43:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.