Provedquery-cover-lawdecode-attentionsoftmaxkv-cache
Bucketed tilt proposal along a direction u: bucket b w.p. ∝ W_b e^{a z_b}, then j ∝ π₀ inside ⇒ P(j) ∝ π₀(j) e^{a z_{b(j)}}
For all , , , , and , if , then
What the notation means · or point at any symbol
- NNatural numbers
- The natural numbers 0, 1, 2, …. In Lean they start at 0. (
ℕ) - x ∈ TVariables
- n, B range over natural numbers: the statement must hold for every choice. (
(n B : ℕ)) - 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 Fin(B). (Between types, A → B is the type of functions from A to B.) (
Fin n → Fin B) - ∀For all
- The statement after the comma holds for every i. (
∀ i, 0 < π0 i) - a/bDivision
- (∑ i, π0(i)) · exp(a · zc(bk(j))) divided by ∑ b, (∑ i, π0(i)) · exp(a · zc(b)). In Lean, dividing by 0 gives 0. (
(∑ i ∈ Finset.univ.filter (fun i => bk …) - ∑Summation
- Add up π0(i) for each i in filter(i ↦ bk(i) = bk(j)). (
∑ i ∈ Finset.univ.filter (fun i => bk i…) - <Less than
- 0 is strictly smaller than π0(i). (
0 < π0 i) - RReal numbers
- The real numbers: every point on the number line. (
ℝ) - 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) - x ↦ f(x)Function (λ-abstraction)
- The function sending i to bk(i) = bk(j). Lean writes fun x => …; papers write x ↦ …. (
fun i => bk i = bk j) - =Equality
- bk(i) and bk(j) are the same. (
bk i = bk j) - eˣExponential function
- e raised to the power a · zc(bk(j)), where e ≈ 2.718. (
Real.exp (a * zc (bk j))) - ·Multiplication
- a times zc(bk(j)). (
a * zc (bk j))
theorem qs-bucket-proposal {n B : ℕ} (bk : Fin n → Fin B) (π0 : Fin n → ℝ) (zc : Fin B → ℝ) (a : ℝ) (j : Fin n) (hπ : ∀ i, 0 < π0 i) :
((∑ i ∈ Finset.univ.filter (fun i => bk i = bk j), π0 i) * Real.exp (a * zc (bk j)) / ∑ b, (∑ i ∈ Finset.univ.filter (fun i => bk i = b), π0 i) * Real.exp (a * zc b)) * (π0 j / ∑ i ∈ Finset.univ.filter (fun i => bk i = bk j), π0 i) = π0 j * Real.exp (a * zc (bk j)) / ∑ i, π0 i * Real.exp (a * zc (bk i))Counterexample to the Query-Cover lower bound: for a rank-1 decode trajectory q_t = q₀ + a_t u, precompute z_j = ⟨u, k_j⟩ once and bucket keys by z. Each query then gets a proposal in O(#buckets) time that is a snapshot-tilt with log-ratio ≤ A·w to the true row, so rejection gives exact samples without any new full pass. 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
- 21 lines of Lean
Sign in to see the proofThe proof, its signed report and its history.