Hoss: Fast Oblivious Semantic Search with Heterogeneous GPU-CPU-TEE Architecture
Hoss uses heterogeneous GPU-CPU TEEs for oblivious semantic search, achieving up to 67x speedup over the Compass ORAM-based system.
Hoss is a first-of-its-kind oblivious semantic search system built on a heterogeneous CPU-GPU TEE architecture, hosting hot-path HNSW graph traversal in large GPU TEE private memory and offloading lower graph layers to CPU TEEs. It invokes oblivious primitives only for lower-layer accesses and adds host-access ORAM and data-dependent optimizations. Benchmarked against prior state-of-the-art Compass, the prototype achieves up to 67x speedup while maintaining high recall, with larger gains at scale.
- Leverages large GPU TEE private memory to bypass traditional ORAM bandwidth constraints
- Offloads lower HNSW layers to CPU TEEs, invoking oblivious primitives only there
- Prototype achieves up to 67x speedup over Compass with high recall
Full article251 words · extracted from arxiv.org · click to collapse
Semantic search is widely deployed in modern AI systems, but protecting both data contents and access patterns remains challenging. The current state-of-the-art system, Compass, achieves oblivious semantic search by building an optimized ORAM over HNSW graphs. However, even with aggressive optimizations, it still incurs large overheads. Closing this performance gap is fundamentally difficult: Compass has already removed most cryptographic overheads, leaving ORAM accesses as the dominant cost, which are constrained by well-known Omega(log N) bandwidth lower bounds. Our key insight is that traditional ORAM overhead stems from the assumption of limited private memory, whereas modern GPU TEEs provide large private memory (Pmem) that blinds internal access patterns (Hunt et al., NSDI '23). This shift opens a new design space. We therefore propose Hoss, a first-of-its-kind oblivious semantic search system with a heterogeneous CPU-GPU TEE architecture that supports fast, scalable search with low cost of ownership. In Hoss, the GPU TEE's large Pmem hosts the hot-path HNSW traversal, while the lower layers of the graph, if they exceed GPU capacity, are offloaded to CPU TEEs. The system invokes oblivious primitives only when accessing these lower layers. The availability of large Pmem also enables new optimization opportunities. For example, Hoss features a host-access ORAM mechanism that goes beyond traditional performance constraints and incorporates several data-dependent optimizations that are not possible in prior designs. We implement a prototype of Hoss and benchmark it against Compass. Our results show that Hoss achieves up to 67x speedup while maintaining high recall, with larger gains at scale.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.04522