What does it cost to skip the slowest workers?

research/straggler-backup

Waiting for the fastest k of n workers: exact order-statistic round times (Pareto mean finite iff n−k+1 > 1/α), exact SGD time-to-accuracy with a minimum k and an interior optimum (34× over wait-for-all at s=0, 1.12× at s=32), joint step tuning, and the exact selection bias of the speed filter with Horvitz–Thompson correction.

10 tests

What it found

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.

A figure from its own output

Figure produced by research/straggler-backup: round_time — straggler-backup/experiments/round_time.svg, written by the project's own experiment code.

Paper, code and results

More in Decentralised training systems

Does a bigger swarm learn more from shared rollouts?Rollout sharing in swarm RL as a public-goods game: Nash gives every agent a lone agent's learning level whatever N (total effort caps at (a/c−1)/θ) while efficient welfare is 4.5× at N=256; at θ=1 one agent generates; a Pigouvian matching subsidy (fraction θ(N−1)/(1+θ(N−1)) of cost) implements the optimum; junk beats honesty iff c−ε > p(τ+F).
How stale can a shared rollout be before it is worthless?Stale off-policy rollouts in swarm RL: exact importance-weight moments (E w²=e^{δ²}, ESS fraction e^{−δ²}), closed-form truncation bias/variance verified by simulation, best cap cuts shift-estimation MSE 1.9× at δ=1 and ~750× at δ=3, and the staleness window √ln(1/ρ)/drift.
How fast does a shared model forget a task, and does splitting it into modules help?Exact catastrophic-forgetting law for sequential training on random low-rank tasks: (r/d)(1−r/d)(ρᵏ−λᵏ) rises then vanishes, uniform module routing dilutes it but sharing wins on seen-plus-fresh loss, conflicting tasks leave a floor 2rτ²/d.
How should independently trained modules be merged, and how much does parallel training buy?Merging independently trained modules on random low-rank tasks: exact residual 1−2amp+a²(mp+m(m−1)p²), optimal scale 1/(1+(m−1)p) (averaging stalls at (1−p)², unscaled sum diverges), harmonic 1/m decay, parallel speedup only logarithmic (8.9× at m=16, d/r=8).
When should a continual learner replay an old task, and does a fixed schedule beat random replay?Exact expected forgetting under replay schedules in sequential training on random low-rank tasks: 2×2 matrix recursion matches simulation, one replay is best at the forgetting-peak lag yet removes only 25–42%, a fixed period beats random replay only below ~1.2–3 peak lags, halving forgetting needs rate 0.25 (d=12, r=3) to 0.015 (d=128, r=1).
How much of an old task must a continual learner store, and is it better to replay a little often or a lot rarely?Partial replay when only m of an old task's r examples are stored: exact 2×2 law interpolating no replay and full replay, best-step saving nearly linear in m/r, and at a fixed example budget a few large replays beat many small ones by only 0.1–6 points.

All 23 Decentralised training systems projects →

Other research topics

Proper scoring & elicitation28 Effort & peer prediction9 Verification games & slashing19 Detection & tolerances14 Markets as routers13 Prediction-market design9 Paying contributors8 Decentralised training systems23 Digital twins & sim-to-real164 LLM chip design loops40 Robot manufacturing loops53 Ambient AI assistant46 Self-replicating manufacturing34 Simulation-first design64 Engineered clothing45 Task-specific AI accelerators40 Algorithmic chip-design loops42 Open-source purpose-built robots44 The software-engineering loop43 Adversarial human imitation41 Open-source residential construction41 Autonomous multi-angle capture34 Sensing, imaging and 3D31 Energy supply and dense energy storage39 Robot societies among people31 Agentic co-design of low-cost robots27 Laundry-hanging robots25 Machine learning on qualitative data23 Robots on the building site27 Civilizations & group psychology1 History & human sciences1

Produced with AI assistance (Claude). Results are from the code in this repository and are simulated or stylised unless the abstract says otherwise; nothing here implies affiliation with or endorsement by any lab, researcher or company cited. MIT licensed.