Definition
Plain language
A way to keep a fair random sample from a stream of data without knowing in advance how much data there will be.
As stated in the literature
A streaming algorithm that maintains a fixed-size uniform random sample over an arbitrarily long or unbounded sequence in a single pass; used in this corpus to estimate attention-score thresholds and memory statistics on the fly.
Why it matters: It enables fair sampling and live statistics from data too large or open-ended to hold in memory all at once.
For example, a program reading an endless feed of tweets can keep a fair random hundred of them without ever storing the whole feed.
Heard on the show
“… The paper proposes some heuristics — reservoir sampling estimators that try to set it so the resulting set is about the right size — but it ultimately …”Episode 036 — Sparse Attention Was the Wrong Frame. Treat It as Geometry Instead.