Mathematical Preparation

Just in time, never just in case. Every topic below is here because a specific project needs it, is scheduled in the week before that project needs it, and has a stated minimum depth beyond which you should stop.

Total budget: ~60 hours across 34 months — about 4% of the journey. If you find yourself doing more than that, you have started a mathematics curriculum, which is a different and worthy project that this one is not.

Table of Contents

• The Rule
• Schedule
• Linear Algebra
• Softmax, Cross-Entropy, and Information
• Chain Rule and Jacobians
• Concentration of Measure in High Dimensions
• Probability Distributions
• Hypothesis Testing
• Power and Sample Size
• Confidence Intervals and the Bootstrap
• Ranking Metrics
• Implicit Feedback and Bias
• Graph Theory
• Queueing Theory
• Numerical Computing
• Distributed-Systems Models
• Optimization
• What To Skip
• References

The Rule

For every topic, four things must be true before you spend an hour on it:

1. Why it is needed — the concrete thing you cannot do without it
2. Which project uses it — by number
3. What practical problem it solves — an actual decision it changes
4. The minimum depth — and an explicit "stop here"

If a topic cannot satisfy all four, it goes on What To Skip.

The failure mode this prevents is real and specific: spending three weeks on measure theory because probability "seems foundational", and arriving at P09 no better equipped than someone who spent two hours on the bootstrap.

Schedule

The remaining ~20 hours of the budget are unallocated slack for the topic that turns out to be harder than planned. Historically that is distributed-systems models.

Linear Algebra

Why: attention is three matrix multiplications and a softmax. You cannot reason about its cost or its shape without fluency in matrix dimensions.

Project: P01, and everything downstream.

Solves: knowing that \(QK^\top\) is \(T \times T\) — and therefore quadratic in sequence length — before you write it. Reading a shape error and knowing which transpose is wrong.

Minimum depth: matrix multiplication and its dimension rules; transpose; the fact that \(AB\) composes linear maps; dot product as similarity; L2 norm; the cosine/L2 equivalence on unit vectors: \(\|a-b\|^2 = \|a\|^2 + \|b\|^2 - 2\langle a,b\rangle = 2 - 2\langle a,b\rangle\).

Stop here. You do not need eigenvalues, SVD, determinants, or matrix decompositions for any project in this journey. If you later take P08's two-tower extension, revisit.

Source: Strang, Introduction to Linear Algebra, chapters 1–2. Or 3Blue1Brown's Essence of Linear Algebra, episodes 1–4, which is 45 minutes and sufficient.

Softmax, Cross-Entropy, and Information

Why: the loss function, and the reason the entropy floor is where it is.

Project: P01, P08 (novelty in bits), P04 (Bloom filter optimality).

Solves: three things. Knowing that a model trained on random labels converges to exactly \(\ln V\) nats, so you can tell a broken model from a hard problem. Converting loss to perplexity by \(e^{\text{loss}}\). Understanding why the optimal Bloom filter is exactly half full.

Minimum depth: softmax and its max-subtraction stabilisation; cross-entropy as negative log-likelihood; entropy \(H = -\sum p\log p\) and why uniform maximises it; self-information \(-\log_2 p\) as "bits of surprise"; the softmax Jacobian \(\partial p_i/\partial z_j = p_i(\delta_{ij} - p_j)\) and the fused softmax + cross-entropy gradient \(p - y\) — derive that one, it is four lines and it is used in P13.

Stop here. No KL divergence beyond the definition, no mutual information, no rate– distortion theory.

Source: Goodfellow, Bengio, Courville, Deep Learning, §3.13 and §6.2. Cover & Thomas ch. 2 if you want the information theory properly.

Chain Rule and Jacobians

Why: this is the mathematical content of P13, and it is genuinely load-bearing — the only topic on this list where insufficient depth will actually stop you.

Project: P13-I.

Solves: deriving each backward rule yourself instead of copying it; understanding why reverse mode costs one pass and forward mode costs \(n\); getting broadcast backward right.

Minimum depth:

• Multivariate chain rule, stated with Jacobians: for \(z = f(y)\), \(y = g(x)\), \(J_{z/x} = J_{z/y} J_{y/x}\)
• Vector-Jacobian products — why you never materialise \(J\), and why an adjoint \(\bar{y}^\top J\) is what actually propagates
• Why associativity choice decides forward vs reverse: right-to-left gives you one column per pass, left-to-right one row
• Derive matmul backward: for \(C = AB\), \(\bar{A} = \bar{C}B^\top\) and \(\bar{B} = A^\top\bar{C}\). Write out \(C_{ij} = \sum_k A_{ik}B_{kj}\) and turn the crank
• The broadcast backward rule: sum over broadcast axes, keeping dims

Stop here. No differential geometry, no manifolds, no higher-order derivatives (unless you take P13's forward-mode extension).

Source: Baydin et al., Automatic Differentiation in Machine Learning: a Survey, §2–3. Then Griewank & Walther chapter 3 if you want rigour.

Do this one properly. Three hours here saves a week of debugging in P13.

Concentration of Measure in High Dimensions

Why: it turns "the curse of dimensionality" from folklore into a number you can measure and predict.

Project: P02, and P03's filtering study.

Solves: knowing before benchmarking that uniform data at \(d=512\) will defeat any index; choosing a test dataset whose difficulty you can state.

Minimum depth: as \(d\) grows, pairwise distances between i.i.d. points concentrate — the ratio of the furthest to the nearest neighbour tends to 1 (Beyer et al. 1999). Relative contrast \(\mathrm{RC} = d_{\text{mean}}/d_1\) as the operational measure. The intrinsic-vs-ambient dimension distinction, and why real embeddings are far easier than their \(d\) suggests.

One concrete fact worth carrying: a Gaussian perturbation with per-axis \(\sigma\) in \(d\) dimensions has expected norm \(\sigma\sqrt{d}\). This is why a "clustered" dataset with \(\sigma\sqrt{d} > 1\) around unit-norm centres is indistinguishable from uniform — measured at \(d=64\): \(\sigma=0.25\) gives RC 1.393 against uniform's 1.356.

Stop here. No measure-theoretic concentration inequalities. Chernoff and Hoeffding by name only.

Source: Beyer et al., When Is "Nearest Neighbor" Meaningful?, ICDT 1999. He, Kumar & Chang, ICML 2012.

Probability Distributions

Why: real workloads are not uniform, and the shape of the distribution decides the system's behaviour more than its mean does.

Project: P04 (Zipfian keys), P06 (stragglers), P07 (event delay), P09 (user models).

Solves: generating a realistic workload; knowing that a Zipf(1.0) catalogue puts 53% of engagement mass in the top 1% of items, so a bestseller list is a hard baseline; knowing why a mean latency is a lie when the distribution is heavy-tailed.

Minimum depth: uniform, normal, exponential, Poisson, log-normal, Zipf/power law. For each: what generates it, what its tail looks like, and how to sample from it. Heavy tails and why the mean can be dominated by rare events. Order statistics enough to know that \(\mathbb{E}[\max \text{ of } n]\) grows with \(n\) — which is why job completion time is a maximum and why stragglers dominate.

Stop here. No measure-theoretic probability. No characteristic functions. Extreme value theory by name only.

Source: Mitzenmacher & Upfal, Probability and Computing, chapters 2–3. Clauset, Shalizi & Newman, Power-Law Distributions in Empirical Data, SIAM Review 51(4), 2009, for how routinely power laws are mis-fitted.

Hypothesis Testing

Why: P10 is a statistics project wearing a systems costume.

Project: P10, and every A/B claim thereafter.

Solves: knowing what a p-value is and is not; why Welch's t is the default rather than Student's; why an SRM invalidates rather than warns.

Minimum depth: null and alternative hypotheses; type I and II error; the p-value's actual definition (the probability of data this extreme given the null, which is not the probability the null is true); t-tests including Welch's for unequal variances and why that is the right default; chi-square for categorical splits; multiple comparisons and the difference between family-wise error and false discovery rate.

Stop here. No Bayesian inference (interesting, and not needed); no ANOVA; no non-parametric tests beyond knowing they exist.

The one thing to internalise: the peeking result. Checking significance repeatedly inflates the false-positive rate from 5% to 19% at 10 looks and 33% at 50. That single table changes how you run experiments forever.

Source: Kohavi, Tang & Xu, Trustworthy Online Controlled Experiments, ch. 17.

Power and Sample Size

Why: it tells you whether an experiment is worth running before you build the variant.

Project: P10, P09.

Solves: the most useful single calculation in applied experimentation.

Minimum depth: statistical power; minimum detectable effect; the formula

\[ n_{\text{per arm}} = \frac{2(z_{1-\alpha/2} + z_{\text{power}})^2\sigma^2}{\delta^2} \]

and — more importantly — its consequence: halving the MDE quadruples \(n\). Verified in tools/metrics.py: at \(\sigma=0.5\), MDEs of 0.05 / 0.025 / 0.0125 require 1,570 / 6,280 / 25,117 per arm. Exactly 4× per halving.

Stop here. No sequential analysis (that is P10's extension), no Bayesian sample sizing.

Source: Cohen, J. Statistical Power Analysis for the Behavioral Sciences, 2nd ed., chapter 1. Or just derive it from the two-sample z-test — twenty minutes and you own it.

Confidence Intervals and the Bootstrap

Why: every performance and quality claim in this journey needs an uncertainty estimate, and latency distributions are not normal.

Project: P09, P10, and every benchmark from week 1.

Solves: saying "no measurable difference" honestly rather than reporting a 3% improvement from overlapping intervals — the single most common benchmarking lie.

Minimum depth: sampling distribution; standard error; why a t-interval on the mean is wrong for right-skewed, multi-modal latency data; the non-parametric bootstrap — resample with replacement, recompute the statistic, take empirical quantiles. Implemented in tools/bench.py in fifteen lines.

Also: common random numbers as a variance-reduction technique. Using the same seeds across experimental arms and varying only the treatment routinely cuts required sample size by an order of magnitude. It is the highest-value technique in P09 and it is one paragraph of theory.

Stop here. No BCa bootstrap, no jackknife, no bootstrap consistency theory.

Source: Efron & Tibshirani, An Introduction to the Bootstrap, chapters 6 and 13. Law, Simulation Modeling and Analysis, for common random numbers.

Ranking Metrics

Why: you will report these constantly, and each encodes an assumption most people using it cannot state.

Project: P08, P09, P10, and P02's recall.

Solves: knowing that NDCG's \(\log_2(i+2)\) discount models a user's examination probability, and is therefore wrong for an infinite-scroll feed; knowing why raw DCG is not comparable across queries.

Minimum depth: precision, recall, and their k-dependence; DCG, IDCG, NDCG and why normalisation matters; MRR and why it only suits one-right-answer tasks; MAP. Then the beyond-accuracy family: coverage, Gini, novelty as mean self-information, intra-list diversity, calibration. All implemented in tools/metrics.py with derivations in the docstrings.

Stop here. No learning-to-rank loss functions (LambdaRank, ListNet) unless you take P08's reranker extension.

Source: Järvelin & Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM TOIS 20(4), 2002.

Implicit Feedback and Bias

Why: clicks are not ratings, and every offline evaluation in P08 is biased by the policy that produced the logs.

Project: P08, P09.

Solves: stating the bias in your report rather than discovering it when the online test disagrees.

Minimum depth: implicit vs explicit feedback; position bias and the examination hypothesis \(P(\text{click}) = P(\text{examine}) \cdot P(\text{attract})\); why absence of a click is not a negative; selection bias from the logging policy; inverse propensity scoring as the standard correction, and why it has high variance (hence capping).

Stop here. No causal graphs, no doubly-robust estimators beyond knowing the name, unless you take P08's off-policy extension.

Source: Joachims, Swaminathan & Schnabel, Unbiased Learning-to-Rank with Biased Feedback, WSDM 2017. Chuklin et al., Click Models for Web Search, ch. 3.

Graph Theory

Why: HNSW is a graph, and its navigability is a graph-theoretic property.

Project: P02, P03.

Solves: understanding why greedy routing works — and predicting when it will not.

Minimum depth: degree, path length, connectivity, connected components. Small-world graphs: high clustering plus short paths. Kleinberg's navigability result — greedy routing achieves \(O(\log^2 n)\) hops only when long-range links follow a specific distance distribution, and fails otherwise. Greedy routing and local minima.

Why this earns its two hours: it is what lets you diagnose P02's clustered-data recall ceiling as a connectivity failure rather than a tuning problem. Without the graph-theoretic framing, the symptom looks like "recall plateaus" and the fix looks like "raise efSearch", which does not work.

Stop here. No spectral graph theory, no flows, no matchings.

Source: Kleinberg, Navigation in a Small World, Nature 406, 2000 — two pages. Watts & Strogatz, Nature 393, 1998.

Queueing Theory

Why: it explains why latency explodes near saturation, which is the single most useful predictive model in systems work.

Project: P05, P07, P15.

Solves: knowing that at 80% utilisation your queue is 4× its low-load length, and at 95% it is 19× — so capacity planning to 90% is not a 10% safety margin, it is a cliff.

Minimum depth:

• Little's Law: \(L = \lambda W\). Deceptively simple, applies to any stable system with no assumptions about the arrival distribution, and lets you convert between queue length, arrival rate, and latency. Use it constantly
• M/M/1 utilisation law: mean queue length \(\propto \rho/(1-\rho)\). The \(1/(1-\rho)\) term is the whole lesson — it is why the last 10% of capacity costs more than the first 90%
• Why variability makes it worse: the same utilisation with bursty arrivals queues far more
• Coordinated omission — the measurement bug where a load generator that waits for a response stops sending during a stall, and therefore fails to record the latencies its own stall caused. This makes almost every naive latency benchmark wrong at the tail

Stop here. No M/G/1, no Jackson networks, no matrix-geometric methods.

Source: Gunther, Guerrilla Capacity Planning, ch. 2. Tene, G. How NOT to Measure Latency (talk) for coordinated omission.

Numerical Computing

Why: your gradients will disagree with PyTorch's, and you need to know whether that is a bug or floating-point arithmetic.

Project: P13, P01, P14.

Solves: deciding whether a 1e-6 discrepancy is a bug (it usually is not) or a 1e-3 one is (it usually is); choosing a gradient-check tolerance you can defend; knowing why fp16 needs loss scaling.

Minimum depth: IEEE 754 single and double precision — sign, exponent, mantissa, and the ~7 significant decimal digits of fp32. Machine epsilon. Catastrophic cancellation. Why floating-point addition is not associative, and therefore why a different summation order legitimately gives a different answer. Log-sum-exp for stability. Central differences and the \(h \approx \sqrt{\epsilon}\) choice for gradient checking. bf16 vs fp16: same 16 bits, different exponent/mantissa split, and why bf16's wider range won for training.

Stop here. No numerical linear algebra, no conditioning theory beyond the concept, no error analysis of algorithms.

Source: Goldberg, D. What Every Computer Scientist Should Know About Floating-Point Arithmetic, ACM Computing Surveys 23(1), 1991. Long, and the definitive answer.

Distributed-Systems Models

Why: P05's correctness arguments are formal, and hand-waving them produces a system that is wrong in a way tests do not catch.

Project: P05, P06, P07.

Solves: knowing what your system guarantees, precisely enough to write it down and have someone attack it.

Minimum depth:

• The asynchronous model and why it is the right default
• Happens-before, Lamport clocks, vector clocks, causality
• FLP impossibility: no deterministic async consensus with one crash failure. The statement and the intuition; the proof is optional
• Quorum intersection: two quorums of size \(Q\) from \(N\) intersect iff \(2Q > N\). Derive it — it is one line and it is the reason for every majority in every consensus protocol
• Linearizability as a formal property, precisely enough to check a history
• CAP as a theorem, and PACELC as the more useful framing
• Failure detectors: completeness and accuracy as separate properties

Budget 4 hours, and expect to need 6. This is the topic most likely to overrun, and it is worth the overrun.

Source: Lamport 1978; FLP 1985; Herlihy & Wing 1990; Gilbert & Lynch 2002. Cachin, Guerraoui & Rodrigues, Introduction to Reliable and Secure Distributed Programming, ch. 2, for the model definitions in one place.

Optimization

Why: you train models in P01 and implement optimizers in P13.

Project: P01, P13.

Solves: knowing why Adam needs warmup; why weight decay and L2 differ under adaptive methods; what a learning-rate schedule is for.

Minimum depth: gradient descent; the role of the learning rate; momentum as an exponential moving average of gradients; Adam's first and second moment estimates and their bias correction; why AdamW's decoupled decay differs from L2 (under Adam, an L2 term is divided by the second-moment estimate, so it is not uniform decay); warmup as a remedy for unreliable second-moment estimates early in training; cosine decay.

Stop here. No convex analysis, no convergence proofs, no second-order methods.

Source: Loshchilov & Hutter, Decoupled Weight Decay Regularization, ICLR 2019. Ruder, S. An overview of gradient descent optimization algorithms, arXiv:1609.04747.

What To Skip

Actively refuse these until a project needs them. Each is genuinely interesting, and each would cost weeks that belong to implementation. See also Not Yet.

TLA+ deserves a note. Specifying Raft in TLA+ and model-checking it would genuinely improve P05 and is what a serious distributed-systems engineer does. It is excluded because it is a 40-hour skill acquisition inside a 143-hour project, and the plan already has P05 as its highest overrun risk. Do it after P05, as a separate two-week piece of work, and compare what the model checker finds against what your fault injector found. That comparison is itself a good blog post.

References

• Strang, G. Introduction to Linear Algebra, 5th ed. Wellesley-Cambridge, 2016.
• Goodfellow, I., Bengio, Y., Courville, A. Deep Learning. MIT Press, 2016.
• Baydin, A. G. et al. Automatic Differentiation in Machine Learning: a Survey. JMLR 18, 2018.
• Griewank, A., Walther, A. Evaluating Derivatives, 2nd ed. SIAM, 2008.
• Beyer, K. et al. When Is "Nearest Neighbor" Meaningful? ICDT 1999.
• He, J., Kumar, S., Chang, S.-F. On the Difficulty of Nearest Neighbor Search. ICML 2012.
• Mitzenmacher, M., Upfal, E. Probability and Computing, 2nd ed. Cambridge, 2017.
• Clauset, A., Shalizi, C. R., Newman, M. E. J. Power-Law Distributions in Empirical Data. SIAM Review 51(4), 2009.
• Efron, B., Tibshirani, R. An Introduction to the Bootstrap. Chapman & Hall, 1993.
• Cohen, J. Statistical Power Analysis for the Behavioral Sciences, 2nd ed. Lawrence Erlbaum, 1988.
• Kohavi, R., Tang, D., Xu, Y. Trustworthy Online Controlled Experiments. Cambridge, 2020.
• Järvelin, K., Kekäläinen, J. Cumulated gain-based evaluation of IR techniques. ACM TOIS 20(4), 2002.
• Kleinberg, J. Navigation in a Small World. Nature 406, 2000.
• Watts, D. J., Strogatz, S. H. Collective dynamics of 'small-world' networks. Nature 393, 1998.
• Gunther, N. J. Guerrilla Capacity Planning. Springer, 2007.
• Goldberg, D. What Every Computer Scientist Should Know About Floating-Point Arithmetic. ACM Computing Surveys 23(1), 1991.
• Cachin, C., Guerraoui, R., Rodrigues, L. Introduction to Reliable and Secure Distributed Programming, 2nd ed. Springer, 2011.
• Loshchilov, I., Hutter, F. Decoupled Weight Decay Regularization. ICLR 2019.