Provedquery-cover-lawdecode-attentionsoftmaxkv-cache

With acceptance ≥ e^{−2η} and η ≤ 1/2, the expected proposals per exact sample is ≤ e

For all $\htmlData{mx=1}{p, \eta \in \htmlData{mx=0}{\mathbb{R}}}$ , if $\htmlData{mx=0}{\eta} \mathrel{\htmlData{mx=2}{\leq}} \htmlData{mx=1}{\frac{1}{2}}$ and $\htmlData{mx=3}{e^{\htmlData{mx=2}{\htmlData{mx=0}{-2} \cdot \htmlData{mx=1}{\eta}}}} \mathrel{\htmlData{mx=5}{\leq}} \htmlData{mx=4}{p}$ , then

\htmlData{mx=1}{\frac{1}{\htmlData{mx=0}{p}}} \mathrel{\htmlData{mx=3}{\leq}} \htmlData{mx=2}{e^{1}}

What the notation means · or point at any symbol

RReal numbers: The real numbers: every point on the number line. (ℝ)
x ∈ TVariables: p, η range over real numbers: the statement must hold for every choice. ((p η : ℝ))
≤At most: η is less than or equal to 1/2. (η ≤ 1 / 2)
eˣExponential function: e raised to the power −2 · η, where e ≈ 2.718. (Real.exp (-2 * η))
a/bDivision: 1 divided by 2. In Lean, dividing by 0 gives 0. (1 / 2)
−xNegation: The negative of 2. (-2)
·Multiplication: −2 times η. (-2 * η)

theorem qc-expected-proposals (p η : ℝ) (hη : η ≤ 1 / 2) (hp : Real.exp (-2 * η) ≤ p) :
    1 / p ≤ Real.exp 1

So each exact sample costs O(1) alias-table draws and dot products. Part of 'The Query-Cover Law: decode attention cost is set by where the queries go, not by how long the context is'.

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: 16 lines of Lean

With acceptance ≥ e^{−2η} and η ≤ 1/2, the expected proposals per exact sample is ≤ e

How it was proved

More proved statements