Provedunbiased-attentionrandomized-algorithmssoftmaxaggregate
Sum of attention outputs: NO rows each ≤ D/(8n), ≥ D YES rows each ≥ 1/2 ⇒ YES sum ≥ 4 × NO sum
For all , , and , if , , , , and , then
What the notation means · or point at any symbol
- NNatural numbers
- The natural numbers 0, 1, 2, …. In Lean they start at 0. (
ℕ) - Fin
- Fin: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (
Fin) - f(x)Function application
- Fin applied to n. Lean writes f x; papers write f(x). (
Fin n) - ⟹Implies
- If Fin(n), then ℝ. (Between types, A → B is the type of functions from A to B.) (
Fin n → ℝ) - x : TVariables
- oNo, oYes range over Fin n → ℝ: the statement must hold for every choice. (
(oNo oYes : Fin n → ℝ)) - Finset
- Finset: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (
Finset) - <Less than
- 0 is strictly smaller than n. (
0 < n) - ≤At most
- 0 is less than or equal to D. (
0 ≤ D) - ∀For all
- The statement after the comma holds for every i. (
∀ i, oNo i ≤ D / (8 * n)) - card
- Y.card: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (
Y.card) - ∑Summation
- Add up oNo(i) for every i. (
∑ i, oNo i) - RReal numbers
- The real numbers: every point on the number line. (
ℝ) - a/bDivision
- D divided by 8 · n. In Lean, dividing by 0 gives 0. (
D / (8 * n)) - ·Multiplication
- 8 times n. (
8 * n)
theorem ua-sum-of-outputs-separation {n : ℕ} (oNo oYes : Fin n → ℝ) (Y : Finset (Fin n)) (D : ℝ) (hn : 0 < n) (hD : 0 ≤ D) (hno : ∀ i, oNo i ≤ D / (8 * n)) (hY : D ≤ Y.card) (hyes : ∀ i ∈ Y, 1 / 2 ≤ oYes i) (hpos : ∀ i, 0 ≤ oYes i) :
4 * ∑ i, oNo i ≤ ∑ i, oYes iAggregates of attention OUTPUTS (ratios, the building blocks of the SGD gradient), not just partition functions: a constant-factor estimate of Σ_i o_i separates the multiplicity gadget's YES and NO instances. Part of 'Unbiased randomized attention: cost x variance thresholds', round 14 (aggregates of attention outputs).
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
- 20 lines of Lean
Sign in to see the proofThe proof, its signed report and its history.