acceptodds
Under review as a conference paper at ICLR 2027

MESS: Fast and Private Semantic Search on Multi-Graph HNSW

Abstract

Semantic search systems map data to a high-dimensional vector space and support retrieval of similar data via approximate nearest neighbor search. When the system is hosted by an untrusted cloud provider, there is no privacy for the data or the query. Our goal is to design a system with three properties: privacy, accuracy, and efficiency. Existing works adopt either homomorphic encryption (HE), oblivious RAM (ORAM), or a differential privacy (DP) approach. They fall short of achieving all three properties. In this paper, we present MESS, a system that realizes our goal. It maps the original vectors into binary codes, applies locality-sensitive hashing (LSH) and randomized response, and constructs a multi-graph Hierarchical Navigable Small World (HNSW) index over the perturbed codes. MESS ensures privacy of data, queries, and access patterns. It also ensures search pattern privacy via a two-phase query perturbation mechanism. The multi-graph index mitigates the impact of perturbation on result quality, thereby achieving accuracy. MESS is efficient because search is performed directly over perturbed codes, without the overhead of homomorphic encryption or ORAM. We provide a formal analysis of the system’s privacy and an extensive evaluation of its performance. The results show that MESS achieves up to 15.08× lower latency than state-of-the-art baselines.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Semantic Search, Differential Privacy

Reviews

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

The paper proposes MESS for private semantic search across multiple non-colluding servers. The client uses server-specific IsoHash mappings to convert embeddings into binary codes, perturbs the codes using randomized response, and stores encrypted vectors alongside them. Each server builds an HNSW index over its perturbed codes. For a query, the client sends a perturbed code to every server, receives encrypted candidates, and decrypts and reranks them locally. The paper gives a per-server privacy leakage analysis and reports up to 15× lower latency than Compass on specific workloads.

Critical strengths
  1. The design allows ordinary HNSW search over perturbed codes, so the search is performed over noisy "plaintext", rather than HE ciphertext. Under the reported LAN setting on TripClick, MESS is 15.08× faster than Compass, reducing query latency from 340.70 ms to 22.60 ms.
  2. The experiments cover several retrieval workloads and show how replication helps recover search quality after perturbation.
  3. The repository includes open-source code that can be audited, which is good.
Critical weaknesses
  1. I find the trust assumption way too demanding. The default setting uses 64 mutually non-colluding servers. There is no joint-view guarantee even for two colluding servers. It is unclear what practical deployment supports this assumption. The previous schemes usually assume two or up to three servers, and even in the multi-server regime, most will assume constant-rate collusion like 1/2 or 1/3.

  2. The reported speedup is not an apples-to-apples comparison. The systems differ in (a) trust assumptions: MESS assumes many non-colluding servers, while Compass does not require this assumption; (b) security guarantees: MESS provides per-server differential privacy bounds, while Compass provides cryptographic protection, including access-pattern hiding; and (c) resource use: MESS searches 64 logical shards, emulated on one machine, but it is unclear whether the baselines use the same total resources and parallelism. A simple baseline would partition the database into 64 shards, run Compass on each shard in parallel, and merge the results. Each shard would contain only 1/64 of the database.

  3. Relevant baselines are missing, including BiSON[1] and Speakeasy[2]. The comparisons would clarify whether MESS offers a compelling privacy and performance tradeoff.

[1]: Das S, Ravi R, Chandran N, et al. BiSON: Billion-Scale Oblivious Nearest-Neighbor Search in Milliseconds. IEEE EuroS&P 2026 [2]: Speakeasy: Billion-Scale Two-Server Private Semantic Search: https://openreview.net/forum?id=toYFHz24kU

Questions for authors
  1. What privacy remains if two or more servers pool their observations? How much additional noise would be needed to protect against collusion, and what would this cost in recall and latency?
  2. How much of the speedup remains against Compass running in parallel on 64 database shards, at matched recall and total resource budgets? Does that gain justify the stronger trust assumption and weaker privacy guarantee?
Reviewer_eqXXOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper presents MESS, a privacy-preserving ANN search system for outsourced vector databases. The system applies hashing and random perturbation to vectors and distributes the transformed data across HNSW indexes maintained by multiple non-colluding servers. The query process employs a two-stage perturbation mechanism involving permanent and instantaneous perturbations. The experimental evaluation demonstrates the system's search efficiency on datasets containing up to 100 million vectors. The main contribution lies in combining random perturbation, multi-graph HNSW indexing with record replication, and client-side reranking to improve the trade-off between privacy and search utility.

Critical strengths

S1: Interesting research problem and large-scale system evaluation. The paper addresses privacy-preserving ANN search in outsourced vector databases, which is an interesting and practically relevant research problem. Furthermore, the paper evaluates the proposed approach on large-scale datasets, exploring its scalability in practical settings.

S2: Consideration of privacy risks from repeated queries. MESS employs a query mechanism that combines permanent and instantaneous perturbations. By reusing cached server-specific PRR query representations, the mechanism mitigates the risk of adversaries recovering the original query codes by averaging out independent noise across repeated observations. The paper also provides a formal privacy analysis for certain repeated-query relationships.

Critical weaknesses

W1: The paper contains noticeable repetition and overly general explanations. For example, the same explanation appears on page 8, lines 392–393 and 398–400. Although the paper formally defines its threat model, it lacks concrete examples illustrating what information a server can actually observe and which adversarial inferences are restricted by the privacy guarantees. Furthermore, the description of MESS lacks an intuitive running example that walks through the index construction and query processing workflow. These issues significantly affect the clarity and readability of the paper.

W2: Appendix A provides an XDP analysis for a fixed semi-honest server under the non-collusion assumption. However, the paper does not sufficiently quantify the actual privacy guarantees achieved under its main experimental configurations. In particular, the privacy guarantees for repeated queries depend on the permanent perturbation probability, the instantaneous perturbation probability, and the number of repeated queries. However, the experiments primarily report the effective query flip rate p_q without disclosing the complete PRR/IRR parameter settings. Different PRR/IRR configurations may yield the same p_q while providing different long-term query privacy guarantees. Consequently, the reported recall and latency curves are not tied to fully specified privacy bounds for repeated-query transcripts. Moreover, Appendix E explicitly states that its cross-shard record-linkage diagnostic scores do not represent formal privacy loss or XDP parameters, and thus cannot address this limitation.

W3: Privacy-preserving mechanisms combining LSH with randomized response, as well as the corresponding XDP analysis under fixed hash mappings, have already been explored in prior work (Fernandes et al., 2021, Section 6.1, Proposition 2). The idea of combining permanent and instantaneous perturbations was also introduced in RAPPOR (Erlingsson et al., 2014). Therefore, the main novelty of MESS appears to lie primarily in the system-level integration of independently perturbed views, multi-graph retrieval, and client-side exact reranking. However, the paper does not clearly distinguish its new contributions from existing techniques. The existing ablations do not isolate the benefits of this combination against simpler alternatives under matched resource and privacy conditions.

W4: The evaluation is insufficient to support the claimed advantages of the proposed design. First, Figure 2 increases the number of replicas per record t, which simultaneously increases the total storage overhead and changes the routing-dependent storage privacy bounds. Therefore, this experiment mainly illustrates trade-offs across different parameter settings rather than establishing the advantages of MESS under comparable privacy guarantees and resource budgets. Second, the No-Noise baseline retains the same multi-graph architecture and thus cannot independently validate the contribution of the multi-graph design itself. Although Figure 2 includes a non-replicated setting with t = 1, and Section 4 reports some single-graph recall results, these comparisons do not isolate the benefits of replication and independently constructed graph views under matched resource and privacy conditions. Compass uses ORAM to hide logical graph-access patterns, whereas MESS exposes local search traces and bounds their leakage through server-local XDP. Their performance differences therefore do not establish algorithmic superiority under equivalent privacy guarantees.

Questions for authors

W1-W4

Reviewer_2y6QOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the problem of private approximate nearest neighbor search (ANNS) and proposes a new solution called MESS using off-the-shelf techniques. Experiments are conducted on multiple datasets against state-of-the-art solutions like Compass. Although the experimental results demonstrate a clear advantage over Compass, the privacy guarantees of these solutions are different. By contrast, MESS sacrifices security to obtain an efficiency gain over Compass, but this security cost is what Compass targets to resolve. Beyond this critical issue, the paper has many other substantial issues, such as limited technical novelty, unconvincing motivation, and incomplete evaluation. Based on these reasons, I am inclined to reject this work.

Critical strengths

S1. The paper studies a meaningful problem.
S2. The paper provides a detailed analysis of the security guarantee.
S3. Experiments are conducted on multiple large-scale vector datasets.

Critical weaknesses

W1. The motivation is unconvincing, since the discussion of prior work is not fair enough.
W2. The technical novelty is incremental, since the major techniques have already been used in prior related work.
W3. The proposed solution lacks a detailed complexity analysis of the communication cost and computational efficiency.
W4. The experimental setup requires further justification and exploration.
W5. Many recent baselines are not considered in the experiments.

Questions for authors

Q1. The privacy guarantee is far weaker than the introduction implies. MESS’s formal guarantee is per-server, non-colluding, Hamming-distance-dependent XDP, with an explicit disclaimer of any joint-view privacy. This is fundamentally different from the security guarantees in prior work. Take Panther [Li et al. 2025] and Compass [Zhu et al. 2025] as examples: both target the single-server setting, arguing that (1) problem complexity can be greatly reduced given the additional assumption of non-colluding participants, and (2) non-colluding servers are difficult to deploy in practice. Unfortunately, the introduction does not fairly explain this difference in privacy guarantees.

Q2. The arguments about other prior studies are not fair enough either. For DP-based methods, the key argument is that “existing works do not consider any index” , but [Chen et al. 2018] is designed for index-based SSE (see their Section II). What is worse, most of the mentioned baselines are not evaluated in the experiments, so no concrete results are given to demonstrate the claimed limitations.

Q3. Complexity analysis is important for ANNS and private ANNS, but such analysis is missing from the methodology section.

Q4. The overall technical novelty is limited. The key components of MESS are largely borrowed from prior work, including LSH + randomized response + XDP, the multiple non-colluding server setting, and HNSW sharding for large-scale vector datasets.

Q5. The PRR/IRR defense does not cover adaptive similar-query attacks. If an adversary submits slightly different queries, each obtains its own independent PRR sample. How does MESS handle this issue?

Q6. The XDP bound ties leakage to Hamming distance, but Hamming distance has a significant gap with semantic meaning. The rationale for using Hamming distance should therefore be justified in more detail.

Q7. The main result (Figure 1) does not show the trade-off between recall and latency, which is commonly used in ANNS benchmarks. The experiment should be re-conducted by varying the efSearch parameter of HNSW and plotting curves for the compared methods. The setting of efSearch should be explicitly reported.

Q8. The privacy budget is never reported as a comparable scalar. It appears difficult to translate the mechanism parameters of XDP into a form comparable to standard (ϵ,δ)(\epsilon, \delta)-DP. This further raises the question: why adopt XDP instead of metric-DP or Geo-indistinguishability (Geo-I)?

Q9. Experiments should be also conducted on larger k (eg k = 100) with varying efSearch.

Q10. Although the comparison against Compass shows a clear advantage, MESS also sacrifices the privacy guarantee and incurs higher index-construction cost. It is important to quantify this trade-off and justify that it is practical or deployable in real-world applications.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.