Navigating the Privacy-Accuracy Trade-Off for Learned Bloom Filter

With the rapid development of membership query applications, there is an increasing demand for accurate membership queries under rigorous differential privacy guarantees and limited storage. In this work, we propose a Differentially Private Learned Bloom Filter (DP-LBF), which protects the sensitive set while maintaining high prediction utility and a compact released representation. DP-LBF combines a fixed public learned model with three private stages for routing-threshold selection, backup-size estimation, and backup-filter release. High-confidence queries are answered directly by the learned model, while low-confidence elements are handled by an adaptive private backup Bloom filter. Theoretical analysis establishes the $ϵ$-differential privacy guarantee and characterizes the utility and space complexity of DP-LBF. Experiments on synthetic and real-world datasets show that DP-LBF achieves substantially lower RMSE and smaller released private representations than the evaluated private membership-query methods.