TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pending

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Fixed soft attention has no parity advantage over the unigram predictor

Statement

Fix $p \in (0, 1)$ . Generate a bit string by a two-state process whose state is the parity of the number of emitted $1$ s: in the even state it terminates with probability $p$ , and otherwise emits $0$ or $1$ with probability $(1 - p) / 2$ each; in the odd state it emits $0$ or $1$ with probability $1 / 2$ each and cannot terminate. For each $n \geq 2$ , let $D_{n}$ be the law of length- $(n - 1)$ prefixes conditional on the process emitting at least $n - 1$ bits, and ask a fixed soft-attention model to predict the next symbol in ${e o s, 0, 1}$ from that prefix followed by the end marker. Let $r_{x}$ be the true next-symbol distribution and let $q_{n} (x)$ be the model's predicted distribution. Define cross-entropy by $CE (r, q) = - \sum_{a} r (a) \log q (a)$ , with value $+ \infty$ if $r (a) > 0 = q (a)$ , and entropy by $H (r) = - \sum_{a : r (a) > 0} r (a) \log r (a)$ . Then every fixed soft-attention model satisfying the one-symbol influence hypotheses has

${lim inf}_{n \to \infty} E_{x \sim D_{n}} CE (r_{x}, q_{n} (x)) \geq H (u), u (e o s) = p / 2, u (0) = u (1) = (2 - p) / 4.$ A constant predictor $q_{n} (x) = u$ attains $H (u)$ for every $n$ , so $H (u)$ is the sharp unigram chance level. An arbitrary fixed predictor may have greater cross-entropy; this result gives no soft-attention exact-classification impossibility theorem.

Statement references

Hahn, §6: the parity automaton, next-token targets, and the soft-attention parity limit

Facts & Assumptions

Given: The parity source process and prefix law in the Statement, and a fixed soft-attention next-token predictor satisfying the one-symbol influence hypotheses.

[F1]

Changing one nonfinal token changes the predicted next-token probability vector by at most $C / n$ for a constant independent of $n$ (A nonfinal token has inverse-length influence under bounded soft attention).

[F2]

The model reads an end marker at its final input position, and the last bit of the prefix is therefore a nonfinal input token (Hard and soft attention sequence models).

[F3]

If two next-token predictions differ by at most $ϵ$ in $ℓ^{1}$ , their average cross-entropy on target laws $r, s$ is at least $H ((r + s) / 2) - \log (1 + ∣ Σ ∣ ϵ)$ (Close paired predictions incur mixture entropy).

Proof

1.1givenalgebra

If a prefix $x$ has even parity, its next-symbol distribution is $r_{e} = (p, (1 - p) / 2, (1 - p) / 2)$ in the coordinate order $(e o s, 0, 1)$ . If it has odd parity, the distribution is $r_{o} = (0, 1 / 2, 1 / 2)$ . Their equal mixture is $u = (r_{e} + r_{o}) / 2$ with the coordinates stated.

1.2givenconstructalgebra

Pair each prefix $w 0$ with $w 1$ , where $w$ has length $n - 2$ . Both extensions have equal probability: their shared first $n - 2$ symbols fix the same pre-emission parity, and the source emits the final bit values with equal probability in either state, conditional on emitting a bit. Each pair contains one even and one odd prefix; conditioning on length at least $n - 1$ uses one common normalizing constant, so the two members still have equal $D_{n}$ mass.

2.1step 1.1step 1.2F1F2

Let $q = q_{n} (w 0)$ and $q^{'} = q_{n} (w 1)$ , and let $r, r^{'}$ be their respective target laws. The pair $(r, r^{'})$ equals $(r_{e}, r_{o})$ or $(r_{o}, r_{e})$ according to the parity of $w$ . By [F1]–[F2], $∥ q - q^{'} ∥_{1} \leq C / n$ . The pair's mean cross-entropy is $\frac{1}{2} CE (r, q) + \frac{1}{2} CE (r^{'}, q^{'})$ ; its mean target is $u$ in either order, so the symmetric bound [F3] applies.

3.1step 2.1step 1.1F3algebra

Applying [F3] with $ϵ = C / n$ bounds the pair mean cross-entropy below by $H (u) - \log (1 + 3 C / n)$ , which tends to $H (u)$ .

4.1step 3.1step 1.2algebra∎

Every prefix pair has the same limiting lower bound from step 3.1. Averaging over the equal-mass pairs in step 1.2 proves the expected cross-entropy lower bound. The constant predictor $u$ has expected loss $H (u)$ because the paired target marginal is $u$ . It is realized within the stated model class as follows: let $e_{1}$ be the first coordinate vector, take $v_{a} = e_{1}$ and $p_{i} = 0$ for every token and position, choose zero query, key, and value maps, and let every positionwise map be the constant map with value $e_{1}$ . These choices obey the additive convention, boundedness, and global Lipschitz hypotheses, and give final hidden state $e_{1}$ at every position. Choose the fixed linear readout whose row for token $a$ is $(\log u (a)) e_{1}^{T}$ ; its logits at the final state are exactly $\log u$ , so softmax gives $u$ . Thus the lower bound is sharp, while no upper bound at $H (u)$ is asserted for every fixed model.

Depends on

Used by

Dependency tree · two levels

5 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Hahn, Theoretical Limitations of Self-Attention in Neural Sequence Models, §6, Theorem 6 proof (standard reference, not scraped)