Learned LSM-trees: Two Approaches Using Learned Bloom Filters

• URL: http://arxiv.org/abs/2508.00882v1
• Date: Thu, 24 Jul 2025 04:23:52 GMT
• Title: Learned LSM-trees: Two Approaches Using Learned Bloom Filters
• Authors: Nicholas Fidalgo, Puyuan Ye,
• Abstract summary: Key-value stores rely heavily on Log-Structured Merge (LSM) trees for write optimization.<n> Auxiliary structures like Bloom filters help, but impose memory costs that scale with tree depth and dataset size.<n>Recent advances in learned data structures suggest that machine learning models can augment or replace these components.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Bloom Filter Encoding for Machine Learning [0.0]
  We present a method that uses the Bloom filter transform to preprocess data for machine learning.<n>Each sample is encoded into a compact, privacy-preserving bit array.<n>We test the method on six datasets: SMS Spam Collection, ECG200, Adult 50K, CDC Diabetes, MNIST, and Fashion MNIST.
  arXiv  Detail & Related papers  (2025-12-23T02:33:57Z)
• TreeLoRA: Efficient Continual Learning via Layer-Wise LoRAs Guided by a Hierarchical Gradient-Similarity Tree [52.44403214958304]
  In this paper, we introduce TreeLoRA, a novel approach that constructs layer-wise adapters by leveraging hierarchical gradient similarity.<n>To reduce the computational burden of task similarity estimation, we employ bandit techniques to develop an algorithm based on lower confidence bounds.<n> experiments on both vision transformers (ViTs) and large language models (LLMs) demonstrate the effectiveness and efficiency of our approach.
  arXiv  Detail & Related papers  (2025-06-12T05:25:35Z)
• Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection [12.555117983678624]
  We propose the Cascaded Learned Bloom Filter (CLBF) to address these issues.<n>Our dynamic programming-based optimization automatically selects configurations that achieve an optimal balance between the model and filter sizes.<n> Experiments on real-world datasets show that CLBF reduces memory usage by up to 24% and decreases reject time by up to 14 times compared to state-of-the-art learned Bloom filters.
  arXiv  Detail & Related papers  (2025-02-06T01:05:41Z)
• ShadowLLM: Predictor-based Contextual Sparsity for Large Language Models [67.97667465509504]
  We develop a novel predictor called ShadowLLM, which can shadow the LLM behavior and enforce better sparsity patterns. ShadowLLM achieves up to a 20% speed-up over the state-of-the-art DejaVu framework.
  arXiv  Detail & Related papers  (2024-06-24T13:41:08Z)
• Bypass Back-propagation: Optimization-based Structural Pruning for Large Language Models via Policy Gradient [57.9629676017527]
  We propose an optimization-based structural pruning that learns the pruning masks in a probabilistic space directly by optimizing the loss of the pruned model.<n>We achieve this by learning an underlying Bernoulli distribution to sample binary pruning masks.<n>Experiments conducted on LLaMA, LLaMA-2, LLaMA-3, Vicuna, and Mistral models demonstrate the promising performance of our method in efficiency and effectiveness.
  arXiv  Detail & Related papers  (2024-06-15T09:31:03Z)
• Characterizing the Accuracy -- Efficiency Trade-off of Low-rank Decomposition in Language Models [1.401463252785724]
  Low-rank decomposition can be a promising direction for LLM-based applications that require real-time service at scale. We formalize the low-rank decomposition design space and show that the decomposition design space is enormous. Our results show that we can achieve a 9% model size reduction with minimal accuracy drops.
  arXiv  Detail & Related papers  (2024-05-10T17:40:02Z)
• Filter Pruning for Efficient CNNs via Knowledge-driven Differential Filter Sampler [103.97487121678276]
  Filter pruning simultaneously accelerates the computation and reduces the memory overhead of CNNs. We propose a novel Knowledge-driven Differential Filter Sampler(KDFS) with Masked Filter Modeling(MFM) framework for filter pruning.
  arXiv  Detail & Related papers  (2023-07-01T02:28:41Z)
• Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining [61.09807522366773]
  We introduce an algorithm that approximates the softmax with provable bounds and that dynamically maintains the tree. In our study on datasets with over twenty million targets, our approach cuts error by half in relation to oracle brute-force negative mining.
  arXiv  Detail & Related papers  (2023-03-27T15:18:32Z)
• Learning Large-scale Neural Fields via Context Pruned Meta-Learning [60.93679437452872]
  We introduce an efficient optimization-based meta-learning technique for large-scale neural field training. We show how gradient re-scaling at meta-test time allows the learning of extremely high-quality neural fields. Our framework is model-agnostic, intuitive, straightforward to implement, and shows significant reconstruction improvements for a wide range of signals.
  arXiv  Detail & Related papers  (2023-02-01T17:32:16Z)
• A Critical Analysis of Classifier Selection in Learned Bloom Filters [0.3359875577705538]
  "Complexity" of the data used to build the filter might heavily impact on its performance. We propose a novel methodology, supported by software, for designing, analyzing and implementing Learned Bloom Filters. Experiments show that the proposed methodology and the supporting software are valid and useful.
  arXiv  Detail & Related papers  (2022-11-28T17:17:18Z)
• Unrolled Compressed Blind-Deconvolution [77.88847247301682]
  sparse multichannel blind deconvolution (S-MBD) arises frequently in many engineering applications such as radar/sonar/ultrasound imaging. We propose a compression method that enables blind recovery from much fewer measurements with respect to the full received signal in time.
  arXiv  Detail & Related papers  (2022-09-28T15:16:58Z)
• Compressing (Multidimensional) Learned Bloom Filters [7.6058140480517356]
  A Bloom filter reveals if an element is not included in the underlying set or is included with a certain error rate. Deep learning models are used to solve this membership testing problem. We show that the benefits of learned Bloom filters are apparent only when considering a vast amount of data.
  arXiv  Detail & Related papers  (2022-08-05T07:54:48Z)
• Symbolic Learning to Optimize: Towards Interpretability and Scalability [113.23813868412954]
  Recent studies on Learning to Optimize (L2O) suggest a promising path to automating and accelerating the optimization procedure for complicated tasks. Existing L2O models parameterize optimization rules by neural networks, and learn those numerical rules via meta-training. In this paper, we establish a holistic symbolic representation and analysis framework for L2O. We propose a lightweight L2O model that can be meta-trained on large-scale problems and outperformed human-designed and tuneds.
  arXiv  Detail & Related papers  (2022-03-13T06:04:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.