Attention should return what remains.

Summary

Attention is defined by its operational mechanics: comparing a query against keys, normalizing the scores, and computing a weighted average over the values. The regression interpretation reframes this mechanism as a local fit.¹ Neither perspective addresses the fundamental purpose of the operation, leaving both unable to answer the central question posed by any reader of the output: was this answer dictated by the contextual constraints, or was it merely selected by the fitting procedure?

Defining what constitutes a correct output renders this question answerable.² Each position imposes a distinct constraint; the operation's role is to intersect these constraints and expose the remaining solution space. What emerges from this process is natively a set, not a point, where forced, open and contradictory outcomes correspond strictly to one, several, or zero remaining solutions. Read as a function value, the softmax output is a single point, which covers only the first case. That limit belongs to the reading, not to the operation: the same average over indicator values, read at one, returns the exact intersection.

1. What remains

That claim requires structural form before it can admit proof; begin with a text short enough to hold entirely in mind.

Consider a single-line context: Ana is in the kitchen or the garden. Ask where Ana is. The text permits two valid answers and resolves neither; the only faithful output is the set containing both. A head whose output is read as the answer itself returns one location, indistinguishable from a context that explicitly stated Ana is in the kitchen.

Add a second line: Both the kitchen and the garden are in Luis's house. Ask instead whose house Ana is in, and the answer is forced, though no single line contains it. Now change that second line to Ana is not in the kitchen and Ana is not in the garden. The text collapses into inconsistency, supporting no answer at all.

These are four distinct structural states—determined, open, compositional, and contradictory—yet a reading that takes the output as the answer itself can express only the first.

Prior to reading, the solution space is unconstrained: every possibility remains open. Each statement acts as an operator that eliminates candidate states. Reading a text is the sequential subtraction of possibilities, and the final state is simply whatever space remains.

Fix a set $\Omega$ of states, a semantics $[\![\sigma]\!]\subseteq\Omega$ for each statement, and read a text conjunctively:

[\![\tau]\!]=\bigcap_{j=1}^{n}[\![\sigma_j]\!] .

A question is a map $g:\Omega\to\mathcal Y$ . Its answer set on $\tau$ is $g([\![\tau]\!])$ . The text forces $y$ when that set is $\{y\}$ , is open when it has two or more points, and is contradictory when it is empty.

Those three words name three of the four states above, the compositional one being a forced answer that no single statement carries. No mechanism has been mentioned yet. This is what a correct answer means, before anything is built to produce one.

A head over a constraint domain does three things: it emits a constraint per position, it combines them, and it reads out the answers the combination permits. When it can, it also exhibits witnesses: states checked against the original constraints, not against its own approximation of them. Their answers form the inner set $H^{-}$ ; the readout is the outer set $H^{+}$ . If the domain preserves intersections, the emitted constraints are never smaller than the truth, and the readout never drops an answer, then the outer set contains the true answer set. That is the whole guarantee, and it has a shape worth stating exactly:

H^{-}(\tau,g)\;\subseteq\;g([\![\tau]\!])\;\subseteq\;H^{+}(\tau,g).

An empty outer set certifies a contradiction. A singleton outer set certifies a forced answer only if the text is consistent, because $\varnothing\subseteq\{y\}$ as well; a witness supplies that consistency, and a state that merely satisfies the head's approximation is not one, since the approximation may admit states the text does not. Two witnessed answers certify that the question is open. A wide outer set certifies nothing about openness on its own, since the width may be the head's imprecision rather than the text's. Those four distinctions are easy to collapse into two, and they are exactly the ones a reader of the output relies on.

The statuses a head can report are therefore four: contradictory, forced, open, and unresolved when neither side of the sandwich is tight enough. The last is a fact about a budget, not about the text.

2. The mechanisms, read against the specification

With the specification fixed, every mechanism in use can be placed against it. Each one carries an implicit answer to two questions: what kind of object a position contributes, and how two of those objects combine.

Representation	Combining law	What comes back	Mechanism read as this instance
Function values with a smoothness prior	weighted average, which is none of the laws below	a point; no width; no empty set	softmax attention; local linear attention³ and the covariance-corrected average, Section 4
Indicator vectors over the state space	conjunction: the same weighted average, read at 1	the exact set; empty when no coordinate reaches 1	softmax attention over set-valued values
Boxes and intervals	conjunction: componentwise min and max	the interval; empty if the ends cross	zero-temperature softmax (selection); max-pooling
Affine subspaces with a bounded state	conjunction: a linear solve	an interval; a contradiction certificate $K^{\top}u=0,\ u^{\top}v\neq0$	Mesa layers in the exact-fit limit⁴
Gaussian information form	accumulation: addition of precisions	mean and variance	linear attention;⁵ MesaNet⁴
Fast-weight state	state update: the delta rule, order-dependent	a point	DeltaNet⁶
Difference bounds $x_i-x_j\le b$	conjunction: entrywise min, then closure	$[-b^{}_{ki},\,b^{}_{ik}]$ ; a negative cycle	min-plus aggregation, Section 5

Three distinct combining laws govern that column, and they must not be conflated.

Conjunction of facts is idempotent and commutative: a restated fact adds zero information, and the sequence of presentation is irrelevant.
Accumulation of evidence is non-idempotent: two independent measurements tighten the distribution more than a single observation.
State update is neither commutative nor idempotent: sequence and transition history alter the final state.

No attention head can infer from statement content alone which of these three laws applies to a given pair of inputs. Two identical constraints combine identically in vector space whether one is a redundant restatement or an independent secondary measurement. The governing law is a property of the data sources' dependence structure, not of the text itself, meaning the aggregation step requires source-dependence metadata that raw text cannot provide.

The top row is the regression reading: the output is an estimate of a function value, a single point. A readout that takes that output as the answer itself is sound only on texts where the true answer set is empty or is precisely that point. On every open text, it fails.

That limit belongs to the reading, not to the operation. The second row is the same weighted average over different values. Give each position the indicator vector of the states its statement allows, keep every weight positive, and read off the coordinates that equal one. A coordinate reaches one exactly when every statement allows that state, so the readout is the exact intersection: empty, a single state, or many. The cost is one coordinate per state, which is the price of enumeration, and nothing here says training finds this representation. But the point stands: a width and the empty set are a matter of what the values encode and how the output is read.

On a strictly forced, consistent text, a single point output can be exactly right. A trained Transformer processes its values through learned projections, further heads and non-linear layers, and nothing here bounds that system. What the two rows show together is where the regression reading stops: it encodes neither a width nor an empty set.

3. What follows for any sound head

Four consequences hold for any head that meets the specification, whatever domain it works in. Two are about what a head must not throw away, one prices what any aggregation can guarantee, and one bounds what a fixed-size state can hold.

Do not discard a dependency before the operations that still need it. For any sets $S_j$ and any question $g$ ,

g\Bigl(\bigcap_j S_j\Bigr)\subseteq\bigcap_j g(S_j),

and the inclusion is strict in general: $x+y=10$ and $x-y=2$ each say nothing about $x$ on their own, and together they say $x=6$ . Projecting each statement and then combining the projections is sound and not exact. The slogan "combine everything before projecting" is not what the theorem supports, though. A projection is safe exactly when it does not identify states that a remaining operation still has to tell apart, and equality holds when $g$ is injective on the states in play. Which states those are depends on what will be asked and what will be added.

Sufficiency for the present question is not sufficiency for later ones. Two contexts that permit the same answers now can permit different answers after one more statement. Both $\{x=y\}$ and $\{x=-y\}$ leave $x$ free, and $y=1$ splits them.

It goes further: sufficiency under each single update is not sufficiency under two. Take three bits, and the two contexts "their parity is even" and "their parity is odd". Revealing $b$ alone leaves the first bit open in both, and so does revealing $c$ alone. Revealing both decides it in opposite directions.

A memory that is updated without re-reading therefore needs more than sufficiency. It needs to be closed under the admissible updates, $T(S\cap U)=F_U(T(S))$ , which is the object studied as a predictive state representation, here with answer-set semantics and a contradiction case.⁷

Any aggregation whose coefficients sum to one has an exact worst-case error. Suppose the attended values obey $v_j=b^{*}+W^{*\top}(k_j-q)+\varepsilon_j$ with $\|W^{*}\|\le R_W$ , and let the estimate be $s^{\top}v$ with $\sum_j s_j=1$ . Under a weighted tolerance $\|P^{1/2}\varepsilon\|\le\delta$ , with $R_W,\delta>0$ ,

\sup\bigl|b^{*}-s^{\top}v\bigr| \;=\; R_W\,\Bigl\|\textstyle\sum_j s_j(k_j-q)\Bigr\|_2+\delta\,\|P^{-1/2}s\|_2 ,

with the supremum attained, so this is the error, not a bound on it. The first term is the part of the query offset the coefficients fail to reproduce; the second is how much they can amplify an error in the data. Any coefficients, learned or not, come with this number for free, and the coefficients that minimize it solve a convex program involving only the design and the declared radii.

The tolerance model matters here. Under per-statement tolerances $|\varepsilon_j|\le\delta_j$ the same argument gives $R_W\|\sum_j s_j(k_j-q)\|_2+\sum_j|s_j|\delta_j$ , and the two are not interchangeable. The weighted one renormalizes when a position is added, so it can readmit a value that was already excluded: that makes it a regression model, not a conjunction. The per-statement one only ever shrinks, and it is the one that implements the specification.

What fits in a linear state is decided by rank. A linear summary from which every coordinate of an unrestricted $d$ -dimensional state can be recovered has rank $d$ , so $L$ arbitrary facts of dimension $d$ do not fit in a $d\times d$ state at fixed precision once $L>d$ . The bound is on linear storage at fixed precision and nothing else. What it suggests about architecture is a reading rather than a consequence: composition within a restricted family of questions and updates may fit a query-independent state, while retrieval of many unrelated facts cannot, and needs the rescan of positions that softmax attention performs.

4. The covariance-corrected average

Thus far, the specification has served primarily as a classification tool. However, it also projects directly back onto a mechanism already in active use: isolating one key identity contained within its own algebraic derivation—interpreted here as a statistic—alongside one distinct result it omits.

That mechanism is the covariance-corrected average, introduced as Parallax:⁸ it retains the standard softmax output and subtracts a projection of the local key–value covariance matrix, bypassing the need to explicitly solve a local linear fit at every query point. This approach represents the current practical trade-off against the high computational cost of a full solve, making it crucial to state its exact formal structure before examining either result.

Write $p_j$ for the softmax weights at a query, $\bar k=\sum_j p_j k_j$ and $\bar v=\sum_j p_j v_j$ for the attended means, and

\Sigma_{KV}=\sum_j p_j\,(v_j-\bar v)(k_j-\bar k)^{\top}, \qquad C=\sum_j p_j\,(k_j-\bar k)(k_j-\bar k)^{\top}

for the attended key–value covariance and key covariance, with $C$ assumed positive definite. Under strictly positive weights that holds exactly when the attended keys affinely span the key space, so it fails whenever there are fewer attended positions than dimensions plus one. Fitting a line to the values rather than a constant means solving for a direction and applying it: $\bar v-\Sigma_{KV}\rho^{\star}$ with $\rho^{\star}$ the solution of a per-query linear system. That solve is what makes the local linear fit expensive and numerically delicate.

The covariance-corrected average keeps that shape and drops the solve. It outputs

o=\bar v-\Sigma_{KV}\,\rho,\qquad \rho=W_R x ,

the softmax output minus a projection of the key–value covariance along a direction produced from the position's own state by a learned matrix, rather than solved for. It also discards a scalar factor that the exact solve carries, on the grounds that the factor is unstable. In coefficient form the same output is

o=\sum_j s_j v_j ,\qquad s_j=p_j\bigl(1-(k_j-\bar k)^{\top}\rho\bigr),

coefficients that still sum to one but may be negative, so the head can subtract a value rather than merely down-weight it. Both results below are about this family, and neither depends on which implementation carries it.

The dropped factor is the leverage of the query. The mechanism's own derivation identifies the discarded factor as a Mahalanobis distance: with $m=\bar k-q$ the offset of the query from the attended centre,

\eta=d^{2}=m^{\top}C^{-1}m .

What that distance is, in the local-polynomial literature, is the classical leverage of the query, and $1+d^2$ is the variance inflation of the local intercept at the boundary under inverse-variance weights.⁹ With the exact query-centred direction and $\eta=0$ , the correction is the local-linear correction divided by $1+d^2$ , suppressed precisely where the boundary makes it large. That is an identity about one particular direction; what a learned direction represents, and why training finds it, are questions of capacity and optimization the identity does not answer.

The worst-case-optimal aggregation is a covariance-corrected average. For $R_W,\delta>0$ , every minimizer of the worst-case error above can be written as

s_j=p_j\bigl(1-(k_j-\bar k)^{\top}\rho\bigr),

which is the corrected-average form, and in terms of $\rho$ the objective becomes $R_W\|m-C\rho\|+\delta\sqrt{1+\rho^{\top}C\rho}$ . Its minimizer is the exact local fit $\rho_0=C^{-1}m$ whenever

\delta\,\|\rho_0\|\le R_W\sqrt{1+\rho_0^{\top}C\rho_0},

and otherwise a ridge solution $(C+\lambda I)\rho=m$ whose $\lambda$ is fixed by the design and the declared radii, not chosen. With two keys at $0$ and $2$ , the query at $0$ , and radii $R_W=1$ , $\delta=2$ , the uniform average has worst-case error $3$ , the exact local fit $2.828$ , and the minimizer $2.732$ , with weights $(0.789,\,0.211)$ : reproducing the query exactly amplifies the data tolerance, and the optimum accepts a small reproduction residual for stability.

So the covariance-corrected average is not an approximation of something better. It is the form of the optimum under this model, and the only thing a learned version leaves to training is the single direction $\rho$ . Whether training finds it is a separate, empirical question; the identity does not say it does.

5. Composition where it is exact

The mechanisms above approximate composition. One domain performs it outright, and it is worth seeing what that costs and what it buys.

Take difference constraints $x_i-x_j\le b_{ij}$ . The element is a bound matrix, combination is entrywise minimum, and composition is closure under the min-plus product $(A\otimes B)_{ik}=\min_j(A_{ij}+B_{jk})$ .

Four things follow at once. Repeated squaring $M\leftarrow\min(M,\,M\otimes M)$ closes a chain of $L$ edges in $\lceil\log_2 L\rceil$ steps. The answer for $x_i-x_k$ is read from two entries. A negative diagonal entry certifies a contradiction. And every partial closure is already a valid outer bound, never the tightest before the end and never wrong.

Entries between variables joined by no chain stay infinite, so the propagation terminating is not the same as every difference being bounded. Octagons extend the language to $\pm x_i\pm x_j\le c$ at the same cost, which covers the $x+y=10$ , $x-y=2$ pair from Section 3.¹⁰

The depth statement is a property of this recurrence under four conditions: positions are the variables, the score matrix is the bound matrix, there is no normalization, and rows pass between steps unchanged. It is not a universal bound on the depth any mechanism needs. A softmax layer cannot perform one closure step in general, since a convex combination of a column never falls below that column's minimum while a closure step can; on nearly additive bound matrices it comes close, and the gap grows with how far the constraints are from a single potential. Attention over a max-plus semiring exists in the literature; the construction here differs in taking the bound matrix itself as score and value, and claims no architectural novelty.¹¹

6. What the specification does not fix

Everything so far has assumed the constraints were already given. They are not, and this is where the formal account reaches its limit.

Combination and readout can be made mathematically sound and exact within a chosen domain, provided one pays that domain's computational cost—and that cost is far from trivial: evaluating arbitrary clauses in a Boolean domain turns contradiction detection directly into a satisfiability problem. Furthermore, any formal certificate remains strictly conditional on the emitted constraints accurately reflecting the source text. Solving an erroneous interpretation with exact precision is still fundamentally wrong.

What remains unresolved is the emit map, which reduces to four distinct identification problems:

Identifying which specific question the text addresses.
Determining which constraint domain its semantic content maps into.
Resolving coreference—deciding which tokens map to the same underlying entity.
Establishing the dependency topology—determining which statements depend on which.

None of these four problems can be resolved by a loss function derived solely from the head's own outputs. Because such a loss is inherently invariant under any reparametrization that preserves the head's internal combining law, breaking those structural symmetries requires external ground-truth data or explicit inductive biases.¹²

This places the theoretical boundary in a precise position:

For a fixed domain and emit map, a head's position along the frontier of "tighter bounds at bounded computational cost" is governed entirely by formal theorems.
How sound the emit map is, conversely, depends strictly on what forces break its symmetries during training—a property that lies entirely outside the aggregation step itself.

For any of this framework to hold practical weight, three conditions must be satisfied simultaneously: the capacity to combine information, the ability to preserve it across sequential updates, and the means to certify answers against the original question once the text is interpreted. Nothing in this analysis guarantees that all three hold in practice. Finally, because a smaller uncertainty certificate can indicate either a higher-fidelity solution or merely a more permissive tolerance set, the admissible error bounds, their radii, and the underlying reference model must be held fixed and shared across all heads prior to any valid comparison.

What was proved

This work establishes a functional specification of attention defined by its semantic task rather than its execution mechanics, specifying an outer and an inner output alongside the exact algebraic conditions required to certify each of the four validity statuses: forced, open, contradictory, and unresolved.

Under this lens, standard architectures — softmax, linear attention, the delta rule, Mesa layers, and local-linear attention — are mapped as concrete instances characterized by explicit constraint domains and combining laws. The limit lands on the reading, not on the operation: a readout that takes the output as the answer itself is unsound on open texts, while the same average over indicator values returns the exact set.

From this foundation, four strict constraints emerge for any sound attention head.

The dependency rule. A projection must not identify states that a remaining operation still has to tell apart, bounded only by an injectivity exception.
Sequential sufficiency. The exact closure properties required for recurrent memory state updates.
Worst-case error bounds. An exact, attained error for any aggregation whose coefficients sum to one, strictly isolating the weighted tolerance model from the per-statement one.
Rank constraints. The fundamental rank bound governing linear state storage capacity.

Applied to specific instances, these principles yield concrete theoretical results.

The covariance-corrected average. Reads the boundary factor it discards, a Mahalanobis distance in its own derivation, as the classical leverage of the query, and proves that for positive radii the worst-case-optimal coefficients are themselves a covariance-corrected average, governed by an exact-fit threshold and a ridge fixed point.
Difference-constraint instance. Demonstrates that algebraic closure, readout extraction, inconsistency detection, and network depth emerge as properties of a single unified recurrence.

Attention should return what remains. Everything else here is what follows from taking that seriously, and where it stops.

References

K. A. Wang, J. Shi, E. B. Fox. Test-time regression: a unifying framework for designing sequence models with associative memory. 2025. Softmax attention as the locally constant kernel fit, and the regression reading of the sequence-model family. ↩
Attention Should Return What Remains: constraint combination as a specification for attention, the existing mechanisms as its instances, and the certificate any of them can carry. Lugel Labs. Full statements, proofs and the executed checks are in the manuscript, available on request from Lugel Labs. ↩
Y. Zuo, Y. Yin, Z. Zeng, A. Li, B. Zhu, Z. Wang. Local Linear Attention: An Optimal Interpolation of Linear and Softmax Attention For Test-Time Regression. 2025. The local linear fit, its per-query solve, and the boundary factor the learned variants drop. ↩
J. von Oswald et al. MesaNet: Sequence Modeling by Locally Optimal Test-Time Training. 2025. ↩ ↩²
I. Schlag, K. Irie, J. Schmidhuber. Linear Transformers Are Secretly Fast Weight Programmers. ICML 2021. ↩
S. Yang, B. Wang, Y. Zhang, Y. Shen, Y. Kim. Parallelizing Linear Transformers with the Delta Rule over Sequence Length. NeurIPS 2024. ↩
B. Boots, G. Gordon, A. Gretton. Hilbert Space Embeddings of Predictive State Representations. UAI 2013. ↩
Y. Zuo, D. Pai, Z. Zeng, A. Dewulf, S. Hu, Z. Wang. Parallax: Parameterized Local Linear Attention for Language Modeling. 2026. The covariance-corrected average of Section 4: a learned query-like projector over the key–value covariance in place of the per-query solve. ↩
D. Ruppert, M. P. Wand. Multivariate locally weighted least squares regression. Annals of Statistics 22(3):1346–1370, 1994. Boundary variance of the local linear estimator. ↩
A. Miné. The octagon abstract domain. Higher-Order and Symbolic Computation 19:31–100, 2006; an earlier version appeared at AST 2001. The domain catalogue follows P. Cousot and R. Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, POPL 1977. ↩
B. Hashemi, K. Pasque, C. Teska, R. Yoshida. Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms. 2025. ↩
F. Locatello et al. Challenging Common Assumptions in the Unsupervised Learning of Disentangled Representations. ICML 2019. ↩