Learned LSM-trees: Two Approaches Using Learned Bloom Filters

Nicholas Fidalgo; Puyuan Ye

REVIEW 4 major objections 5 minor 9 references

Learned LSM-trees: Two Approaches Using Learned Bloom Filters

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Two learned designs for LSM-trees—one that skips unneeded Bloom filter probes and one that replaces them with compact learned models plus tiny backup filters—can cut read latency by up to 2.28x or cut per-level filter memory by 70–80%.

desk verdict A solid but green systems experiment whose zero-false-negative learned filter only works on a frozen tree, and whose classifier skipping outright breaks correctness. read the letter →

arxiv 2508.00882 v1 pith:ZAWTPUPW submitted 2025-07-24 cs.DS cs.LG

Nicholas Fidalgo , Puyuan Ye This is my paper · ORCID

classification cs.DScs.LG

keywords learnedBloomfilterLSM-treepointlookuplatencyclassifier-basedskippingfalse-negativeratememoryfootprintgradientboostedtreeskey-valuestore

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that machine-learned components can be dropped into the LSM-tree lookup path to improve either latency or memory without giving up correctness in the memory-saving design. The first approach trains a per-level classifier to skip Bloom filter probes for levels where a key is unlikely to be, cutting average GET latency by up to 2.28x while accepting a tunable false-negative rate. The second replaces each level's Bloom filter with a compact classifier plus a small backup filter that stores the model's false negatives, achieving zero false negatives and matching baseline latency while reducing per-level memory by 70–80%. If these results hold beyond the static, pre-trained setting, learned auxiliary structures become practical for read-heavy and memory-constrained key-value stores.

What carries the argument

The central objects are two per-level structures built on gradient-boosted tree classifiers. The first is a level-membership classifier that takes 45 engineered features derived from the key (powers, logs, trigonometric, digit-based, and bit-level encodings) and emits a binary prediction; a positive prediction falls through to the original Bloom filter, while a negative prediction skips that level entirely. The second is a sandwich learned Bloom filter: a compact classifier makes the primary membership decision, and a backup Bloom filter containing only the classifier's training-time false negatives guarantees that no true key is rejected. The Monkey-style LSM-tree—1 MB MemTable, 10x size ratio, leveled compaction, per-level Bloom filters from L1 onward—serves as the baseline configuration against which both designs are measured.

What would settle it

Run the learned Bloom filter on a tree that ingests new writes after training, or that performs compactions migrating keys across levels, and check whether any key present in a level is missed by both the classifier and the backup filter; a single such miss refutes the zero-false-negative guarantee. For the classifier, feed a query workload drawn from a different key distribution and record the bypass rate and false-negative rate; if true-negative precision collapses, the latency speedup will not survive distribution shift.

Watch

Extended reading notes

Core claim

The central claim is that two learned designs outperform or match a traditional Bloom-filtered LSM-tree on disjoint axes. On a Monkey-style LSM-tree with leveled compaction and a 10x size ratio, a gradient-boosted classifier trained on engineered key features bypasses roughly one-third of Bloom filter checks, yielding GET speedups from 1.56x to 2.28x depending on workload, at the cost of false-negative rates up to 31% on deep-level lookups. The learned Bloom filter, following the sandwich construction, stores only the classifier's false negatives in a small backup Bloom filter and thereby reports zero false negatives across all workloads while keeping latency within 1% of baseline and cutting per-level filter memory by 70–80%.

Load-bearing premise

The evaluation assumes a static tree: all models are trained offline and every workload runs on identical SSTable data, so the backup Bloom filter in the learned design already contains every false negative that can occur during testing.

Editorial extensions

If this is right

Classifier-guided skipping can cut average GET latency roughly in half in read-heavy workloads, with the largest absolute gains on deep-level lookups.
A learned Bloom filter can hold 70–80% less memory per level while reporting zero false negatives, making it a candidate for memory-constrained deployments.
The latency speedup comes from bypassing about one-third of Bloom filter probes, and the benefit increases with level depth because deeper probes are more expensive.
The classifier variant adds 5.6–6.1 MB of model memory, whereas the learned filter uses 530–903 KB per level, quantifying the memory-versus-latency trade-off between the two designs.
The zero-false-negative guarantee of the learned filter holds because the backup filter is built on the model's false negatives at training time and requires those negatives to remain stable during serving.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the static-tree assumption were lifted—allowing writes and compactions after training—the zero-FNR guarantee would require periodic retraining or dynamic backup-filter updates, since keys migrate between levels and new keys appear.
The classifier's strong latency gains at moderate accuracy suggest that even imperfect predictors can win if their true-negative precision is high, so reporting precision and recall per level would sharpen the design guidance.
A single multiclass predictor that directly outputs the most likely level could replace per-level binary classifiers and enable prefetching, though the paper reports that its own preliminary multiclass experiments were less accurate.
The same sandwich construction could be applied to fence pointers, with a regression model predicting the page index directly instead of binary searching the pointer array, potentially shaving cache misses per lookup.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the short version: the paper is a clean implementation of two known learned-filter ideas in a Monkey-style LSM-tree, with honest experiments and code on GitHub. But the central correctness claims don't hold up in a dynamic tree. The classifier approach returns false negatives (up to 31% at Level 3), which means a GET for an existing key can return NULL. The learned Bloom filter's "zero false negatives" is true only by construction on the static dataset used for training and testing; once new writes or compactions move keys around, the backup filter won't contain the new false negatives. The paper acknowledges this in Section 7, where the flush-triggered retraining pipeline is described as future work, not implemented.

What is genuinely new: applying Mitzenmacher's sandwich learned Bloom filter per level in an LSM-tree, and measuring classifier-guided skipping. The experimental setup is transparent—fixed Monkey parameters, uniform random keys, six workload types, multiple runs—and the code is available. That is real work and earns credit.

The soft spots are significant. The classifier's false negatives violate key-value store correctness; calling that "modest" undersells it. The zero-FN learned filter is only demonstrated on a frozen tree; no experiment exercises writes or compactions after training. The memory numbers are internally inconsistent: Table 1 says the learned filter model uses 530–903 KB per level, but Figure 4 claims the learned filter at Level 1 is 12 KB—an order of magnitude off, and the backup filter size is never reconciled. Results are reported from the "best run" with no error bars, which weakens the latency claims. The related work also does not compare with other learned LSM systems, so the contribution is a legitimate extension but not situated in the current landscape.

Who this is for: someone working on learned index structures who wants a starting point for LSM-specific evaluation. It is not a publishable-as-is claim that learned components are production-ready. A revision that reframes the classifier as approximate querying, proves or implements dynamic retraining, fixes the memory accounting, and adds error bars could be worth another look.

My recommendation: send it to peer review, but with the expectation of major revision. The experiment is real, the code is reproducible, and the failure modes are instructive—but the correctness and static-data issues are load-bearing, and the memory inconsistency needs to be fixed before the paper can be taken seriously.

Referee Report

4 major / 5 minor

Summary. This paper proposes two ways to use learned models in LSM-tree GET paths. The first is a per-level gradient-boosted classifier that decides whether to consult a level's Bloom filter; if the classifier predicts absence, the level is skipped entirely. The second replaces each per-level Bloom filter with a learned classifier plus a small backup Bloom filter populated with the model's training-time false negatives. The authors implement both designs in a Monkey-configured LSM-tree and evaluate them on six GET-only workloads. They report up to 2.28x latency speedup for the classifier (at the cost of a false-negative rate) and zero false negatives with 70-80% memory reduction per level for the learned Bloom filter. The evaluation is performed entirely on a static tree using the same SSTable data used for training.

Significance. If the results held in a dynamic system, the paper would be a useful empirical data point for learned components in LSM read paths. The authors provide a concrete code artifact, adopt a recognized Monkey-style baseline, and test several workloads. However, the central claims are not established by the reported experiments. The classifier's speedup is obtained only by allowing GET to return NULL for existing keys in a substantial fraction of lookups; the learned filter's zero-false-negative property holds only on the static training set; and the reported memory savings contradict the model sizes stated elsewhere in the same paper. The absence of any workload with writes or compactions after training leaves the defining dynamic behavior of an LSM-tree untested. The paper is clearly written in places and the system-building effort is visible, but the central quantitative claims are currently unsupported.

major comments (4)

[Algorithm 1; Table 2] Algorithm 1 skips level i when Classifier_i(k)=0 (lines 6-13). If k is actually stored in that level, the GET procedure returns NULL at line 15. Table 2 reports classifier FNR values of 0.1125 for Random, 0.2125 for Sequential, and 0.3125 for Level-3 targeted queries, with per-level FNRs of 0.2727-0.3265 on Level 3. A key-value store that returns NULL for an existing key is incorrect, and a 31% false-negative rate is not 'modest'. The abstract's claim that the classifier reduces GET latency is therefore only valid if the store is allowed to return wrong answers to point lookups, which is not an acceptable trade-off for a standard key-value store. Section 7 also acknowledges that subsampling at deeper levels contributes to the elevated FNR, but this does not mitigate the correctness violation.
[Algorithm 2; Sections 4.2, 5.3, 6, 7] The zero-false-negative guarantee of Algorithm 2 is true by construction on the test set, not as a property of the learned filter under operation. The backup Bloom filter is populated with the classifier's false negatives during training (Section 4.2), and Section 6 states that all workloads run on 'identical SSTable data' to the training data. For any key that appears in a level only after training - through a new write, a flush, or a compaction - the classifier may reject it and the backup filter will not contain it, causing a false negative. Section 7 describes a flush-triggered retraining pipeline only as future work and reports no experiment that exercises it. Thus the 'zero false negatives' claim is not demonstrated for a dynamic LSM-tree, which is the operating regime of the system the paper targets.
[Figure 4 vs. Section 4.4 and Table 1] Figure 4 states that the learned Bloom filter at Level 1 occupies about 12 KB versus 68 KB for the traditional filter, an 80% reduction. Yet Section 4.4 and Table 1 report that the learned-design classifier itself is 530-903 KB per level. If model memory is included, the learned design is several times larger than the traditional Bloom filter, which contradicts the 'cutting memory usage per level by 70-80%' claim in the abstract. Either the figure omits the classifier memory or the model-size numbers in the text are wrong; the manuscript does not resolve this inconsistency, and the memory-savings claim is therefore not supported.
[Section 6] Section 6 says that the reported results correspond to 'the run that best illustrates the consistent patterns observed' rather than to means, medians, or confidence intervals over the multiple runs. With no error bars or variance reported, the speedup, accuracy, and FNR numbers are not statistically grounded, and the phrase 'consistent patterns' is not quantified. This weakens the empirical support for the paper's headline quantitative claims, especially because the same section also shows per-level FNRs that vary widely across workloads.

minor comments (5)

[Section 5.6] The text says the classifier lookup algorithm 'was given earlier as Algorithm 2' and the learned-Bloom mechanism is 'detailed in Algorithm 3 from the Design section,' but the correct algorithms are Algorithm 1 and Algorithm 2, respectively; the cross-references are wrong.
[Figure 1 and Table 2] The narrative in Figure 1 describes average times such as '181 ms,' while Table 2's header says all times are in microseconds. The units should be made consistent throughout.
[References [4] and [9]] The related-work text describes Kipf et al. as a learned replacement for B-trees and Tsai et al. as learned hash tables, but the cited papers are about learned cardinality estimation and nearest-neighbor indexing; the citations do not match the claims.
[Figure 4] Figure 4 lacks clear axis labels and does not explain whether the plotted learned-filter size includes the classifier weights or only the backup Bloom filter; given the 530-903 KB model sizes elsewhere, this needs to be resolved.
[Section 7, 'False Negatives and Spike Analysis'] The claim that most speed gains arise from correctly skipping filter checks 'rather than merely exploiting its own errors' is not established, because the paper does not compare the classifier's decisions against ground-truth level membership on the skipped keys.

Circularity Check

2 steps flagged · score 5.0 of 10

The learned-Bloom zero-false-negative claim is tautological on the identical static test set, and classifier accuracy/FNR are in-sample fits; latency and memory measurements remain independent.

self definitional [Section 4.2, Algorithm 2, Section 6, Table 2]
"If the model returns false, we consult the backup Bloom filter—constructed only on the model’s false negatives—to avoid erroneous rejections. ... Each workload was executed across multiple runs on identical SSTable data."

Algorithm 2 returns a key whenever the classifier predicts presence and it is found, and otherwise falls back to BackupFilteri. Because the backup filter is constructed from exactly the classifier's false negatives on the training set, and because every test workload reuses the identical SSTable data from which those training labels were derived, a present key rejected by the classifier is guaranteed to be in the backup. The reported FNR (Lrn.) = 0.0000 is therefore true by construction, not a measured property of the model on unseen data. Under post-training writes or compaction, a new key appearing in a level the classifier has not seen would not be in the backup; Algorithm 2 would then return NULL for that key, so the correctness claim does not extend to the dynamic regime.
fitted input called prediction [Section 5.4, Section 5.7, Section 6, Table 2]
"Keys are sorted and flushed according to the tree’s leveling compaction policy, and metadata on key-level associations is logged for use in supervised training of predictive models. ... Each workload was executed across multiple runs on identical SSTable data."

The classifier's level labels are extracted from the very same tree layout used for every test workload. Training on those key-level associations and then measuring accuracy and FNR on identical SSTable data makes the reported accuracy (e.g., 0.9100 Random, 0.7500 Level 3) and FNR (e.g., 0.3125 Level 3) in-sample resubstitution statistics, not out-of-sample predictions. These numbers characterize how well the fitted classifier reproduces its own training distribution. For keys inserted after training, there are no training labels at all, and the classifier could skip a level containing the key, producing a false negative and an incorrect NULL result.

full rationale

The paper is an empirical engineering report rather than a formal derivation chain. The measured latency speedups (up to 2.28x) and memory reductions (70-80%) are genuine runtime and memory measurements on the implemented system and are not circular. The citations to Monkey, Mitzenmacher's sandwich filter, and algorithms-with-predictions are external prior work and are not load-bearing self-citations. The circularity is concentrated in the two headline 'prediction' claims. The learned Bloom filter's zero-false-negative result is tautological given the construction: the backup filter is defined as the storage of the classifier's false negatives found during training, and all workloads run on identical SSTable data, so no present key can be rejected by both the classifier and the backup. The classifier's accuracy and FNR figures are similarly in-sample fits because the training labels come from the same tree layout used for evaluation. Section 7 describes a flush-triggered retraining pipeline as a mitigation, but it is not implemented or benchmarked, so the experiments do not demonstrate behavior under post-training inserts or compactions. These issues undercut the generality and predictive content of the correctness and accuracy claims, though the honest latency and memory measurements provide independent empirical content, resulting in a moderate score.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central claims rest on hand-chosen model hyperparameters, a fixed decision threshold, and the static-data assumption. The classifier route additionally requires accepting false negatives as a valid correctness trade-off, which is not standard for key-value stores.

free parameters (4)

Gradient boosting hyperparameters (n_estimators=200, max_depth=6, learning_rate=0.1)
Hand-chosen in Section 5.5; no ablation shows sensitivity, and they determine model size and inference cost.
Fixed decision threshold 0.5 = 0.5
Section 7 mentions dynamic thresholds as future work; the fixed threshold controls the trade-off between bypass rate and false-negative rate.
Backup filter false-negative budget delta = delta = 0.01 in motivating example
Section 4.2 motivates backup size with delta = 0.01, but the actual delta and resulting backup filter sizes used in experiments are not reported.
Level 2 and Level 3 training subsample rate = 10-20%
Section 7 states 10-20% of Level 2 and Level 3 keys were subsampled to bound training time; this affects tail-key accuracy and reported FNR.

assumptions (5)

standard math Standard Bloom filter false-positive formula and optimal k = (m/n) ln 2.
Used in Section 3.2 as the theoretical basis for filter tuning; standard result.
domain assumption Leveled compaction creates non-overlapping key ranges per level, so per-level classifiers can learn key-to-level mappings.
Sections 5.3 and 5.4 rely on Monkey-style leveling; if levels overlap heavily (e.g., tiered compaction or L0), the classifier's prediction task changes.
ad hoc to paper The tree is static during evaluation; no writes or updates occur after training.
Section 5.4 pre-trains models and Section 6 runs all workloads on identical SSTable data; this is required for the learned Bloom filter's zero-false-negative guarantee.
ad hoc to paper Returning a false negative (NULL for an existing key) is an acceptable cost.
The classifier design can skip a level that contains the key; standard key-value store semantics forbid this, and the paper's own FNR numbers acknowledge it.
domain assumption Randomly generated 128-bit keys are representative of real-world key distributions.
Section 5.1 chooses random keys to avoid artificial patterns, but this also means the engineered features may not transfer to skewed real workloads.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Learned LSM-trees: Two Approaches Using Learned Bloom Filters." pith.science (2026). https://pith.science/paper/ZAWTPUPW

@misc{pith2026250800882,
  author       = {Pith},
  title        = {Pith review of: Learned LSM-trees: Two Approaches Using Learned Bloom Filters},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZAWTPUPW}},
  note         = {Machine review of arXiv:2508.00882}
}

read the original abstract

Modern key-value stores rely heavily on Log-Structured Merge (LSM) trees for write optimization, but this design introduces significant read amplification. Auxiliary structures like Bloom filters help, but impose memory costs that scale with tree depth and dataset size. Recent advances in learned data structures suggest that machine learning models can augment or replace these components, trading handcrafted heuristics for data-adaptive behavior. In this work, we explore two approaches for integrating learned predictions into the LSM-tree lookup path. The first uses a classifier to selectively bypass Bloom filter probes for irrelevant levels, aiming to reduce average-case query latency. The second replaces traditional Bloom filters with compact learned models and small backup filters, targeting memory footprint reduction without compromising correctness. We implement both methods atop a Monkey-style LSM-tree with leveled compaction, per-level Bloom filters, and realistic workloads. Our experiments show that the classifier reduces GET latency by up to 2.28x by skipping over 30% of Bloom filter checks with high precision, though it incurs a modest false-negative rate. The learned Bloom filter design achieves zero false negatives and retains baseline latency while cutting memory usage per level by 70-80%. Together, these designs illustrate complementary trade-offs between latency, memory, and correctness, and highlight the potential of learned index components in write-optimized storage systems.

Figures

Figures reproduced from arXiv: 2508.00882 by the authors.

**Figure 2.** Speedup factors of Classifier and Learned variants over Traditional across all workloads. [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗

**Figure 3.** Per-lookup latency profiles in a 3×2 grid. Classifier dips indicate Bloom-filter bypasses; Learned-Bloom aligns with Traditional. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Memory usage comparison between traditional and learned Bloom filters across levels. [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]

**Figure 5.** Figure 5: Average query time for traditional vs. learned Bloom filters across levels. Despite smaller [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

9 extracted references · 7 canonical work pages

[1]

Space/time trade-offs in hash coding with allowable errors

Burton H Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422–426, 1970

1970
[2]

Ada-bf: Adaptive bloom filter with learned model

Peng Dai and Anshumali Shrivastava. Ada-bf: Adaptive bloom filter with learned model. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 1551–1566, 2020

work page 2020
[3]

Monkey: Optimal navigable key-value store

Niv Dayan and Stratos Idreos. Monkey: Optimal navigable key-value store. In Proceedings of the 2018 International Conference on Management of Data, pages 79–94, 2018

work page 2018
[4]

Learned cardinalities: Estimating correlated joins with deep learning

Andreas Kipf, Tobias Kipf, Benedikt Radke, Alfons Kemper, and Thomas Neumann. Learned cardinalities: Estimating correlated joins with deep learning. In CIDR, 2019

work page 2019
[5]

The case for learned index structures

Tim Kraska, Alex Beutel, Ed H Chi, Jeff Dean, and Neoklis Polyzotis. The case for learned index structures. Proceedings of the 2018 International Conference on Management of Data, pages 489–504, 2018

work page 2018
[6]

A model for learned bloom filters and optimizing by sandwiching

Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Proceedings of the 36th ACM Symposium on Principles of Distributed Computing, pages 123– 131, 2018

work page 2018
[7]

Algorithms with predictions

Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. arXiv preprint arXiv:2006.09123, 2020

arXiv 2006
[8]

Abelian subgroups, nilpotent subgroups, and the largest character degree of a finite group

Jack Rae, Sharan Dathathri, Tim Rockt¨ aschel, Emilio Parisotto, Theophane Weber, and Ed- ward Grefenstette. Meta-learning neural bloom filters. arXiv preprint arXiv:1905.10512, 2019. 19

work page Pith review arXiv 1905

Show all 9 references

[9]

Learning to index for nearest neighbor search

Song Tsai, Jeff Johnson, Matthijs Douze, and Herve Jegou. Learning to index for nearest neighbor search. In International Conference on Learning Representations (ICLR), 2020. 20

2020

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Space/time trade-offs in hash coding with allowable errors

Burton H Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422–426, 1970

1970

[2] [2]

Ada-bf: Adaptive bloom filter with learned model

Peng Dai and Anshumali Shrivastava. Ada-bf: Adaptive bloom filter with learned model. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 1551–1566, 2020

work page 2020

[3] [3]

Monkey: Optimal navigable key-value store

Niv Dayan and Stratos Idreos. Monkey: Optimal navigable key-value store. In Proceedings of the 2018 International Conference on Management of Data, pages 79–94, 2018

work page 2018

[4] [4]

Learned cardinalities: Estimating correlated joins with deep learning

Andreas Kipf, Tobias Kipf, Benedikt Radke, Alfons Kemper, and Thomas Neumann. Learned cardinalities: Estimating correlated joins with deep learning. In CIDR, 2019

work page 2019

[5] [5]

The case for learned index structures

Tim Kraska, Alex Beutel, Ed H Chi, Jeff Dean, and Neoklis Polyzotis. The case for learned index structures. Proceedings of the 2018 International Conference on Management of Data, pages 489–504, 2018

work page 2018

[6] [6]

A model for learned bloom filters and optimizing by sandwiching

Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Proceedings of the 36th ACM Symposium on Principles of Distributed Computing, pages 123– 131, 2018

work page 2018

[7] [7]

Algorithms with predictions

Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. arXiv preprint arXiv:2006.09123, 2020

arXiv 2006

[8] [8]

Abelian subgroups, nilpotent subgroups, and the largest character degree of a finite group

Jack Rae, Sharan Dathathri, Tim Rockt¨ aschel, Emilio Parisotto, Theophane Weber, and Ed- ward Grefenstette. Meta-learning neural bloom filters. arXiv preprint arXiv:1905.10512, 2019. 19

work page Pith review arXiv 1905