Proof library
463 statements. 339 of them carry a proof obligation, and 294 (87%) are proved in full on their page. The remaining 124 are definitions, heuristics, empirical observations, conjectures and open problems — things that are true by convention, things that are observed but not proven, and things nobody knows.
The distinction is the point. A theorem has a proof; a heuristic is an argument that is useful and not rigorous; an empirical observation is a measurement that has been reproduced and not explained. Nothing on this site presents one as another, and the filters here let you check that claim rather than take it on trust.
Proof status
Epistemic status
Field
463 of 463 statements
The inner product of two vectors is bounded by the product of their norms, with equality exactly for parallel vectors.
Foundations · Linear Algebra for Machine Learning
Every vector decomposes uniquely into a component in a subspace and a component orthogonal to it, and the subspace component is the nearest point.
Foundations · Linear Algebra for Machine Learning
A real symmetric matrix has an orthonormal eigenbasis and real eigenvalues.
Foundations · Linear Algebra for Machine Learning
The extreme eigenvalues of a symmetric matrix are the extreme values of the Rayleigh quotient.
Foundations · Linear Algebra for Machine Learning
Every real matrix factors as a rotation, a non-negative scaling and another rotation.
Foundations · Linear Algebra for Machine Learning
- TheoremEckart–Young–Mirsky theorem
Truncating the SVD gives the best low-rank approximation in both the spectral and the Frobenius norm.
Foundations · Linear Algebra for Machine Learning
Four equivalent descriptions of a PSD matrix, each of which is the convenient one somewhere later.
Foundations · Linear Algebra for Machine Learning
A twice-differentiable function equals its linear model plus an exact curvature term.
Foundations · Multivariable and Matrix Calculus
L-smoothness sandwiches a function between its linear model and that model plus a quadratic.
Foundations · Multivariable and Matrix Calculus
- TheoremChain rule for compositions
The Jacobian of a composition is the product of the Jacobians, in reverse order of evaluation.
Foundations · Multivariable and Matrix Calculus
- TheoremSymmetry of the Hessian
Continuous second partials commute, so the Hessian is symmetric.
Foundations · Multivariable and Matrix Calculus
A convex function of an average is at most the average of the function.
Foundations · Analysis Prerequisites
- TheoremHölder's inequality
The expectation of a product is bounded by the product of conjugate Lp norms.
Foundations · Analysis Prerequisites
Conditions under which a limit may be exchanged with an integral.
Foundations · Analysis Prerequisites
- TheoremExtreme value theorem
A continuous function on a compact set attains its supremum.
Foundations · Analysis Prerequisites
Monotonicity, finite additivity, complements, continuity along monotone sequences and the union bound, all from the three axioms.
Probability · Probability Spaces and Random Variables
The probability of a union is at most the sum of the probabilities.
Probability · Probability Spaces and Random Variables
A random variable induces a probability measure on the real line, and only that measure matters for its law.
Probability · Probability Spaces and Random Variables
Summable probabilities imply almost surely finitely many occurrences; for independent events the converse holds.
Probability · Probability Spaces and Random Variables
The mean of a non-negative random variable is the integral of its tail probability.
Probability · Expectation, Variance and Conditional Expectation
Mean squared error splits into squared bias plus variance; total variance splits into explained and residual parts.
Probability · Expectation, Variance and Conditional Expectation
Conditional expectation is the orthogonal projection of a square-integrable variable onto the sub-sigma-algebra's functions.
Probability · Expectation, Variance and Conditional Expectation
The two computational rules that make every conditional-expectation manipulation work.
Probability · Expectation, Variance and Conditional Expectation
Almost sure and Lp convergence both imply convergence in probability, which implies convergence in distribution; no other implication holds in general.
Probability · Modes of Convergence, LLN and CLT
For i.i.d. variables with finite variance the sample mean converges to the mean in probability.
Probability · Modes of Convergence, LLN and CLT
- TheoremStrong law of large numbers
For i.i.d. integrable variables the sample mean converges almost surely.
Probability · Modes of Convergence, LLN and CLT
- TheoremCentral limit theorem
The standardised sample mean of i.i.d. variables with finite variance converges in distribution to a standard normal.
Probability · Modes of Convergence, LLN and CLT
- TheoremBerry–Esseen bound
A quantitative CLT with an explicit n^{-1/2} rate in Kolmogorov distance.
Probability · Modes of Convergence, LLN and CLT
- Empirical observationThe CLT does not license Gaussian tail estimates
Pointwise convergence of the CDF says nothing about the far tail at finite n, which is why concentration inequalities are needed.
Probability · Modes of Convergence, LLN and CLT
Gaussian tails, moment growth, MGF bounds and finiteness of the psi-2 Orlicz norm are equivalent up to absolute constants.
High-Dim Probability · Sub-Gaussian and Sub-Exponential Random Variables
- DefinitionThe psi-2 and psi-1 Orlicz norms
Norms whose finiteness encodes Gaussian and exponential tail decay respectively.
High-Dim Probability · Sub-Gaussian and Sub-Exponential Random Variables
A centred Gaussian has MGF exactly exp(lambda^2 sigma^2 / 2).
High-Dim Probability · Sub-Gaussian and Sub-Exponential Random Variables
A centred random variable supported on an interval of length b-a is sub-Gaussian with parameter (b-a)/2.
High-Dim Probability · Sub-Gaussian and Sub-Exponential Random Variables
Sub-Gaussian parameters add in square, exactly as variances do.
High-Dim Probability · Sub-Gaussian and Sub-Exponential Random Variables
Exponential tails, linear moment growth and a one-sided MGF bound near zero are equivalent up to constants.
High-Dim Probability · Sub-Gaussian and Sub-Exponential Random Variables
X sub-Gaussian implies X^2 sub-exponential, with the psi-1 norm the square of the psi-2 norm.
High-Dim Probability · Sub-Gaussian and Sub-Exponential Random Variables
A non-negative random variable exceeds t with probability at most its mean over t.
High-Dim Probability · Concentration Inequalities
Deviations of size t have probability at most the variance over t squared.
High-Dim Probability · Concentration Inequalities
Optimising an exponential Markov bound over the tilting parameter yields the Legendre transform of the cumulant generating function.
High-Dim Probability · Concentration Inequalities
Sums of independent bounded variables have Gaussian tails with parameter determined by the ranges alone.
High-Dim Probability · Concentration Inequalities
For bounded variables, a tail bound interpolating between Gaussian behaviour at small deviations and exponential behaviour at large ones.
High-Dim Probability · Concentration Inequalities
Hoeffding's bound for martingales with bounded increments, requiring no independence.
High-Dim Probability · Concentration Inequalities
A function of independent variables that changes little when any single coordinate is changed concentrates around its mean.
High-Dim Probability · Concentration Inequalities
A Lipschitz function of a standard Gaussian vector is sub-Gaussian with parameter equal to its Lipschitz constant, with no dependence on dimension.
High-Dim Probability · Concentration Inequalities
Both inequalities are tight, so their weakness is a property of their hypotheses and not of their proofs.
High-Dim Probability · Concentration Inequalities
For a vector with independent sub-Gaussian coordinates, the norm deviates from the square root of the dimension by an O(1) sub-Gaussian amount.
High-Dim Probability · High-Dimensional Geometry and Concentration of the Norm
The mean of the norm is the square root of the dimension up to a 1/d correction, and the variance is bounded by a constant.
High-Dim Probability · High-Dimensional Geometry and Concentration of the Norm
The inner product of two independent uniform directions is of order one over the square root of the dimension.
High-Dim Probability · High-Dimensional Geometry and Concentration of the Norm
A spherical cap at distance t from the equator carries at most exp(-d t^2 / 2) of the sphere's measure.
High-Dim Probability · High-Dimensional Geometry and Concentration of the Norm
Almost all of the volume of a high-dimensional ball lies within O(1/d) of its boundary.
High-Dim Probability · High-Dimensional Geometry and Concentration of the Norm
The same concentration that destroys local methods is what makes random projections and dot-product retrieval work.
High-Dim Probability · High-Dimensional Geometry and Concentration of the Norm
- DefinitionNets, covering and packing numbers
The three finite-approximation quantities and the notation used for them.
High-Dim Probability · Nets, Covering Numbers and Metric Entropy
The two quantities sandwich each other at scales differing by a factor of two.
High-Dim Probability · Nets, Covering Numbers and Metric Entropy
The unit ball of R^d admits an epsilon-net of size at most (3/epsilon)^d, and needs at least (1/epsilon)^d points.
High-Dim Probability · Nets, Covering Numbers and Metric Entropy
The spectral norm computed on a fine enough net is within a constant factor of the true spectral norm.
High-Dim Probability · Nets, Covering Numbers and Metric Entropy
- TheoremDudley's entropy integral
The expected supremum of a sub-Gaussian process is bounded by an integral of the square root of the metric entropy.
High-Dim Probability · Nets, Covering Numbers and Metric Entropy
- DefinitionGaussian width
A single scalar summary of a set's complexity that controls many high-dimensional estimates.
High-Dim Probability · Nets, Covering Numbers and Metric Entropy
A random Gaussian projection preserves the norm of any single fixed vector to within a factor 1 ± eps with probability 1 − 2exp(−c k eps^2).
High-Dim Probability · The Johnson–Lindenstrauss Lemma
Any N points in Euclidean space embed into O(eps^{-2} log N) dimensions with all pairwise distances preserved to within 1 ± eps.
High-Dim Probability · The Johnson–Lindenstrauss Lemma
The eps^{-2} log N dependence cannot be improved in general.
High-Dim Probability · The Johnson–Lindenstrauss Lemma
Distance preservation for a point set closed under differences implies inner-product preservation.
High-Dim Probability · The Johnson–Lindenstrauss Lemma
- Empirical observationDistance preservation is not neighbour preservation
A 1 ± eps distortion guarantee does not preserve the identity of the nearest neighbour when the gap to the runner-up is smaller than eps.
High-Dim Probability · The Johnson–Lindenstrauss Lemma
An n-by-p matrix with independent sub-Gaussian entries has spectral norm O(sqrt n + sqrt p) with exponentially high probability.
Random Matrices · Spectral Norm of Random Matrices
The spectral norm is the maximum of a bilinear form over two spheres, which is what allows a two-sided net argument.
Random Matrices · Spectral Norm of Random Matrices
- TheoremWigner semicircle law
The empirical spectral distribution of a scaled Wigner matrix converges to the semicircle density on [-2,2].
Random Matrices · Spectral Norm of Random Matrices
For i.i.d. entries with four finite moments the extreme singular values converge to sqrt n ± sqrt p.
Random Matrices · Spectral Norm of Random Matrices
- TheoremMatrix Bernstein inequality
A Bernstein-type bound for sums of independent random matrices, with a log-dimension factor.
Random Matrices · Spectral Norm of Random Matrices
- TheoremMarchenko–Pastur law
The empirical spectral distribution of a sample covariance matrix with identity population covariance converges to an explicit density supported on an interval determined by the aspect ratio.
Random Matrices · Sample Covariance and the Marchenko–Pastur Law
The extreme eigenvalues sit at (1 ± sqrt(lambda))^2, so the condition number blows up as the aspect ratio approaches one.
Random Matrices · Sample Covariance and the Marchenko–Pastur Law
A verification that the stated density is a probability density on its bulk when the aspect ratio is at most one.
Random Matrices · Sample Covariance and the Marchenko–Pastur Law
As the aspect ratio tends to zero the bulk collapses to a point mass at one, which is the classical fixed-dimension result.
Random Matrices · Sample Covariance and the Marchenko–Pastur Law
- Empirical observationReal covariance spectra are not Marchenko–Pastur
Empirical spectra of real data typically show spiked structure that the identity-population law does not describe.
Random Matrices · Sample Covariance and the Marchenko–Pastur Law
For sub-Gaussian data the sample covariance satisfies an operator-norm error of order sqrt(p/n) + p/n.
High-Dim Statistics · Covariance Estimation and Sample Complexity
Achieving relative operator-norm error epsilon requires order p/epsilon^2 samples.
High-Dim Statistics · Covariance Estimation and Sample Complexity
For any aspect ratio there is a shrinkage intensity whose expected squared error is strictly below that of the unshrunk estimator.
High-Dim Statistics · Covariance Estimation and Sample Complexity
The number of samples needed grows linearly in the dimension for covariance estimation and exponentially for nonparametric estimation, and conflating the two causes most confusion about the phrase.
High-Dim Statistics · Covariance Estimation and Sample Complexity
- DefinitionRestricted isometry property
A matrix acts as a near-isometry on all sparse vectors.
High-Dim Statistics · Sparse Recovery, Compressed Sensing and the Lasso
A Gaussian matrix with order s log(p/s) rows satisfies the restricted isometry property with high probability.
High-Dim Statistics · Sparse Recovery, Compressed Sensing and the Lasso
Under a restricted isometry condition, minimising the l1 norm subject to the measurements recovers every sparse signal exactly.
High-Dim Statistics · Sparse Recovery, Compressed Sensing and the Lasso
Under a restricted eigenvalue condition the lasso attains squared error of order s log(p) / n.
High-Dim Statistics · Sparse Recovery, Compressed Sensing and the Lasso
No estimator can beat s log(p/s) / n uniformly over s-sparse signals, so the lasso is optimal up to constants.
High-Dim Statistics · Sparse Recovery, Compressed Sensing and the Lasso
- Open problemCertifying the RIP for a given matrix
Deciding whether a specific matrix satisfies the restricted isometry property is computationally hard in general.
High-Dim Statistics · Sparse Recovery, Compressed Sensing and the Lasso
A differentiable function is convex exactly when it lies above all of its tangent planes.
Optimization · Convex Sets, Convex Functions, Smoothness and Strong Convexity
A twice-differentiable function is convex exactly when its Hessian is positive semidefinite everywhere.
Optimization · Convex Sets, Convex Functions, Smoothness and Strong Convexity
Strong convexity gives a unique minimiser, a quadratic growth lower bound and the Polyak–Lojasiewicz inequality.
Optimization · Convex Sets, Convex Functions, Smoothness and Strong Convexity
An L-smooth and mu-strongly convex function is trapped between two quadratics, and the ratio L/mu is the condition number.
Optimization · Convex Sets, Convex Functions, Smoothness and Strong Convexity
For convex functions the first-order condition is sufficient, not merely necessary.
Optimization · Convex Sets, Convex Functions, Smoothness and Strong Convexity
Explicit functions separating convexity, strong convexity, smoothness and Lipschitz continuity.
Optimization · Convex Sets, Convex Functions, Smoothness and Strong Convexity
With step size at most 1/L each gradient step reduces f by at least half the step times the squared gradient norm.
Optimization · Gradient Descent and Its Convergence Rates
With step 1/L the suboptimality after t steps is at most L times the initial squared distance over 2t.
Optimization · Gradient Descent and Its Convergence Rates
With step 1/L the iterates converge geometrically at rate (1 - 1/kappa).
Optimization · Gradient Descent and Its Convergence Rates
The smallest gradient norm among the first t iterates is O(1/sqrt t); no statement about minima is possible.
Optimization · Gradient Descent and Its Convergence Rates
With a fixed horizon and tuned step the averaged iterate attains O(1/sqrt t) suboptimality.
Optimization · Gradient Descent and Its Convergence Rates
No method that only queries gradients can beat O(1/t^2) on convex smooth problems or (1 - 1/sqrt kappa)^t on strongly convex ones.
Optimization · Gradient Descent and Its Convergence Rates
On a quadratic, gradient descent diverges precisely when the step exceeds 2/L.
Optimization · Gradient Descent and Its Convergence Rates
The dual optimum never exceeds the primal optimum, with no convexity assumed.
Advanced Optimization · Lagrangian Duality and the KKT Conditions
The dual is a pointwise infimum of affine functions, hence concave regardless of the primal problem.
Advanced Optimization · Lagrangian Duality and the KKT Conditions
For a convex problem with a strictly feasible point the duality gap is zero.
Advanced Optimization · Lagrangian Duality and the KKT Conditions
Under strong duality the five KKT conditions are necessary, and for convex problems they are also sufficient.
Advanced Optimization · Lagrangian Duality and the KKT Conditions
At optimum, every inactive constraint has zero multiplier and every nonzero multiplier marks an active constraint.
Advanced Optimization · Lagrangian Duality and the KKT Conditions
Euclidean projection onto a closed convex set is 1-Lipschitz, and satisfies the obtuse-angle inequality.
Advanced Optimization · Projected, Proximal and Constrained First-Order Methods
Projected gradient descent attains the same rates as gradient descent on constrained convex problems.
Advanced Optimization · Projected, Proximal and Constrained First-Order Methods
- DefinitionProximal operator
The proximal operator trades a step towards minimising a function against staying near the current point.
Advanced Optimization · Projected, Proximal and Constrained First-Order Methods
An explicit closed form that makes proximal gradient practical for the lasso.
Advanced Optimization · Projected, Proximal and Constrained First-Order Methods
Proximal gradient descent on a smooth-plus-convex composite objective attains the O(1/t) rate.
Advanced Optimization · Projected, Proximal and Constrained First-Order Methods
The conditional gradient method attains O(1/t) using only linear minimisations over the constraint set.
Advanced Optimization · Projected, Proximal and Constrained First-Order Methods
Replacing the Euclidean proximity term by a Bregman divergence changes which norm the rate is measured in.
Advanced Optimization · Projected, Proximal and Constrained First-Order Methods
On a quadratic, optimally tuned heavy ball converges at rate 1 - 2/(sqrt kappa + 1), a square-root improvement over gradient descent.
Advanced Optimization · Momentum and Nesterov Acceleration
An O(1/t^2) rate, matching the first-order lower bound.
Advanced Optimization · Momentum and Nesterov Acceleration
A geometric rate with sqrt(kappa) in place of kappa.
Advanced Optimization · Momentum and Nesterov Acceleration
There is a smooth strongly convex function on which a fixed-momentum heavy ball cycles.
Advanced Optimization · Momentum and Nesterov Acceleration
- HeuristicInterpretations of acceleration
Three readings of why momentum helps, none of which is a proof on its own.
Advanced Optimization · Momentum and Nesterov Acceleration
Near a nondegenerate minimiser, Newton's method squares the error at each step.
Advanced Optimization · Newton, Quasi-Newton and Conjugate Gradient
The Newton iterates commute with invertible linear reparameterisation, so no step size tuning is needed and no condition number appears.
Advanced Optimization · Newton, Quasi-Newton and Conjugate Gradient
- PropositionThe secant condition and the BFGS update
BFGS is the minimum-change symmetric positive definite update satisfying the secant equation.
Advanced Optimization · Newton, Quasi-Newton and Conjugate Gradient
The t-th CG iterate is optimal over the Krylov subspace, giving the Chebyshev rate and exact termination in d steps.
Advanced Optimization · Newton, Quasi-Newton and Conjugate Gradient
- Empirical observationSecond-order methods are rarely used at scale
The reasons are cost per step, stochastic curvature estimates and the absence of the local regime the theorems require.
Advanced Optimization · Newton, Quasi-Newton and Conjugate Gradient
- DefinitionThe stochastic gradient oracle
The three standard assumptions on the gradient estimator — unbiasedness, bounded variance, and independence across steps.
With a tuned constant step the averaged iterate attains expected suboptimality of order 1/sqrt T.
The error contracts geometrically to a noise floor proportional to the step size times the variance.
With step of order 1/(mu t) the expected error is of order sigma squared over mu squared t, with no floor.
- TheoremRobbins–Monro conditions
Square-summable but non-summable step sizes give almost sure convergence in the stochastic approximation setting.
The expected squared gradient norm averaged over iterates is O(1/sqrt T) with a tuned constant step.
A batch of size B divides the gradient variance by B, which buys a constant factor and not a better exponent.
A bound on the expected gap gives only a Markov-type tail bound, which is far weaker than an exponential one.
In a small-step limit SGD resembles a stochastic differential equation, a useful picture whose hypotheses rarely hold in practice.
AdaGrad attains a regret bound that adapts to the observed gradient scale per coordinate.
- DefinitionAdam
Exponential moving averages of the gradient and its square, with bias correction.
- TheoremAdam can fail to converge
There is a convex online problem on which Adam with standard parameters has non-vanishing average regret.
Adding lambda times the weight to the gradient is not the same as shrinking the weight, once the update is rescaled per coordinate.
Variance reduction removes the noise floor entirely for strongly convex finite-sum problems.
- Empirical observationVariance reduction does not help deep learning in practice
The methods that provably remove the noise floor for finite sums have not produced wall-clock gains on large neural networks.
The excess risk of ERM is bounded by twice the uniform deviation plus the approximation error of the class.
Learning Theory · Empirical Risk Minimisation and Uniform Convergence
For a class of size N the uniform deviation is of order the square root of log N over n.
Learning Theory · Empirical Risk Minimisation and Uniform Convergence
When some hypothesis has zero risk the rate improves from 1/sqrt n to log N over n.
Learning Theory · Empirical Risk Minimisation and Uniform Convergence
- DefinitionPAC learnability
A class is PAC learnable if a polynomial sample suffices to get low risk with high confidence.
Learning Theory · Empirical Risk Minimisation and Uniform Convergence
Without restricting the hypothesis class no algorithm can generalise, so some inductive bias is mathematically necessary.
Learning Theory · Empirical Risk Minimisation and Uniform Convergence
- Empirical observationUniform convergence is not necessary for generalisation
Overparameterised models can generalise while the uniform deviation over their hypothesis class is vacuous.
Learning Theory · Empirical Risk Minimisation and Uniform Convergence
The combinatorial capacity of a binary hypothesis class.
Learning Theory · VC Dimension, Sauer's Lemma and Rademacher Complexity
A class of VC dimension d produces at most order n^d labellings on n points — polynomial, not exponential.
Learning Theory · VC Dimension, Sauer's Lemma and Rademacher Complexity
- TheoremVC generalisation bound
The uniform deviation is of order the square root of (d log n) over n for a class of VC dimension d.
Learning Theory · VC Dimension, Sauer's Lemma and Rademacher Complexity
Homogeneous halfspaces in d dimensions have VC dimension exactly d.
Learning Theory · VC Dimension, Sauer's Lemma and Rademacher Complexity
- DefinitionRademacher complexity
The expected best correlation of the class with random signs.
Learning Theory · VC Dimension, Sauer's Lemma and Rademacher Complexity
The uniform deviation is bounded by twice the Rademacher complexity plus a concentration term.
Learning Theory · VC Dimension, Sauer's Lemma and Rademacher Complexity
The Rademacher complexity of a finite set grows like the square root of log cardinality.
Learning Theory · VC Dimension, Sauer's Lemma and Rademacher Complexity
Bounded linear predictors have Rademacher complexity BR over the square root of n, with no dimension dependence.
Learning Theory · VC Dimension, Sauer's Lemma and Rademacher Complexity
Composing a class with a Lipschitz function multiplies its Rademacher complexity by the Lipschitz constant.
Learning Theory · VC Dimension, Sauer's Lemma and Rademacher Complexity
For squared loss the risk splits exactly into noise, squared bias and variance.
Learning Theory · Bias–Variance, Interpolation and Double Descent
- HeuristicThe bias–variance trade-off
The claim that increasing capacity must increase variance is a description of certain model families, not a theorem.
Learning Theory · Bias–Variance, Interpolation and Double Descent
In an asymptotic random-design model the risk of the minimum-norm interpolator diverges at the interpolation threshold and decreases beyond it.
Learning Theory · Bias–Variance, Interpolation and Double Descent
The variance of the minimum-norm solution is controlled by the inverse smallest eigenvalue of the sample covariance, which vanishes exactly when p equals n.
Learning Theory · Bias–Variance, Interpolation and Double Descent
- Empirical observationDouble descent in deep networks
Test error curves with a second descent have been reported for networks across width, data size and training time; the mechanism is not established.
Learning Theory · Bias–Variance, Interpolation and Double Descent
The least-squares fit is the orthogonal projection of y onto the column space of X.
Classical ML · Linear, Ridge and Lasso Regression
Among linear unbiased estimators, least squares has the smallest variance.
Classical ML · Linear, Ridge and Lasso Regression
Ridge shrinks each singular direction by a factor depending on its singular value.
Classical ML · Linear, Ridge and Lasso Regression
The derivative of the mean squared error with respect to the ridge parameter is strictly negative at zero.
Classical ML · Linear, Ridge and Lasso Regression
The geometry of the l1 and l2 balls, and the closed forms of the two proximal operators.
Classical ML · Linear, Ridge and Lasso Regression
Gradient equals the design matrix times the residual; Hessian is a variance-weighted Gram matrix.
Classical ML · Logistic Regression
Convexity follows from the PSD Hessian; strictness requires full column rank and non-degenerate probabilities.
Classical ML · Logistic Regression
If the classes are linearly separable the likelihood has no maximiser and the norm of the iterates diverges.
Classical ML · Logistic Regression
At the optimum the predicted probabilities match the observed labels in every feature direction.
Classical ML · Logistic Regression
The asymptotic risk of the 1-nearest-neighbour rule is at most twice the Bayes risk.
Classical ML · Nearest Neighbours and the Curse of Dimensionality
With k growing and k/n going to zero, the k-NN risk converges to the Bayes risk for every distribution.
Classical ML · Nearest Neighbours and the Curse of Dimensionality
Under Lipschitz smoothness the excess risk is of order n to the minus two over d plus two.
Classical ML · Nearest Neighbours and the Curse of Dimensionality
The ratio of the farthest to the nearest distance among n random points tends to one as the dimension grows.
Classical ML · Nearest Neighbours and the Curse of Dimensionality
- Empirical observationNearest neighbours work better than the theory predicts
Real data concentrates near low-dimensional structure, so the relevant exponent is the intrinsic dimension.
Classical ML · Nearest Neighbours and the Curse of Dimensionality
A split can never increase a concave impurity measure in expectation, which is what makes greedy splitting well posed.
Classical ML · Trees, Bagging and Boosting
Averaging B correlated predictors leaves the correlated part of the variance untouched, which is exactly what feature subsampling attacks.
Classical ML · Trees, Bagging and Boosting
The AdaBoost weights and coefficients are exactly the exact line search and greedy coordinate choice for the exponential loss.
Classical ML · Trees, Bagging and Boosting
If every weak learner beats chance by a fixed margin the training error decays geometrically in the number of rounds.
Classical ML · Trees, Bagging and Boosting
Each round fits a base learner to the negative functional gradient of the loss at the current model.
Classical ML · Trees, Bagging and Boosting
- Empirical observationBoosting resists overfitting longer than the training error suggests
Test error often keeps improving after training error reaches zero, which margin theory partially explains.
Classical ML · Trees, Bagging and Boosting
- DefinitionPositive definite kernel
A symmetric function whose Gram matrices are all PSD.
Classical ML · Kernels, RKHS and the Representer Theorem
Positive definiteness is exactly the condition for a feature-map representation to exist.
Classical ML · Kernels, RKHS and the Representer Theorem
Every positive definite kernel has a unique Hilbert space of functions in which it reproduces evaluation.
Classical ML · Kernels, RKHS and the Representer Theorem
Any regularised empirical risk minimiser over an RKHS lies in the span of the kernel sections at the data points.
Classical ML · Kernels, RKHS and the Representer Theorem
The coefficients solve an n-by-n linear system involving only the kernel matrix.
Classical ML · Kernels, RKHS and the Representer Theorem
Sums, products, scalings, limits and compositions with power series of PD kernels are PD.
Classical ML · Kernels, RKHS and the Representer Theorem
The exact solution requires forming and factorising the kernel matrix, which is why approximations exist.
Classical ML · Kernels, RKHS and the Representer Theorem
The distance from a point to a hyperplane is the functional margin divided by the norm of the weight vector.
Classical ML · Support Vector Machines — Complete Derivation
Scaling invariance is removed by the canonical normalisation, giving a strictly convex quadratic program.
Classical ML · Support Vector Machines — Complete Derivation
Maximise the sum of multipliers minus a quadratic form in the labelled Gram matrix, subject to non-negativity and a label-balance constraint.
Classical ML · Support Vector Machines — Complete Derivation
Only points exactly on the margin can have non-zero multipliers, so the solution depends on those points alone.
Classical ML · Support Vector Machines — Complete Derivation
The same dual with the multipliers box-constrained above by C; the slack variables disappear entirely.
Classical ML · Support Vector Machines — Complete Derivation
Every point is interior, on the margin, or a margin violator, determined by its multiplier.
Classical ML · Support Vector Machines — Complete Derivation
Eliminating the slack variables turns the constrained program into an unconstrained convex objective.
Classical ML · Support Vector Machines — Complete Derivation
The risk is controlled by the empirical margin loss plus a term depending on the margin and the data radius, with no dimension dependence.
Classical ML · Support Vector Machines — Complete Derivation
- Empirical observationWhy SVMs are no longer the default
The cubic cost in the sample size, not a theoretical deficiency, is what displaced them.
Classical ML · Support Vector Machines — Complete Derivation
The classic separability obstruction, and the exact reason a hidden layer is needed.
Deep Learning · Approximation Theory and Backpropagation
One hidden layer with a non-polynomial activation approximates any continuous function on a compact set uniformly.
Deep Learning · Approximation Theory and Backpropagation
It is a density statement with no bound on width, no learning algorithm and no sample complexity.
Deep Learning · Approximation Theory and Backpropagation
- TheoremDepth separation
There are functions expressible by a small three-layer network that require exponential width at two layers.
Deep Learning · Approximation Theory and Backpropagation
Reverse accumulation on a computational graph returns the exact derivative, not an approximation, in time proportional to the forward pass.
Deep Learning · Approximation Theory and Backpropagation
The gradient is a product of layer Jacobians, so its norm is governed by a product of singular values and is generically exponential in depth.
Deep Learning · Approximation Theory and Backpropagation
Equivariance is not a property convolution happens to have; it characterises convolution completely.
Deep Learning · Convolution, Recurrence and Normalisation
Convolution becomes pointwise multiplication in the Fourier basis, which diagonalises every convolution at once.
Deep Learning · Convolution, Recurrence and Normalisation
Stacked convolutions grow the receptive field linearly, dilation grows it exponentially.
Deep Learning · Convolution, Recurrence and Normalisation
Backpropagation through time multiplies the same matrix T times, so the gradient decays or explodes exponentially in the sequence length.
Deep Learning · Convolution, Recurrence and Normalisation
- PropositionThe LSTM cell state has an additive path with Jacobian equal to the forget gateproof included
Gating replaces a matrix product by a product of scalars in (0,1), which is what makes long-range gradients survivable.
Deep Learning · Convolution, Recurrence and Normalisation
- Empirical observationWhy batch normalisation helps is not settled
The original internal-covariate-shift explanation has been challenged; smoothing of the loss landscape is the leading alternative.
Deep Learning · Convolution, Recurrence and Normalisation
- DefinitionScaled dot-product attention
A row-stochastic mixing of value vectors with weights given by a softmax over scaled query-key inner products.
Deep Learning · The Mathematics of Transformers
At random initialisation the logits have variance d_k, so dividing by its square root makes their scale independent of the head dimension.
Deep Learning · The Mathematics of Transformers
The attention Jacobian is a variance under the attention distribution, which vanishes when the distribution is concentrated.
Deep Learning · The Mathematics of Transformers
Without positional information a transformer cannot distinguish orderings of its input, which is why positional encodings are required rather than optional.
Deep Learning · The Mathematics of Transformers
Each head has rank at most d_k, so h heads give an attention operator that is a sum of h low-rank pieces rather than one full-rank piece.
Deep Learning · The Mathematics of Transformers
Rotating queries and keys by position-dependent angles makes their inner product a function of the position difference.
Deep Learning · The Mathematics of Transformers
Attention costs n^2 d and the MLP costs n d^2, so the crossover is at sequence length comparable to the model width.
Deep Learning · The Mathematics of Transformers
- HeuristicAttention as a kernel smoother
Softmax attention has the form of a Nadaraya-Watson estimator with an exponential kernel, a useful but incomplete analogy.
Deep Learning · The Mathematics of Transformers
- Empirical observationPre-norm versus post-norm
Placing layer normalisation before the sublayer makes deep transformers trainable without warmup; the reasons are partly understood.
Deep Learning · The Mathematics of Transformers
Even fitting a three-node network to data exactly is NP-complete, so no efficient algorithm can work for all instances.
DL Theory · Why Does Deep Learning Optimization Work?
Convergence to an approximate stationary point at a known rate, and nothing more.
DL Theory · Why Does Deep Learning Optimization Work?
With width polynomial in the sample size and small enough step size, gradient descent on the squared loss converges to zero training error at a linear rate.
DL Theory · Why Does Deep Learning Optimization Work?
Wide networks have a near-constant tangent kernel, which makes the loss satisfy a Polyak-Lojasiewicz inequality along the trajectory.
DL Theory · Why Does Deep Learning Optimization Work?
Feature learning, the widths used in practice and the observed kernel drift all contradict the regime's hypotheses.
DL Theory · Why Does Deep Learning Optimization Work?
For linear models and some simple networks the solution selected by gradient descent is characterised exactly.
DL Theory · Why Does Deep Learning Optimization Work?
- Open problemImplicit bias of SGD on deep networks
No characterisation of the solution selected by SGD on a realistic deep network is known.
DL Theory · Why Does Deep Learning Optimization Work?
With noise, first-order methods reach approximate second-order stationary points in polynomial time.
DL Theory · Why Does Deep Learning Optimization Work?
- Empirical observationFlat minima and generalisation
Sharpness correlates with generalisation across many experiments, but the measure is reparameterisation-dependent and the causal claim is unproved.
DL Theory · Why Does Deep Learning Optimization Work?
- Empirical observationEdge of stability
Training typically settles at a sharpness just above the classical stability threshold two over the learning rate.
DL Theory · Why Does Deep Learning Optimization Work?
- Empirical observationGrokking
Test accuracy can jump from chance to perfect long after training accuracy saturates; several mechanisms are proposed and none is established in general.
DL Theory · Why Does Deep Learning Optimization Work?
- Empirical observationScaling laws
Loss follows a power law in parameters, data and compute over many orders of magnitude, an extremely robust empirical regularity without a derivation from first principles.
DL Theory · Why Does Deep Learning Optimization Work?
- Open problemThe central open problem
There is no theory that predicts, for a given architecture and dataset, that training will find a solution that generalises.
DL Theory · Why Does Deep Learning Optimization Work?
Any joint distribution over sequences factorises as a product of conditionals, so the modelling choice is the parameterisation and the ordering, not the factorisation.
Minimising cross entropy is minimising the KL divergence from the data distribution up to a constant equal to the data entropy.
Cross entropy is bounded below by the entropy of the true conditional, with equality only for a perfect model.
- DefinitionPerplexity
The exponential of the average cross entropy, interpretable as an effective branching factor.
Changing the tokenisation changes the per-token loss even when the per-character loss is identical.
The gradient with respect to the logits is the predicted distribution minus the one-hot target.
Raising the sampling temperature increases the entropy of the sampled distribution.
- DefinitionBradley–Terry preference model
The probability that one response is preferred is the logistic function of the reward difference.
LLMs · RLHF, Bradley–Terry and DPO
Bradley-Terry depends on reward differences, so any function of the prompt alone can be added without changing the likelihood.
LLMs · RLHF, Bradley–Terry and DPO
The optimal policy is the reference policy reweighted by the exponentiated reward.
LLMs · RLHF, Bradley–Terry and DPO
Inverting the closed-form optimum expresses the reward in terms of the policy, turning RLHF into a supervised classification loss.
LLMs · RLHF, Bradley–Terry and DPO
- Empirical observationWhat DPO does and does not replace
DPO removes the reward model and the RL loop but inherits the Bradley-Terry assumption and behaves differently off the preference distribution.
LLMs · RLHF, Bradley–Terry and DPO
The KL penalty is what keeps the optimised policy inside the region where the learned reward is trustworthy.
LLMs · RLHF, Bradley–Terry and DPO
Minimising the fitted loss at fixed compute gives parameter and token budgets that scale as powers of the compute, with the exponents determined by the loss exponents.
Training a dense transformer costs about six FLOPs per parameter per token, two for the forward pass and four for the backward.
A rank-r update to a d-by-k matrix costs r(d+k) parameters instead of dk, and composes with the existing weight at no inference cost.
- Empirical observationIn-context learning
Models perform tasks specified only in the prompt; several mechanisms are demonstrated in restricted settings and none accounts for the general phenomenon.
There are explicit weight constructions under which a transformer's forward pass performs steps of gradient descent on an in-context regression problem.
Routing each token to k of E experts makes the compute proportional to k rather than E, at the cost of memory and load-balancing.
A rank-r adapter on a d×k matrix trains r(d+k) parameters instead of dk, a reduction by dk/(r(d+k)).
Fine-Tuning · Low-Rank Adaptation
Initialising B = 0 makes the adapted model identical to the pretrained one at step zero while keeping the gradient non-zero.
Fine-Tuning · Low-Rank Adaptation
Under standard initialisation, scaling by α/r keeps the expected size of the update independent of r, so the learning rate need not be retuned per rank.
Fine-Tuning · Low-Rank Adaptation
The best rank-r approximation in Frobenius or spectral norm is given by truncating the SVD, with error determined by the discarded singular values.
Fine-Tuning · Low-Rank Adaptation
- ConjectureThe low-rank update hypothesis
That the weight change required to adapt a pretrained model to a downstream task is well approximated by a low-rank matrix — assumed by LoRA, supported empirically, not proved.
Fine-Tuning · Low-Rank Adaptation
Mixed-precision Adam requires 16 bytes of persistent state per trainable parameter, of which only 2 are the weights used in the forward pass.
Fine-Tuning · The Memory Arithmetic of Training
Storing activations for backpropagation costs Θ(L·B·S·d) bytes, independent of parameter count.
Fine-Tuning · The Memory Arithmetic of Training
Storing every k-th layer's activations minimises peak memory at k = √L, giving Θ(√L) storage for one extra forward pass.
Fine-Tuning · The Memory Arithmetic of Training
Freezing the base model removes the 14 bytes of optimizer and gradient state per parameter, but leaves activation memory untouched.
Fine-Tuning · The Memory Arithmetic of Training
Under regularity, the Fisher information equals the expected Hessian of the negative log-likelihood, so the Fisher is curvature.
Fine-Tuning · Forgetting and Regularisation
A Laplace approximation to the posterior from the first task turns sequential learning into the new task's loss plus a Fisher-weighted quadratic pull toward the old weights.
Fine-Tuning · Forgetting and Regularisation
A rank-r adapter changes any layer's output by at most the adapter's spectral norm times the input norm, giving an explicit and controllable deviation budget.
Fine-Tuning · Forgetting and Regularisation
- Empirical observationNarrow fine-tuning degrades unrelated capability
Fine-tuning on a narrow distribution measurably reduces performance on tasks the base model previously handled, with the loss growing with steps and learning rate.
Fine-Tuning · Forgetting and Regularisation
With step size Δ and no clipping, the dequantized value differs from the original by at most Δ/2, deterministically.
Quantization · Uniform Quantization and Its Error
If the input is uniform on one quantization cell, the error is exactly uniform on [−Δ/2, Δ/2] with variance Δ²/12.
Quantization · Uniform Quantization and Its Error
- HeuristicThe additive white-noise model
Treating quantization error as zero-mean noise of variance Δ²/12, independent of the signal, is an approximation that fails at low bit widths.
Quantization · Uniform Quantization and Its Error
Under the noise model, each additional bit adds 6.02 dB of signal-to-quantization-noise ratio.
Quantization · Uniform Quantization and Its Error
Total distortion splits into a clipping term that decreases with range and a rounding term that grows with it, so an interior optimum exists.
Quantization · Uniform Quantization and Its Error
Reconstruction error decouples across output rows and equals a quadratic form with Hessian 2XXᵀ.
Quantization · Hessian-Aware Rounding
Fixing one weight to its quantized value, the error-minimising correction to the remaining weights has a closed form involving one column of the inverse Hessian.
Quantization · Hessian-Aware Rounding
The incurred error is the squared rounding residual divided by twice the corresponding diagonal entry of the inverse Hessian.
Quantization · Hessian-Aware Rounding
Removing one coordinate updates the inverse Hessian by a rank-one correction, so the whole sweep costs one inversion rather than one per weight.
Quantization · Hessian-Aware Rounding
If the input covariance is not diagonal, rounding each weight independently is strictly worse than the corrected update for some weight vector.
Quantization · Hessian-Aware Rounding
- Empirical observationSystematic outlier features in large transformers
Above a few billion parameters, a small fixed set of hidden dimensions carries activations one to two orders of magnitude larger than the rest.
Quantization · Outlier Features and Scale Migration
A per-tensor quantizer whose range is set by an outlier loses log2(max/typical) bits of effective resolution on ordinary values.
Quantization · Outlier Features and Scale Migration
For any invertible diagonal S, XW equals (XS⁻¹)(SW), so quantization difficulty can be moved between activations and weights without changing the function.
Quantization · Outlier Features and Scale Migration
If a channel's scale-up does not move the group maximum, its relative error falls by exactly the scale factor.
Quantization · Outlier Features and Scale Migration
A forward pass over S tokens costs about 2NS + 4LdS² FLOPs, with the quadratic term negligible until S exceeds N/(2Ld).
LLM Ops · Inference Arithmetic and the Roofline
Attainable throughput is at most the minimum of peak compute and arithmetic intensity times memory bandwidth.
LLM Ops · Inference Arithmetic and the Roofline
With b bytes per parameter, weight-limited decoding has arithmetic intensity 2B/b, independent of model size.
LLM Ops · Inference Arithmetic and the Roofline
No implementation can emit a token faster than the time to stream the weights once from memory.
LLM Ops · Inference Arithmetic and the Roofline
The cache costs 2·L·d_kv·b bytes per token per sequence, linear in context length and independent of batch-wide sharing.
LLM Ops · KV Cache, Batching and Little's Law
Available memory after weights, divided by per-sequence cache, bounds the batch size — usually well below the batch needed to be compute-bound.
LLM Ops · KV Cache, Batching and Little's Law
In any stable queueing system the mean number in system equals arrival rate times mean time in system, with no distributional assumptions.
LLM Ops · KV Cache, Batching and Little's Law
With exponentially distributed output lengths, a static batch of size B wastes a fraction 1 − 1/H_B of its decode steps.
LLM Ops · KV Cache, Batching and Little's Law
Allocating the cache in blocks of k tokens wastes fewer than k tokens per sequence, independent of context length.
LLM Ops · KV Cache, Batching and Little's Law
Modified rejection sampling with a residual fallback produces samples distributed exactly according to the target model, for any draft model.
LLM Ops · Speculative Decoding
The per-token acceptance rate is exactly 1 − TV(p, q), tying speedup directly to how well the draft matches the target.
LLM Ops · Speculative Decoding
With draft length γ and i.i.d. acceptance rate α, each round emits (1 − α^(γ+1))/(1 − α) tokens in expectation.
LLM Ops · Speculative Decoding
Wall-clock gain is the expected token count divided by γc + 1, which is maximised at a finite γ whenever the draft is not free.
LLM Ops · Speculative Decoding
A queue with arrival rate above service capacity has a backlog growing without bound, so throughput equals offered load only when utilisation is strictly below 1.
AI Systems · What a Serving System Must Guarantee
The p-quantile of a non-negative latency is at most its mean divided by 1-p, and that bound is attained, so a mean of 200 ms permits a p99 of 20 s and nothing sharper can be said.
AI Systems · What a Serving System Must Guarantee
The 99th percentile of a sum of independent stages is generally far below the sum of their 99th percentiles, and never above it by more than the stage count allows.
AI Systems · What a Serving System Must Guarantee
The six quantities every capacity argument is written in, and the distinction between throughput and capacity.
AI Systems · What a Serving System Must Guarantee
- DefinitionService-level objective
A metric, a quantile and a window — and the three consequences that follow from reading it literally.
AI Systems · What a Serving System Must Guarantee
In any stable system, the long-run average number in the system equals the long-run arrival rate times the long-run average time in the system.
AI Systems · Little's Law and the Capacity of a Serving System
Applying Little's law to the servers alone shows that utilisation equals throughput times mean service time, per server.
AI Systems · Little's Law and the Capacity of a Serving System
To sustain throughput X at latency W the system must hold XW requests concurrently, which bounds the batch size and the KV-cache memory a serving replica needs.
AI Systems · Little's Law and the Capacity of a Serving System
With Poisson arrivals at rate λ and exponential service at rate μ, the number in system is geometric with parameter ρ = λ/μ.
AI Systems · Queueing and the Utilisation Wall
Mean time in system is 1/(μ−λ), so latency diverges like 1/(1−ρ) as load approaches capacity.
AI Systems · Queueing and the Utilisation Wall
For Poisson arrivals and any service distribution, mean queueing delay is λE[S²]/(2(1−ρ)), so it grows linearly in the second moment of service time.
AI Systems · Queueing and the Utilisation Wall
Deterministic service produces exactly half the mean queueing delay of exponential service at the same utilisation.
AI Systems · Queueing and the Utilisation Wall
One queue served by c servers has strictly lower mean waiting time than c separate queues of the same total capacity, and the gap widens with c.
AI Systems · Queueing and the Utilisation Wall
- HeuristicKingman's approximation
For a general single-server queue, mean wait is approximately the product of a utilisation factor, a variability factor and the mean service time.
AI Systems · Queueing and the Utilisation Wall
- DefinitionKendall notation
The A/B/c naming scheme for queues, and what M, D and G stand for.
AI Systems · Queueing and the Utilisation Wall
With independent sub-requests the parent latency is the maximum, whose CDF is the per-call CDF raised to the n-th power.
AI Systems · Tail Latency and Fan-Out Amplification
To keep the parent's p-quantile at t, each of n independent children needs its p^(1/n) quantile at t, which for n = 100 and p = 0.99 is the child's p99.99.
AI Systems · Tail Latency and Fan-Out Amplification
Issuing a duplicate after d seconds and taking the first reply bounds the tail by d plus an independent copy of the latency, so the tail beyond d decays like the square of the original.
AI Systems · Tail Latency and Fan-Out Amplification
Hedging at the p-quantile adds at most a 1−p fraction of extra requests, so hedging at p95 costs 5% more capacity.
AI Systems · Tail Latency and Fan-Out Amplification
If a fraction s of the work is inherently serial, speedup is capped at 1/s however many processors are added.
AI Systems · Scaling Limits — Amdahl, Gustafson and the Coherency Penalty
If the problem grows with the machine so that the serial part stays fixed in absolute time, speedup is linear in the processor count.
AI Systems · Scaling Limits — Amdahl, Gustafson and the Coherency Penalty
With a coherency term, capacity peaks at p* = sqrt((1−α)/β) processors and decreases beyond it.
AI Systems · Scaling Limits — Amdahl, Gustafson and the Coherency Penalty
A replica's KV-cache budget divided by the per-sequence cache size is a hard cap on how many requests it can hold at once.
AI Systems · Sizing a Serving Cluster End to End
Combining the memory ceiling with Little's law bounds a replica's throughput by its concurrency cap divided by request latency.
AI Systems · Sizing a Serving Cluster End to End
The replica count needed is offered load times latency, divided by the product of the concurrency cap and the target utilisation.
AI Systems · Sizing a Serving Cluster End to End
Comparing the memory-limited and compute-limited concurrency caps says whether to buy memory, buy FLOPs, or shorten requests.
AI Systems · Sizing a Serving Cluster End to End
Mean latency is the hit rate times the hit cost plus the miss rate times the miss cost, so the benefit is linear in the hit rate and bounded by the miss cost.
AI Systems · Caching — Hit Rates, Zipf and the Working Set
Caching the C most popular of N items under Zipf exponent a gives a hit rate equal to a ratio of generalised harmonic numbers.
AI Systems · Caching — Hit Rates, Zipf and the Working Set
For exponent below one the hit rate grows like (C/N)^(1−a), so each order of magnitude of cache buys a fixed multiplicative gain.
AI Systems · Caching — Hit Rates, Zipf and the Working Set
However large the cache, speedup is capped by the ratio of miss cost to hit cost, which is Amdahl's law with the miss rate as the serial fraction.
AI Systems · Caching — Hit Rates, Zipf and the Working Set
- DefinitionZipf popularity
Rank-ordered request probabilities proportional to a negative power of the rank, normalised by a generalised harmonic number.
AI Systems · Caching — Hit Rates, Zipf and the Working Set
- HeuristicChe's approximation for LRU
Replacing each item's eviction time by one shared characteristic time gives a closed-form estimate of the LRU hit rate.
AI Systems · Caching — Hit Rates, Zipf and the Working Set
A cached prompt prefix of k tokens saves 2Nk + 4Ldk^2 FLOPs, which is superlinear in the shared length.
AI Systems · Caching — Hit Rates, Zipf and the Working Set
Throwing n balls into n bins uniformly leaves a fullest bin with about log n / log log n balls with high probability.
AI Systems · Load Balancing and the Power of Two Choices
- TheoremThe power of two choices
Sampling d bins and using the least loaded reduces the maximum load to log log n / log d plus a constant — an exponential improvement in d = 2 already.
AI Systems · Load Balancing and the Power of Two Choices
A first-moment argument shows uniform assignment leaves no bin with materially more than log n / log log n balls.
AI Systems · Load Balancing and the Power of Two Choices
Round robin equalises request counts, which equalises load only when service times are identical; least-outstanding-requests equalises occupancy, which by Little's law tracks load.
AI Systems · Load Balancing and the Power of Two Choices
A request needing k independent services succeeds with probability equal to the product of their availabilities, so unavailabilities approximately add.
AI Systems · Availability, Redundancy and Correlated Failure
With n independent replicas and any one sufficing, unavailability is the n-th power of a single replica's, so each replica multiplies the nines.
AI Systems · Availability, Redundancy and Correlated Failure
A system needing k of n replicas is available with probability given by a binomial tail, which is maximised at k = 1 and degrades sharply once k exceeds n/2.
AI Systems · Availability, Redundancy and Correlated Failure
If a fraction beta of failures are common-mode, unavailability cannot be driven below beta times a single component's unavailability, however many replicas are added.
AI Systems · Availability, Redundancy and Correlated Failure
- DefinitionAvailability
The long-run fraction of requests a component serves successfully, and its complement, unavailability, measured in nines.
AI Systems · Availability, Redundancy and Correlated Failure
Unit cost is the hourly price of a replica divided by the tokens it actually delivers, which is its capacity scaled by utilisation.
AI Systems · The Economics of Serving — Cost per Token
Under a single-server queueing model, cost per token is proportional to W/(W−S), so it diverges as the latency target approaches the bare service time.
AI Systems · The Economics of Serving — Cost per Token
In the weight-bound decode regime, tokens per second scale with batch size, so unit cost falls roughly inversely with the batch a replica can hold.
AI Systems · The Economics of Serving — Cost per Token
- DefinitionThe alpha–beta cost model
Transferring n bytes costs a fixed startup latency plus n divided by bandwidth.
AI Systems · The Cost of Collective Communication
Gathering at one root and broadcasting back moves (p−1)N bytes across the root's link, so its time grows linearly in the node count.
AI Systems · The Cost of Collective Communication
Reduce-scatter followed by all-gather moves 2(p−1)N/p bytes per node, which is below 2N for every p, while incurring 2(p−1) latency terms.
AI Systems · The Cost of Collective Communication
Every node must receive at least N(p−1)/p bytes of information, so no algorithm beats the ring's bandwidth term by more than a factor of two.
AI Systems · The Cost of Collective Communication
The ring is bandwidth-optimal for large messages and latency-suboptimal for small ones, with the crossover at a message size proportional to alpha times bandwidth.
AI Systems · The Cost of Collective Communication
The ratio of gradient-synchronisation time to compute time is independent of the parameter count and falls inversely with tokens processed per device per step.
AI Systems · Splitting a Model Across Devices
The ratio of activation-exchange time to compute time is independent of layer count and sequence length, and falls inversely with model width.
AI Systems · Splitting a Model Across Devices
With p stages and m microbatches, the fraction of wall-clock time in which some stage is idle is (p−1)/(m+p−1).
AI Systems · Splitting a Model Across Devices
Each strategy is amortised by a different quantity, so the cheapest configuration mixes them rather than maximising any one.
AI Systems · Splitting a Model Across Devices
Among all preemptive scheduling disciplines on one server, serving the job with least remaining work minimises the mean time in system on every arrival sequence.
AI Systems · Scheduling, Admission Control and Fairness
Under SRPT a job can be delayed by every shorter job that arrives while it waits, so its response time is unbounded in the arrival sequence even at stable utilisation.
AI Systems · Scheduling, Admission Control and Fairness
With first-come-first-served, a request waits for the full service of everything ahead of it, so mean wait scales with the second moment of service time rather than the mean.
AI Systems · Scheduling, Admission Control and Fairness
Capping the queue at K bounds the waiting time by K times the service time, at the cost of a computable rejection probability.
AI Systems · Scheduling, Admission Control and Fairness
A load step above capacity builds a backlog equal to the excess rate times the delay, whatever the controller does afterwards.
AI Systems · Autoscaling — Delay, Overshoot and Standing Headroom
Time to clear the backlog is the delay multiplied by the ratio of total capacity added to the surplus over the new load.
AI Systems · Autoscaling — Delay, Overshoot and Standing Headroom
To absorb a load step of factor g without any backlog, steady-state utilisation must not exceed 1/g.
AI Systems · Autoscaling — Delay, Overshoot and Standing Headroom
Utilisation is a bounded signal that saturates before the SLO breaks, while queue depth keeps growing, making it the better controller input.
AI Systems · Autoscaling — Delay, Overshoot and Standing Headroom
Detecting a difference of size Delta with 80% power at the 5% level needs about 16 sigma squared over Delta squared observations per arm.
AI Systems · Rollout, Canaries and Online Experiments
Duration is the required sample size divided by the traffic share allocated to the canary, so small canaries are slow detectors.
AI Systems · Rollout, Canaries and Online Experiments
Testing at k interim points, each at level alpha, gives an overall false-positive probability that grows with k and tends to 1 under continuous monitoring.
AI Systems · Rollout, Canaries and Online Experiments
Controlling the family-wise error rate across m metrics by Bonferroni raises the required sample size by roughly a factor of log m over the single-metric case.
AI Systems · Rollout, Canaries and Online Experiments
- DefinitionThe request path
The ordered stages a request crosses between the client and the model, and the one job each stage owns.
AI Engineering · The Anatomy of an AI System
- DefinitionControl plane and data plane
The split between components on the per-request path and components that configure them.
AI Engineering · The Anatomy of an AI System
- HeuristicOrder stages by cost of rejection
Put the checks that can reject a request earliest, cheapest first, so that work is never spent on a request that will be refused.
AI Engineering · The Anatomy of an AI System
Only the KV cache and the conversation store hold per-request state worth keeping; everything else should be reconstructible.
AI Engineering · The Anatomy of an AI System
- DefinitionThe streaming response contract
A token stream is a sequence of typed events ending in exactly one terminal event, so that a truncated connection is distinguishable from a completed one.
AI Engineering · API Design for Model Endpoints
Each hop should pass the remaining time budget downstream rather than applying its own fixed timeout, so that total latency is bounded and no hop works on an already-abandoned request.
AI Engineering · API Design for Model Endpoints
A client-supplied key plus a stored result makes a retried generation return the original output rather than paying for and producing a second one.
AI Engineering · API Design for Model Endpoints
Errors must separate retryable from terminal, and caller-fault from service-fault, because those two axes determine the client's next action.
AI Engineering · API Design for Model Endpoints
Model identity belongs in the request and must be explicit and pinnable; the wire schema should only ever gain optional fields.
AI Engineering · API Design for Model Endpoints
- DefinitionWhat a gateway owns
Transport, identity, schema, routing and metering — and explicitly not business logic or model selection policy.
AI Engineering · Gateways, Authentication and Quota
A rate limit protects the service from a moment of excess; a quota protects a commercial boundary over a billing period, and they fail in opposite directions.
AI Engineering · Gateways, Authentication and Quota
- DefinitionThe identity chain
A credential resolves to a principal, a principal to a tenant, and a tenant to a policy — and each arrow can fail in a way the caller must be able to distinguish.
AI Engineering · Gateways, Authentication and Quota
Authentication fails closed and metering fails open, because the cost of the wrong answer is asymmetric in opposite directions.
AI Engineering · Gateways, Authentication and Quota
- DefinitionToken bucket
A counter refilled at a constant rate and capped at a burst capacity, decremented by the cost of each admitted request.
AI Engineering · Rate Limiting Algorithms
Over any interval of length t a token bucket admits at most B + rt units of cost, and this is tight.
AI Engineering · Rate Limiting Algorithms
A fixed-window counter of N per window permits 2N requests in an interval shorter than one window, straddling a boundary.
AI Engineering · Rate Limiting Algorithms
The generic cell rate algorithm with emission interval T and tolerance tau admits exactly the sequences a token bucket of rate 1/T and capacity 1 + tau/T admits.
AI Engineering · Rate Limiting Algorithms
- HeuristicReserve on entry, reconcile on exit
Output length is unknown in advance, so a token limiter must hold a reservation against an estimate and settle the difference when generation ends.
AI Engineering · Rate Limiting Algorithms
Statically dividing a rate limit among N instances admits only the fraction of the budget that reaches each instance, which under skewed routing is far below the intended rate.
AI Engineering · Rate Limiting Algorithms
- DefinitionHosts, clients and servers
An application hosts one client per server, and each server exposes context and capabilities over a JSON-RPC session.
AI Engineering · The Model Context Protocol
Tools are model-controlled, resources are application-controlled and prompts are user-controlled, and that distinction is the design's load-bearing idea.
AI Engineering · The Model Context Protocol
- DefinitionCapability negotiation
A session begins with an initialize exchange in which both sides declare what they support, so neither has to assume.
AI Engineering · The Model Context Protocol
Connecting n applications to m data sources costs n times m bespoke integrations without a protocol and n plus m with one.
AI Engineering · The Model Context Protocol
Tool descriptions and tool results are untrusted input, so consent, isolation and authorisation belong to the host rather than to any server.
AI Engineering · The Model Context Protocol
Exact caching, prefix caching and semantic caching differ in what they key on, what they save and how they can be wrong.
AI Engineering · Semantic Caching
A semantic cache pays off only when the hit rate times the saving exceeds the false-hit rate times the cost of a wrong answer.
AI Engineering · Semantic Caching
Hit rate and false-hit rate are both non-increasing in the similarity threshold, so there is no threshold that improves both.
AI Engineering · Semantic Caching
- HeuristicWhat must never be cached
Anything personalised, time-sensitive, side-effecting or authorisation-dependent is unsafe to serve from a similarity match.
AI Engineering · Semantic Caching
- DefinitionWhat the cold start is made of
Scheduling, image pull, weight load, CUDA initialisation, compilation and warm-up, each with a different remedy.
AI Engineering · Autoscaling and Cold Starts
Loading N parameters at b bytes each over a link of bandwidth B cannot take less than Nb/B seconds, which for a large model over object storage is minutes.
AI Engineering · Autoscaling and Cold Starts
Scaling to zero is cheaper than a warm replica only when the idle fraction exceeds the cold-start cost amortised over the requests it delays.
AI Engineering · Autoscaling and Cold Starts
- HeuristicScale on queued work, with a lead
The controller must act on a signal that grows past saturation and must act early enough to cover the cold start, which means predicting rather than reacting.
AI Engineering · Autoscaling and Cold Starts
- DefinitionFour places a check can sit
Before the model, inside the prompt, after the model and before the side effect — each catching a different class and with different costs.
AI Engineering · Guardrails and Safety Layers
Anything the model reads that it did not receive from the authenticated user is attacker-controlled and must be framed as data.
AI Engineering · Guardrails and Safety Layers
At a false-positive rate q on n requests, qn legitimate requests are blocked, which for small q and large n still dominates the number of genuine catches when the base rate is low.
AI Engineering · Guardrails and Safety Layers
The only check that cannot be talked around is the one in the code that performs the action, using the caller's real authority.
AI Engineering · Guardrails and Safety Layers
- DefinitionThe stages, and what each may not do
Ingest, validate, transform, embed, index and publish, with validation as a gate rather than a filter.
AI Engineering · Data Pipelines and Lineage
Pipelines fail partway, so each stage must be safe to re-run over the same input and produce the same output.
AI Engineering · Data Pipelines and Lineage
- DefinitionThe lineage record
Each artefact records the exact inputs, code version and configuration that produced it, so any output can be traced back to its sources.
AI Engineering · Data Pipelines and Lineage
- DefinitionTraining–serving skew
A discrepancy between how a feature is computed offline and online, which produces a model that is correct in evaluation and wrong in production.
AI Engineering · Data Pipelines and Lineage
Switching embedding models requires re-embedding the whole corpus, so the migration cost is linear in corpus size and independent of query volume.
AI Engineering · Data Pipelines and Lineage
With unbounded retries and an independent failure probability f, each logical request generates 1/(1-f) attempts, which diverges as the service degrades.
AI Engineering · Reliability Patterns
Capping retries at a few percent of successful requests bounds amplification regardless of the failure rate.
AI Engineering · Reliability Patterns
Without randomisation, clients that failed together retry together, so the retry traffic arrives as a spike rather than spread over the backoff interval.
AI Engineering · Reliability Patterns
- DefinitionThe circuit breaker
A three-state machine that stops sending traffic to a failing dependency and probes it periodically rather than continuously.
AI Engineering · Reliability Patterns
- DefinitionBulkheads
Partitioning a shared resource per dependency or per tenant so that exhaustion by one cannot starve the others.
AI Engineering · Reliability Patterns
- DefinitionThe span tree of a model request
One trace per request with nested spans for gateway, retrieval, each model call and each tool call, carrying token counts as attributes.
AI Engineering · Observability for AI Systems
Tokens in and out, time to first token, cache tier hit, tool call outcomes, stop reason and configuration hash.
AI Engineering · Observability for AI Systems
Deciding which traces to keep after the request finishes lets you keep every error and slow request while discarding most of the ordinary ones.
AI Engineering · Observability for AI Systems
- HeuristicPrompts are user data
Prompt and completion text must be redacted or separately access-controlled, because it contains whatever the user pasted.
AI Engineering · Observability for AI Systems
- DefinitionWhat each index type costs
Flat, IVF and HNSW trade build time, memory and query latency against recall in different proportions.
AI Engineering · Vector Search Infrastructure
An answer that requires a document the retriever did not return cannot be produced, so index recall multiplies into every downstream metric.
AI Engineering · Vector Search Infrastructure
Pre-filtering, post-filtering and filtered traversal differ in whether they can silently return too few results.
AI Engineering · Vector Search Infrastructure
- HeuristicTwo-tier indexing for freshness
A small frequently-rebuilt hot index beside a large periodically-rebuilt cold one gives low write latency without paying incremental-update costs on the whole corpus.
AI Engineering · Vector Search Infrastructure
- DefinitionSix things whose change alters behaviour
Model version, system prompt, tool schemas, retrieval index, sampling parameters and guardrail configuration are all deployments.
AI Engineering · Deployment and Rollout
- DefinitionThe rollout ladder
Offline eval, then shadow, then canary, then progressive rollout, each answering a question the previous one could not.
AI Engineering · Deployment and Rollout
A change is only safe to ship if reverting it is a single fast action that does not depend on the thing being reverted.
AI Engineering · Deployment and Rollout
Configuration distributed by a control plane propagates without a rolling deploy, so it is a beta-equal-one correlated failure in the redundancy model.
AI Engineering · Deployment and Rollout
- DefinitionThe loop
Append the user turn, call the model, execute any requested tools, append their results, repeat until the model stops asking or a budget is exhausted.
AI Engineering · Tool Loops in Production
- DefinitionFour independent stopping conditions
A production loop terminates on model completion, step budget, token budget or wall-clock deadline, and all four must exist.
AI Engineering · Tool Loops in Production
Because every step resends the whole transcript, appending r tokens per step costs O(r n squared) prefill tokens over n steps.
AI Engineering · Tool Loops in Production
A retried or replayed tool call must either be safe to run twice or require an explicit confirmation step that the model cannot forge.
AI Engineering · Tool Loops in Production
- Empirical observationSelection accuracy degrades with tool count
Reported evaluations find tool-selection accuracy falls as the number of simultaneously exposed tools grows, motivating retrieval over the tool list itself.
AI Engineering · Tool Loops in Production
- DefinitionThe affinity–pooling tension
Routing to the replica holding a request's KV prefix saves prefill but partitions the queue, and the two effects pull in opposite directions.
AI Engineering · GPU Routing and Cache Affinity
Prefer the cache-warm replica exactly when the prefill saved exceeds the extra queueing its load implies.
AI Engineering · GPU Routing and Cache Affinity
Requests differ by orders of magnitude in size, so the balancing signal must be queued tokens rather than queued requests.
AI Engineering · GPU Routing and Cache Affinity
- DefinitionAdapter-aware routing
Replicas holding different LoRA adapters form overlapping capability classes, turning routing into a constrained assignment rather than a free choice.
AI Engineering · GPU Routing and Cache Affinity
- DefinitionDraining a replica
Removing a replica requires stopping new admissions, letting in-flight generations finish, and bounding the wait with a forced-migration deadline.
AI Engineering · GPU Routing and Cache Affinity
- DefinitionThe iteration-level scheduler
The server schedules per decode step rather than per request, so arrivals and completions are handled between tokens rather than between generations.
AI Engineering · Inference Server Architecture
Reserving max_tokens contiguously per sequence wastes the gap between reserved and used, which for a mixed workload is most of the budget.
AI Engineering · Inference Server Architecture
- DefinitionTwo ways to reclaim a running sequence
A preempted sequence is either swapped out to host memory or recomputed from its prompt, trading bandwidth against compute.
AI Engineering · Inference Server Architecture
- DefinitionPrefill/decode disaggregation
Running compute-bound prefill and memory-bound decode on separate pools lets each be provisioned for its own bottleneck, at the cost of transferring the KV cache between them.
AI Engineering · Inference Server Architecture
- DefinitionFour things called drift
Covariate shift, prior shift, concept drift and upstream corruption have the same symptom and different remedies.
AI Engineering · Drift Detection
- DefinitionThe population stability index
A binned comparison of two distributions, summing the signed difference of bin masses times the log of their ratio.
AI Engineering · Drift Detection
The population stability index is exactly KL(p,q) plus KL(q,p), so it is non-negative and zero only when the distributions agree.
AI Engineering · Drift Detection
- HeuristicThe conventional PSI thresholds
Values below 0.1, between 0.1 and 0.25, and above 0.25 are conventionally read as stable, moderate and significant, with no distributional justification.
AI Engineering · Drift Detection
Independent tests on m features at level alpha, repeated each period, produce alarms at a rate that approaches certainty as m or the number of periods grows.
AI Engineering · Drift Detection
- HeuristicMonitor proxies when labels are late
Refusal rate, output length, tool-call rate, retry rate and escalation rate move before ground truth arrives and are available immediately.
AI Engineering · Drift Detection
- DefinitionThe four parts of an eval
A dataset, a runner pinned to an exact configuration, a grader, and an aggregation with a decision rule.
AI Engineering · Evaluation Harnesses
- DefinitionThe grader ladder
Prefer exact match, then programmatic checks, then reference-based similarity, then a model judge, then a human — cheaper and more reliable first.
AI Engineering · Evaluation Harnesses
- Empirical observationModel judges have systematic biases
Reported evaluations find judges favour longer answers, answers in the first position, and outputs from the model family doing the judging.
AI Engineering · Evaluation Harnesses
With binary grading on n items, the standard error of the pass rate is at most 1/(2 sqrt n), so small sets cannot distinguish small regressions.
AI Engineering · Evaluation Harnesses
Model, prompt, tools, retrieval index and sampling parameters jointly determine behaviour, so all of them must be pinned and recorded.
AI Engineering · Evaluation Harnesses
On the unit sphere the three ranking criteria induce the same ordering; off it they do not.
Dot-product retrieval prefers high-norm documents independently of direction, which is a documented failure mode.
The cosine between two independent uniform directions has an explicit density concentrating at zero at rate one over the square root of the dimension.
The best of N random distractor scores grows like the square root of two log N over d, so the alignment a retriever needs grows with the corpus.
The query-document alignment must exceed the maximum distractor similarity, giving an explicit threshold in terms of corpus size and dimension.
- Empirical observationReal embeddings are anisotropic
Learned embeddings occupy a narrow cone rather than the sphere uniformly, which inflates baseline similarities and invalidates the isotropic model.
Brute force is N d per query with no preprocessing; no known method achieves both sublinear query time and subexponential space in high dimension.
RAG · Vector Search — Exact and Approximate Nearest Neighbours
Pruning requires the query ball to miss most cells, and concentration of distances makes that impossible once the dimension exceeds log of the number of points.
RAG · Vector Search — Exact and Approximate Nearest Neighbours
- DefinitionLocality-sensitive hash family
A hash family whose collision probability decreases with distance, with a gap parameter that determines the achievable exponent.
RAG · Vector Search — Exact and Approximate Nearest Neighbours
The probability that a random hyperplane separates two vectors is their angle divided by pi.
RAG · Vector Search — Exact and Approximate Nearest Neighbours
Concatenating k hashes and using L tables turns the collision gap into a sublinear query exponent.
RAG · Vector Search — Exact and Approximate Nearest Neighbours
Splitting the vector into m subspaces with 256 centroids each gives m bytes per vector and an error that is the sum of subspace quantisation errors.
RAG · Vector Search — Exact and Approximate Nearest Neighbours
- Empirical observationHNSW has no worst-case guarantee
The dominant ANN index in practice is justified by benchmarks and a small-world heuristic, not by a theorem about its recall.
RAG · Vector Search — Exact and Approximate Nearest Neighbours
A retrieval stage's recall bounds everything downstream, so a 0.9-recall index caps the whole system at 0.9 regardless of the reranker.
RAG · Vector Search — Exact and Approximate Nearest Neighbours
The generation probability is a mixture over retrieved documents weighted by the retriever's posterior.
Marginalising once per sequence and once per token give different distributions, and only the second can switch sources mid-generation.
Jensen's inequality gives an evidence lower bound whose gap is the KL divergence between the retriever posterior and the true posterior.
The total variation distance between the RAG output and the oracle output is bounded by the retriever's probability of missing the relevant document.
There are instances where a retrieval failure changes the output distribution by exactly the failure probability, so the bound cannot be improved.
A reranker improves precision within the retrieved set and cannot exceed the first-stage recall.
Corrective, agentic, hybrid and graph RAG are different ways of shaping the posterior over documents, not different probabilistic frameworks.
Under independent steps with success probability p, an n-step trajectory succeeds with probability pⁿ, so the per-step bar for a target T is T^(1/n).
For k independent votes each correct with probability p > 1/2, the majority is wrong with probability at most exp(−2k(p−1/2)²).
With perfectly correlated errors the majority is exactly as reliable as a single sample, however large k is.
With detection probability d and m retries, effective per-step success rises to 1 − (1−p)(1−dp)^m under the stated independence.
Failure probability falls as (1−p)ⁿ, so success improves exponentially in samples while cost grows linearly.
Agents · Inference-Time Search and Best-of-n
From n samples with c correct, 1 − C(n−c, k)/C(n, k) is an unbiased estimate of the probability that k draws contain a correct one.
Agents · Inference-Time Search and Best-of-n
Best-of-n sampling against a continuous reward has KL divergence exactly log n − (n−1)/n from the base policy.
Agents · Inference-Time Search and Best-of-n
With false-positive rate φ, selected-answer precision is bounded regardless of n, and for large n the verifier's errors dominate.
Agents · Inference-Time Search and Best-of-n
- DefinitionCumulative regret
The shortfall of an algorithm's total reward against always playing the best arm in hindsight.
Agents · Tool Selection and Regret
With confidence radius √(2 log t / n), the expected number of pulls of an arm with gap Δ is at most 8 log T/Δ² plus a constant.
Agents · Tool Selection and Regret
Cumulative regret is O(Σ log T/Δᵢ) for gap-dependent bounds, and O(√(KT log T)) uniformly over gaps.
Agents · Tool Selection and Regret
Any algorithm with sublinear regret on every instance suffers Ω(log T) regret on some instance, so UCB is optimal in order.
Agents · Tool Selection and Regret