proofs
Provedunbiased-attentionend-to-endsoftmaxlower-bound

Unbiased two-point bound: unbiased z₁, z₂ (variance ≤ V) agreeing outside an event of mass q satisfy |o₁ − o₂|(1 − q) ≤ 2√(qV)

For all Ω∈Type⁡\htmlData{mx=1}{\Omega \in \htmlData{mx=0}{\operatorname{Type}}}, w,z1,z2:Ω→R\htmlData{mx=3}{w, z_{1}, z_{2} : \htmlData{mx=0}{\Omega} \mathrel{\htmlData{mx=2}{\to}} \htmlData{mx=1}{\mathbb{R}}}, A:Ω→Prop⁡\htmlData{mx=3}{A : \htmlData{mx=0}{\Omega} \mathrel{\htmlData{mx=2}{\to}} \htmlData{mx=1}{\operatorname{Prop}}} and o1,o2,q,V∈R\htmlData{mx=1}{o_{1}, o_{2}, q, V \in \htmlData{mx=0}{\mathbb{R}}}, if ∀ω, 0≤w(ω)\htmlData{mx=4}{\forall \omega,\ 0 \mathrel{\htmlData{mx=3}{\leq}} \htmlData{mx=2}{\htmlData{mx=0}{w}(\htmlData{mx=1}{\omega})}}, ∑ωw(ω)=1\htmlData{mx=3}{\sum_{\omega} \htmlData{mx=2}{\htmlData{mx=0}{w}(\htmlData{mx=1}{\omega})}} \mathrel{\htmlData{mx=4}{=}} 1, ∑ω∈filter⁡(A)w(ω)=q\htmlData{mx=6}{\sum_{\omega \in \htmlData{mx=2}{\htmlData{mx=0}{\operatorname{filter}}(\htmlData{mx=1}{A})}} \htmlData{mx=5}{\htmlData{mx=3}{w}(\htmlData{mx=4}{\omega})}} \mathrel{\htmlData{mx=8}{=}} \htmlData{mx=7}{q}, ∑ωw(ω)⋅z1(ω)=o1\htmlData{mx=7}{\sum_{\omega} \htmlData{mx=6}{\htmlData{mx=2}{\htmlData{mx=0}{w}(\htmlData{mx=1}{\omega})} \cdot \htmlData{mx=5}{\htmlData{mx=3}{z_{1}}(\htmlData{mx=4}{\omega})}}} \mathrel{\htmlData{mx=9}{=}} \htmlData{mx=8}{o_{1}}, ∑ωw(ω)⋅z2(ω)=o2\htmlData{mx=7}{\sum_{\omega} \htmlData{mx=6}{\htmlData{mx=2}{\htmlData{mx=0}{w}(\htmlData{mx=1}{\omega})} \cdot \htmlData{mx=5}{\htmlData{mx=3}{z_{2}}(\htmlData{mx=4}{\omega})}}} \mathrel{\htmlData{mx=9}{=}} \htmlData{mx=8}{o_{2}}, ∑ωw(ω)⋅(z1(ω)−o1)2≤V\htmlData{mx=10}{\sum_{\omega} \htmlData{mx=9}{\htmlData{mx=2}{\htmlData{mx=0}{w}(\htmlData{mx=1}{\omega})} \cdot \htmlData{mx=8}{(\htmlData{mx=7}{\htmlData{mx=5}{\htmlData{mx=3}{z_{1}}(\htmlData{mx=4}{\omega})} - \htmlData{mx=6}{o_{1}}})^{2}}}} \mathrel{\htmlData{mx=12}{\leq}} \htmlData{mx=11}{V}, ∑ωw(ω)⋅(z2(ω)−o2)2≤V\htmlData{mx=10}{\sum_{\omega} \htmlData{mx=9}{\htmlData{mx=2}{\htmlData{mx=0}{w}(\htmlData{mx=1}{\omega})} \cdot \htmlData{mx=8}{(\htmlData{mx=7}{\htmlData{mx=5}{\htmlData{mx=3}{z_{2}}(\htmlData{mx=4}{\omega})} - \htmlData{mx=6}{o_{2}}})^{2}}}} \mathrel{\htmlData{mx=12}{\leq}} \htmlData{mx=11}{V} and ∀ω, ¬A(ω)  ⟹  z1(ω)=z2(ω)\htmlData{mx=12}{\forall \omega,\ \htmlData{mx=3}{\lnot \htmlData{mx=2}{\htmlData{mx=0}{A}(\htmlData{mx=1}{\omega})}} \mathrel{\htmlData{mx=11}{\implies}} \htmlData{mx=6}{\htmlData{mx=4}{z_{1}}(\htmlData{mx=5}{\omega})} \mathrel{\htmlData{mx=10}{=}} \htmlData{mx=9}{\htmlData{mx=7}{z_{2}}(\htmlData{mx=8}{\omega})}} (given Fintype⁡ Ω\htmlData{mx=2}{\htmlData{mx=0}{\operatorname{Fintype}}\,\htmlData{mx=1}{\Omega}} and DecidablePred⁡ A\htmlData{mx=2}{\htmlData{mx=0}{\operatorname{DecidablePred}}\,\htmlData{mx=1}{A}}), then

∣o1−o2∣⋅(1−q)≤2q⋅V\htmlData{mx=6}{\htmlData{mx=3}{\left\lvert \htmlData{mx=2}{\htmlData{mx=0}{o_{1}} - \htmlData{mx=1}{o_{2}}} \right\rvert} \cdot (\htmlData{mx=5}{1 - \htmlData{mx=4}{q}})} \mathrel{\htmlData{mx=12}{\leq}} \htmlData{mx=11}{2\htmlData{mx=10}{\sqrt{\htmlData{mx=9}{\htmlData{mx=7}{q} \cdot \htmlData{mx=8}{V}}}}}
What the notation means · or point at any symbol
Type
Type: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (Type)
Fintype
Fintype: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (Fintype)
f(x)Function application
Fintype applied to Ω. Lean writes f x; papers write f(x). (Fintype Ω)
⟹Implies
If Ω, then ℝ. (Between types, A → B is the type of functions from A to B.) (Ω → ℝ)
x : TVariables
w, z₁, z₂ range over Ω → ℝ: the statement must hold for every choice. ((w z₁ z₂ : Ω → ℝ))
DecidablePred
DecidablePred: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (DecidablePred)
x ∈ TVariables
o₁, o₂, q, V range over real numbers: the statement must hold for every choice. ((o₁ o₂ q V : ℝ))
∀For all
The statement after the comma holds for every ω. (∀ ω, 0 ≤ w ω)
∑Summation
Add up w(ω) for every ω. (∑ ω, w ω)
=Equality
∑ ω, w(ω) and 1 are the same. (∑ ω, w ω = 1)
|x|Absolute value
The size of o₁ − o₂ without its sign. (|o₁ - o₂|)
RReal numbers
The real numbers: every point on the number line. (ℝ)
Prop
Prop: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (Prop)
≤At most
0 is less than or equal to w(ω). (0 ≤ w ω)
·Multiplication
w(ω) times z₁(ω). (w ω * z₁ ω)
¬Not
It is not the case that A(ω). (¬ A ω)
filter
Finset.univ.filter: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (Finset.univ.filter)
aᵇPower
z₁(ω) − o₁ raised to the power 2. ((z₁ ω - o₁) ^ 2)
-Subtraction
z₁(ω) minus o₁. On ℕ, Lean's subtraction stops at 0: 2 − 5 = 0. (z₁ ω - o₁)
√Square root
The non-negative number whose square is q · V. (Real.sqrt (q * V))

Suggested by the external reviewer; strengthens ua-two-point-lower-bound from worst-case MSE to any pair of unbiased estimators. Consequence: an exactly unbiased attention estimator must read a key that changes the output by Δ with probability ≥ Δ²(1−q)²/(4V) — exact unbiasedness forces positive read probability on every influential key, so with the random-plant hitting bound the Ω(min(n, e^R)) draws-per-row floor applies to unbiased samplers. Part of 'Unbiased randomized attention: cost x variance thresholds' (end-to-end composition round).

How it was proved

Proved
4 October 2026
By
Ajax, with the agent “Baguette math & proofs (Claude Code, 2026-10-03)”
Checked by
Lean's kernel (Lean 4.33.1, with Mathlib); the proof is signed and replays offline
Axioms
Classical.choice, Quot.sound, propext
Proof
64 lines of Lean
Sign in to see the proofThe proof, its signed report and its history.

More proved statements