← All Problems

33. Reservoir Sampling for Eval Set Construction

General Pattern Medium Reservoir Sampling
Grounding: General: building held-out eval sets by uniformly sampling from a large or streaming pool of production traffic is standard practice for training/evaluating any ML-serving system, including a real-time speech pipeline; this is not a confirmed detail of how Cartesia specifically builds its own eval sets.

Problem

Building a held-out evaluation set for a speech model means pulling a uniformly random sample of utterances out of a production traffic stream for human review. That stream has unknown, effectively unbounded length — it can't be buffered into a list and sliced, so the sampler must maintain a uniformly-random sample of size k using only O(k) memory as utterances flow past one at a time. This is the classic Reservoir Sampling problem (Algorithm R).

stream is given as a list here for testability, but the algorithm must process it as if it were a one-pass stream: a single forward loop, never looking back or peeking at len(stream) to shortcut the algorithm, even though Python would let you. seed seeds a random.Random(seed) instance used for all randomness, so results are exactly reproducible.

Source: src/33_reservoir_sample_eval_set.py

def sample_eval_utterances(stream: list[str], k: int, seed: int) -> list[str]: ...

>>> sample_eval_utterances(["u1", "u2", "u3"], k=5, seed=0)
['u1', 'u2', 'u3']
>>> sample_eval_utterances([f"u{i}" for i in range(10)], k=3, seed=42)
['u4', 'u1', 'u9']

Step-by-Step Approach

  1. Initialize an empty reservoir list of capacity k.
  2. For the first k items in the stream (indices 0 through k-1), add each one to the reservoir unconditionally — there's nothing yet to weigh them against.
  3. For every item after that, at index i (0-indexed, so this is the (i+1)-th item), draw a uniformly random integer j in [0, i] inclusive.
  4. If j < k, overwrite reservoir[j] with the current item; otherwise discard the current item and move on.
  5. This rule is exactly what keeps every item seen so far equally likely to be in the final reservoir: at the moment the (i+1)-th item arrives, it lands in the reservoir with probability k/(i+1), and it can be shown by induction that every earlier item independently also survives to that point with probability k/(i+1).
  6. After the stream ends (whenever that is), the reservoir holds a uniformly random sample of size min(k, n) with no bias toward earlier or later items.

The key insight is the acceptance probability k/(i+1) combined with picking the eviction slot uniformly at random from the current reservoir (via j < k) — together they guarantee every item that has streamed past so far has exactly equal odds of surviving to the end, without the algorithm ever needing to know how many items are left or how many there were in total.

Reference solution

import random


def sample_eval_utterances(stream: list[str], k: int, seed: int) -> list[str]:
    rng = random.Random(seed)
    reservoir: list[str] = []

    for i, item in enumerate(stream):
        if i < k:
            # fill the reservoir unconditionally for the first k items
            reservoir.append(item)
        else:
            # for the (i+1)-th item, keep it with probability k/(i+1): draw
            # j uniformly from [0, i] and replace reservoir[j] only if
            # j < k. This is the invariant that makes every item seen so
            # far equally likely to survive to the end, without knowing
            # the stream's total length in advance.
            j = rng.randint(0, i)
            if j < k:
                reservoir[j] = item

    return reservoir

Key Functions & Tricks

  • random.Random(seed) — an isolated, seeded RNG instance rather than the module-level random functions, so results are reproducible and don't interact with any other randomness elsewhere in the program.
  • rng.randint(0, i) — inclusive on both ends; drawing from a growing range [0, i] as i increases is what shrinks each new item's acceptance probability over time.
  • if j < k: reservoir[j] = item — both the acceptance test and the eviction-slot choice in one comparison, since j was already drawn uniformly.
  • O(k) space, O(n) time, single forward pass — no buffering the full stream, no knowledge of total length required in advance.
  • enumerate(stream) — the i it yields is exactly the "how many items seen so far, 0-indexed" value the probability formula needs.

How to Recognize This Pattern

The signal is "uniformly random sample from a stream of unknown or unbounded length, using bounded memory" — if the total length were known and the data fit in memory, random.sample on the full list would be simpler and is the right answer instead. A common variation is weighted reservoir sampling, where items have unequal selection probabilities (e.g. sampling proportional to some priority score), which needs a different acceptance rule (commonly the "A-Res" algorithm using exponential jumps) rather than the uniform k/(i+1) rule here. A common pitfall is peeking at len(stream) to compute an exact sampling probability up front, which defeats the purpose in a true streaming setting and won't translate to a real one-pass stream (a generator, a log tailer, a Kafka consumer) where the total length genuinely isn't known until the stream ends.

← Previous Next →