acceptodds
Under review as a conference paper at ICLR 2027

Five Invariants Govern Attention Expressivity: A Completeness Theorem

Abstract

Dozens of impossibility and separation theorems now record what one attention variant can do and another cannot, each proved on its own terms. We ask whether they share a structure, and prove that on the canonical tasks they do. We identify five structural invariants of a single-head attention architecture, namely kernel-rank, piecewise-degree, boundedness, symmetry, and recurrent-state, and prove a completeness theorem about them. Each invariant is an obstruction on its own class of tasks. On the associative-recall, averaging, counting, and indexing tasks the five are also jointly sufficient. For the realization regimes covered by the theorem, every cost gap beyond polylogarithmic factors on these tasks has an invariant witness. Under a matrix-dimension cost measure, budgeted invariant profiles determine each canonical task's cost up to polylogarithmic factors. We tabulate that cost for softmax, hard, average-hard, polynomial, sigmoid, causal, and position-free attention, as well as state-space architectures, on every canonical task. Two consequences stand out. Single-layer linear attention needs width at least on associative recall over keys, at any head count, against for softmax. The single-layer polynomial kernels form a strict hierarchy in the degree.

Primary area:
foundation or frontier models, including LLMs
Keywords:
attention, transformers, expressivity, lower bounds, separation theorems, state-space models, kernel rank, hard attention, associative recall, learning theory

Reviews

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

The paper organizes the expressivity of attention and recurrent architectures through five structural invariants. Under specified architectural and realization assumptions, it establishes necessary conditions and sufficiency up to polylogarithmic factors for four canonical tasks.

Critical strengths
  • The goal of organizing the expressivity of different architectures through a common perspective is interesting.
  • The width lower bounds and matching constructions for associative recall with single-layer polynomial attention provide concrete quantitative insights under the stated assumptions.
Critical weaknesses
  1. The conceptual advance from the unification is insufficiently demonstrated.
    The framework largely combines separate obstructions and task-specific constructions for four canonical tasks under different realization conditions. It remains unclear what new insight it provides beyond the individual results and how the contribution differs from the closest prior work. This makes the significance of the central completeness claim difficult to assess.

  2. The cost comparisons are difficult to interpret.
    The measure does not directly account for the complexity of embeddings, readouts, or feature maps, while the restrictions controlling their function-class richness at a fixed budget are unclear. Since these components affect realizability, the paper needs a stronger justification of what the reported cost gaps establish about model complexity.

Questions for authors

Clarification questions

  1. Within the results already established in the paper, what additional insight does the unified framework provide beyond the individual obstructions? Please identify one representative result illustrating this benefit and explain its advance over the closest prior work, including relevant differences in assumptions and scope.

  2. At a fixed cost budget, to what extent do the stated assumptions constrain the function-class richness of embeddings, readouts, and feature maps? Given that their complexity is not directly counted, what notion of model complexity do the reported cost gaps capture?

Presentation suggestion

A concise comparison table with the closest prior work would help clarify the assumptions, scope, guarantees, and new contributions.

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

The paper presents a single theorem that aims to shed light on the expressivity, efficiency, and nature of attention, and variants thereof.

Critical strengths

None

Critical weaknesses

The paper consists of ~8 pages of definitions, sandwiched by the (repeated) completeness theorem, which is framed as the main contribution. However a) The theorem is not parseable without concepts defined in the 8 pages of definition, which themselves mostly refer to proofs, definitions and concepts in a 38 page appendix. I have not read the appendix, and don't believe I have to. b) The theorem is not so much a single theorem, but a collection of heavily qualified statement on a number of constructs, logically wrangled into one statement.

Questions for authors

You state the following in the Paper: Claude (Anthropic) and Codex (OpenAI) helped develop and check proofs, search and verify relevant literature, and draft and edit the manuscript. The authors posed the research question, reviewed the AI-assisted work, and take responsibility for the paper and any errors.

What was the research question posed?

On lines 76-80: Are the statements clarifications or qualifications?

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

This paper uses five metrics to organize the expressive power limitations of attention architecture: kernel rank, shard dependent position count, output range, permutation symmetry, and recursive state dimension. Authors separately prove the necessity of these quantities in the corresponding task categories, and constructs matching implementations for the specified architecture for four types of tasks: associated recall, averaging, counting, and indexing, in order to reduce agency costs and obtain a cost characterization that ignores multiple logarithmic factors.

Critical strengths
  1. Corollary B.2 extends the capacity limitation of linear attention to any number of heads and explicitly constrains the total width. Lemma A.9 (c) achieves precise log_2^n depth using cyclic multiplication and repeated position weight correction at any sequence length, with a relatively concise construction.

  2. The author distinguishes between accurate and approximate implementations, lower bound of dimensions and lower bound of bits, length by length model and cross length unified model. D. D.13 and D.17 also proactively provide limitations and counterexamples to avoid generalizing conclusions directly to all attention architectures. These discussions themselves have reference value.

Critical weaknesses
  1. The core 'completeness' actually only requires three invariants at the cost resolution used. Remark D.18 explicitly proves that the sufficiency of Theorem 4.2 (ii) only requires the passing of KRank, Sym, and State; The separation witness section will never use PDeg and Bound. Because the logarithmic depth difference introduced by PDeg for precise averaging is hidden by \ widtilde O; Bound truly forms a strongly separated length uniform counting, which is outside the range of length by length comparison in the main theorem.

  2. This paper does not contain any experiments to validate and support the author's ideas, therefore it is more suitable for JMLR than ICLR.

Questions for authors
  1. Since D.18 indicates that three items are sufficient, what is the additional theoretical contribution of the five item unified framework compared to the three item classification?

  2. After taking into account the dimensionality, coefficient accuracy, or description length of feature maps, which separations can still be retained?

  3. Is there a natural multi-layer implementation that cannot be reduced to a single layer and can still prove a lower bound similar to kernel rank?

  4. Can the fixed kernel counterexample of D.8 be included in the main thread to clarify what structural information is missing beyond the characterization of kernel rank?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.