Hal Turing and Dr. Ada Shannon revisit the paper that reframed B-Trees, hash maps, and Bloom filters as functions that can be learned instead of hand-engineered — and argue over whether "70% faster, order-of-magnitude smaller" survives contact with real workloads.
Looking up a key in a sorted array is equivalent to evaluating the cumulative distribution function of the key set and multiplying by N. A B-Tree approximates that function with branchy comparisons; a tiny model can approximate it with arithmetic.
The paper's central move: every classic index is a function in disguise. That means every classic index has a learnable substitute.
| Classic Structure | What it answers | Learned Substitute |
|---|---|---|
| B-Tree | position of key in sorted order | Recursive Model Index (regression) |
| Hash Map | bucket slot for key | CDF-tuned hash function |
| Bloom Filter | is key (probably) a member? | Binary classifier + overflow filter |
A single two-layer, 32-neuron net trained on 200M web-log timestamps took 80,000ns per prediction — before the record was even located. A B-Tree traversal over the same data ran ~300ns.
Instead of one model doing everything, a hierarchy of cheap models each solves a narrower slice. Hover a stage-1 model to trace its region and fallback path.
Figure 4/5-style comparison. Pick a dataset to update lookup latency and memory footprint. Learned index wins both axes on Lognormal; FAST's SIMD alignment inflates memory.
Lookup latency (ns) — lower is better
Memory footprint (MB, log scale) — lower is better
Model execution can eat up to 72% of total learned-index lookup time. The hosts disagree on whether that undercuts the headline speedup.
A CDF-scaled hash spreads keys more evenly than generic MurmurHash3, especially on linear data like Maps. Toggle to compare bucket collision heatmaps.
A learned classifier can have false negatives, which a real Bloom filter never does. Fix: sandwich a small overflow Bloom filter around it to catch exactly what the model misses.
FPRoverall = FPRτ + (1 − FPRτ) × FPRB — Mitzenmacher, 2018. The formula proves the composition is sound; it says nothing about whether the classifier's accuracy generalizes past 1.7M phishing URLs.
All 2017 results are static, read-only, in-memory. Inserts, updates, and concurrency were explicitly future work — closed by later papers.