Onyx : Cost-Efficient Disk-Oblivious ANN Search

Deevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao, G. Edward Suh, Raluca Ada Popa · 2026

Read Onyx : Cost-Efficient Disk-Oblivious ANN Search by Deevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao, G. Edward Suh, Raluca Ada Popa (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-20401.txt.

Introduction

Rathee and four colleagues present Onyx, a cost-efficient design for oblivious approximate nearest neighbor search over external SSDs. Trusted execution environments protect data on third-party machines, but queries leak through disk access patterns, and hiding those patterns with oblivious RAM is costly. Onyx flips the usual design, saving bandwidth at the search layer and access count at the oblivious RAM layer, where each choice fits better. Against the prior best oblivious system, Onyx cuts cost about two to ten times and latency about two to twelve times.

Catalog record

CREATORDeevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao, G. Edward Suh, Raluca Ada Popa
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96243
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.20401

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Onyx : Cost-Efficient Disk-Oblivious ANN Search Deevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao, G. Edward Suh, Raluca Ada Popa Abstract . Approximate nearest neighbor (ANN) search in AI systems increasingly handles sensitive data on third-party infrastructure. Trusted execution environments (TEEs) offer protection, but cost-efficient deployments must rely on external SSDs, which leaks user queries through disk access patterns to the host. Oblivious RAM (ORAM) can hide these access patterns but at a high cost; when paired with existing disk-based ANN search techniques, it makes poor use of SSD resources, yielding high latency and poor cost-efficiency. The core challenge for efficient oblivious ANN search over SSDs is balancing both bandwidth and access count. The state-of-the-art ORAM-ANN design minimizes access count at the ANN level and bandwidth at the ORAM level, each trading-off the other, leaving the combined system with both resources overutilized. We propose inverting this design, minimizing bandwidth consumption in the ANN layer and access count in the ORAM layer, since each component is better suited for its new role: ANN’s inherent approximation allows for more bandwidth efficiency, while ORAM has no fundamental lower bounds on access count (as opposed to bandwidth). To this end, we propose a cost-efficient approach, Onyx , with two new co-designed components: Onyx -ANNS introduces a compact intermediate representation that proactively prunes the majority of bandwidth-intensive accesses without hurting recall, and Onyx -ORAM proposes a locality-aware shallow tree design that reduces access count while remaining compatible with bandwidth-efficient ORAM techniques. Compared to the state-of-the-art oblivious ANN search system, Onyx achieves 1.7 1.7 – 9.9 × 9.9\times lower cost and 2.3 2.3 – 12.3 × 12.3\times lower latency. 1. Introduction Approximate nearest neighbor (ANN) search powers many AI systems, including retrieval-augmented generation (RAG) ( 61 ; 44 ) , search ( 52 ; 79 ) , and recommendation ( 92 ; 123 ) . As these systems increasingly run on third-party infrastructure and operate over sensitive data, privacy has become a critical requirement. For example, systems such as ChatGPT serve hundreds of millions of users and perform RAG queries over their highly sensitive chat messages ( 90 ) . A natural first step to protect the search index and query contents is to encrypt them. However, it is well-known from over a decade of leakage-abuse attacks ( 47 ; 13 ; 127 ; 41 ; 11 ; 81 ; 78 ; 50 ) that encryption alone is not enough: a service provider observing the sequence of accesses during query processing can infer information about the query and the dataset, and sometimes, recover the dataset entirely ( 56 ) . Cryptographic approaches such as oblivious RAM (ORAM) ( 35 ) hide this leakage, but remain too expensive for ANN search. Given a 10M-vector index at 90\% recall, the state-of-the-art solution Compass ( 131 ) serves 100 queries/$ and incurs over 1 s of latency, far from the under-20 ms latencies expected in production deployments ( 110 ) . To avoid the high overhead of purely cryptographic approaches, a practical alternative is to rely on hardware assumptions and run ANN search inside a trusted execution environment (TEE) ( 51 ; 18 ) , where the index is stored in the protected TEE memory. However, keeping the entire index in enclave memory quickly becomes expensive at scale (§ 2.1 ). In practice, cost-efficient ANN systems store the index on SSDs ( 105 ; 16 ; 114 ; 106 ; 99 ; 111 ) , but this storage typically lies outside the TEE trust boundary, introducing access pattern leakage through disk I/O (§ 3.1 ). ORAM-in-TEE for disk-oblivious accesses. In principle, the solution is simple: run Compass ( 131 ) , the state-of-the-art ORAM-ANN system, inside a TEE to hide disk access patterns. However, this approach is unsuitable for the disk setting as it places heavy demands on SSD I/O , ultimately requiring more compute and SSD resources and driving up cost. For instance, sustaining \approx 50 QPS on a 20M 3 KB vector index at 90% recall requires at least 4 vCPUs and 8 SSD units, and still incurs \approx 160 ms latency (§ 6.3 ). Figure 1 . Prior designs for oblivious ANNS and Onyx . Compass ( 131 ) suffers from poor performance due to high network overhead, and mirroring its design into a TEE yields a system that needs significant CPU and SSD resources to sustain reasonable performance. Onyx proposes co-designed primitives for ANNS and ORAM that jointly improve resource utilization, yielding high performance and low cost. To address this, we propose Onyx , a fundamentally different ANN-ORAM co-design for the disk setting that significantly reduces this overhead through efficient utilization of SSD resources (see Figure 1 for an overview). Onyx achieves up to 10\times better cost-efficiency than the Compass-in-TEE approach; with a single vCPU and a single SSD unit on the same index, it sustains \approx 70 QPS at 12 ms latency. Inverting the ORAM-ANN co-design. The core challenge for efficient oblivious ANN search over SSDs is balancing SSD bandwidth and SSD access count , since both directly determine performance and resource cost. Prior ORAM-ANN co-design ( 131 ) , optimizing for oblivious search over a network, combines an access-count-efficient ANN (reducing network round-trips) with a bandwidth-efficient ORAM (reducing communication bandwidth), but each primitive aggressively trades off the other resource. The ANN layer fetches larger blocks to reduce accesses, wasting bandwidth due to the inherently low spatial locality of ANN search ( 114 ; 77 ) , while the ORAM layer makes many fine-grained accesses to reduce data movement but is ultimately limited by fundamental lower bounds to ORAM bandwidth ( 57 ; 55 ) . In this work, we invert this design, arguing that both ORAM and ANN are better-suited for their new role. ANN search is naturally approximate, so it can maintain high recall with smaller, lower-precision representations, supporting aggressive bandwidth reduction. ORAM has no fundamental lower bounds on access count, allowing it to significantly reduce the number of I/O operations required per access. New primitives for our co-design. Existing primitives fall short of realizing the optimization objectives of our design. ANN search algorithms for disk-hosted indices are designed assuming bandwidth is plentiful, which is true for plain SSDs but not for ORAM over SSDs. On the ORAM side, access-efficient designs such as EnigMap ( 108 ) introduce high bandwidth amplification, negating the ANN-side savings. To address both, we propose two new co-designed primitives. Onyx -ANNS (§ 5 ) retains the low memory footprint and accesses required for disk-hosted indices, while introducing a compact intermediate representation that proactively prunes the majority of bandwidth-intensive full-precision accesses without hurting recall. This reduces ANN bandwidth by up to 5\times while increasing access count by at most 15\% compared to the state-of-the-art ( 105 ) disk-based ANN search (§ 5.2 ). Onyx -ORAM (§ 4 ) proposes a locality-aware shallow tree design that significantly reduces access count while remaining compatible with bandwidth-efficient ORAM techniques. Compared to EnigMap-style access-optimized PathORAM ( 108 ) , our design achieves 2\times lower access count and 4.6\times lower bandwidth simultaneously (§ 4.2 ) Together, the two primitives achieve a much better balance of SSD bandwidth and access count than any prior combination.

Read the complete text