Attention, transformer universality, and sequence limits

In a left-to-right grammar expansion, expanding the current $S$ nontrivially emits its opening bracket and leaves an inner $S$, its matching closing bracket, and a following $S$. Choosing $ϵ$ finishes the current $S$ and either emits the pending matching close or, when no close is pending, ends the word. Thus each token is generated by precisely the stack transition stated above. The remaining choices after any finite emitted prefix are fresh independent choices. This constructs the stream law directly, including on nonterminating samples. Each valid prefix uniquely specifies the transition choices so far: every opening requires its type choice and every closing requires an epsilon choice. Their product is $w_p(x)$. In particular $s_{p,k}$ is the probability of reaching $k$ bracket tokens, is positive (all-open prefixes have positive probability), and is nonincreasing in $k$. Conditioning on reaching $k$ does not constrain the fresh choice after the prefix.

The grammar is unambiguous: a nonempty Dyck word has a unique first opening, its matching closing, and the resulting inside and following Dyck words, which recursively determine the derivation. A word with $m$ bracket pairs has $m$ nonempty choices and $m+1$ epsilon leaves, proving its stated finite-word mass. To calculate total termination mass, the probabilities of trees having height below successive finite bounds start at $q_0=0$ and satisfy $q_{j+1}=1-p+p{q}_j^2$. Their increasing limit is the probability of a finite tree: every finite binary tree has finite height, and an infinite finitely branching tree cannot have bounded height. The limit is the least fixed point in $[0,1]$, since iteration from zero stays below any nonnegative fixed point. The roots are $1$ and $(1-p)\mathrm{/}p$, giving the stated $q_p$. The stream is finite exactly when the derivation is finite: every nonempty expansion emits an opening and any derivation with only finitely many nonempty expansions has only finitely many nodes.

Each prefix in $E_k$ is uniquely $uab\bar{b}$, where $u$ is a valid prefix of length $k-3$. Such an extension is always valid, has height $h(u)+1$, and has the $a$-opening as its top unmatched opening. Its cylinder weight is $w_p(u)(p\mathrm{/}2{)}^2(1-p)$. Summing the four choices of $a,b$ and then all $u$ gives $p^2(1-p)s_{p,k-3}$. Divide by $s_{p,k}$ and use monotonicity from step 1.1 to obtain the bound. Flipping $a$ changes no count, leaves the suffix pattern valid, and changes only position $k-2$; applying the flip twice restores the prefix. There are no fixed points, so its orbits are disjoint equal-mass pairs with swapped closing targets.

After a valid prefix of height $h$, the left-to-right residual derivation contains exactly $h+1$ still independent $S$ subtrees (and $h$ pending closing brackets). Its probability of eventual termination is therefore $q_p^{h+1}$. Consequently the termination-conditioned prefix cylinder is $w_p(x)q_p^{h(x)+1}\mathrm{/}{q}_p=(p{q}_p\mathrm{/}2{)}^{o(x)}((1-p)\mathrm{/}{q}_p{)}^{c(x)}$. The fixed-point equation gives $(1-p)\mathrm{/}{q}_p=1-p{q}_p$. This is exactly $w_a(x)$ with $a=p{q}_p$. The finite-word laws likewise agree, either by the same calculation including the final epsilon or directly from step 1.2. Applying step 2.1 with $a$ gives its pairing bound. Finally all typed Dyck words of a fixed length have the same mass by step 1.2 and there are finitely many of them, proving the uniform exact-length law and the asserted distinction of conditioning.

Put $\bar{r}=(r+s)\mathrm{/}2$ and $\bar{q}=(q+q^{\mathrm{\prime }})\mathrm{/}2$. For every $a\in \mathrm{\Sigma }$, $q(a)\le \bar{q}(a)+ϵ$ and $q^{\mathrm{\prime }}(a)\le \bar{q}(a)+ϵ$. Define $w(a)=(\bar{q}(a)+ϵ)\mathrm{/}(1+mϵ)$; its coordinates are nonnegative and sum to one. Monotonicity of $-\log$ on positive reals gives $\frac{1}{2}\mathrm{CE}(r,q)+\frac{1}{2}\mathrm{CE}(s,q^{\mathrm{\prime }})\ge \mathrm{CE}(\bar{r},w)-\log (1+mϵ)$. If a term on the left is infinite, the claimed inequality is immediate; otherwise this comparison is valid on each target-positive coordinate.

For any probability vectors $\bar{r},w$, if $w(a)=0<\bar{r}(a)$ then $\mathrm{CE}(\bar{r},w)=+\mathrm{\infty }$. Otherwise $\mathrm{CE}(\bar{r},w)-H(\bar{r})={\sum }_{a:\bar{r}(a)>0}\bar{r}(a)\log (\bar{r}(a)\mathrm{/}w(a))\ge 0$: applying $\log t\le t-1$ to $t=w(a)\mathrm{/}\bar{r}(a)$ gives the sum at least ${\sum }_{a:\bar{r}(a)>0}(\bar{r}(a)-w(a))\ge 0$. Combining with step 1.1 proves the bound.

Choose $0<\eta <1\mathrm{/}4$ so that $(1-2\eta )C>C^{\mathrm{\prime }}$, then choose $0<\delta <1$ and $0<q<1\mathrm{/}(1+\delta )$ so that $(1-(1+\delta )q)(1-2\eta )C>C^{\mathrm{\prime }}$. Put $D=\lceil c\mathrm{/}(\eta C)\rceil$ and regard $k\ge 1$ as an integer parameter whose finitely many lower bounds will be fixed after the local-lemma estimates. For each position $j$, choose a support $S_j$ of at most $c$ currently free input positions determining its layer-zero activation. There are at most $cn$ incidences between supports and positions. Fix every free input position occurring in more than $D$ supports, using any fixed symbol. At most $cn\mathrm{/}D\le \eta Cn$ positions are fixed; afterwards every free input position belongs to at most $D$ supports.

For a current restriction and query triple $(i,h,z)$, where $h$ is a head at position $i$ and $z$ is a possible layer-zero activation at $i$, at most $cD$ key positions have supports intersecting $S_i$; call these exceptional. For every other key position $j$, its support is disjoint from $S_i$, so the maximum score $m_j$ for query value $z$ is attainable by assigning its free support. Order these eligible positions by decreasing $m_j$, breaking ties by position, and put $R=\lceil cD(k+1)\rceil$. For all sufficiently large $n$, at least $R$ eligible positions exist. Greedily select $k$ among the first $R$ with pairwise disjoint supports: each choice removes at most $cD$ candidates because its support has at most $c$ symbols and each symbol occurs in at most $D$ supports. Record for each selected position a support assignment attaining its maximum.

If a selected support is fixed to its recorded maximum-attaining assignment, that key's score is at least $m_R$. Every eligible position after the first $R$ has maximum score at most $m_R$; equality is resolved in favor of a position among the first $R$ by the chosen tie order. Hence a head's winner lies among the exceptional positions or the first $R$ eligible positions. The first-layer output at position $i$ is therefore determined by $S_i$ and the supports of at most $H{s}^c(cD+R)$ candidate key positions, one set for each possible query activation, head, and key. It depends on at most $c^{\mathrm{\prime }}=c+H{s}^{c}c(cD+R)$ original input positions.

Starting from the restriction in step 1.1, repeatedly recompute the candidate sets in step 2.1 for every still-uncaptured triple. When a triple is captured, retain its current exceptional set and first-$R$ eligible positions as its candidate set. Its assigned cutoff key remains at least as highly scored as every later position in the old eligible ordering, since refinements leave its score fixed and can only decrease other attainable maxima; any position that later leaves the eligible set was already in the retained exceptional set. If some key activation is selected in more than $s^{c}kH$ uncaptured triples, one of its at most $s^c$ possible values is a recorded maximum for more than $kH$ of them. Fix its at most $c$ free input symbols to a support assignment producing that value. The query values of those triples remain unchanged, so all become captured. There are at most $s^{c}Hn$ triples, so this process has at most $s^{c}n\mathrm{/}k$ refinements and fixes at most $s^{c}cn\mathrm{/}k$ additional symbols. Require $k$ large enough that $s^{c}c\mathrm{/}k\le \eta C$. At termination at least $(1-2\eta )Cn$ inputs remain free, and each key activation is selected in at most $T=s^{c}kH$ uncaptured triples.

For each uncaptured triple $t=(i,h,z)$, let $X_t$ be the event that none of its $k$ selected supports is fixed to its recorded maximum-attaining assignment by the random restriction [A1]. An assignment on $r\le c$ free symbols has probability $(q\mathrm{/}s{)}^r\ge (q\mathrm{/}s{)}^c$. The selected supports are pairwise disjoint, so these assignment events are independent and $\mathbb{P}(X_t)\le a^k$, where $a=1-(q\mathrm{/}s{)}^c<1$.

Let $m$ be the number of free inputs after step 3.2 and let $X_0$ be the event that more than $(1+\delta )qm$ of them are fixed by [A1]. For $Z\sim \mathrm{Binomial}(m,q)$ and $\mu =mq$, exponential Markov at $t=\log (1+\delta )$ gives $\mathbb{P}(Z\ge (1+\delta )\mu )\le e^{-t(1+\delta )\mu }(1-q+q{e}^t{)}^m\le e^{-\mu ((1+\delta )\log (1+\delta )-\delta )}\le e^{-{\delta }^2\mu \mathrm{/}3}$. The middle inequality uses $1+u\le e^u$. For the last, $g(\delta )=(1+\delta )\log (1+\delta )-\delta -{\delta }^2\mathrm{/}3$ has $g(0)=0$ and $g^{\mathrm{\prime }}(\delta )=\log (1+\delta )-2\delta \mathrm{/}3\ge 0$ on $[0,1]$, since $\log (1+\delta )\ge 2\delta \mathrm{/}(2+\delta )\ge 2\delta \mathrm{/}3$. Consequently $\mathbb{P}(X_0)\le e^{-\alpha n}$, where $\alpha ={\delta }^{2}q(1-2\eta )C\mathrm{/}3>0$.

For each event $X_t$, take its defining-coordinate set to be the union of its query support and its $k$ selected key supports. Join two $X_t$ events when these sets overlap, and join $X_0$ to every $X_t$. Each coordinate occurs in at most $DH{s}^c$ query supports: at most $D$ position supports contain it, and each such position has at most $H{s}^c$ head-and-query-value triples. It occurs in at most $D{s}^{c}T$ selected key supports: each of at most $D$ position supports has at most $s^c$ possible key activations, and each activation is selected in at most $T$ triples by step 3.2. Each event uses at most $c(k+1)$ coordinates, so its degree is at most $f=1+c(k+1)D(H{s}^c+s^{c}T)=O(k^2)$. Non-neighbours' defining-coordinate sets are disjoint from the event's set; product independence therefore gives independence from every conjunction of their complements, as required by [F2]. Set $x_{X_0}=1\mathrm{/}2$ and $x_{X_t}=1\mathrm{/}{k}^2$. Since $a=1-(q\mathrm{/}s{)}^c<1$ and $f=O(k^2)$, the quantity $k^{-2}(1\mathrm{/}2)(1-k^{-2}{)}^f$ is bounded below by a positive constant times $k^{-2}$ for large $k$, whereas $a^k$ decays exponentially. Thus the local-lemma condition holds for every $X_t$ once $k$ is sufficiently large.

There are at most $s^{c}Hn$ events other than $X_0$. Its local-lemma condition follows if $e^{-\alpha n}\le \frac{1}{2}(1-k^{-2}{)}^{s^{c}Hn}$. Choose $k$ large enough that $s^{c}H[-\log (1-k^{-2})]<\alpha$; the inequality then holds for all sufficiently large $n$. The stage-two, local-event, and $X_0$ requirements are finitely many eventual lower bounds on $k$, so they hold simultaneously for sufficiently large $k$. By [F2], a refinement avoiding $X_0$ and every $X_t$ exists.

Avoiding $X_0$ leaves at least $(1-(1+\delta )q)m\ge (1-(1+\delta )q)(1-2\eta )Cn>C^{\mathrm{\prime }}n$ free inputs by the choices in step 1.1. Avoiding every $X_t$ captures each remaining triple. For a captured triple, its retained cutoff key and candidate set from step 3.2 continue to block every later eligible position; for an uncaptured triple, step 6.1 fixes a cutoff key from its final candidate set. Step 3.1 therefore confines each head's winner to at most $cD+R$ candidate positions for each query value. Taking the union over at most $s^c$ query values and $H$ heads, together with the query support, gives the dependence bound $c^{\mathrm{\prime }}=c+H{s}^{c}c(cD+R)$. Replacing each layer-zero activation by its first-layer output absorbs one layer while preserving the model's restricted computation.

Apply the one-layer reduction successively to the fixed $L$ layers, choosing intermediate fractions $C=C_0>C_1>\cdots >C_L=C^{\mathrm{\prime }}$. Each stage has a finite dependence bound and a finite length threshold. Since $L$ is finite, their maximum threshold is finite; beyond it, the final restriction leaves at least $C^{\mathrm{\prime }}n$ inputs free and the final output depends on a bounded number of original inputs. This proves the Statement.

Let the model have $L$ layers and let $N=n+1$ be the number of input positions for a word of length $n$, including its fixed end marker. Initially each free layer-zero state depends on its own input symbol. For all sufficiently large $n$, at least $0.99N$ positions are free, since only the end-marker position is fixed. Apply [F1] successively through the $L$ layers, using free fractions $0.99=C_0>C_1>\cdots >C_L=0.9$. For every sufficiently large $n$, this gives a restriction leaving at least $0.9N$ free word positions and a constant $c_L$ such that the classification output depends on at most $c_L$ input positions.

Now suppose the model recognizes $2\mathrm{D}\mathrm{Y}\mathrm{C}\mathrm{K}$. Its restriction to the two-symbol subalphabet consisting of one opening bracket and its matching closing bracket would recognize the one-type Dyck language, whose words have equal numbers of opening and closing brackets and nonnegative opening-minus-closing count at every prefix. Fix an even word length $n$, put $N=n+1$, and let $m=\lfloor n\mathrm{/}5\rfloor$. Initially fix the first $m$ word symbols to the opening bracket and the last $m$ word symbols to the closing bracket; leave the middle symbols free and keep the end marker fixed. For all sufficiently large even $n$, at least $0.59N$ positions are free. By [F1], with final free fraction $0.55$, refine this restriction so the model output depends on at most $c_L$ input positions and at least $0.55N$ word positions remain free. If $t$ middle positions were additionally fixed, then $t\le n-2m-0.55N\le 0.06N$ for all sufficiently large $N$. Also $m\ge N\mathrm{/}5-6\mathrm{/}5$, so $m>t$.

Choose $n$ large enough that $0.9N>c_L$. Some free bit position $i$ is not among the at most $c_L$ positions determining the output. Complete the restriction arbitrarily to a word $w$, and let $w^{\mathrm{\prime }}$ be obtained by flipping bit $i$. Their model outputs agree because all input positions on which the output depends agree, but exactly one of $w,w^{\mathrm{\prime }}$ has an even number of ones. Thus no such model classifies all length-$n$ words exactly as $\mathrm{P}\mathrm{A}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{Y}$.

Let $f_o$ be the number of additionally fixed middle symbols that are opening brackets, and let $M=n-2m-t$ be the number of still-free middle positions. Assign an opening bracket to the first $r=n\mathrm{/}2-m-f_o$ still-free positions in their order, and assign a closing bracket to the rest. Since $m+t<n\mathrm{/}2$, we have $r\ge 0$ and $M-r=n\mathrm{/}2-m-t+f_o>0.$ The completed word has exactly $n\mathrm{/}2$ opening brackets, hence total balance zero. A prefix before the last of the assigned free opening brackets has height at least $m-t>0$, because at most $t$ fixed middle symbols are closings. After that last free opening, every still-free middle symbol is a closing. For any later prefix ending in the middle segment, its remaining suffix contains the final $m$ fixed closings and at most $t$ fixed openings, so its net opening-minus-closing count is at most $t-m<0$. Since the whole word has total balance zero, every such middle prefix has positive height. The final $m$ closing brackets decrease the height from $m$ to zero. Thus this completion is a valid one-type Dyck word.

At least $0.55N$ positions remain free, so for sufficiently large $n$ there is a free word position $i$ outside the at most $c_L$ positions determining the model output. Flip its bracket in the valid completion from step 2.2. The new word is unbalanced, while the model output is unchanged because position $i$ does not affect that output. This contradicts recognition of the one-type Dyck language. Any exact recognizer for $2\mathrm{D}\mathrm{Y}\mathrm{C}\mathrm{K}$ would restrict to an exact recognizer for this one-type sublanguage, so no such hard-attention model recognizes $2\mathrm{D}\mathrm{Y}\mathrm{C}\mathrm{K}$.

There are constants $B_k<\mathrm{\infty }$ such that $\mathrm{\parallel }{y}_j^{(k)}{\mathrm{\parallel }}_2\le B_k$ for every position $j$, input length $n$, and input pair. At layer zero this follows from $y_j^{(0)}=v_{x_j}+p_j$ and the bounded token and positional embeddings. If it holds at layer $k-1$, each value vector has norm at most $\mathrm{\parallel }{V}_{k,h}\mathrm{\parallel }{B}_{k-1}$ and each attention output is a convex combination of those values by [F1]; the fixed globally Lipschitz positionwise map is bounded on this resulting bounded set. Induction gives all $B_k$.

Consequently every dot-product score at every layer has absolute value at most some $A_k<\mathrm{\infty }$. For any row with $n$ keys, its softmax weight $a_j$ is at most $e^{2A_k}\mathrm{/}n$, since its numerator is at most $e^{A_k}$ and its denominator is at least $n{e}^{-A_k}$.

We prove by induction on $k$ that for constants $D_k,E_k$ independent of $n$, the changed position satisfies $\mathrm{\parallel }{y}_i^{(k)}-y_i^{\mathrm{\prime }(k)}{\mathrm{\parallel }}_2\le D_k$, while every $j\mathrm{\ne }i$ satisfies $\mathrm{\parallel }{y}_j^{(k)}-y_j^{\mathrm{\prime }(k)}{\mathrm{\parallel }}_2\le E_k\mathrm{/}n$. This holds at $k=0$ because only the bounded token embedding at $i$ changes. Assume it holds at $k-1$ and fix a query position $j\mathrm{\ne }i$ and one head. Its query changes by $O(1\mathrm{/}n)$. Its key at position $i$ can change by $O(1)$, while all other keys change by $O(1\mathrm{/}n)$, using the fixed linear matrices and the induction hypothesis. Hence its score-difference vector $\mathrm{\Delta }$ has $\mathrm{\mid }{\mathrm{\Delta }}_i\mathrm{\mid }\le K$ and $\mathrm{\mid }{\mathrm{\Delta }}_r\mathrm{\mid }\le K\mathrm{/}n$ for $r\mathrm{\ne }i$, for a constant $K$ independent of $n$.

Interpolate the two score vectors linearly. All interpolated scores remain in $[-A_k,A_k]$, so the distinguished key has softmax weight at most $e^{2A_k}\mathrm{/}n$ throughout by step 2.1. For softmax probabilities $a_r(t)$, differentiation gives $a_r^{\mathrm{\prime }}(t)=a_r(t)({\mathrm{\Delta }}_r-{\sum }_s{a}_s(t){\mathrm{\Delta }}_s)$; therefore ${\sum }_r\mathrm{\mid }{a}_r^{\mathrm{\prime }}(t)\mathrm{\mid }\le 2{\sum }_r{a}_r(t)\mathrm{\mid }{\mathrm{\Delta }}_r\mathrm{\mid }=O(1\mathrm{/}n)$, and integration yields $\mathrm{\parallel }a-a^{\mathrm{\prime }}{\mathrm{\parallel }}_1=O(1\mathrm{/}n)$.

The head values are uniformly bounded by step 1.1. Splitting the difference of the two weighted sums into (i) the change of values under the first attention row and (ii) the change of attention weights applied to the second value list gives $\mathrm{\parallel }{b}_{j,k,h}-b_{j,k,h}^{\mathrm{\prime }}{\mathrm{\parallel }}_2=O(1\mathrm{/}n)$: the changed value at $i$ has weight $O(1\mathrm{/}n)$, all other value changes are $O(1\mathrm{/}n)$, and the total weight change is $O(1\mathrm{/}n)$ by step 4.1. The positionwise map is Lipschitz, so $\mathrm{\parallel }{y}_j^{(k)}-y_j^{\mathrm{\prime }(k)}{\mathrm{\parallel }}_2=O(1\mathrm{/}n)$ for every $j\mathrm{\ne }i$. At $j=i$, boundedness from step 1.1 gives a constant difference. This proves the induction claim.

Since $i<n$, the induction bound gives $\mathrm{\parallel }{y}_n^{(L)}-y_n^{\mathrm{\prime }(L)}{\mathrm{\parallel }}_2\le E_L\mathrm{/}n$. For a logit perturbation $\mathrm{\Delta }$, the softmax derivative is $p_r({\mathrm{\Delta }}_r-{\sum }_s{p}_s{\mathrm{\Delta }}_s)$, whose ${\mathrm{\ell }}^1$ norm is at most $2\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_{\mathrm{\infty }}\le 2\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_2$; hence the prediction probabilities differ by at most a constant times $1\mathrm{/}n$. Taking $C=E_L$ completes the hidden-state bound and supplies the stated probability bound.