Decentralised training systems

A stylised free-choice study of five limiters configured as L requests per window W, by adversarial search on an integer tick clock and a Poisson overload test. Only the sliding log never admits more than L in a rolling window. The sliding-window counter admits up to about 1.4–1.5L (1.40, 1.45, 1.48 for W = 20, 40, 100), and token and leaky buckets admit 1.90–1.98L; fixed window reaches 2L. At 1.5× offered Poisson load, 47% of rolling windows exceed L for fixed window, 39% for the buckets, 8.8% for the sliding counter and none for the sliding log. The searches give lower bounds, not proofs; one client, no distributed state.

Pairwise gossip averaging as a stand-in for all-reduce: disagreement contracts by exactly (n−2)/(2(n−1)) ≈ ½ per matching round (about 20 rounds at any n), the noise floor is (n−1)(n−2)s²/n (matched to 0.3%), a single stubborn node captures the honest mean at exact rate 1−1/(n(n−1)), and a trust-region clip turns capture into linear creep of at most τ/(n(n−1)) per step. Stylised.

Local-SGD / DiLoCo-style averaging of heterogeneous quadratic workers has a closed-form fixed point: a weighted mean of the workers' optima with weights 1−(1−ηa_i)^H that saturate, so it is exactly unbiased at H=1, forgets curvature as H grows (converging to the unweighted mean), and is non-monotone in between. Weighting by a_i/w_i removes the bias exactly; if the server trusts claimed step counts, a low-curvature worker moves the fixed point from 0.50 to 0.91 by claiming 100 steps instead of 5, tying communication savings to verified work. Wall-clock-optimal H under a bias tolerance is 5.7× faster than H=1 at moderate comm cost, with a non-interval feasible set. Noise formulas match Monte Carlo. Stylised.

Exact checkpoint interval under Poisson churn: w* = (1+W₀(−e^−1−λC))/λ, independent of restart cost, with Young/Daly overshooting by 5–25%; intervals within 2× cost under 3.5%; a synchronous job on n workers restarts at rate nλ so efficiency falls to 50% near n≈700, and admitting flaky workers cut throughput five-fold. Stylised.

A microbatch crosses L stages held by workers that come and go. The drop probability is the exact binomial tail P(Bin(L,q)>s) with stage outage q = ρ + (1−ρ)(1−a)^r, so replicas cannot lift success above the shared-domain floor (1−ρ)^L: at L=48, ρ=10⁻³ no r reaches a 1% drop rate, but allowing one skipped stage makes r=3 enough. At a=0.9 a four-stage skip budget cuts the workers for a 10⁻³ drop rate from 240 to 96; under a per-skip quality loss κ the cost-optimal design is skip-heavy for cheap skips and moves to replication as κ grows (gain over no-skip 2.9× down to 1.08×). Independent outages, multiplicative skip penalty. Stylised.

For a fixed pipeline order, greedy filling is an exact test of a target stage time (agreeing with an independent dynamic program, with and without memory caps), and every order satisfies W/V ≤ T* < W/V + m w_max/V. A speed-blind equal split costs exactly v̄/v_min times the lower bound (2.40× at log-speed spread 0.5, 8.25× at 1.0) while speed-aware cutting stays within 1.4% at 240 layers. What is left is the device order: at 14 layers and 6 devices the worst order is 1.34× the best, fast-first and slow-first sorts do no better than an arbitrary order (all about 1.16× optimal), and pairwise-swap search gets within 1.1%; the penalty fades to 1.03× at 224 layers. Memory that shrinks as speed grows inflates the bottleneck 1.7×. No communication cost, static speeds.

Waiting for the fastest k of n workers has exact round time s + (H_n−H_n−k)/μ for exponential tails, and for Pareto tails the mean is finite iff n−k+1 > 1/α, so with α ≤ 1 waiting for everyone has infinite expected round time. For SGD on a quadratic the time to accuracy has a minimum k and an interior optimum (34× faster than waiting for all at zero fixed cost, 1.12× at large fixed cost). If speed correlates with data, the fastest-k average is biased by Σ(π_i/k−1/n)θ_i; Horvitz–Thompson reweighting removes it but only pays when the bias is large.

Not without incentives. With diminishing returns and a peer-rollout discount θ, symmetric Nash play gives every agent exactly the learning level of a lone agent whatever the swarm size (total effort caps at (a/c−1)/θ), while the efficient level grows linearly in N: welfare per agent is 4.5× higher at N=256. At θ=1 a single agent generates everything. A Pigouvian matching subsidy covering θ(N−1)/(1+θ(N−1)) of cost implements the optimum exactly, and junk rollouts beat honesty iff c−ε > p(τ+F).

With Gaussian policies whose mean has moved by δ standard deviations, the importance weight has exact moments E w = 1 and E w² = e^δ², so the effective-sample fraction is e^−δ² (0.37 at δ=1) and a learner needing fraction ρ accepts a lag of √ln(1/ρ)/drift policy versions. Truncating weights has closed-form lost mass, bias and variance (matched by simulation); the best cap cuts the mean-shift estimator’s MSE 1.9× at δ=1, 12.8× at δ=2 and about 750× at δ=3, and finite-sample ESS is optimistic once weights are heavy-tailed. Equal-variance Gaussians, one statistic.

Training to convergence on random rank-r tasks in R^d is a projection, and the expected loss on a task learned k tasks ago is exactly (r/d)(1−r/d)(ρ^k−λ^k): zero when learned, a peak (0.044 at d=12, r=3, lag 2.5) at a lag near 0.7d/r, then decay because the tasks agree; matched by simulation to the third decimal. Routing tasks to m modules dilutes both rates by m and cuts short-horizon forgetting (5.9× at T=4, m=8) but a single shared model minimises seen-plus-fresh loss at every horizon tried, and two modules forget more than one at T=12. With conflicting tasks forgetting has a floor 2rτ²/d that only task-specific modules remove. Stylised: linear regression, exact convergence, isotropic tasks.

Averaging m modules trained to convergence on random rank-r tasks has an exact residual error 1−2amp+a²(mp+m(m−1)p²) with p=r/d, needing only isotropy. The optimal scale is 1/(1+(m−1)p) and leaves (1−p)/(1+(m−1)p): plain averaging stalls at (1−p)² (0.78 vs 0.47 at m=8, d/r=8) and unscaled task arithmetic diverges (56 at m=64). The decay is harmonic, not geometric, so m parallel workers give a wall-clock speedup that grows only logarithmically (8.9× at m=16, 17× at m=64) and halves in efficiency near m≈d/r×2.5. Seen and fresh losses are closed forms matched by simulation. Stylised: linear regression, exact convergence, consistent isotropic tasks.

Replaying a task alongside each fresh one is a joint projection, so the expected loss on a tracked task is an exact product of 2×2 matrices for any schedule (matched to simulation at every step; recovers the no-replay law). One replay is best at the forgetting-peak lag — 5 at d=32, r=4; 89 at d=128, r=1 — yet removes only 25–42% of total forgetting (replaying at step 1 barely helps at small r/d). A period longer than the peak lag never touches the peak, and a fixed period beats random replay at the same rate only below roughly 1.2–3 peak lags (e.g. 1/8 at d=32, r=4, but random wins at 1/12). Halving forgetting needs a rate 0.25 at d=12, r=3 and 0.015 at d=128, r=1; tasks with 2r≥d are fully recovered by one replay. Stylised: realizable linear regression, exact convergence, one tracked task.

If only m of an old task’s r examples are stored, replaying them with a fresh task is “project out the stored subspace, then take a plain step in dimension d−m”. That gives an exact 2×2 mean-state matrix interpolating no replay (m=0) and full replay (m=r, matched to replay-law to 12 digits), agreeing with simulation at every step. One replay at its best step recovers a fraction of the full saving that is nearly linear in m/r (0.23, 0.47, 0.72 at ¼, ½, ¾ for d=12, r=4; within 0.004 of m/r at d=128, r=8). At a fixed rate, half the memory buys 57–65% of the saving. At a fixed budget of examples per step, one large replay beats many small ones, but only by 0.1–2 points of total forgetting in wide models and up to 6 in a tight one (d=12, r=4), so buffer size matters more than schedule. Stylised: realizable linear regression, exact convergence, one tracked task.

With cluster-structured conflicts, the long-run loss on an old task is exactly (2r/d)[τ_w² + τ_b²(1 − Purity)], where Purity is one minus the router’s expected Gini impurity (matched to simulation within 0.3–2.3% across six routers). Random routing to any number of modules leaves the whole floor; a perfect router onto m modules removes exactly (m−1)/(K−1) of the between-cluster floor, so half needs 5 of 8 clusters’ worth of modules; and a routing error q costs 2q of impurity at first order (10% error returns 36% of the shared-model floor at K=8, 25% returns 59%). Purity is auditable with an unbiased pair-collision estimator. Stylised: realizable linear regression, exact convergence, Gaussian cluster centres, hard routing.

On a quadratic, H inner steps make the outer optimiser see curvatures 1 − (1 − ηa)^H, which saturate at 1: the outer condition number shrinks from κ to about κ/H (1000 → 16.1 at H=64). Per-round rates are exact 2×2 spectral radii (matching literal simulation), the tuned heavy-ball outer step puts every mode at exactly √β*, and the best momentum falls from 0.88 at H=1 to 0.01 at H=1024, so a fixed Nesterov 0.7/0.9 needs 4–8× more rounds. With a sync costing C inner steps, the wallclock-optimal interval is H* ≈ C, worth about √C/2 over syncing every step (16× at C=1000), while plain averaging has no interior optimum. Stylised: noiseless quadratic with a shared Hessian.

On a quadratic with M workers, H noisy inner steps and a heavy-ball outer step, the stationary variance per mode is exactly αV(1+β)/((1−β)s(2(1+β)−αs)) with V the averaged inner noise and s = 1 − (1 − ηa)^H, matching literal simulation to 0.2%. At α = 1 the floor is independent of H; for small α more local steps shrink it by less than a factor of 2. Momentum costs no extra floor at equal effective step (and lowers it at large steps), workers give near-linear speedup (331× at M = 256, α still below 1), and unlike the noise-free case the best sync interval grows as the noise-floor target falls (H* = 5, 11, 38 at C = 10), up to 41× faster than syncing every step. Stylised: quadratic, Gaussian noise, shared Hessian, fixed α.

Each of N workers joins a round with probability p. Averaging the participants has exact stationary variance αV_wm/(s(2−αs)) with m = E[1/K | K≥1]; dividing by the expected count instead is stable only for αs < 2/c, c = 1+(1−p)/(Np), and cannot contract faster than 1−1/c per round (0.22 at N=32, p=0.1). At matched speed the fixed normaliser is quieter at small steps by E[K|K≥1]·E[1/K|K≥1] (1.34×), and averaging wins only at fast rates. Reliable workers bias the fixed point (0.467 instead of 1.000 in our example) unless displacements are inverse-propensity weighted. Matched to simulation within 0.5%. Stylised.

Unbiased compression of each worker's displacement (rand-k, relative variance ω) gives an exact stationary variance αV_w(1+ω)/(N s((2−αs)−αsω/N)) and shrinks the stable outer step to 2/(s(1+ω/N)): more workers restore the step (0.47 → 2.44 for ω=99, N=16 → 256) but never the floor, which stays (1+ω)×. Norm-scaled (QSGD-style) quantisation has a closed form through one scalar T = E|d|²; at equal error energy its loss equals coordinate-wise at H=1 and is about 10% worse at H=16, with the stiff mode's variance doubling. For equal bytes, syncing 1/ρ times less often leaves the floor unchanged at α=1 while keeping a fraction ρ multiplies it by 1/ρ. Matched to simulation within 2%. Stylised: quadratic, shared curvature (no client drift), unbiased compressors only.

Applying the averaged displacement τ rounds late obeys z^τ+1 − z^τ + c = 0 with c = αs, so the stable step is exactly c < 2 sin(π/(4τ+2)) ≈ π/(2τ+1): 2, 1, 0.62, 0.45 for τ = 0…3, shrinking like 1/τ. The fastest single-mode rate is the double root τ/(τ+1), and the stationary noise floor is an exact Yule–Walker solve (closed form (1+c)/((1−c)c(2+c)) at τ = 1) that matches literal delayed-DiLoCo simulation to 0.3%. Delay is free at small steps (+1% at α = 10⁻³, τ = 4) but multiplies the floor by 3.9× at c = 0.8. At an equal floor each delay round costs only about 6% more rounds, so the wall-clock-optimal delay is exactly ⌈latency / compute time⌉ (1.9–7.5× faster than no overlap). Stylised: constant delay, identical workers, quadratics, no momentum.

Workers keep the unsent part of their displacement and add it to the next message. On a quadratic with random sparsification the second moments close exactly: stability requires αs < 2(2−ρ)Nρ/(Nρ²+4(1−ρ)) — half the unbiased limit for a single worker, above the uncompressed limit for large cohorts — and the floor has a closed form that returns to the uncompressed one at small steps (1.08× at ρ=¼ where unbiased compression pays 4×) while the mean keeps its speed. What the residual buys is unbiasedness: dropping converges to the send-rate-weighted mean, feedback to the true mean, but at a variance that only pays off for very small steps. Top-k is simulation only; stylised quadratics.

With worker i running H_i steps, weighted averaging has exact floor α²Σw_i²V_i/(r(2−r)), r = αΣw_is_i. One worker's information is I_∞tanh(λH/2): H=8 carries 20% of the ceiling and H=64 93%, so a fast device is worth far less than its step count. Information-optimal weights span at most 2×, hence equal weights lose at most 9/8 (measured ≤1.09), whereas step-proportional (FedAvg-style) weights lose up to 1.76× per mode and 10.5× on three modes when one worker in eight is 256× faster. Matched to simulation within 1%. Stylised: quadratic, shared optimum (no client drift), fixed H_i.

Because the median and trimmed mean commute with shifts, the outer loop stays exactly linear: floor αV_wv/(s(2−αs)) plus a bias V_wm²/s², with the same stability limit as averaging. With no attackers the median costs N·Var = 1.35 to 1.56 (→ π/2). With a fraction ε of attackers its bias is bounded (Φ(z) = 1/(2(1−ε)): 0.18 noise-sigmas at ε = 1/8) and beats averaging once the attack offset exceeds about 1.4 sigmas; more workers shrink only the variance part (total loss 0.103 → 0.102 from N=8 to 128), while a longer inner loop shrinks the bias (39× from H=1 to 256). Trimming exactly the attacker count is worse than the median. Matched to simulation within 1.3%. Stylised: quadratic, Gaussian noise, shared curvature, constant-offset attackers.

An open research programme rather than a finished project. DiLoCo-style training cuts communication by orders of magnitude, but choosing the sync interval, compressor and outer optimiser is still a sweep at every scale, and the best empirical scaling laws do not say why one axis costs more than another. This repository holds about a dozen closed-form results on a quadratic with gradient noise (a noise floor inflated by 1+ω under compression, a delay stability limit 2 sin(π/(4τ+2)), an optimal outer momentum that falls with the sync interval, a median that costs π/2 in variance). The programme asks whether those structural factors survive on trained transformers and compose, so that two or three measured constants per model size predict the final loss of configurations never run, as well as a refitted scaling law does. Six falsifiable hypotheses each state the result that would refute them. Milestone 1 is done: a simulated M-worker DiLoCo harness on a 0.41M-parameter GPT reproduces the synchronous loop exactly at M=1, H=1 and the quadratic closed form to 2% (ratio 0.983, 95% CI containing it). No result on the research question yet; the proposal's citations are not yet machine-checked because the registries were unreachable.