# Learned Bloom filters: name the query distribution

A backup filter prevents missing represented keys only when it covers every key
rejected by the current classifier and threshold. A low false-positive rate on
one query workload does not establish the rate on another.

## Exact hypothetical example

Run `python3 model.py` to regenerate example.json and
`python3 -B -m unittest discover -s . -p test_model.py` to check it.
Python standard library only. Code and generated rows are CC0.

All rates are conditional on the key being absent. With classifier-positive
probability a and backup-positive probability b conditional on classifier rejection,
the total is a + (1-a)b. Hold b at 2%, and change a from 1% to 10% to 40%:
the resulting probabilities are 2.98%, 11.8% and 41.2%.

For a front filter independently admitting 10% of absent queries, those become
0.298%, 1.18% and 4.12%. The front filter must contain every represented key.
These are exact rational calculations under stated assumptions, not measurements,
trained model results, confidence intervals or a fixed-memory comparison.

## Why conditional rates matter

The script enumerates 1000 synthetic absent queries. Exactly 100 pass the front
stage; those same 100 are classifier-positive. The backup rejects everything.
The true overall rate is 100/1000 = 10%. Multiplying the marginal 10% rates
incorrectly gives 1%. The classifier rate among front survivors is 100%.
This deliberately correlated fixture does not model independent randomized hashing.

## Operational consequence

Treat represented keys, classifier, threshold and backup coverage as one versioned
configuration. The set-coverage test constructs a model-change counterexample:
retaining an old backup while replacing the classifier can omit a stored key.
This is an elementary contract example, not a discovered product bug.
Rebuild or verify coverage when replacing the model. Track absent-query outcomes
and full model-plus-filter memory; mixed-query accuracy is not the FPR denominator.

## Sources

- Kraska, Beutel, Chi, Dean and Polyzotis, SIGMOD 2018, section 5.1:
  [The Case for Learned Index Structures](https://doi.org/10.1145/3183713.3196909).
  Classifier plus overflow construction and held-out workload evaluation.
- Mitzenmacher, NeurIPS 2018, sections 3-5:
  [A Model for Learned Bloom Filters and Optimizing by Sandwiching](https://proceedings.neurips.cc/paper_files/paper/2018/file/0f49c89d1e7298bb9930789c8ed59d48-Paper.pdf).
  Query-distribution qualification, model-size accounting and sandwich analysis.

Accessed 2026-11-10. Original works retain their rights; no source figure,
training data or third-party implementation is redistributed.