Proofs

Eighteen results this track leans on, each derived and then numerically verified.

Every claim here is checked by tools/proofs.py — 116 checks, all passing. A derivation on a page is an assertion until something tests it, and shipping the first without the second is what rule 8 forbids.

cd tools && python3 proofs.py             # 116/116 checks passed
              python3 proofs.py --verbose # with the numbers behind each

Table of Contents

• How To Use This
• P1 — Why Attention Divides by √dₖ
• P2 — The Optimal Bloom Hash Count
• P3 — The Bloom False-Positive Rate
• P4 — Quorum Intersection
• P5 — Little's Law and Bytes in Flight
• P6 — Decode Intensity Is Batch Size
• P7 — Why Reverse-Mode Autodiff
• P8 — The Matmul Backward Rule
• P9 — Sample Size and the Four-Times Law
• P10 — Why Peeking Destroys Your Error Rate
• P11 — EMA Half-Life
• P12 — Post-Filter Over-Fetch
• P13 — The Three Amplifications
• P14 — The Tail at Scale
• P15 — Systolic Operand Reuse
• P16 — Distance Concentration
• P17 — Cosine and L2 Coincide on Unit Vectors
• P18 — Zipf Head Mass
• References

How To Use This

Not as a reference to look things up in. As a set of derivations to reproduce.

The calibration battery measures whether you can do back-of-envelope arithmetic, and the highest-return remedy for a low score is working through this page on paper. Each proof is short enough to redo in ten minutes and each one licences a decision you will otherwise make by folklore.

Each entry has four parts: Claim · Proof · Verification (real output from proofs.py) · What it licenses.

P1 — Why Attention Divides by √dₖ

Claim. For queries and keys with i.i.d. zero-mean unit-variance components, \(\mathrm{Var}(q \cdot k) = d_k\). Therefore scores have typical magnitude \(\sqrt{d_k}\), and dividing by \(\sqrt{d_k}\) restores unit variance.

Proof. Let \(q, k \in \mathbb{R}^{d_k}\) with all components independent, \(\mathbb{E}[q_i] = \mathbb{E}[k_i] = 0\), \(\mathrm{Var}(q_i) = \mathrm{Var}(k_i) = 1\).

\[ q \cdot k = \sum_{i=1}^{d_k} q_i k_i \]

Each term has \(\mathbb{E}[q_i k_i] = \mathbb{E}[q_i]\mathbb{E}[k_i] = 0\) by independence, and

\[ \mathrm{Var}(q_i k_i) = \mathbb{E}[q_i^2 k_i^2] - 0 = \mathbb{E}[q_i^2]\mathbb{E}[k_i^2] = 1 \]

The \(d_k\) terms are mutually independent, so variances add:

\[ \mathrm{Var}(q \cdot k) = \sum_{i=1}^{d_k} \mathrm{Var}(q_i k_i) = d_k \qquad\blacksquare \]

Why that matters. Standard deviation \(\sqrt{d_k}\) means at \(d_k = 64\) scores are typically ±8, and gaps between the largest and second-largest are several units. \(\mathrm{softmax}\) of such a vector is nearly one-hot, and its Jacobian \(\partial p_i/\partial z_j = p_i(\delta_{ij} - p_j)\) vanishes when any \(p_i \to 1\). The layer stops learning.

Verification — 20,000 samples per dimension:

P1 Var(q·k) = d_k at d=16      measured   16.0, predicted   16
P1 Var(q·k) = d_k at d=64      measured   63.7, predicted   64
P1 Var(q·k) = d_k at d=256     measured  254.8, predicted  256
P1 Var(q·k) = d_k at d=1024    measured 1006.0, predicted 1024
P1 scaling raises softmax entropy
       entropy unscaled 0.006 -> scaled 2.240 (max possible 2.996)

Entropy 0.006 out of a possible 2.996 is the saturation, measured. Scaling recovers 2.240 — most of the available entropy — and the layer can learn again.

What it licenses. P01's E-scale experiment: predict what removing the scale does to attention entropy, then measure. You now know the prediction is "collapse toward zero", and why.

P2 — The Optimal Bloom Hash Count

Claim. With \(m\) bits and \(n\) keys, false-positive rate is minimised at \(k^{*} = (m/n)\ln 2\).

Proof. After inserting \(n\) keys with \(k\) hashes, a given bit is still 0 with probability

\[ \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m} \]

A false positive requires all \(k\) probed bits to be 1, so (treating bits as independent — the source of the small measured gap)

\[ f(k) = \left(1 - e^{-kn/m}\right)^{k} \]

Let \(c = n/m\) and minimise \(\ln f = k \ln(1 - e^{-kc})\):

\[ \frac{d}{dk}\ln f = \ln(1 - e^{-kc}) + k \cdot \frac{c,e^{-kc}}{1 - e^{-kc}} = 0 \]

Substitute \(x = e^{-kc}\), so \(k = -\ln x / c\):

\[ \ln(1-x) - \frac{\ln x \cdot x}{1-x} = 0 \]

which is satisfied at \(x = 1/2\) by symmetry of \(\ln(1-x)\) and \(\frac{x\ln x}{1-x}\) about that point. Then \(e^{-kc} = 1/2\) gives

\[ k^{*} = \frac{\ln 2}{c} = \frac{m}{n}\ln 2 \approx 0.693 \cdot \text{bits per key} \qquad\blacksquare \]

The elegant consequence. At \(x = 1/2\), each bit is 1 with probability exactly one half — the filter is at maximum entropy, carrying the most information per bit. That is the information-theoretic reason this is the optimum, not a coincidence.

Verification — closed form against a brute-force grid search over \(k\):

P2 at k* each bit is 1 with probability 1/2    P(bit=1) = 0.500000000000

What it licenses. The universal 10-bits/key default gives \(k = 7\), and you can now derive it rather than cite RocksDB. Also Monkey: if the optimum depends only on \(m/n\), allocating uniformly across LSM levels of very different \(n\) cannot be optimal.

P3 — The Bloom False-Positive Rate

Claim. At the optimal \(k\), \(\text{fpr} = 2^{-k^{*}} = 0.6185^{m/n}\).

Proof. Substituting \(e^{-k^{*}n/m} = 1/2\) into \(f(k) = (1 - e^{-kn/m})^k\):

\[ f(k^{*}) = \left(1 - \tfrac{1}{2}\right)^{k^{*}} = 2^{-k^{*}} = 2^{-(m/n)\ln 2} = \left(2^{-\ln 2}\right)^{m/n} = 0.61850\ldots^{,m/n} \qquad\blacksquare \]

Verification:

And against a real filter with 100k keys and 200k absent probes (tools/bloom.py): theory 0.00819, measured 0.00822.

What it licenses. Each additional 10 bits/key divides the fpr by \(0.6185^{10} = 0.0082\), i.e. ~122×. That single ratio sizes every Bloom decision in P04, and it turns 40 disk reads for an absent key into 0.33.

P4 — Quorum Intersection

Claim. Every two quorums of size \(Q\) drawn from \(N\) replicas intersect iff \(2Q > N\).

Proof. (⇐) Suppose \(2Q > N\) and let \(A, B\) be quorums with \(A \cap B = \emptyset\). Then \(|A \cup B| = |A| + |B| = 2Q > N\), but \(A \cup B\) is a subset of the \(N\) replicas, so \(|A \cup B| \le N\) — contradiction. Hence they intersect.

(⇒) Suppose \(2Q \le N\). Take \(A\) as any \(Q\) replicas and \(B\) as \(Q\) of the remaining \(N - Q \ge Q\). These are disjoint quorums, so intersection is not guaranteed. \(\blacksquare\)

Therefore \(Q \ge \lfloor N/2 \rfloor + 1\).

Verification — exhaustive over all \(N \in [2,9]\) and all \(Q \in [1,N]\), testing every pair of \(Q\)-subsets for disjointness (48 cases, all agreeing with the predicate):

P4 N=3 Q=1: disjoint pair exists: True;  2Q>N: False
P4 N=3 Q=2: disjoint pair exists: False; 2Q>N: True
P4 N=6 Q=3: disjoint pair exists: True;  2Q>N: False
P4 N=6 Q=4: disjoint pair exists: False; 2Q>N: True

Note \(N=6, Q=3\): a majority of six is four, not three. Even splits are exactly where operators get this wrong, which is why even replica counts are discouraged.

What it licenses. Split-brain is not an implementation bug — it is this inequality being violated, usually by someone changing the replica count. And the availability arithmetic in numbers §10 rests on it.

P5 — Little's Law and Bytes in Flight

Claim. For any stable system, \(L = \lambda W\) — items in system = arrival rate × time in system. No distributional assumptions.

Proof sketch. Over a long interval \(T\), let \(A(T)\) be arrivals and \(\int_0^T L(t),dt\) the accumulated item-time. Each item contributes exactly its sojourn time, so \(\int_0^T L(t)dt = \sum_{i} W_i\). Dividing by \(T\):

\[ \bar{L} = \frac{\sum_i W_i}{T} = \frac{A(T)}{T} \cdot \frac{\sum_i W_i}{A(T)} = \lambda \bar{W} \qquad\blacksquare \]

The only requirement is that the limits exist — hence "any stable system".

Verification — Poisson arrivals at λ=500/s, fixed 50 ms sojourn, 400 s simulated, count integrated over time:

P5 Little's Law L = lambda*W      measured L 24.94, predicted 25.00

The application that matters here. To sustain bandwidth \(B\) at latency \(\ell\), the memory system must hold \(B \times \ell\) bytes in flight:

P5 bytes in flight to sustain 57.5 GB/s at 121 ns
       6958 bytes = 108.7 cache lines

What it licenses. A single dependent-load chain keeps one line in flight, so it achieves \(64/121\text{ns} = 0.53\) GB/s — 108× below peak on identical hardware. That one calculation explains prefetching, structure-of-arrays layouts, batching, why GPUs need thousands of threads, and why a graph walk loses to a scan.

P6 — Decode Intensity Is Batch Size

Claim. For dense autoregressive decode, arithmetic intensity is \(I = 2b/\text{bytes}\), independent of model size.

Proof. Per generated token with batch \(b\) and \(N\) parameters: every weight participates in exactly one multiply-accumulate per sequence, so

\[ W = 2Nb \quad\text{FLOPs} \]

The weights are read from memory once and shared across the batch:

\[ Q = N \cdot \text{bytes per parameter} \]

\[ I = \frac{W}{Q} = \frac{2Nb}{N \cdot \text{bytes}} = \frac{2b}{\text{bytes}} \qquad\blacksquare \]

\(N\) cancels. Model size affects how long a step takes, never whether you are memory-bound.

Verification — intensity computed for \(N\) spanning \(10^8\) to \(4\times10^{11}\) (a 4,000× range) at each batch size:

P6 intensity independent of N (b=1,   2B)   I = 1.0   for every N
P6 intensity independent of N (b=8,   2B)   I = 8.0   for every N
P6 intensity independent of N (b=64,  2B)   I = 64.0  for every N
P6 intensity independent of N (b=512, 2B)   I = 512.0 for every N

What it licenses. Setting \(I = I_{\text{ridge}}\) gives the batch needed to leave the memory-bound regime:

\[ b^{*} = \frac{I_{\text{ridge}} \times \text{bytes}}{2} \]

= 295 on an H100 at bf16, 148 at fp8. A batch-1 chatbot runs at ~0.3% MFU. This is the whole argument for continuous batching, and the real reason low precision wins at inference is smaller operands, not faster arithmetic.

P7 — Why Reverse-Mode Autodiff

Claim. For \(f : \mathbb{R}^n \to \mathbb{R}^m\), forward mode needs \(n\) passes to build the full Jacobian and reverse mode needs \(m\).

Proof. By the chain rule, \(J = J_L J_{L-1} \cdots J_1\). You never materialise these; you multiply by vectors, and matrix products are associative, so you may bracket either way:

• Right to left: \(J_L(J_{L-1}(\cdots(J_1 v)))\). Each step is a Jacobian-vector product. Seeding \(v = e_j\) yields column \(j\) of \(J\) — the derivative of every output with respect to one input. Full Jacobian: \(n\) passes.
• Left to right: \(((u^\top J_L)J_{L-1})\cdots J_1\). Each step is a vector-Jacobian product. Seeding \(u = e_i\) yields row \(i\) — the derivative of one output with respect to everything. Full Jacobian: \(m\) passes. \(\blacksquare\)

Verification — a 4-layer linear chain \(\mathbb{R}^6 \to \mathbb{R}^2\), Jacobian assembled both ways:

P7 forward and reverse produce the same Jacobian
       max |J_fwd - J_rev| = 7.11e-15; forward used 6 passes, reverse 2

Identical to machine precision, at 3× the cost for forward mode on this shape.

What it licenses. Training has \(n \approx 10^7\)–\(10^{11}\) parameters and \(m = 1\) scalar loss. For a 10M-parameter model with a 10 ms forward pass:

A factor of \(5\times10^6\). That ratio is the entire reason deep learning is computationally possible, and the price is memory — every intermediate must live until its adjoint is consumed, which is what gradient checkpointing trades back.

P8 — The Matmul Backward Rule

Claim. For \(C = AB\) with upstream gradient \(\bar{C} = \partial L/\partial C\): \(\bar{A} = \bar{C}B^\top\) and \(\bar{B} = A^\top\bar{C}\).

Proof. Write \(C_{ij} = \sum_k A_{ik}B_{kj}\). By the chain rule,

\[ \bar{A}_{ik} = \frac{\partial L}{\partial A_{ik}} = \sum_{i^{\prime}j} \frac{\partial L}{\partial C_{i^{\prime}j}} \frac{\partial C_{i^{\prime}j}}{\partial A_{ik}} \]

Now \(\partial C_{i^{\prime}j}/\partial A_{ik} = \delta_{ii^{\prime}}B_{kj}\), because \(A_{ik}\) appears in \(C_{i^{\prime}j}\) only when \(i^{\prime} = i\), multiplied by \(B_{kj}\). So

\[ \bar{A}_{ik} = \sum_j \bar{C}_{ij}B_{kj} = \sum_j \bar{C}_{ij}(B^\top)_{jk} = (\bar{C}B^\top)_{ik} \]

Symmetrically, \(\partial C_{ij^{\prime}}/\partial B_{kj} = \delta_{jj^{\prime}}A_{ik}\) gives \(\bar{B}_{kj} = \sum_i A_{ik}\bar{C}_{ij} = (A^\top\bar{C})_{kj}\). \(\blacksquare\)

Verification — analytic gradients against central finite differences on a \(4\times3\times5\) product, every element of both \(A\) and \(B\):

P8 dA = dC B^T and dB = A^T dC
       worst relative error vs finite differences: 1.20e-08

What it licenses. A backward pass is two matmuls of the same shape as the forward one, hence ~2× the cost — which is where the \(C \approx 6ND\) training-FLOPs rule comes from (1 forward + 2 backward). It is also the exit criterion for P13 Phase I: derive this, do not copy it.

P9 — Sample Size and the Four-Times Law

Claim. \(n_{\text{per arm}} = \dfrac{2(z_{1-\alpha/2} + z_{\text{power}})^2\sigma^2}{\delta^2}\), so halving the detectable effect quadruples the sample.

Proof. For a two-sample test with equal \(n\) and variance \(\sigma^2\), the difference in means has standard error \(\mathrm{SE} = \sigma\sqrt{2/n}\). To reject at level \(\alpha\) you need \(|\hat\delta| > z_{1-\alpha/2}\mathrm{SE}\); to do so with probability \(1-\beta\) when the true effect is \(\delta\), the distribution must be shifted far enough that

\[ \delta = (z_{1-\alpha/2} + z_{\text{power}}),\mathrm{SE} = (z_{1-\alpha/2} + z_{\text{power}}),\sigma\sqrt{2/n} \]

Solving for \(n\) gives the formula. Since \(n \propto \delta^{-2}\), replacing \(\delta\) by \(\delta/2\) multiplies \(n\) by 4. \(\blacksquare\)

Verification:

P9 (z_0.975 + z_0.80)^2 = 7.848880
       the folklore '16 sigma^2/delta^2' is 2*7.849 = 15.70
P9 halving the MDE quadruples n
       n = 1570, 6280, 25117; ratios 4.000, 4.000
P9 the formula delivers ~80% power
       n=393 per arm, measured power 0.809 over 3000 trials

The last line is the important one: the formula is not just algebra, it delivers the power it promises — 0.809 measured against 0.80 nominal.

What it licenses. Compute this before building a variant. P10 makes it a pre-registration requirement, and it kills more proposed experiments than any other number in the track.

P10 — Why Peeking Destroys Your Error Rate

Claim. Testing repeatedly and stopping at the first significant result inflates the false-positive rate far above \(\alpha\).

Proof sketch. Let \(E_i\) be the event "significant at look \(i\)". You reject if \(\bigcup_i E_i\) occurs. Each \(P(E_i) \approx \alpha\), and while the \(E_i\) are positively correlated (they share data), they are far from identical — each look adds fresh data and a fresh chance for the random walk of the test statistic to cross the boundary. So

\[ P\left(\bigcup_{i=1}^{L} E_i\right) > \alpha \quad\text{and grows with } L \]

In the continuous limit, the test statistic under the null is a Brownian motion; by the law of the iterated logarithm it crosses any fixed boundary almost surely given enough looks. Peek forever and you reject with probability 1. \(\blacksquare\)

Verification — A/A simulations, 3,000 trials, 400 users per look, α=0.05:

What it licenses. Checking a dashboard daily for a fortnight turns a 5% error rate into roughly 25% — one in four "wins" is noise. The remedy is a pre-registered fixed sample size, or an explicitly sequential method that pays for the looks. This is the single largest source of false results in industrial experimentation.

P11 — EMA Half-Life

Claim. For \(u_t = \alpha x_t + (1-\alpha)u_{t-1}\), an observation's weight halves after \(h = \ln(0.5)/\ln(1-\alpha)\) steps.

Proof. Unrolling the recurrence,

\[ u_t = \alpha\sum_{i=0}^{\infty}(1-\alpha)^i x_{t-i} \]

so the observation \(i\) steps back carries weight \(w(i) = \alpha(1-\alpha)^i\). Setting \(w(h)/w(0) = 1/2\):

\[ (1-\alpha)^h = \tfrac{1}{2} \quad\Longrightarrow\quad h = \frac{\ln 0.5}{\ln(1-\alpha)} \qquad\blacksquare \]

The weights also form a geometric series summing to \(\alpha \cdot \frac{1}{1-(1-\alpha)} = 1\), so this is a proper weighted average.

Verification:

P11 EMA weights sum to 1     sum = 1.000000000000

What it licenses. At α=0.5 the profile is "the last two things you clicked"; at α=0.02 it will not notice a real interest change for a month. Choose α from a stated assumption about drift rate — and P09 is what finally lets you test that assumption against known ground truth.

P12 — Post-Filter Over-Fetch

Claim. Post-filtering an ANN result with selectivity \(s\) requires \(K \ge k/s\) candidates to return \(k\) results.

Proof. If the filter is independent of similarity, each of the top-\(K\) matches with probability \(s\), so the number surviving is \(\mathrm{Binomial}(K, s)\) with mean \(Ks\). Requiring \(\mathbb{E}[\text{survivors}] \ge k\) gives \(K \ge k/s\). \(\blacksquare\)

Two caveats the proof exposes. (1) This is an expectation: at \(K = k/s\) you fall short about half the time, so real systems over-fetch further. (2) Independence fails whenever the filtered attribute correlates with position in embedding space — and in the adversarial case, where all matching items lie outside the unfiltered top-\(K\), no \(K\) suffices.

Verification — 400 trials per selectivity, counting survivors among the top \(k/s\):

What it licenses. At \(s = 10^{-4}\) on a 1M corpus you scan 10% of everything — efSearch ≥ 100,000, which is brute force with a worse constant. This is the production p99 cliff on narrow filters. Note the escape: exact brute force over the filtered set is \(O(sn)\) = 100 distance computations, faster than either alternative and exact.

P13 — The Three Amplifications

Claim. With fanout \(T\) and \(L\) levels, leveled compaction gives \(W \approx TL\), \(R \approx L\), \(S \approx 1 + 1/T\); size-tiered gives \(W \approx L\), \(R \approx TL\), \(S \approx 2\).

Proof.

Leveled. Level \(i\) holds non-overlapping runs totalling \(T^i\) times the base size. Merging one byte from level \(i\) into level \(i+1\) requires rewriting the overlapping portion of level \(i+1\), which is \(T\)× larger — so each byte is rewritten \(\approx T\) times per level, and it traverses \(L\) levels: \(W \approx TL\). A point read consults at most one run per level plus L0: \(R \approx L + 1\). Since each level is fully merged, at most one obsolete copy of a key exists per level, dominated by the largest: \(S \approx 1 + 1/T\).

Size-tiered. Runs of similar size accumulate until \(T\) of them merge into one of the next tier. Each byte is written once per tier: \(W \approx L\). But up to \(T\) runs coexist per level, all of which a read must consult: \(R \approx TL\). And up to \(T\) copies of a key coexist, with compaction needing free space equal to its inputs: \(S \approx 2\). \(\blacksquare\)

Verification — \(T = 10\), 64 MB base:

P13 neither strategy dominates on all three axes
       leveled wins R and S, size-tiered wins W -- that is the conjecture, felt

What it licenses. This is the RUM conjecture with numbers. On write-heavy ingest size-tiered is ~8× cheaper in device wear; on read-heavy serving leveled is ~7× cheaper in seeks. There is no third option that wins both, and P04's headline figure is the crossover between them.

P14 — The Tail at Scale

Claim. If a request touches \(N\) independent components each slow with probability \(p\), the request is slow with probability \(1 - (1-p)^N\).

Proof. The request is fast only if every component is fast. By independence that is \((1-p)^N\), so the complement is \(1 - (1-p)^N\). \(\blacksquare\)

For small \(p\), \(1-(1-p)^N \approx Np\) — the tail probability grows roughly linearly in fan-out until it saturates.

Verification — 40,000 trials per \(N\), \(p = 0.01\):

What it licenses. At 100 components, the majority of requests hit a p99 event. Tail latency is not an edge case at scale, it is the common case — which is why P06 measures straggler inflation and why hedged requests exist. The independence assumption is generous; correlated slowness (a shared dependency, a GC storm) makes it worse.

P15 — Systolic Operand Reuse

Claim. A \(k \times k\) weight-stationary systolic array achieves \(O(k)\) operand reuse.

Proof. Each of the \(k^2\) cells holds one weight and performs one multiply-accumulate per cycle: \(k^2\) MACs/cycle. Per cycle the array ingests one column of \(k\) activations and emits one row of \(k\) partial sums — \(2k\) operand transfers. Hence

\[ \text{reuse} = \frac{k^2}{2k} = \frac{k}{2} = O(k) \qquad\blacksquare \]

Achieved by wiring, not caching: no tags, no misses, no replacement policy.

Verification:

And the headline figure of a real accelerator from two integers:

P15 TPUv1 92 TOPS from k=256 at 700 MHz
       2 * 256^2 * 700MHz = 91.75 TOPS (reported: 92)

What it licenses. You can derive a commercial accelerator's specification from its array dimension and clock. The cost is total inflexibility — no branches, no gather, one operation — which is the same restriction-buys-performance trade as MapReduce's programming model, implemented in silicon.

P16 — Distance Concentration

Claim. For i.i.d. coordinates, relative contrast \(\mathrm{RC} = d_{\text{mean}}/d_1 \to 1\) as dimension grows.

Proof sketch. For \(x, y\) with i.i.d. components, \(|x-y|^2\) is a sum of \(d\) i.i.d. terms, so by the law of large numbers its mean grows like \(d\) while by the central limit theorem its standard deviation grows like \(\sqrt{d}\). The relative spread is therefore

\[ \frac{\text{sd}(|x-y|)}{\mathbb{E}[|x-y|]} = O!\left(\frac{1}{\sqrt{d}}\right) \to 0 \]

All pairwise distances converge to the same value, so the nearest neighbour ceases to be meaningfully nearer than the mean and \(\mathrm{RC} \to 1\). \(\blacksquare\)

Verification — 1,500 uniform points on the unit sphere:

What it licenses. RC, not \(d\), predicts ANN difficulty — which is why every recall number in this track is reported with its RC. It also explains why a benchmark on uniform high-dimensional data measures the dataset rather than the index, and why real embeddings (concentrated near a low-dimensional manifold) behave far better than their ambient \(d\) suggests.

P17 — Cosine and L2 Coincide on Unit Vectors

Claim. For \(|a| = |b| = 1\): \(|a-b|^2 = 2 - 2\langle a,b\rangle\), so ranking by max dot product, max cosine, and min L2 give identical orderings.

Proof.

\[ |a-b|^2 = \langle a-b, a-b\rangle = |a|^2 + |b|^2 - 2\langle a,b\rangle = 2 - 2\langle a,b\rangle \]

\(|a-b|^2\) is a strictly decreasing affine function of \(\langle a,b\rangle\), and \(x \mapsto \sqrt{x}\) is increasing, so the orderings coincide exactly. Cosine equals the dot product because the norms are 1. \(\blacksquare\)

Verification — 400 unit vectors in \(\mathbb{R}^{32}\):

P17 ||a-b||^2 = 2 - 2<a,b> on unit vectors     max deviation 8.88e-16
P17 max-dot and min-L2 give identical orderings  top-10 identical: True
P17 the equivalence FAILS on unnormalised vectors

What it licenses. You may pick whichever metric is fastest to compute — and, more importantly, the equivalence holds only under normalisation. Forgetting to normalise silently changes the ranking with no error raised, which is exactly P02's E6 and one of the quietest recall bugs in retrieval systems.

P18 — Zipf Head Mass

Claim. Under a Zipf law with exponent \(\alpha\), the top \(f\) fraction of items carries a share of the mass that rises steeply with \(\alpha\).

Proof. With \(w(r) = r^{-\alpha}\) over ranks \(1..n\), the share of the top \(m\) is

\[ S(m) = \frac{\sum_{r=1}^{m} r^{-\alpha}}{\sum_{r=1}^{n} r^{-\alpha}} \approx \frac{\int_1^m r^{-\alpha}dr}{\int_1^n r^{-\alpha}dr} = \frac{m^{1-\alpha}-1}{n^{1-\alpha}-1} \quad (\alpha \ne 1) \]

For \(\alpha = 1\) both integrals are logarithms and \(S(m) \approx \ln m/\ln n\). \(\blacksquare\)

Verification — \(n = 10{,}000\), exact sums:

What it licenses. At \(\alpha = 1\), recommending only the top 1% of a catalogue captures 53% of all engagement. A trivial bestseller list therefore beats a mediocre personalised model on any accuracy metric while covering 1% of the catalogue — which is why the popularity baseline is mandatory in P08 and why coverage must be reported next to NDCG every time.

References

• Vaswani, A. et al. Attention Is All You Need. NeurIPS 2017. §3.2.1 states the \(\sqrt{d_k}\) scaling with the variance argument in a footnote — P1 is that footnote, expanded.
• Bloom, B. H. Space/time trade-offs in hash coding with allowable errors. CACM 13(7), 1970. P2 and P3.
• Mitzenmacher, M., Upfal, E. Probability and Computing, 2nd ed. Cambridge, 2017. The independence-approximation caveat in P2, and P14.
• Gifford, D. K. Weighted Voting for Replicated Data. SOSP 1979. The origin of P4.
• Little, J. D. C. A Proof for the Queuing Formula L = λW. Operations Research 9(3), 1961. P5, including the distribution-free argument.
• Williams, S., Waterman, A., Patterson, D. Roofline. CACM 52(4), 2009. P6, P15.
• Baydin, A. G. et al. Automatic Differentiation in Machine Learning: a Survey. JMLR 18, 2018. P7 and P8, with the mode-cost analysis in §3.
• Griewank, A., Walther, A. Evaluating Derivatives, 2nd ed. SIAM, 2008. The rigorous form of P7.
• Cohen, J. Statistical Power Analysis for the Behavioral Sciences, 2nd ed. Lawrence Erlbaum, 1988. P9.
• Armitage, P., McPherson, C. K., Rowe, B. C. Repeated Significance Tests on Accumulating Data. JRSS A 132(2), 1969. The original quantification of P10.
• Johari, R. et al. Peeking at A/B Tests. KDD 2017. P10, and the principled remedy.
• O'Neil, P. et al. The Log-Structured Merge-Tree. Acta Informatica 33, 1996. P13.
• Athanassoulis, M. et al. Designing Access Methods: The RUM Conjecture. EDBT 2016. The framing of P13.
• Dean, J., Barroso, L. A. The Tail at Scale. CACM 56(2), 2013. P14.
• Kung, H. T., Leiserson, C. E. Systolic Arrays for VLSI. 1978. P15.
• Jouppi, N. P. et al. In-Datacenter Performance Analysis of a TPU. ISCA 2017. The 92 TOPS figure P15 reproduces.
• Beyer, K. et al. When Is "Nearest Neighbor" Meaningful? ICDT 1999. P16.
• He, J., Kumar, S., Chang, S.-F. On the Difficulty of Nearest Neighbor Search. ICML 2012. Relative contrast, P16.
• Clauset, A., Shalizi, C. R., Newman, M. E. J. Power-Law Distributions in Empirical Data. SIAM Review 51(4), 2009. P18, and how routinely these are mis-fitted.