Technical Summary: OTRO – Oblivious Tokenization Path with Square-Root ORAM

1. Problem Statement

The paper identifies a critical security gap in confidential Large Language Model (LLM) serving: the tokenizer. While Trusted Execution Environments (TEEs) like Intel TDX and NVIDIA GPU TEEs protect memory contents and computations, they do not inherently hide memory access patterns.

• The Vulnerability: Modern LLMs use Byte-Pair Encoding (BPE) tokenizers, which rely on deterministic, table-driven lookups (vocabulary and merge tables) to convert raw text into token IDs. Because the mapping from tokens to memory addresses is fixed after initialization, an adversary controlling the hypervisor or with physical access to the server can observe DRAM access patterns (via page faults or cache side-channels).
• The Consequence: Recent work (TDXRay) demonstrated that these access patterns allow for end-to-end reconstruction of user prompts with over 90% similarity, effectively bypassing TEE protections.
• The Challenge of Mitigation: Standard Oblivious RAM (ORAM) solutions, such as PathORAM, introduce prohibitive latency. Naive integration of PathORAM increases Time-To-First-Token (TTFT) by ~13×, while naive Square-Root ORAM (SqrtORAM) increases it by ~323× due to expensive $O(N \log^2 N)$ rebuild costs occurring every $\sqrt{N}$ accesses. These overheads are unacceptable for latency-critical LLM inference.

2. Methodology: OTRO Architecture

The authors propose OTRO (Oblivious Tokenization Path), an efficient, oblivious tokenization path tailored for LLM serving. The core insight is that tokenizer tables are read-only during inference. This property allows OTRO to decouple the expensive rebuild operations from the critical access path.

OTRO achieves this through three key innovations:

A. Pooled SqrtORAM Replication

Instead of a single SqrtORAM instance that must be rebuilt after $\sqrt{N}$ accesses, OTRO maintains a pool of replicated, read-only SqrtORAM instances.

• Each instance holds the same vocabulary and merge data but with a distinct random permutation.
• Since the data is read-only, instances do not need to reconcile updates; they only need to be reshuffled to maintain obliviousness.
• While one instance is being rebuilt, others continue to serve requests.

B. Epoch-Based Rotation and Padding

OTRO implements an epoch-based rotation policy to manage the pool:

• Rotation: Each instance serves exactly $\sqrt{N}$ accesses (one epoch). Once the limit is reached, the instance is marked for asynchronous background rebuilding, and the system rotates to a fresh instance.
• Padding: To prevent the exact number of accesses within an epoch from leaking information, OTRO pads each epoch with dummy accesses to reach the $\sqrt{N}$ boundary. This ensures the observable transcript reveals only the epoch count (and thus the coarse access count), not the precise number of lookups.
• Security: Instance selection is a deterministic function of the global access count, independent of the specific logical address being accessed, ensuring access-pattern indistinguishability.

C. Chunked Tokenization with KV-Cache Awareness

To minimize the pool size required to avoid stalls and hide rebuild latency, OTRO introduces chunked tokenization:

• Long input prompts are split into smaller chunks at pre-tokenization boundaries (whitespace-delimited words).
• Tokenization of a chunk is interleaved with the GPU's prefill phase.
• The system is tuned such that the time required for the GPU to process a chunk ($T_{gpu, prefill}$) is greater than the time required to rebuild a SqrtORAM instance ($T_{reshuffle}$).
• This overlap allows rebuilds to occur in the background while the GPU is computing, effectively amortizing the rebuild cost and reducing the number of required SqrtORAM instances in the pool.

D. Detokenization

OTRO also applies ORAM protection to the detokenization path (converting token IDs back to text). Due to the nature of the decode stage (where tokens are generated slowly over time), a small pool (e.g., 2 instances) is sufficient to overlap rebuilds with the decode kernels, hiding the latency.

3. Key Contributions

1. Cost Characterization: The authors demonstrate that while naive ORAM defenses are prohibitive (13×–323× slowdown), the rebuild cost is the primary bottleneck. By removing rebuilds from the critical path, OTRO tracks the unprotected baseline with less than 2.4× overhead.
2. Oblivious Architecture: A novel architecture utilizing a pool of read-only SqrtORAM instances, epoch-based rotation, and access-count padding to eliminate rebuilds from the critical path.
3. Latency-Aware Integration: The integration of chunked tokenization with GPU prefill and KV-cache mechanisms to overlap CPU-side rebuilds with GPU computation, minimizing memory footprint and instance count.
4. End-to-End Prototype: Implementation of OTRO within HuggingFace Tokenizers and nano-vLLM, running inside a TDX-enabled Confidential Virtual Machine (CVM) with an NVIDIA H100 GPU.
5. Leakage Reduction: Formal proof that OTRO's access patterns reveal nothing about specific table entries touched. With padding, the only unavoidable leakage is the input prompt length (byte length), which is inherent to any practical ORAM design.

4. Experimental Results

The system was evaluated on Llama-3.1, Qwen3, Gemma-3, and Phi-3 models using an Intel Xeon Gold CPU and NVIDIA H100 GPU.

• Latency (TTFT): OTRO limits the TTFT overhead to at most 4.5% compared to the unprotected baseline.
  • PathORAM increased TTFT by ~1.48×.
  • Naive SqrtORAM increased TTFT by ~11.12×.
  • OTRO (with chunking) performs near the "ideal" SqrtORAM scenario (no rebuild penalties), keeping tokenizer-induced latency under 10% of total TTFT.
• Memory Overhead: OTRO adds less than 0.5 GB of memory overhead per client (e.g., ~286 MB for Llama-3.1 with 48 instances). This is significantly lower than the overhead required for PathORAM in some configurations and allows a 256 GB CVM to support tens of concurrent clients.
• Initialization: Initialization costs increase by 35–350% depending on the model, but since this is a one-time cost per model load, it is not considered a system bottleneck.
• Leakage Analysis:
  • Without ORAM, an adversary can reconstruct prompts with ~0 bits of residual uncertainty.
  • With OTRO (no padding), residual uncertainty is 1.60 bits.
  • With OTRO (with access-count padding), residual uncertainty rises to 5.49 bits, recovering 38.4% of the original prompt entropy. The remaining leakage is primarily due to the unavoidable correlation between input byte length and access count.

5. Significance and Claims

The paper claims that OTRO provides a viable path to end-to-end confidentiality in production LLM-serving stacks. It addresses a specific, high-fidelity side-channel (tokenizer access patterns) that survives standard TEE protections.

• Practicality: Unlike previous theoretical ORAM solutions or those designed for different threat models (e.g., SGX with memory constraints), OTRO is designed specifically for the latency-sensitive, read-only nature of LLM tokenization in modern CVMs with GPU support.
• Security vs. Performance Trade-off: The work demonstrates that it is possible to achieve strong access-pattern confidentiality (hiding which tokens are accessed) with negligible performance impact (<5% TTFT overhead), a trade-off that was previously thought to be prohibitive.
• Scope: The authors explicitly state that OTRO protects the memory access patterns of the tokenizer tables. It does not claim to eliminate all side channels (e.g., timing variability from specific code patterns) or protect against input-length leakage, which is treated as an unavoidable baseline in practical ORAM deployments.

In summary, OTRO transforms the bursty, critical-path rebuild cost of SqrtORAM into background work through replication and scheduling, enabling secure, low-latency LLM inference in the presence of a powerful, privileged adversary.