Hoss: Fast Oblivious Semantic Search with Heterogeneous GPU-CPU-TEE Architecture

• URL: http://arxiv.org/abs/2609.04522v1
• Date: Thu, 03 Sep 2026 22:21:51 GMT
• Title: Hoss: Fast Oblivious Semantic Search with Heterogeneous GPU-CPU-TEE Architecture
• Abstract summary: Current oblivious semantic search system, Compass, incurs large overheads.<n>We propose a first-of-its-kind oblivious semantic search system with a heterogeneous CPU-GPU TEE architecture.<n>Hoss achieves 67x speedup while maintaining high recall, with larger gains at scale.
• Score: 13.990684047479578
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• GRAB-ANNS: High-Throughput Indexing and Hybrid Search via GPU-Native Bucketing [39.763467046232584]
  We present GRAB-ANNS, a GPU-native graph index for dynamic hybrid search.<n>We show that GRAB-ANNS achieves up to 240.1 times higher query throughput and 12.6 times faster index construction than state-of-the-art CPU-based systems.
  arXiv  Detail & Related papers  (2026-03-31T11:00:10Z)
• GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions [54.570944939061555]
  We present a comprehensive study of GPU-accelerated graph-based vector search algorithms.<n>We establish a detailed taxonomy of GPU optimization strategies and clarify the mapping between algorithmic tasks and hardware execution units.<n>Our findings offer clear guidelines for designing scalable and robust GPU-powered approximate nearest neighbor search systems.
  arXiv  Detail & Related papers  (2026-02-10T16:18:04Z)
• GPU-Accelerated ANNS: Quantized for Speed, Built for Change [1.8419317899207142]
  Current Approximate nearest neighbor search (ANNS) systems face three key limitations.<n>Current systems lack efficient quantization techniques that reduce data movement without introducing costly random memory accesses.<n>We present Jasper, a GPU-accelerated ANNS system with both high query throughput and upability.
  arXiv  Detail & Related papers  (2026-01-11T19:51:54Z)
• FaST: Efficient and Effective Long-Horizon Forecasting for Large-Scale Spatial-Temporal Graphs via Mixture-of-Experts [49.9321870703948]
  Existing models predominantly focus on short-horizon predictions and suffer from notorious computational costs and memory consumption.<n>We present FaST, an effective and efficient framework based on Mixture-of-Experts (MoEs) for long-horizon and large-scale STG forecasting.<n>FaST is underpinned by two key innovations. First, an adaptive graph agent attention mechanism is proposed to alleviate the computational burden.<n>Second, we propose a new parallel MoE module that replaces traditional feed-forward networks with Gated Linear Units (GLUs)
  arXiv  Detail & Related papers  (2026-01-08T18:00:58Z)
• Theodosian: A Deep Dive into Memory-Hierarchy-Centric FHE Acceleration [3.8153115302044296]
  Fully homomorphic encryption (FHE) enables secure computation on encrypted data, mitigating privacy concerns in cloud and edge environments.<n>In this paper, we perform a microarchitectural analysis of CKKS, a popular FHE scheme, on modern GPUs.<n>We show that the dominant kernels remain bound by memory bandwidth despite a high-bandwidth L2 cache, exposing a persistent memory wall.<n>Motivated by these findings, we introduce Theodosian, a set of complementary, memory-aware optimizations that improve cache efficiency and reduce overheads.
  arXiv  Detail & Related papers  (2025-12-20T12:18:29Z)
• BOLT: Bandwidth-Optimized Lightning-Fast Oblivious Map powered by Secure HBM Accelerators [13.90111222973057]
  Cloud Execution Environments are vulnerable to access pattern leakages.<n>Oblivious Maps mitigate this by hiding access patterns but suffer from high overhead.<n>We present BOLT, a Bandwidth Optimized, Lightning-fast OMAP accelerator.
  arXiv  Detail & Related papers  (2025-09-01T19:49:21Z)
• A Parallel CPU-GPU Framework for Cost-Bounded DFS with Applications to IDA* and BTS [13.186524200050957]
  We introduce a method for GPU computations in depth first search.<n>This is used to create algorithms like emphsynchronous IDA*, an extension of the Iterative Deepening A* (IDA*) algorithm.<n>We evaluate the approach on the 3x3's Rubik Cube and 4x4 sliding tile puzzle (STP), showing that GPU operations can be efficiently batched in DFS.
  arXiv  Detail & Related papers  (2025-07-16T05:07:33Z)
• MoE-Lightning: High-Throughput MoE Inference on Memory-constrained GPUs [55.95879347182669]
  MoE architecture is renowned for its ability to increase model capacity without a proportional increase in inference cost. MoE-Lightning introduces a novel CPU-GPU-I/O pipelining schedule, CGOPipe, with paged weights to achieve high resource utilization. MoE-Lightning can achieve up to 10.3x higher throughput than state-of-the-art offloading-enabled LLM inference systems for Mixtral 8x7B on a single T4 GPU (16GB)
  arXiv  Detail & Related papers  (2024-11-18T01:06:12Z)
• FusionAI: Decentralized Training and Deploying LLMs with Massive Consumer-Level GPUs [57.12856172329322]
  We envision a decentralized system unlocking the potential vast untapped consumer-level GPU. This system faces critical challenges, including limited CPU and GPU memory, low network bandwidth, the variability of peer and device heterogeneity.
  arXiv  Detail & Related papers  (2023-09-03T13:27:56Z)
• Communication-Efficient Graph Neural Networks with Probabilistic Neighborhood Expansion Analysis and Caching [59.8522166385372]
  Training and inference with graph neural networks (GNNs) on massive graphs has been actively studied since the inception of GNNs. This paper is concerned with minibatch training and inference with GNNs that employ node-wise sampling in distributed settings. We present SALIENT++, which extends the prior state-of-the-art SALIENT system to work with partitioned feature data.
  arXiv  Detail & Related papers  (2023-05-04T21:04:01Z)
• ASH: A Modern Framework for Parallel Spatial Hashing in 3D Perception [91.24236600199542]
  ASH is a modern and high-performance framework for parallel spatial hashing on GPU. ASH achieves higher performance, supports richer functionality, and requires fewer lines of code. ASH and its example applications are open sourced in Open3D.
  arXiv  Detail & Related papers  (2021-10-01T16:25:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.