💻 computer science

Onyx: Cost-Efficient Disk-Oblivious ANN Search

Onyx is a cost-efficient, disk-oblivious Approximate Nearest Neighbor (ANN) search system that achieves significant reductions in latency and cost by inverting traditional design trade-offs, utilizing a bandwidth-efficient ANN layer with proactive pruning and a locality-aware ORAM layer to minimize both disk access patterns and bandwidth consumption on third-party infrastructure.

Original authors: Deevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao, G. Edward Suh, Raluca Ada Popa

Published 2026-04-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Deevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao, G. Edward Suh, Raluca Ada Popa

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, highly sensitive library of books (your data) that you want to keep safe. You don't have enough space in your own house (your computer's memory) to store all of them, so you rent a warehouse (a cloud server) to keep them.

The problem? The warehouse owner is untrustworthy. They can't read the books because they are locked in steel boxes (encryption), but they can watch which boxes you open and when. By watching your habits—like "Oh, he always opens Box A, then Box B, then Box C"—the owner can guess what you are looking for, even without seeing the contents. This is called an access pattern leak.

To stop this, you need a system that makes your movements look random, like a magician shuffling cards so no one can tell which card you picked. This is called ORAM (Oblivious RAM). But here's the catch: doing this magic shuffle is incredibly slow and expensive. It's like hiring a team of 100 people just to walk you to the library door so no one sees which shelf you go to.

Onyx is a new system designed to make this "magic shuffle" fast, cheap, and practical. Here is how it works, broken down into simple concepts:

1. The Old Way: The "Heavy Box" Problem

In previous systems (like the one called Compass), the library was organized like a giant maze. To find a book, you had to walk through many corridors.

The Flaw: The old system tried to be smart by grabbing huge boxes (blocks of data) at once to save time walking. But in the "magic shuffle" world, grabbing a huge box is actually a disaster. It wastes a lot of bandwidth (like trying to carry a sofa through a narrow hallway) and makes the "shuffling" process incredibly slow and expensive.
The Result: It was so slow and costly that only the richest companies could afford it, and even then, it took seconds to find a single book.

2. The Onyx Solution: "The Two-Step Dance"

Onyx changes the rules by splitting the job into two specialized teams that work together perfectly. Think of it like a Detective and a Librarian.

Step A: The Detective (Onyx-ANNS)

The Detective's job is to find the right books without carrying heavy boxes.

The Old Way: The Detective would grab a massive box containing the book's full text and its location map just to check if it's the right one.
The Onyx Way: The Detective grabs a tiny, lightweight "clue card" (a compact hint) first. This card tells them, "Hey, this book is probably what you want."
The Magic: The Detective only grabs the heavy, full-text box if the clue card says "Yes, definitely." This means they spend 90% of their time carrying tiny cards and only occasionally carrying heavy boxes. This saves a massive amount of energy (bandwidth).

Step B: The Librarian (Onyx-ORAM)

The Librarian's job is to hide the Detective's movements from the warehouse owner.

The Old Way: The Librarian was trying to hide the movement of those massive boxes. It was hard to shuffle big boxes quickly without making noise.
The Onyx Way: Since the Detective is mostly carrying tiny cards, the Librarian only needs to shuffle tiny cards.
The Innovation: Onyx uses a special "shallow tree" structure (like a wide, flat pyramid instead of a tall, skinny one). This allows the Librarian to move many tiny cards at once in a very organized, efficient way. Because the boxes are small, the Librarian can move them incredibly fast.

3. Why It's a Game Changer

By swapping the roles, Onyx creates a perfect match:

The Detective is great at guessing which tiny cards to fetch (saving bandwidth).
The Librarian is great at shuffling those tiny cards quickly (saving time and money).

The Analogy:
Imagine you are trying to find a specific grain of sand on a beach.

The Old Way: You bring a giant shovel and scoop up a whole bucket of sand every time you take a step, hoping the grain is there. It's slow, and everyone sees you carrying heavy buckets.
The Onyx Way: You use a metal detector (the tiny clue card) to beep when you are close. You only dig with the shovel (the heavy box) when the detector beeps. You walk lightly, carrying almost nothing, and the person watching you can't tell what you are looking for because your path looks random and light.

The Results

Because of this clever teamwork:

Speed: It finds answers 2 to 12 times faster than the previous best systems.
Cost: It costs 2 to 10 times less to run.
Scale: It can handle millions of users and billions of data points without breaking the bank.

In short, Onyx takes a technology that was previously too slow and expensive for real-world use and makes it fast enough to power the next generation of private AI assistants, secure search engines, and private data stores. It proves that you can have privacy without sacrificing speed or breaking the bank.

1. Problem Statement

Approximate Nearest Neighbor (ANN) search is critical for AI systems (e.g., RAG, recommendations), but these systems increasingly run on third-party infrastructure using sensitive data.

The Privacy Gap: While Trusted Execution Environments (TEEs) protect data in memory, cost-efficiency requires storing large indices on external SSDs. However, SSDs lie outside the TEE trust boundary. Observing disk access patterns allows adversaries to infer user queries and reconstruct datasets (via leakage-abuse attacks), even if data is encrypted.
The Performance/Cost Bottleneck:
- ORAM Limitations: Oblivious RAM (ORAM) hides access patterns but introduces significant overhead. Existing ORAM-ANN designs (e.g., Compass) optimize for network settings, minimizing access counts at the ANN level and bandwidth at the ORAM level.
- Resource Mismatch: When applied to SSDs, this design fails. ANN search inherently has low spatial locality, leading to high bandwidth waste when fetching large blocks to reduce access counts. Conversely, ORAM has fundamental lower bounds on bandwidth but no fundamental lower bounds on access count.
- Result: State-of-the-art solutions suffer from high latency (>1s) and poor cost-efficiency (e.g., 100 queries/$), making them impractical for production.

2. Methodology: The Onyx Co-Design

Onyx proposes a fundamental inversion of the ORAM-ANN co-design philosophy. Instead of minimizing access counts in the ANN layer and bandwidth in the ORAM layer, Onyx minimizes bandwidth in the ANN layer and minimizes access counts in the ORAM layer.

This is achieved through two newly co-designed components:

A. Onyx-ANNS (Bandwidth-Efficient ANN Search)

Core Idea: Decouple the traversal phase from the refinement phase.
Mechanism:
1. Traversal: Uses a graph-based search (like DiskANN) but fetches only small blocks containing adjacency lists and compact pruning hints ( $H_{prn}$ ). These hints are intermediate representations (e.g., product quantization) that are more precise than in-memory hints but much smaller than full-precision vectors.
2. Pruning: The system ranks candidates using these small pruning hints to aggressively filter the candidate list.
3. Refinement: Only the top candidates (a small subset) are fetched for full-precision vector refinement.
Benefit: This reduces the bandwidth consumed by the ANN layer by 2–5× compared to standard DiskANN, while increasing the access count by only 5–15%. Crucially, it keeps the DRAM footprint unchanged by not storing these hints in memory.

B. Onyx-ORAM (Access-Count-Efficient ORAM)

Core Idea: Optimize for access count reduction while maintaining compatibility with bandwidth-efficient large-block operations.
Mechanism:
1. Local Metadata: Stores bucket metadata locally within the TEE to eliminate per-level metadata fetches (reducing I/O requests per level).
2. Full Bucket Reads: During eviction, reads entire buckets (including dummy slots) as single sequential I/Os rather than fetching individual blocks, trading bandwidth for fewer access operations.
3. Shallow $d$ -ary Trees: Replaces the standard binary tree with a wide, shallow $d$ -ary tree (e.g., $d=8$ ). This reduces tree depth (and thus access count) by a factor of $\log_2 d$ .
Key Insight: While $d$ -ary trees typically increase eviction frequency (and thus bandwidth), Onyx-ORAM leverages the fact that larger buckets (enabled by local metadata) allow for proportionally larger eviction periods. This balances the trade-off, reducing access counts by 3× with negligible bandwidth penalty.

3. Key Contributions

Inverted Design Paradigm: The paper identifies that ANN search is naturally suited for bandwidth reduction (via approximation), while ORAM is suited for access count reduction (via structural optimization), and proposes a system that exploits these strengths.
Onyx-ANNS: Introduces a three-step granular refinement strategy (Traverse $\to$ Prune $\to$ Refine) using compact pruning hints fetched from disk, achieving massive bandwidth savings without increasing memory usage.
Onyx-ORAM: Proposes a locality-aware shallow tree design that combines local metadata, full-bucket reads, and $d$ -ary trees to simultaneously minimize both I/O access count and bandwidth overhead.
System Integration: Demonstrates how these two components reinforce each other: Onyx-ANNS generates small block sizes (256–512 bytes) where Onyx-ORAM achieves peak throughput, creating a synergistic effect.

4. Results

The authors evaluated Onyx against state-of-the-art baselines (Compass-in-TEE, RingORAM+DiskANN, PathORAM+DiskANN) across four datasets (SIFT, MS-MARCO, WIKI, DEEP) on TEE-enabled cloud hardware.

Latency & Throughput:
- Onyx achieves 2.3–12.3× lower latency and 2.3–12.2× higher throughput compared to Compass-in-TEE.
- Compared to the best disk-optimized baselines, Onyx achieves 2.5–9.5× lower latency.
Cost Efficiency:
- Onyx achieves 1.7–9.9× lower cost (Queries per Dollar) than Compass-in-TEE.
- It achieves 2.6–7.3× higher cost-efficiency than other ORAM-ANN combinations.
Resource Utilization:
- With a single vCPU and a single SSD unit, Onyx can host a 64 GB index, sustain 70 QPS at 12 ms latency with 90% recall, and serve over 8 million queries per dollar.
Ablation Studies: The results confirm that neither component alone is sufficient; the co-design is essential. On small-vector datasets, the ORAM optimization drives performance; on large-vector datasets, the ANN bandwidth reduction is critical.

5. Significance

Practicality for Private AI: Onyx bridges the gap between theoretical privacy (ORAM) and practical deployment (cost and latency). It makes private, disk-resident ANN search viable for real-world applications like enterprise RAG and personalized AI agents.
Scalability: By reducing the reliance on expensive DRAM and optimizing SSD usage, Onyx enables the deployment of massive indices (billions of vectors) on cost-effective hardware within TEEs.
Security: It provides strong guarantees against access-pattern leakage, a critical vulnerability in encrypted search systems, without sacrificing the performance required for interactive AI applications.

In summary, Onyx represents a breakthrough in secure database systems by rethinking the interaction between search algorithms and oblivious storage, proving that cost-efficient, low-latency, and privacy-preserving ANN search is achievable at scale.