Onyx: Cost-Efficient Disk-Oblivious ANN Search

Researchers proposed Onyx, a disk-oblivious approximate nearest neighbor (ANN) search system that achieves 1.7–9.9× lower cost and 2.3–12.3× lower latency than the state-of-the-art oblivious ANN search system. Onyx inverts prior ORAM-ANN design by minimizing bandwidth consumption in the ANN layer via Onyx-ANNS, a compact intermediate representation that prunes bandwidth-intensive accesses without hurting recall, and minimizing access count in the ORAM layer via Onyx-ORAM, a locality-aware shallow tree design. The approach targets cost-efficient ANN search over external SSDs in trusted execution environments, where disk access patterns would otherwise leak user queries to the host.

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−9.9× lower cost and 2.3−12.3× lower latency.