Hard-attention depth reduction under input restrictions

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.