acceptodds
Withdrawn from ICLR 2027

Robust Decision Capacity of Multi-Head Attention

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

We establish head-count limits on stable threshold decisions in a single attention layer, through its response to changing one source value along an affine query path while holding keys and scores fixed during the intervention. We quantify stable decision complexity by robust alternating capacity: the maximal number of transitions between alternating threshold labels, each certified under every independent head gain in . Two heads can approximate every smooth scalar response in on a compact interval, yet robust decision capacity remains limited by head count. For and , we prove that unrestricted-score capacity is . The upper bound holds for every output norm and is independent of width, context length, and output-coefficient magnitude; finite scalar attention constructions attain the same order. With source-relative score slopes bounded by on a path of length , we derive matching Euclidean capacity laws in joint head–score regimes, including a transition from factorially constrained growth to a square-root regime governed by , , and . Fixed-head high-score laws reach the unrestricted capacity order, while a fixed non-Euclidean output norm changes the score-dependent order. These results show that head count controls stable decision complexity even after smooth approximation has saturated.

Primary area:
interpretability and explainable AI
Keywords:
Multi-head attention, Robust decision capacity, Expressivity, Head complexity, Approximation theory, Attention robustness

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_4CyGOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how head count limits gain-stable threshold decisions in a single attention layer. The main result is a robust capacity law of Θ(Hδ−1log⁡(1/δ))\Theta(H\delta^{-1}\log(1/\delta)), together with more detailed bounds under score constraints. I think the main capacity result is technically nontrivial, and I did not find an obvious correctness issue. My main concern is significance: the paper develops a fairly elaborate theory around a very specific notion of localized-source decision capacity, but does not yet show why this quantity matters for attention computation more broadly. The novelty positioning is also incomplete, especially given several closely related attention-only universality papers missing from the discussion.

Critical strengths
  • Thm 3 gives a clean head-count limitation that is independent of width, context length, and output coefficient magnitude. The matching finite construction makes this substantially stronger than a simple upper-bound or parameter-counting result.

  • Thm 2 and Thm 3 together give an interesting separation: two heads already approximate arbitrary smooth scalar responses in this interface, while robust decision capacity still grows with head count. I think this is the clearest conceptual contribution of the paper.

Critical weaknesses
  • Significance/relevance. My main concern is that robust alternating capacity is a fairly specialized quantity. It counts threshold crossings of one source intervention along an affine query path, with the threshold and witness locations also optimized. The paper characterizes this quantity in considerable depth, but I am not yet convinced what important capability or limitation of Transformers this explains. The technical results may be new, but the significance currently feels limited for ICLR.

  • Novelty/positioning. I do not think the main capacity theorem is obviously subsumed by prior work. However, the paper misses several directly relevant attention-only universality papers, including work by Hu et al., Liu et al., and Petrov et al. This is especially problematic for Thm 2 and the discussion in Sec 8, which currently contrasts mainly with universality results that still use feed-forward layers. The paper needs a much clearer comparison of what is actually new in terms of architecture, number of heads, preprocessing, depth, and approximation setting.

    • Hu et al., Universal Approximation with Softmax Attention
    • Liu et al., Attention Mechanism, Max-Affine Partition, and Universal Approximation
    • Petrov et al., Prompting a Pretrained Transformer Can Be a Universal Approximator
    • Petrov et al., When Do Prompting and Prefix-Tuning Work? A Theory of Capabilities and Limitations
    • Dana et al., Memorization in Attention-only Transformers
Questions for authors
  1. What concrete consequence does robust alternating capacity have for actual Transformer computation, learning, or interpretability? Is there a natural task where this capacity directly determines what the model can or cannot do?

  2. How does Thm 2 compare directly with Hu et al., Liu et al., and Petrov et al. on architecture, head count, FFN use, preprocessing, target fn, and approximation topology? What exactly remains new?

  3. How essential is the localized-source setup where keys and scores are fixed during the intervention? Can the main capacity result be extended to a less restricted attention setting?

Reviewer_fnFkOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies how the stability of the influence of a single query changes as the number of heads of attention grows. Formally, consider a single query qq and suppose that we can shift it in some fixed direction uu by some scalar zz. Then, shifting the query by zz will induce some change to the softmax distribution softmax(qKt)\mathrm{softmax}(q K^t), which we denote by w(z)w(z). This correspondingly induces the output of attention at this query to be w(z)⋅vw(z) \cdot v. The authors characterize the influence of this distribution shift induced by zz by the operator norm, denoted T(z)T(z): what is the maximum change in w(z)⋅vw(z) \cdot v over all (unit length) value vectors vv? Here, I have summarized the definition of T(z)T(z) for one head, but we can extend the definition to HH heads by summing over heads, weighting each head appropriately. As a first result, the authors show that T(z)T(z) is highly unstable: even with two heads, T(z)T(z) can fluctuate heavily.

This leads to the authors defining At(z)A_t(z), essentially T(z)T(z) under slight perturbations of the weights afforded to each head. The key question considered by the authors is: for some fixed threshold zz, how many times can At(z)A_t(z) fluctuate above and below a given threshold ε\varepsilon? For this quantity, they show that At(z)A_t(z) fluctuates approximately at most HH times around a given threshold as zz increases. The authors also consider some structured variants: for example, when the attention scores can not change by two much over a small interval (see e.g. Theorem 5).

Critical strengths

The authors consider some notion of stability for attention, and obtain some results quantifying their studied notion of stability.

It is possible this notion could capture some measure of expressiveness (e.g. more heads can express more complex functions?)

Critical weaknesses

I don’t understand the motivation of this quantity. Why does it matter? Sure, it says something about how the importance of a given token might vary under changes to the input, but what does the instability notion have to do with either the performance of the transformer, either in how powerful/expressive it is, or how easy/difficult it is to train? The authors do not seem to discuss this motivation in much detail (or it should be emphasized strongly at the start of the paper). Presumably (although I’m not sure about this) one would want to use a result such as this to show that more heads are more expressive?

Why this notion of variation? In particular, why should we expect the query to shift along a single direction, instead of just being randomly a little bit perturbed in any direction? This seems like a very unnatural notion. Also, what motivates the definition of At(z)A_t(z) (i.e. allowing the weight of each head to be perturbed) other than the fact that it seems to give the theorem the authors want to prove?

My main complaint of the paper is that it is very hard to follow. For example, much of the write is extremely terse, does not motivate any arguments, and introduces unnecessary jargon throughout the paper. Terms are often not defined on the first time that they are used (e.g. the first time the main theorem is stated, unrestricted-score capacity is not defined).

Questions for authors

see weaknesses, my main two suggestions are:

(1) properly define the main quantity you are studying at the intro, and motivate why it is important

(2) significantly improve the presentation of the paper. in its current state, it is very difficult to follow.

Reviewer_VohJOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper theoretically studies the expressivity of multi-head attention. As the query moves along a line, it considers the output response to changes in the value of a single source token at each point. It shows that, with two heads, this response can approximate any smooth scalar function to arbitrary accuracy. It then introduces robust alternating capacity, a measure of the ability to robustly switch the output's sensitivity to the source value between high and low, and analyzes how this measure depends on the number of heads. It also analyzes the capacity when attention-score variation is restricted.

Critical strengths

The paper defines a new measure, robust alternating capacity, and analyzes it in terms of the number of heads, attention-score variation, and the output norm.

Critical weaknesses
  1. The paper quantifies how robust alternating capacity depends on the number of heads, but it does not show that this measure captures an important aspect of expressivity. Upper and lower bounds alone do not demonstrate sufficient theoretical significance.
  2. The paper prioritizes listing results over explaining the motivation for its problem setting and what each theorem reveals. For example, it does not explain why it is important to study whether the output response to changes in a source value can be approximated. Nor does it give examples connecting robust alternating capacity to the ability to solve concrete tasks. Section 5 likewise does not explain what practical settings the restriction on attention-score variation corresponds to, or why it matters in those settings.
Questions for authors

How is robust alternating capacity justified as a measure of expressivity? How does it relate to the ability to solve concrete tasks?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.