LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck pendingjudge pass (gpt-6-luna)

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.

Close paired predictions incur mixture entropy

Statement

Let $Σ$ be a finite alphabet of size $m \geq 1$ . Let $r, s, q, q^{'}$ be probability vectors on $Σ$ , and let $ϵ \geq 0$ satisfy $∥ q - q^{'} ∥_{1} \leq ϵ$ . For $CE (r, q) = - \sum_{a} r (a) \log q (a)$ , with value $+ \infty$ if $r (a) > 0 = q (a)$ , and $H (r) = - \sum_{a : r (a) > 0} r (a) \log r (a)$ , the paired loss satisfies

\frac{1}{2} CE (r, q) + \frac{1}{2} CE (s, q^{'}) \geq H ⁣ (\frac{r + s}{2}) - \log (1 + m ϵ) .

In particular, predictions whose $ℓ^{1}$ distance tends to zero cannot have asymptotic paired loss below the entropy of the mean target law.

Statement references

Hahn, §6: paired next-token distributions and cross-entropy lower bounds

Facts & Assumptions

Given: Probability vectors $r, s, q, q^{'}$ on a finite alphabet, with $∥ q - q^{'} ∥_{1} \leq ϵ$ .

Proof

1.1givenconstructalgebra

Put $\overset{ˉ}{r} = (r + s) / 2$ and $\overset{ˉ}{q} = (q + q^{'}) / 2$ . For every $a \in Σ$ , $q (a) \leq \overset{ˉ}{q} (a) + ϵ$ and $q^{'} (a) \leq \overset{ˉ}{q} (a) + ϵ$ . Define $w (a) = (\overset{ˉ}{q} (a) + ϵ) / (1 + m ϵ)$ ; its coordinates are nonnegative and sum to one. Monotonicity of $- \log$ on positive reals gives $\frac{1}{2} CE (r, q) + \frac{1}{2} CE (s, q^{'}) \geq CE (\overset{ˉ}{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.

2.1step 1.1givenalgebra∎

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

Used by

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

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