acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Learned Bloom filter, Differential Privacy

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_W6CFOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a differentially private learned Bloom filter. Technically, the authors employ exponential mechanism for threshold sampling, Laplace noise for backup‑size release, and randomized response to perturb backup filter. They prove sequential composition differential privacy guarantees and derive approximate utility and space bounds. The proposed data structure is evaluated against existing private BF baselines over synthetic, URL phishing and Spambase datasets.

Critical strengths
  • The paper provides full differential privacy proofs for each component and their sequential composition, together with approximate utility and space complexity derivations. The theoretical exposition is self‑contained.
Critical weaknesses
  • While the paper proves \epsilon‑DP guarantee, it never formalizes the adversarial attacker model. Without specifying what adversaries can observe and what they aim to infer, the security implications of DP‑LBF cannot be fully assessed. Differential‑privacy is a mathematical primitive, not a complete security guarantee on its own. Omitting attacker model and analysis makes this an incomplete security research.
  • While a pre‑trained ML model is used in LBF, the core research problem is differentially private probabilistic data structure. Therefore, the paper’s central scientific questions belong to security & privacy or data structures rather than AI.
  • The novelty of the paper is rather limited, in the sense that the technical part essentially applies well-known techniques in DP.
Questions for authors

What concrete attacker model are you assuming for DP‑LBF? Please explicitly define adversary’s background knowledge, observable outputs, inference objectives, and any excluded attack vectors.

2 comments
AuthorsOpenReview ↗

Response to Reviewer W6CF

Thank you for requesting an explicit threat model and a clearer account of the technical contribution.

1. Attacker model and scope of the guarantee

Section 4.1 assumes a trusted curator holding S\mathcal S. The learned model, calibration data, candidate thresholds, and hash-generation rules are public and fixed before accessing S\mathcal S. A computationally unbounded adversary may observe the complete released state R=(τ∗,t~,b~)R=(\tau^*,\tilde t,\tilde{\boldsymbol b}), query it adaptively, and possess arbitrary auxiliary information.

The adversary may attempt membership inference or infer other set properties. For every pair of sets differing by one added or removed member and every output event, the complete released state satisfies the probability-ratio bound of ϵ\epsilon-differential privacy. Queries based only on the same released state and fixed public inputs are post-processing and incur no additional privacy cost. A new release accessing the sensitive set requires separate accounting.

This protects individual participation; it does not prevent inference of population-level regularities. Timing or memory side channels, leakage originating in public data or the public model, and a malicious curator are outside this model.

2. Novelty of the complete release framework and data-structure construction

Our novelty lies in the DP-LBF framework and data-structure construction for protecting the complete released state, together with their joint privacy and utility analysis. Even with a fixed public predictor, the sensitive set determines the routing threshold, backup members, capacity, and bit array. These quantities are interdependent, and the threshold, noisy capacity, and randomized bits jointly form the released state R=(τ∗,t~,b~)R=(\tau^*,\tilde t,\tilde{\boldsymbol b}). Randomizing only the final bit array does not protect the preceding set-dependent routing and capacity decisions. The technical problem is therefore how to construct and release the complete structure while accounting for these dependencies.

We realize this framework through concrete structural designs. Private threshold selection uses a sensitivity-one utility with a false-positive penalty computed on fixed public calibration data. The selected threshold determines which actual members enter the backup. Noisy capacity and public parameters determine the filter geometry, and the bits encoding those backup members are then randomized. Construction does not abort when the true backup count exceeds the noisy capacity, avoiding additional leakage through a data-dependent failure event. A zero noisy capacity produces a fixed empty representation. These decisions coordinate the release of routing, capacity, and bits.

For this construction, we establish conditional privacy guarantees for each stage and prove the complete-state guarantee in Theorem 5 through adaptive composition. The utility analysis explains the costs and benefits of the design: Corollary 1 characterizes when enabling the backup reduces conditional expected error count relative to rejecting all low-score queries at the same released threshold and noisy capacity, under the stated Bloom-filter approximations. The resulting contribution includes a concrete data-structure construction, a joint privacy guarantee, and conditions under which the backup improves utility.

This construction also differs from Tirmazi's input-set perturbation approach (Section 4.4), where training and filter construction operate on a randomized set. We fix a publicly trained model and privatize the subsequent set-dependent routing and adaptive backup construction. The exponential mechanism, Laplace mechanism, and randomized response are the underlying tools. Our framework and construction contribution is the design that coordinates these tools with the interdependent LBF components and establishes a unified guarantee for the complete released state.

3. Relevance to AI

The learned score determines which queries are answered directly and which enter the backup. Private threshold selection therefore changes the use of the predictor, backup size, and error composition. The learning component directly shapes the structure and its privacy–utility trade-off. Our focus is how to use a pretrained predictor safely within a data structure built from sensitive records, connecting learning-augmented data structures with differential privacy.

I appreciate the response of the authors, but I still hold my opinion that the novelty of the paper is relatively weak after reading the response.

Reviewer_hzQwOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes DP-LBF, a private membership-query representation built around a fixed public classifier. It privately selects a routing threshold using an exponential mechanism, releases a noisy count of low-score members, and constructs a backup Bloom filter with geometry determined by that count and bits perturbed by randomized response. The released threshold, count, and bit array satisfy an additive epsilon-DP guarantee under add/remove adjacency; subsequent queries are post-processing. The paper also derives an approximate utility expression and evaluates RMSE, serialized private-state size, and amortized query time on Synthetic, URL, and Spambase over five privacy budgets and 100 randomized releases per setting.

Critical strengths
  1. The released-state privacy boundary is explicit and technically useful. Sections 4–5 and Appendix B distinguish fixed public inputs from the sensitive set, privatize the backup count before choosing the filter geometry, and handle the zero-count case without a data-dependent abort. This addresses a real source of leakage in adaptive private data structures and makes the composition argument substantially easier to assess.

  2. The evaluation includes several relevant private set-representation mechanisms and reports accuracy, size, and query cost together. The complete parameter grids in Appendix C.7 expose dataset-dependent trade-offs rather than presenting only a favorable tuned setting. These are useful ingredients for evaluating a practical private membership structure.

Critical weaknesses
  1. The evaluation does not separate the value of the public classifier from the value of the proposed private backup and threshold selection. Appendix C.1 uses binary classification datasets and draws the query workload from the private partition. The very low URL RMSE and the nearly budget-independent Synthetic/Spambase curves can therefore reflect how predictable the membership labels already are from public training data. Figures 5–7 vary mechanism parameters but do not include a public-classifier-only reference or a comparable public-model-plus-private-backup baseline. Without these controls, the large improvement over methods that cannot exploit the same public predictor is insufficient evidence for the incremental contribution of DP-LBF. Class-specific false-positive/false-negative rates would also clarify whether the randomized backup meaningfully recovers low-score members.

  2. The reported size advantage uses a narrower accounting boundary than a serving-space comparison. Appendix C.2/C.6 excludes the fixed DP-LBF model but includes the privately trained Warner-LBF model. This distinction is disclosed and is legitimate for measuring released private state, but it does not establish that a standalone DP-LBF system is smaller. Theorem 7 itself includes the model in total serving space. A utility–total-serving-size comparison, with equal access to public predictive information, is needed to support the practical space-efficiency interpretation. These two evaluation issues determine my weak-reject recommendation; I do not identify a counterexample to the stated privacy composition under its fixed-public-input assumptions.

Questions for authors
  1. Can you report the public classifier's FPR/FNR and RMSE on the exact query workload, and compare DP-LBF with a public-only decision rule and a fixed public threshold combined with a comparable private backup at the same total privacy budget? In particular, how much of the URL improvement remains after matching public information?

  2. How exactly is the sensitive member set selected from the private partition? Does it contain all positively labeled records, and how does the method behave when set inclusion varies independently of the class label or when the public/private distributions differ? This clarification affects whether the experiments evaluate private set membership beyond label generalization.

  3. What are the serialized public-model size and total serving size for DP-LBF, and does its accuracy–space advantage persist when the public model is included or shared consistently across learned baselines? These are clarification/control requests that could change my assessment.

2 comments
AuthorsOpenReview ↗

Response to Reviewer hzQw

Thank you for the concrete control and accounting requests. We address them with matched accuracy measurements, an alternative set-selection experiment, and total serving-size accounting.

1. Public-only and matched-budget controls on the exact workload

Section 6.2, Tables 1 and 3, uses the same public model and query workload for all three rules below. The public threshold is selected using public calibration data only. The fixed-threshold DP backup uses the same total budget as DP-LBF and reallocates its unused threshold budget to the bits. At ϵ=2.5\epsilon=2.5, public-only is a fixed rule, and each private row averages 60 releases:

DatasetRuleRMSEFPRFNR
SyntheticPublic-only0.15650.02000.0290
SyntheticFixed-threshold DP0.16750.02770.0285
SyntheticDP-LBF0.16410.02830.0257
URL (string-only)Public-only0.14760.01150.0321
URL (string-only)Fixed-threshold DP0.15950.01950.0314
URL (string-only)DP-LBF0.16170.01880.0335
SpambasePublic-only0.26780.06300.0804
SpambaseFixed-threshold DP0.27310.07080.0784
SpambaseDP-LBF0.27300.05440.0950

After matching public information, DP-LBF has no net URL RMSE improvement over public-only at this budget. Public-only does not access S\mathcal S and is itself 00-DP with respect to that set. The comparison measures the incremental utility of accessing the set through the private construction.

For URL, an exact non-private backup achieves RMSE 0.07570.0757 at τpub\tau_{\mathrm{pub}} and an average of 0.07330.0733 at DP-LBF's per-release τ∗\tau^*. These diagnostics quantify correctable errors at the respective thresholds. Corollary 1 analyzes enabling a private backup versus rejecting all low-score queries at the same released threshold and capacity, under the stated approximations; it does not directly compare RMSE across different threshold rules.

The original URL figure uses the full feature set, where the public model already perfectly separates the evaluated queries. The string-only diagnostic in Appendix C.2 examines residual model errors under a different feature protocol. We report the protocols separately and do not compare the string-only results directly with the original full-feature private baselines.

2. Set selection, label-independent inclusion, and distribution shift

The main sensitive set contains all positively labeled records in the private partition, and queries are drawn from that partition. Appendix C.3 additionally selects a random 20%20\% subset of the Synthetic private partition, independently of class labels. Public-only at threshold 0.50.5 has RMSE 0.7110.711; DP-LBF averages 0.7080.708 and 0.6790.679 at ϵ=2.5\epsilon=2.5 and 1010, respectively, over 20 releases of the same test set. These are measurements of the complete construction, not an isolated component effect.

We have not separately evaluated public/private distribution shift. Utility depends on score quality on the target workload. With public inputs fixed, the privacy proof does not require matching data distributions or accurate predictions.

3. Public-model size and total serving size

Section 6.2, Table 2, separates private released state from total serving size. Using the paper's model-text serialization convention:

DatasetPublic model (KB)Total serving size (KB)
Synthetic135.9136.0
URL (string-only)23.926.7
Spambase543.5543.6–543.7

When the public model is shared infrastructure, private released state measures the additional representation for each set. Standalone deployment must include the model. On Synthetic/Spambase, DP-LBF's total size exceeds BLIP (2.964/1.087 KB) and DPSet (0.672–2.641/0.318–1.224 KB), and is comparable to Warner-LBF (approximately 144–145/571–584 KB). Thus, the compactness result concerns private released state; it is not a universal total-space advantage. We have not evaluated all learned baselines under a common shared public model, so we do not claim an accuracy–total-space advantage under that deployment protocol.

Reviewer_hzQwOpenReview ↗

Response to authors

Thank you for the detailed response and the new controls.

The public-only comparison answers my first question: at ε = 2.5, public-only has lower RMSE than DP-LBF on all three datasets, and the random-set experiment shows almost no gain (0.708 vs. 0.711). The total serving-size table also shows that the size advantage holds only for the released private state, not for a standalone system.

I appreciate that the authors report these results openly and narrow their claims, and the privacy construction is still a useful contribution. However, the results confirm that the experiments do not show a practical utility or size advantage at the budgets studied. I will keep my score of 2.

Reviewer_HnFSOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes a differentially private learned Bloom filter (DP-LBF) for approximate membership queries over a sensitive set SS, assuming access to a public classifier (trained only on public data and fixed before accessing SS). The data structure directly answers YES if the classifier score exceeds a threshold, and otherwise queries a private backup Bloom filter.

Methodologically, the authors uses three private mechanisms: (i) sample the routing threshold using the exponential mechanism, (ii) release a Laplace-noised count of members routed to the backup filter; and (iii) construct the backup Bloom filter and apply bitwise randomized response before releasing it. They prove that the resulting data structure satisfies ϵ\epsilon-differential privacy by composition, and provide an approximate analysis of its query accuracy, space complexity, and query time.

Empirically, the paper compares DP-LBF against four existing private membership-query methods on synthetic and real-world classification datasets. The proposed method achieves lower RMSE than the baselines across the tested privacy budgets, while maintaining a compact released private representation.

Critical strengths

The privacy analysis appears technically sound to me. Although the individual mechanisms are standard, having a formal privacy guarantee is indeed a positive aspect of the paper.

Critical weaknesses

My biggest concern is the motivation and relevance of the setting studied by this paper: for a sensitive set SS, the goal is to release a data structure that supports approximate queries 1(x∈S)\mathbf{1} (x \in S). The paper assumes access to a public classifier, say a classifier trained on public data to detect whether a URL is malicious. Then there's a backup Bloom filter built from a private database. This paper proposes that when the public classifier answers YES, the data structure immediately answers YES; otherwise, we consult the backup Bloom filter.

I find it difficult to see when this combination would be useful: The proposed method combines a public classifier with a private backup Bloom filter, but the two components seem to address different membership questions: whether an element belongs to a class (e.g., whether a URL is malicious), and whether it belongs to the sensitive set SS. It is unclear why a classifier trained independently of SS would be useful for testing membership in SS.

In the experiments, the authors construct SS from the positive examples in the private partition of a binary classification dataset. The queries are sampled only from the private partition. In this setup, predicting the membership to SS is equivalent to predicting the binary class label. This setup obscure the mismatch between the two distinct membership problems discussed above. Therefore, I am not convinced that the experiments demonstrate the usefulness of the proposed construction for general membership queries.

(Even putting aside the concerns about the setup, I also find the comparison somewhat unfair: the proposed method benefits from a public classifier, while the comparison baselines do not use the same information. This makes it difficult to attribute the observed advantage to the proposed data structure or to the strong public classifier.)

Questions for authors

See the weakness section.

3 comments
AuthorsOpenReview ↗

Response to Reviewer HnFS

Thank you for asking us to clarify the membership task and isolate the private construction's contribution.

1. Why can a public classifier help with private set membership?

LBFs exploit predictable membership features: their false-positive rates depend on the query distribution, and their space benefit depends on the combined model and backup size, as analyzed by Mitzenmacher (NeurIPS 2018). We protect set-dependent routing and backup releases within this framework. Conventional LBFs can learn from the target set; our predictor is publicly trained and fixed before accessing it. Training without access to the sensitive set does not imply that the learned features are statistically unrelated to membership.

Let UU be the private-partition query domain and S={x∈U:y(x)=1}\mathcal S=\{x\in U:y(x)=1\}. Within UU, membership equals the positive label, so a model trained on separate public examples of this task can supply a membership score. For example, the sensitive subset contains the maliciously labeled records in a collected URL domain. This correspondence depends on the domain and inclusion rule; a maliciousness classifier does not automatically predict inclusion in an arbitrary organization's blacklist.

The backup uses actual set information to correct low-score members missed by the model. High-score nonmembers still count as false positives; both branches approximate the same set-membership query. On Spambase, holding the public model, public threshold, and workload fixed, an exact non-private backup reduces RMSE from 0.26780.2678 to 0.17750.1775. A conventional LBF backup eliminates model false negatives, whereas a randomized private backup can introduce errors of its own. Our construction and utility analysis address this additional trade-off while protecting the threshold, capacity, and bits jointly.

Appendix C.3 also tests a random 20%20\% subset of the Synthetic private partition, selected independently of the class label. Public-only prediction at threshold 0.50.5 has RMSE 0.7110.711; DP-LBF averages 0.7080.708 and 0.6790.679 at ϵ=2.5\epsilon=2.5 and 1010, respectively, over 20 releases of the same test set. Here the class predictor has no systematic membership signal. Predictive alignment affects utility; the privacy guarantee, with public inputs fixed, does not require an accurate predictor.

2. Does the advantage come from unequal access to public information?

Section 6.2 adds controls sharing the same public model and query workload. The fixed-threshold DP backup uses the public-calibrated threshold τpub\tau_{\mathrm{pub}}, retains the same total privacy budget, and reallocates the unused threshold budget to the bits. At ϵ=2.5\epsilon=2.5:

DatasetPublic-onlyFixed-threshold DPDP-LBFExact backup
Synthetic0.15650.16750.16410.1000
URL (string-only)0.14760.15950.16170.0757
Spambase0.26780.27310.27300.1775

Entries are RMSE; private entries average 60 releases. Public-only and exact backup are fixed references using τpub\tau_{\mathrm{pub}}. The exact backup is non-private and not size-matched. The URL row uses a separate feature protocol from the original full-feature baseline figure.

These controls show that public prediction accounts for the strong accuracy at this budget: DP-LBF does not improve RMSE over public-only. Exact backups quantify additional correctable errors; their gap to private backups includes filter approximation, noisy capacity, and randomized bits, not solely privacy noise.

Corollary 1 gives an approximate condition for reducing conditional expected error count by enabling the backup at the same released threshold and capacity. Comparisons against a separately calibrated public threshold are empirical. In a further Spambase diagnostic, DP-LBF at ϵ=10\epsilon=10, with public geometry parameter k=2k=2, averages RMSE 0.19460.1946 over 20 releases, versus 0.26780.2678 for public-only on the same workload. Both budget and geometry change, so this demonstrates one beneficial configuration rather than isolating either change or the threshold mechanism.

These controls isolate the role of public information in assessing our contribution. DP-LBF provides a joint private construction for the set-dependent routing threshold, backup capacity, and bit array, together with an analysis of when using the backup is beneficial. Even after the model is fixed, routing and adaptive capacity can reveal information about the set; Theorem 5 protects these interdependent releases jointly. We ask the reviewer to assess this contribution using the matched controls, utility conditions, and complete-state privacy analysis.

Thank you for your responses. I appreciate the clarification that a classifier trained without access to SS can nevertheless provide useful membership information when class labels correlate with membership of S. However, I don't think this argument is sufficient for demonstrating the usefulness of the proposed construction.

In the original experiment, SS consists of the positive examples in the private partition, and queries are restricted to that partition. Thus, set membership coincides with the binary class label on all queries. The new results show that, at ϵ=2.5\epsilon=2.5, DP-LBF does not improve RMSE over the public classifier alone on any of the three reported datasets.

I also appreciate the experiment in which set inclusion is independent of the class label. However, comparison with a public classifier that has no systematic membership signal does not establish an advantage over an appropriate private membership-query baseline without that classifier.

These clarifications do not sufficiently resolve my concern. I therefore retain my original score.

AuthorsOpenReview ↗

Response to Reviewer HnFS

Thank you for the follow-up. We address your concerns about the construction's value beyond public prediction.

1. Motivation and the value of protecting an LBF.

Our question is how to construct and privately release an LBF when a fixed public predictor provides relevant membership information. Even with that predictor fixed, the sensitive set determines the routing threshold, backup members, capacity, and bits. These decisions are not protected merely because the model is public; randomizing the final bits alone does not protect the preceding routing and capacity choices.

Kraska et al. (SIGMOD 2018, Section 5.1.1) formulate membership prediction as binary classification and build a backup from actual members missed by the predictor. Our public-model setting additionally requires a connection between public prediction and target membership. We specify this connection: within the experimental query domain, records satisfying the target label rule form the sensitive set, and separate public examples provide predictive information about that rule. This defines the task; it does not establish usefulness by itself.

Our construction coordinates private threshold selection, noisy capacity, and bit randomization. It continues when the true backup count exceeds the noisy count, avoiding a data-dependent abort. Theorem 5 establishes a joint privacy guarantee for the released threshold, noisy capacity, and randomized bits. This complete-release guarantee is not supplied by the public classifier.

2. Incremental utility relative to public-only.

Your interpretation of the matched results at epsilon = 2.5 is correct: the reported configuration does not improve RMSE over public-only. We therefore do not attribute the original advantage over other private methods entirely to the private backup. The public-only control separates the contribution of public predictions from that of accessing the sensitive set.

In the original non-private LBF, the backup recovers members missed by the predictor, eliminating false negatives while potentially adding false positives (Kraska et al., SIGMOD 2018, Section 5.1.1). After privatization, that no-false-negative guarantee no longer applies, and the incremental benefit requires analysis.

Corollary 1 addresses this question: at the same released threshold and noisy capacity, under the stated approximations, it characterizes when recovering low-score members outweighs additional false positives and reduces conditional expected error count relative to rejecting all low-score queries.

Appendix C.3 provides a beneficial configuration: on Spambase, using the same public model and workload, DP-LBF at epsilon = 10 and k = 2 achieves mean RMSE 0.1946, versus 0.2678 for public-only. This demonstrates incremental utility in that configuration. It is not evidence of an advantage at epsilon = 2.5; because both budget and geometry change, it does not isolate either factor. Our claim concerns conditions under which the private backup helps, rather than an improvement at every budget.

3. The random-set experiment and classifier-free private baselines.

We agree that comparison with an uninformative public classifier cannot establish superiority over a classifier-free private membership baseline. The random-set experiment examines behavior when the connection between the public prediction task and target membership is removed.

This interpretation follows established LBF analysis. Mitzenmacher (NeurIPS 2018, Section 3.2) explicitly ties LBF false-positive rates to the query distribution. Section 4 derives conditions for improvement over an ordinary Bloom filter at equal total space, accounting for model size and prediction errors. An unconditional advantage on arbitrary sets and workloads is therefore not a property guaranteed by LBFs.

Our random-set experiment retains the original class predictor but selects members independently of class labels, removing its systematic membership signal. The additional same-budget BLIP comparison also shows that directly encoding the set is more accurate in this setting. We use this result to clarify the applicability of our fixed-predictor approach, not to claim a general-membership advantage.

Our contribution is the complete private-release framework and concrete LBF construction, together with joint privacy and conditional utility analysis. With public inputs fixed, privacy does not require predictive accuracy; utility depends on the predictor, workload, budget, and structural parameters. The LBF literature specifies the information conditions, while our construction, analysis, and measurements establish our own claims.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.