Learned LSM-trees: Two Approaches Using Learned Bloom Filters
Nico Fidalgo, Puyuan Ye · 2025
Read Learned LSM-trees: Two Approaches Using Learned Bloom Filters by Nico Fidalgo, Puyuan Ye (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-00882.txt.
Introduction
Fidalgo and Ye teach storage trees to skip needless checks in a 2025 paper. Key value stores write into log structured trees for speed, but reads pay by probing many levels, and the Bloom filters that shortcut probes swell with data.
Two learned designs attack the cost. A classifier skips filter probes at levels unlikely to hold a key, cutting read delay more than twofold. A learned filter swaps the classic one for a compact model plus a small backup, trimming memory by up to four fifths with no missed keys. Tests run on a leveled tree under real style workloads.
Catalog record
| CREATOR | Nico Fidalgo, Puyuan Ye |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-00882
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learned LSM-trees: Two Approaches Using Learned Bloom Filters Thanks: Code available at: https://github.com/fiidalgo/predictive-lsm-trees Nico Fidalgo, Puyuan Ye 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.28× 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. 1 Introduction Log-structured merge trees (LSM-trees) have become the de facto standard for high-throughput write-heavy workloads in modern key-value stores such as RocksDB, Cassandra, and LevelDB. Their core strength lies in write amplification reduction: rather than writing directly to disk on each update, writes are first buffered in memory (in the MemTable), and later flushed as immutable, sorted disk segments known as SSTables. These SSTables are organized hierarchically across levels, each exponentially larger than the last, using a compaction strategy that periodically merges overlapping tables to maintain sorted order and free space. This batching and merging architecture drastically improves write throughput, making LSM-trees ideal for large-scale logging, time-series data, and streaming ingestion applications. Yet this write-optimized design creates a well-known tradeoff: increased read latency. Point queries (GET operations) must examine the MemTable and potentially every level of the disk hierarchy, querying filters and scanning SSTables. The deeper the level hierarchy, the greater the number of SSTables, and thus the more auxiliary data structures are required to ensure acceptable read performance. Bloom filters and fence pointers are the most common of these. Bloom filters prevent unnecessary I/O by probabilistically excluding levels, and fence pointers accelerate binary search within an SSTable. However, these structures impose substantial memory overhead and have limited adaptivity, especially as datasets grow and key distributions evolve. In response to these challenges, a new class of techniques has emerged: learned data structures. Rooted in the idea of algorithms with predictions, these approaches use machine learning models to approximate, augment, or replace traditional data structures. For example, a classifier can predict whether a key exists in a level, or whether a key is likely to be in the dataset at all. Such predictions can reduce memory consumption, avoid redundant filter checks, and skip entire levels, thereby reducing query latency. In this project, we explore two approaches for integrating learned predictions into LSM-tree read paths. First, we propose a classifier-based method that predicts whether a given key is likely to reside in each level. Instead of querying every Bloom filter sequentially, we use the classifier to selectively consult only the most promising levels. This avoids wasted memory accesses and reduces average lookup latency in multi-level trees. Second, we implement a learned Bloom filter, replacing large traditional Bloom filters with compact hybrid structures consisting of a lightweight classifier and a small backup Bloom filter. This approach offers substantial memory savings while still preserving correctness guarantees. To rigorously test these ideas, we constructed an LSM-tree implementation based on the design choices of the Monkey paper [ 3 ] , including leveled compaction, a 10x level size ratio, and realistic SSTable thresholds. We simulate workloads using 287.6 MB of randomly generated data with 16-byte keys and 100-byte values to emulate RocksDB conditions and avoid overfitting to artificial patterns. Our experiments span a diverse set of read-intensive scenarios (random access, sequential scans, and level-specific lookups) to examine how learned models behave under varying access distributions. These contributions demonstrate the practical viability of integrating ML-based predictions into critical paths of database storage engines. Our findings offer a compelling case for memory-efficient, prediction-aware auxiliary structures that optimize LSM-tree query performance without compromising correctness. This work adds to a growing body of literature at the intersection of data systems, algorithms, and machine learning, where classical structures are being reimagined as adaptive, data-driven components. 2 Related Work The idea of enhancing traditional data structures with machine learning was catalyzed by the seminal work of Kraska et al. [ 5 ] in “The Case for Learned Index Structures.” This work argued that core components of databases (e.g., B-trees, hash maps, and Bloom filters) can be replaced or augmented with models trained to exploit regularities in real-world data distributions. The key insight was that fixed data structures are agnostic to input distributions, while learned models can adaptively leverage them to reduce space and time complexity. This marked the beginning of a broader research trend toward learned data structures, with a growing focus on replacing deterministic components with adaptive, data-driven approximations. This idea was extended to Bloom filters by Mitzenmacher [ 6 ] , who introduced the sandwich learned Bloom filter. In this design, a machine learning classifier first predicts whether a key belongs to a set. If the classifier accepts the key, a backup traditional Bloom filter is queried to verify membership, ensuring that false negatives (which traditional Bloom filters avoid by design) are not introduced. This hybrid structure preserved correctness while significantly reducing memory usage. Our work builds on this framework by applying it to a realistic, multi-level LSM-tree, incorporating classifiers at the level granularity, and empirically evaluating performance across diverse workloads. The concept of learned Bloom filters was further developed in follow-up studies such as Ada-BF [ 2 ] , which introduced adaptivity into the classifier itself, allowing the filter to change over time as data distributions evolved. Meanwhile, Rae et al. [ 8 ] proposed neural Bloom filters using deep learning architectures to model complex patterns in key distributions. While these techniques achieved strong empirical results, most prior work tested them on static datasets or in isolation from real systems. Our project addresses this gap by deeply integrating learned filters into a full LSM-tree pipeline and evaluating their behavior in dynamic, hierarchical environments. Parallel to these empirical advancements, theoretical work emerged under the banner of “Algorithms with Predictions.” Mitzenmacher and Vassilvitskii formalized how algorithms can safely incorporate ML predictions while maintaining worst-case performance bounds [ 7 ] . The core idea is to use predictions to improve average-case efficiency, while ensuring robustness through fallback mechanisms that guard against poor predictions. This principle guided our classifier-based design: we allow the model to skip levels when confident, but always revert to Bloom filter fallback when uncertain or incorrect. This interplay between data adaptivity and algorithmic resilience is central to making machine learning