Composing Probabilistic Checks: Why Error Budgets Do Not Add

A single probabilistic structure has one error parameter and one clean interpretation: a Bloom filter at 1% returns a false positive on about one percent of absent keys. Real systems rarely stop at one. A request passes a membership filter, then a frequency sketch, then a rate limiter built on another sketch, then a cache index that is itself a filter. Each stage has its own error budget, and the temptation is to add them: 1% here, 2% there, and the pipeline is claimed accurate to 3%. That arithmetic is wrong in both directions, and the way it is wrong determines how the budgets should be allocated.

Multiplication, not addition, for chained rejections

Consider two filters in series, where a key must pass both to be treated as present. The probability that an absent key passes both is the product of the per-stage false-positive rates, provided the stages’ errors are independent:

$$ \varepsilon_{\text{pipeline}} = \varepsilon_1 \varepsilon_2 $$

Two filters at 1% each give a combined rate of 0.01%, a hundredfold improvement over either alone. This is the useful direction, and it is why a cheap wide filter in front of an expensive narrow one works: the first removes 99% of the absent keys at low cost, and the second sees a stream that is already mostly present, so its own error applies to a much smaller population.

Now consider the opposite arrangement, where a key is treated as present if either stage accepts it — a union of two indexes, two replicas, two partitions consulted in parallel. The rate is

$$ \varepsilon_{\text{union}} = 1 - (1 - \varepsilon_1)(1 - \varepsilon_2) \approx \varepsilon_1 + \varepsilon_2 $$

Two filters at 1% give 2%. The sum is correct only to first order; the exact form matters when the rates are large. Ten filters at 5% each in a union give $1 - 0.95^{10} \approx 40%$, not 50% — and either figure is unusable, which is the point: union amplifies error far faster than most designs anticipate, because each additional stage is another chance for an absent key to be accepted.

The distinction between the two arrangements is not a detail of the arithmetic. It corresponds to the question the pipeline asks. “Is this key in all of these?” multiplies. “Is it in any of these?” adds. A query planner that consults several filters to rule out partitions is in the first regime; a distributed lookup that asks every node whether it holds a key is in the second.

Independence is the assumption that fails

Both formulas assume the stages err independently, and that assumption is usually false when the stages share a hash function, share a key distribution, or were sized from the same estimate.

Sharing a hash is the sharpest case. Two filters built with the same hash function and the same $m$ but different insertion sets have positively correlated errors for keys that collide in both: a key whose hash lands in a dense region of one filter lands in a dense region of the other, because the region is determined by the hash. The product formula then understates the combined rate, potentially by a large factor, since the failures cluster on the same keys rather than spreading independently.

Sharing a key distribution has a similar effect without sharing a hash. Skewed traffic — a few hot keys and a long tail — means both filters see the same hot keys, and their bit arrays are both saturated in the regions those keys touch. A query for a hot-region key is more likely to false-positive in both than independence predicts. The union bound still holds, so the sum is a safe upper bound, but the product is not a safe lower bound and the measured rate sits between them.

The practical rule is that the product form is trustworthy only when the stages were built from different hash seeds and different key populations. A pipeline that reuses a seed across stages for convenience — one global hash function, one set of parameters — should budget as though the errors add, because for the keys that matter they do.

Where the pipeline error actually lives

For a chain of stages each of which must accept, the pipeline’s error is dominated by the weakest stage only if the others are much stronger. With rates $\varepsilon_1 = 0.10$ and $\varepsilon_2 = 0.001$, the product is $10^{-4}$: the weak stage contributes 99% of the surviving error. Halving the weak stage’s rate halves the pipeline error; halving the strong stage’s rate changes almost nothing. Budget allocation should follow the derivative, not the intuition that every stage deserves an equal share.

The same logic in reverse applies to union. With rates 10% and 0.1%, the union is about 10.1%: the weak stage dominates, and improving the strong stage is wasted effort. In both regimes the marginal value of reducing a stage’s error is proportional to its share of the total, so an equal split of the budget across stages is optimal only when the stages are independent and equally weighted — a coincidence rather than a design principle.

There is a second-order effect when stages are not independent: the derivative shifts toward the stage whose errors correlate with the others. A stage whose failures predict another’s is worth more improvement than its standalone rate suggests, because fixing it removes error from both.

Rates versus counts

The arithmetic above is in rates, and rates are the wrong unit for capacity planning. A filter’s false-positive rate applies per query, so a pipeline that answers $10^9$ queries a day at a combined rate of $10^{-4}$ produces $10^5$ wrong answers daily. Whether that is acceptable depends on what a wrong answer costs, and the two failure directions usually have different costs.

For a membership pipeline the expensive direction is the false positive: it triggers a disk read, a network call, or a full scan that the filter existed to avoid. The false negative is a correctness bug and is not permitted at all, which is why the structures in this cluster are chosen for one-sided error. A pipeline of filters preserves that property — an absent key can be wrongly accepted at any stage, but a present key is never wrongly rejected, because every stage would accept it.

For a frequency pipeline the arithmetic is different again. A Count-Min estimate is biased upward by an amount proportional to the total stream, so chaining two sketches means the second one’s input is already inflated by the first one’s error. The errors compound multiplicatively in the estimate, not additively: a key whose true count is 100, estimated at 110 by the first stage, is then counted as 110 by the second, whose own excess adds on top. The composition is a function applied to a perturbed input, and the perturbation propagates through the function’s derivative. For a monotone estimator the derivative is at least one, so the errors never cancel and the pipeline estimate is biased by at least the first stage’s bias.

The cost of checking twice

Every additional probabilistic stage costs a lookup, and lookups are memory references. A pipeline of three filters at seven probes each is twenty-one random accesses per query, which for a large structure is twenty-one potential cache misses. The error reduction from the third stage is a factor of a hundred in the product regime, but the latency cost is a third more memory traffic — and if the stages are consulted in sequence, the latency adds rather than overlaps.

The design response is to order the stages by cost, not by accuracy. A cheap, weak filter first: it rejects most keys, and the expensive stages only see the survivors. A pipeline arranged this way has an expected cost per query close to the cost of the first stage plus a small fraction of the rest, because the rejection rate of the first stage determines how often the later ones run. Arranged the other way — accurate but expensive first — every query pays the full cost, and the cheap stages never get a chance to reject anything.

The ordering also affects the effective error. A key rejected by the first stage is never tested by the second, so the second stage’s error applies only to keys that survived the first. That is the product form again, but it also means the second stage sees a different key population than the first — the survivors are biased toward keys that collide in the first filter, which is precisely the correlated subpopulation where the second stage is most likely to fail. Independence is violated by the ordering itself, not just by shared hashes.

A budget that survives composition

The workable approach is to fix the pipeline’s total error as a hard requirement, then derive per-stage budgets from the composition law the pipeline actually obeys. For a chain of $s$ independent must-accept stages, an equal split of the total in log space — each stage at $\varepsilon^{1/s}$ — equalises the marginal contribution. For a union of $s$ stages, the split is linear: each gets $\varepsilon/s$, and the sum is exact to first order. For a chain of frequency sketches, the budget must be assigned in the count domain, because the additive error of each stage is a fraction of its own input size, and the sizes differ by the accumulated inflation.

The budgets must then be validated against the correlation the design introduces. If stages share a hash seed, the union bound is the only safe composition, and the sum may be several times larger than the product. If stages share a key population, the same. If the pipeline reorders or filters keys between stages, the population reaching each stage is not the population the budget was computed for.

The last constraint is the one that gets forgotten: a probabilistic structure’s guarantee is a statement about a distribution of queries, and a pipeline changes that distribution. The layered filters of a scalable Bloom filter see every key, but the second layer of a two-stage pipeline sees only the keys the first layer accepted. Sizing the second layer for the original traffic overstates its error; sizing it for the survivor traffic understates the correlation. Neither figure is the right one, and the honest answer is the union bound, applied to the whole pipeline as a single structure with a single measured rate.