Amora: Communication-Efficient Private Approximate Nearest Neighbors Search

arXiv:2610.21174 · cs.DB, cs.CR · Submitted 2026-10-15 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia.

Elias: And I'm Elias, here with Priya.

Nadia: Today's paper: "Amora: Communication-Efficient Private Approximate Nearest Neighbors Search".

Elias: The gist The Amora system presents a communication-efficient Private Approximate Nearest Neighbors Search (PANNS) that significantly reduces online communication by 93–99% compared to state-of-the-art methods while achieving higher search accuracy…

Nadia: First, who's behind it and why it matters.

Title and authors: Nadia: So we're talking about "Amora: Communication-Efficient Private Approximate Nearest Neighbors Search," and the title tells us they are focusing on making the search efficient while keeping everything private.

Elias: That privacy part is key because typically sending your query vector out to a database exposes sensitive information about what you’re actually looking for, so they're trying to solve that problem.

Nadia: It sounds like the core challenge they are addressing is that existing methods require too much communication just to find those closest items.

Elias: Right, and the authors are Qiuhao Wang, Zuowei Chen, Xu Yang, Saiyu Qi and Yong Qi from Xi’an Jiaotong University who put forward this new system.

Nadia: They seem to be proposing a fundamental shift in how we handle that communication overhead during the search process itself.

Elias: That's right. Amora is designed specifically to be much more efficient in terms of the data sent back and forth over the network compared to what we see now.

Nadia: So, if Pacmann is a high-accuracy method, what exactly does this paper claim they are achieving that existing methods like Pacmann aren't doing well?

Elias: Pacmann uses graph-based search with private information retrieval to get high accuracy, but it has this issue where each PIR query only retrieves a single vertex’s vector and neighbor list.

The paper's summary: Nadia: The paper says that this per-vertex cost model in Pacmann is the main source of inefficiency because it means a lot of communication for just one vertex.

Elias: They point out that SimplePIR offers an inherent information density advantage because it organizes the database as a matrix in which one query retrieves an entire column.

Nadia: So, if you query that matrix, Amora is designed so that one PIR query is amortized over many vertices in that column, meaning you get distance information for everything at once.

Elias: Precisely. They use a dual-PIR split layout to handle this, separating the vector information from the neighbor lists into two different databases.

Nadia: So, one part of it handles finding distances across entire partitions, and the other part handles getting those specific neighbor lists at a finer level of detail for traversal.

Elias: That's what they mean by dual-PIR split layout. The goal is to shift the cost model from paying for every single vertex query to paying per partition instead.

Nadia: So, if you’re searching, instead of talking to the server thousands of times for individual items, you talk a few times per larger chunk of data?

Elias: Exactly. They are moving away from that per-vertex cost model which they call the fundamental source of Pacmann’s inefficiency because it incurs O(√N) communication yet retrieves only a single vertex’s vector and neighbor list.

The paper's improvements: Elias: They address how to organize the PIR database—that was challenge C1—by using this dual-PIR split layout where VecPIR stores only vector information horizontally, spreading each vertex’s vector across columns.

Nadia: And NbrPIR handles the neighbor lists vertically, and they cut each partition into subgroups so they can retrieve those lists at a subgroup granularity instead of trying to get everything all at once.

Elias: On top of that layout, Amora uses three specific optimizations to reduce how many scans and query rounds are needed in the PIR database.

Nadia: Can you tell us about those optimizations? What specifically makes it faster than just changing the storage layout?

Elias: First, they have Batch PIR which packs multiple queries into one matrix multiplication. Then there’s Centroid-based pruning to filter out partitions that aren't promising before spending too much time on them.

Nadia: And the third thing you mentioned is TopCand exploration? What does that do for the actual search navigation once you get those initial points?

Elias: That seeds jump-style graph navigation with the closest vertices from each retrieved partition, letting you leap directly to promising regions instead of following graph edges one step at a time.

Conclusion: Elias: To wrap up, Amora uses this combination of techniques—simplePIR with graph partitioning and batching and pruning—to achieve higher accuracy while drastically reducing online communication.

Nadia: The results on five datasets, ranging from ninety-six to one thousand twenty-four dimensions with up to ten million vectors show a reduction in online communication between ninety-three percent and ninety-nine percent compared to Pacmann.

Elias: They also found that the optimal number of partitions for VecPIR is set by C star equals the square root of N over d, where N is the total number of vectors and d is the dimensionality.

Nadia: And they noted that this scaling helps because each VecPIR query returns distances to all K vertices in a partition at once, which is much better than per-vertex PIR systems that pay O(d) communication per compared vertex.

Elias: The main implication for us is that Amora achieves a proportional reduction in communication because it's not paying the full cost for every single vertex comparison anymore.

Nadia: So, what does this mean practically? It means clients with limited bandwidth can actually use these high-accuracy private search methods without their data transmission costs ballooning.

Priya: From a privacy and measurement view, what I see here is that they’ve managed to keep the query vector hidden while still getting good distance estimates, which is exactly what we need when you're dealing with sensitive user intent.

Elias: Exactly. And the paper highlights that Amora achieves this efficiency by having a fixed communication pattern regardless of the query content, which is really solid for deployment.

Nadia: So to summarize "Amora: Communication-Efficient Private Approximate Nearest Neighbors Search," they successfully combined graph partitioning, batching, and specific exploration techniques within a dual-PIR split layout to achieve high search accuracy while reducing online communication by ninety-three to ninety-nine percent.

Priya: It’s an important piece of work because it shows that you can get better privacy guarantees without sacrificing the speed or the quality of the nearest neighbor results too much.

Qiuhao Wang, Zuowei Chen, Xu Yang, §Saiyu Qi*, Yong Qi

Xi’an Jiaotong University

cs.DB, cs.CR

Submitted: 2026-10-15

Updated: 2026-10-15

Comments: Accepted at SIGMOD 2027

Code: https://github.com/meander-wqh/Amora

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 91/100

The gist: The gist The Amora system presents a communication-efficient Private Approximate Nearest Neighbors Search (PANNS) that significantly reduces online communication by 93–99% compared to

Key concepts

Dual-PIR Split Layout: This layout organizes data into two separate PIR databases: VecPIR stores vector information horizontally across columns for fast inner product retrieval, while NbrPIR stores neighbor lists vertically at a subgroup level. This separation allows the system to retrieve full partition distances quickly and detailed neighbor lists efficiently.
Per-Partition Cost Model: Amora changes how communication is counted. Instead of paying for every single vertex query, it pays once per graph partition query. This is achieved by using graph partitioning and batching, meaning one PIR query covers many vertices simultaneously, significantly reducing the total communication overhead.
TopCand Exploration: This technique seeds the search process with jump-style navigation. After retrieving initial results from a partition, TopCand uses the closest vertices found to directly navigate to promising regions within that partition. This allows the system to leap directly to relevant areas instead of following slow, step-by-step graph traversals.

Summary

The gist The Amora system presents a communication-efficient Private Approximate Nearest Neighbors Search (PANNS) that significantly reduces online communication by 93–99% compared to state-of-the-art methods while achieving higher search accuracy

How it works

Amora is a graph-based PANNS system that employs a dual-PIR split layout to maximize the information retrieved per PIR query The system organizes the two types of payloads into two separate PIR databases with vertices grouped by graph partition VecPIR retrieves inner products for an entire partition of vertices as their distance at once, while NbrPIR retrieves necessary neighbor lists at subgroup granularity for graph traversal This layout shifts the cost model of PIR query from per-vertex to per-partition, which significantly reduces the communication overhead

Key components and optimizations

The system addresses challenges C1 (how to organize the PIR database) and C2 (how to reduce the number of scans and query rounds) For C1, Amora adopts a dual-PIR split layout where VecPIR stores only vector information horizontally, spreading each vertex’s vector across columns, and NbrPIR stacks neighbor lists vertically and cuts each partition into subgroups To improve efficiency by reducing the number of scans and query rounds in the PIR database, Amora introduces three optimization techniques These include Batch PIR to pack multiple queries into one matrix multiplication, Centroid-based pruning to filter unpromising partitions, and TopCand exploration that seeds jump-style graph navigation with the closest vertices from each retrieved partition

Amora Protocols and Search Flow

The Amora protocols operate in two phases: offline preprocessing (Algorithm 1) and online search (Algorithm 2) In the offline phase, the server constructs a proximity graph, partitions it into balanced partitions via graph partitioning, builds the VecPIR and NbrPIR databases following specific layouts, and performs the SimplePIR setup In the online phase (Algorithm 2), Stage 1 involves Centroid entry where the client computes inner products between query vector and all partition centroids locally to select entry points, followed by a BatchVecPir query Stage 2 consists of a fixed-iteration search loop where Phase A retrieves neighbor lists via BatchNbrPIR queries, Phase B selectively decrypts only the necessary neighbor entries from the cached subgroup ciphertext, and Phase C involves Centroid-based pruning and BatchVecPir queries to retrieve distances for new partitions The system executes exactly 1 +T VecPIR rounds and T NbrPIR rounds with fixed batch sizes per round, ensuring an identical communication pattern regardless of query content

Performance and Analysis

Experiments on five datasets spanning 96 to 1024 dimensions and up to 10 million vectors show that Amora reduces online communication by 93–99% while achieving higher search accuracy compared to Pacmann The optimal parameter selection yields an optimal number of partitions C∗ = √N/d for VecPIR and an optimal subgroup size S∗ = √N/(M0·t) for NbrPIR Amora achieves a proportional reduction in communication because each VecPIR query returns distances to all K vertices in a partition at once, whereas per-vertex PIR systems pay O(d) communication per compared vertex The system's latency is governed by the round count, and the reduction in rounds more than compensates for the SimplePIR computation overhead The dual-PIR split layout is necessary because a combined column carries d + M0 t values per vertex, leading to a 25× to 161× increase in online communication compared to the split layout

Conclusion

Amora successfully demonstrates that by combining SimplePIR with graph partitioning and employing batching, pruning, and TopCand exploration within a dual-PIR split layout, it achieves high accuracy while drastically reducing online communication over competitors The system's performance scales sublinearly with N, matching the O(√N·d) per-round cost of other PIR schemes The final results confirm that Amora reduces online communication by 93–99% over the competitors while achieving higher search accuracy

Improvements for AI systems

Amortized Communication Cost: The system achieves a per-partition cost model by applying SimplePIR to a partitioned graph index so that one PIR query is amortized over many vertices, which significantly reduces communication overhead compared to per-vertex PIR schemes where each PIR query retrieves only a single vertex.
Dual-Payload Information Density: Amora employs a dual-PIR split layout to address the dilemma of vertex payloads by organizing the two types of data separately: VecPIR retrieves inner products for an entire partition of vertices as their distance at once, while NbrPIR retrieves necessary neighbor lists at subgroup granularity for graph traversal.
Batching and Pruning Optimization: Efficiency is further enhanced through optimization techniques like Batch PIR to pack multiple queries into one matrix multiplication and Centroid-based pruning to filter unpromising partitions, which reduces the number of scans and query rounds required to reach target accuracy.
Jump-Style Graph Navigation: Amora incorporates TopCand exploration that seeds jump-style graph navigation with the closest vertices from each retrieved partition, enabling the system to leap directly to promising regions of a partition without following graph edges step by step.
Scalability and Dimensionality Handling: The optimal number of partitions is set as C∗ = √N/d (Eq. 5), ensuring that the cost model scales appropriately across different datasets, making the system robust when moving from lower-dimensional data to higher-dimensional vectors.

Abstract

Approximate nearest neighbors search (ANNS) over cloud-hosted vector databases raises a critical privacy concern: the query vector, which often encodes sensitive user intent, is exposed to the server. Private ANNS (PANNS) allows a client to retrieve nearest neighbors without revealing its query. The state-of-the-art single-server scheme, Pacmann (ICLR'25), achieves high accuracy via graph-based search with private information retrieval (PIR), but incurs substantial communication overhead because each PIR query retrieves only a single vertex. We present Amora, a communication-efficient PANNS system that applies SimplePIR to a partitioned graph index so that one PIR query is amortized over many vertices. To retrieve as much of the distance and neighbor information the search needs under a limited communication budget, Amora adopts a dual-PIR split layout with two heterogeneous PIR matrices that stay balanced in dimension: VecPIR retrieves inner products for an entire partition of vertices as their distance at once, while NbrPIR retrieves necessary neighbor lists at subgroup granularity for graph traversal. This layout shifts the cost model of PIR query from per-vertex to per-partition, which significantly reduces the communication overhead. To further improve efficiency by reducing the number of scans and query rounds in the PIR database, Amora introduces batch PIR to pack multiple queries into one matrix multiplication, centroid-based pruning to filter unpromising partitions, and TopCand exploration that seeds jump-style graph navigation with the closest vertices from each retrieved partition. We evaluate Amora on five datasets spanning 96 to 1024 dimensions and up to 10 million vectors. Compared to Pacmann, Amora reduces online communication by 93--99% while achieving higher search accuracy.