Hard and soft attention limits for formal-language prediction

For PARITY, whose members are the bit strings with an even number of $1$s, no fixed finite-depth hard-attention sequence model with fixed parameters recognizes every sufficiently long input exactly. For 2DYCK, whose words are correctly balanced and properly nested strings over two bracket types, no such hard-attention model recognizes the language. In both cases the model appends an end marker before classification.

For all soft-attention conclusions below, fix the parameter matrices, depth, and number of heads independently of length; use scaled dot-product scores with fixed linear query/key/value maps, uniformly bounded token and positional embeddings combined by addition, globally Lipschitz positionwise maps, and a fixed globally Lipschitz logit readout followed by softmax. Under these one-symbol influence assumptions, the parity source process with fixed $p\in (0,1)$ has sharp unigram cross-entropy level

Every such predictor has limiting lower cross-entropy at least $H(u)$, and the constant predictor $u$ attains it.

For the 2DYCK PCFG with rules $S\to (S)S$ and $S\to [S]S$ each of probability $p\mathrm{/}2$, and $S\to ϵ$ of probability $1-p$, fix any $p\in (0,1)$. Read its left-to-right output as a finite or infinite bracket stream; sample a length-$k$ prefix conditional on at least $k$ bracket tokens having been emitted, and predict the ordinary next token, without conditioning on exact total length. Every fixed soft-attention predictor satisfying these one-symbol influence assumptions has

where ${\mathcal{L}}_{p,k}$ is its expected next-token cross-entropy under this prefix law and ${\mathcal{L}}_{p,k}^{\ast }$ is the corresponding optimal conditional cross-entropy.

The PCFG is a probability law on finite words precisely when $p\le 1\mathrm{/}2$. For all $p\in (0,1)$ its finite output can instead be conditioned on eventual termination. For that finite-word probability law, sample prefixes conditional on reaching length $k$ and predict the next token without any additional length conditioning. The same positive-gap conclusion holds with $p$ replaced by $a=\min (p,1-p)$:

For $p\le 1\mathrm{/}2$ these two prefix laws agree. At $p=1\mathrm{/}2$ finite words have infinite expected length, but the prefix bounds still hold. For $p>1\mathrm{/}2$ the first law includes nonterminating streams and the second conditions them away; neither is an unconditioned probability distribution on finite words with the original parameter $p$. These are cross-entropy limits, not exact-classification impossibility theorems.

Hahn, §§5–6: hard-attention language limits and soft-attention prediction bounds

A nonfinal token has inverse-length influence under bounded soft attention: the precise bounded dot-product model and globally Lipschitz readout followed by softmax.

Paired-prefix lower bound for soft-attention 2DYCK prediction: the paired-prefix soft-attention gap.

Exact 2DYCK PCFG prefix laws and positive paired-prefix mass: exact stream and finite-word prefix laws and a uniform equal-mass pairing.

The explicit prefix-sampling law resolves the conditioning left implicit in Hahn's Theorem 6. Its finite-mean Markov-chain sketch is unnecessary: extending any surviving prefix by two openings and the matching inner close supplies positive paired mass directly. Exact-total-length conditioning is a different prediction problem; its next-token probabilities are not generally $p\mathrm{/}2,p\mathrm{/}2,1-p$. The fixed-length universality theorem concerns a separate regime with resources allowed to grow.