OTRO: Oblivious Tokenization Path with Square-Root ORAM

arXiv:2606.17358 · cs.CR · Submitted 2026-06-15 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia, and with me are Elias and Priya, guest researcher.

Elias: Today's paper: "OTRO: Oblivious Tokenization Path with Square-Root ORAM".

Nadia: The gist The CPU-side large language model (LLM) tokenizer is a critical security gap in LLM serving through a confidential computing stack with CPU and GPU trusted execution environments (TEEs).

Elias: First, who's behind it and why it matters.

Title and authors: Nadia: Okay, moving on to the title and authors of "OTRO: Oblivious Tokenization Path with Square-Root ORAM."

Elias: The title itself is quite technical, but it immediately tells you what the core idea is. It’s about an oblivious path using Square-Root ORAM for tokenization.

Nadia: It’s specific because it points directly to the two main components: making the process oblivious and using a specific type of RAM structure, which is SqrtORAM one.

Elias: And by naming those things, they are signaling that this isn't just a general defense; it’s tied to a particular memory management technique. It grounds the research in existing concepts.

Priya: So when you hear that, what does that imply about the complexity of implementing this? Are we talking about something simple to set up, or is it very intricate engineering?

Nadia: It implies a certain level of engineering because they are building a system around existing ORAM concepts but adapting them for the specific constraints of LLM serving one.

Elias: Yeah, and they’re addressing the fact that standard tree-based Oblivious RAMs, like PathORAM, can introduce significant slowdowns, which is why they are focusing on SqrtORAM one.

Priya: So the research isn't just about finding a new mathematical proof; it’s about engineering a practical system that actually runs without crippling performance.

Nadia: Precisely, and they’re showing that you can use these structures to achieve the privacy goal without incurring those prohibitive slowdowns one.

Elias: The authors are focused on proving the cost characterization of this oblivious tokenization, which is a key contribution they highlight three <ref:2606.17358#pg2>. They aren't just claiming it works; they are quantifying exactly how much time and memory it costs.

Priya: That sounds like necessary work for anyone who wants to trust these kinds of systems in real-world applications. You need those numbers to know if the protection is worth the performance hit.

Nadia: Absolutely, because they provide cost characterization, which means they tell you exactly what's happening under the hood with their defense three <ref:2606.17358#pg2>. It moves it from a theoretical concept to something measurable.

Elias: And that measurement helps verify that their design actually meets the promise of being oblivious to prompt content leakage one. They are showing they can achieve the privacy goal without introducing massive overhead.

Priya: So, when we look at this paper in terms of its practical application, what does that suggest about how we should approach building these systems?

Nadia: It suggests that you need a defense that’s integrated into the serving path itself, not something bolted on later three <ref:2606.17358#pg2>. It needs to be woven into the tokenization process.

Elias: And by using SqrtORAM, they are optimizing for fast single-access lookups while managing those rebuild costs more efficiently than other options one.

The paper's summary: Priya: Now that we understand the setup a bit better, can you give us the main summary of what OTRO is actually doing in plain terms?

Nadia: In essence, OTRO provides an efficient, oblivious tokenization path tailored for latency-critical LLM serving three <ref:2606.17358#pg2>. It focuses on making sure that tokenizer access patterns reveal nothing about the prompt content.

Elias: The core idea is using a pool of read-only SqrtORAM instances with an epoch-based rotation strategy to handle the rebuilds asynchronously in the background three <ref:2606.17358#pg2>.

Priya: So, if I had to boil it down for someone who isn't deep in cryptography, what’s the operational flow? How does a request get processed through this system?

Nadia: A request hits one of these instances, and after serving N accesses—which is one epoch—that instance goes offline for an oblivious rebuild. New requests are routed to a fresh instance that's ready to go three <ref:2606.17358#pg2>.

Elias: And they add padding during those epochs by adding dummy accesses up to the square-root boundary three <ref:2606.17358#pg2>. This padding is what helps them keep things orderly while waiting for the rebuilds.

Priya: So, it’s essentially managing a dynamic pool of these structures so that no single structure is ever overloaded or stuck rebuilding when you need a response?

Nadia: That’s right, it manages the pool so that requests are always routed to an instance that isn't busy doing heavy rebuild work three <ref:2606.17358#pg2>. And they also use chunked tokenization to overlap the prefill of prompt chunks with the rebuild phase of another instance three <ref:2606.17358#pg2>.

Elias: That chunking is clever because it allows them to keep serving requests while other parts are rebuilding, which keeps the entire pipeline moving smoothly.

Priya: It sounds like they’re taking a complicated, bursty task and turning it into something that can be processed continuously without bottlenecks three <ref:2606.17358#pg2>.

Nadia: They did that by making the rebuild cost amortized work over time rather than hitting your critical path every single time three <ref:2606.17358#pg2>. The entire paper is about turning that stall into background work.

Elias: It’s a sophisticated way to handle the dynamics of tokenization in this context three <ref:2606.17358#pg2>. But they are showing how you can keep the system running smoothly under heavy load and still maintain the illusion of a fast, uninterrupted service.

Priya: So, if someone only listens to this show, what's the big picture here? What does it change for them about LLM serving?

Nadia: It shows that workloadaware ORAM integration is a viable path to end-to-end confidentiality in production LLM-serving stacks three <ref:2606.17358#pg2>. It’s not just a theoretical idea anymore; it’s showing how to implement it practically.

Elias: It moves the discussion from 'can we do this?' to 'how do we make sure it runs reliably under real load' three <ref:2606.17358#pg2>.

The paper's improvements: Priya: Okay, let's dig into the specific improvements they suggest and what they’ve done that makes OTRO better than what came before.

Nadia: Their main improvement is moving away from naive SqrtORAM or PathORAM, which are known to introduce slowdowns like ten–fifty-eight percent higher timeto-first-token time one.

Elias: They’re using the specific properties of SqrtORAM to ensure fast single-access lookups while managing the rebuild costs more efficiently one.

Priya: So, what is the concrete difference in performance that we should be paying attention to? Is it a small percentage point or a factor of ten?

Nadia: The cost characterization they do shows that OTRO keeps the overhead within four point five percent of the unprotected baseline three. That's not just a small number; it’s kept very low compared to what other methods could introduce three <ref:2606.17358#pg2>.

Elias: They are also using the chunked tokenization technique to overlap prefill with GPU prefill and minimize the instance count by interleaving these two tasks three <ref:2606.17358#pg2>.

Priya: So, that means they’re not just fixing one problem; they’re solving the latency issue while simultaneously managing memory usage?

Nadia: Exactly, because by overlapping those tasks, you reduce the number of instances needed in the pool and keep rebuilds from stalling the critical path three <ref:2606.17358#pg2>.

Elias: And they also use access-count padding to reveal only a coarse epoch count instead of trying to leak per-word merge pass counts three <ref:2606.17358#pg2>. That’s a significant refinement for security, because it reduces the observable transcript substantially.

Priya: So, in short, they’ve improved the defense by combining a few different techniques—better RAM choice with workloadaware scheduling and better padding to get a much stronger security result for less performance cost one.

Nadia: That combination is what makes this approach practical for production use in real-world LLM serving stacks three <ref:2606.17358#pg2>. It moves it from a theoretical idea to something that actually works.

Conclusion: Elias: So, wrapping up the discussion on "OTRO: Oblivious Tokenization Path with Square-Root ORAM." We’ve talked about how this approach turns the bursty rebuild cost of SqrtORAM into background work that doesn't stall the serving pipeline.

Nadia: The key is that they managed to keep the timeto-first-token overhead at four point five nine percent on average compared to the baseline three. That’s a modest cost when you consider what this does for security, which is reducing observable leakage to just prompt length alone.

Priya: For someone listening, what’s the final word on the implications of this work? What should they really be focusing on moving forward?

Nadia: The implication is that workloadaware ORAM integration is a viable path to end-to-end confidentiality in production LLM-serving stacks three <ref:2606.17358#pg2>. It’s showing how you can implement a defense practically.

Elias: It proves that you can build systems that are both fast and secure without adding prohibitive performance penalties one. They did it by making the rebuild cost amortized work rather than hitting the critical path every single time.

Priya: I think what we should be focusing on is on the practical implementation details—how to actually integrate this into existing infrastructure.

Nadia: Right, so that’s where we are going for next time, but for today, that covers what this paper has to offer regarding OTRO: Oblivious Tokenization Path with Square-Root ORAM.

University of Southern California

cs.CR

Submitted: 2026-06-15

Updated: 2026-10-07

Code: https://github.com/meta-llama/llama3

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 90/100

The gist: The gist The CPU-side large language model (LLM) tokenizer is a critical security gap in LLM serving through a confidential computing stack with CPU and GPU trusted execution environments (TEEs).

Key concepts

Oblivious Tokenization Architecture
This architecture uses a pool of independently permuted Square-Root ORAM instances. Because tokenizer tables are read-only during inference, OTRO avoids the expensive periodic rebuilds by having multiple instances serving requests simultaneously. This prevents an adversary from observing which specific vocabulary entries are being looked up.
Latency-aware ORAM Integration
OTRO partitions input into chunks and tokenizes them in parallel with GPU prefill. This chunked approach overlaps the tokenization work of one chunk with the rebuild phase of another. By carefully choosing chunk sizes, it minimizes observable overhead while maintaining identical logical token sequences to a single large input.
Access-count Padding
To hide detailed access patterns in the physical DRAM trace, OTRO pads each epoch with dummy accesses up to the square root of the table size (√N). This technique ensures that only aggregate access counts are visible, preventing adversaries from distinguishing between different vocabulary lookups or merge operations.

Terminology

Summary

The gist The CPU-side large language model (LLM) tokenizer is a critical security gap in LLM serving through a confidential computing stack with CPU and GPU trusted execution environments (TEEs).

How it works

OTRO provides an efficient, oblivious tokenization path tailored to latency-critical LLM serving, relying on square-root ORAM for fast single-access lookups while avoiding its prohibitive O(N log2 N) rebuild cost every √N accesses through three key innovations <ref:2606.17358#pg4>. First, OTRO provides a pool of replicated square-root ORAM instances that utilize the read-only nature of tokenizer table <ref:2606.17358#pg5>. Second, an epoch-based rotation policy decouples accesses from rebuilds and pads each epoch with dummy accesses to its boundaries, minimizing observable information <ref:2606.17358#pg6>. Lastly, chunked KV-cacheaware tokenization further overlaps rebuilds with GPU prefill and minimizes the instance count <ref:2606.17358#pg6>. Implemented as modules in HuggingFace Tokenizers and nano-vLLM, running within a TDX-enabled CVM with an NVIDIA H100 GPU, OTRO limits TTFT overhead to at most 4.5% <ref:2606.17358#pg6>.

Oblivious Tokenization Architecture

OTRO introduces a pool of read-only SqrtORAM instances with an epoch-based rotation strategy and access-count padding, leveraging the static nature of tokenizer tables to remove rebuilds from the critical path <ref:2606.17358#pg8>. The key observation is that the tokenizer tables are read-only structures during inference, which lets us circumvent the periodic rebuild overhead inherent to in SqrtORAM <ref:2606.17358#pg6>. OTRO maintains a pool of independently permuted SqrtORAM instances that hold the same vocab/merge data, so while one instance rebuilds asynchronously, other continues serving requests uninterrupted <ref:2606.17358#pg8>. Initialization involves constructing multiple independently permuted SqrtORAM instances by concatenating the vocab and merge table into a single flat array and generating P independent permutations using perinstance keys (ki, 0 ≤ i < P), instantiating P SqrtORAM structures each with a distinct random layout <ref:2606.17358#pg8>.

Latency-aware ORAM Integration

OTRO partitions the input prompt into multiple smaller chunks that are tokenized and fed into the LLM pipeline, and chunked tokenization works as a scheduling module that interleaves tokenization and prefill above nanovLLM’s existing KV-cache mechanisms <ref:2606.17358#pg8>. The chunking is strictly an internal scheduling mechanism occurring at pre-tokenization boundaries (i.e., whitespacedelimited words) and does not change the logical behavior of the tokenizer or the model, producing a token sequence bit-forbit identical to tokenizing the full input at once <ref:2606.17358#pg9>. Chunk size chunktok is chosen with explicit awareness of GPU utilization and ORAM rebuild time so that the prefill duration of the chunk overlaps with the rebuild phase of the next chunk <ref:2606.17358#pg10>.

Security Analysis and Leakage Reduction

The security goal of OTRO is to protect the table-dependent memory behavior of tokenization and detokenization, ensuring that even if an adversary can observe the CVM’s physical DRAM trace, they should learn nothing about which logical entries in the vocabulary table or merge table are accessed <ref:2606.17358#pg7>. The observable transcript consists of the sequence of physical DRAM accesses arising from i) tokenizer and detokenizer table lookups and ii) background rebuild operations <ref:2606.17358#pg10>. With access-count padding enabled, only the epoch count ⌈access count/√N⌉ is revealed, since dummy accesses fill each epoch to the √N boundary before rotation <ref:2606.17358#pg10>. The adversary therefore cannot observe per-word merge pass counts or distinguish vocab lookups from merge lookups; only the aggregate access count is visible <ref:2606.17358#pg10>.

Performance Evaluation

OTRO keeps TTFT overhead within 4.5% of the unprotected baseline while reducing the observable trace to prompt length alone, demonstrating that workloadaware ORAM integration is a viable path to end-to-end confidentiality in production LLM-serving stacks <ref:2606.17358#pg12>. Across our evaluation, OTRO increases TTFT by only 4.59% on average compared to the baseline <ref:2606.17358#pg12>. This small overhead leaves TTFT dominated by the model execution (91.41%) rather than tokenization (5.58%), so the cost of oblivious tokenization is modest in practice <ref:2606.17358#pg10>.

Memory Footprint and Initialization

OTRO requires an extra 285.9 MB for Llama-3.1 (48 instances), 46.0 MB for Qwen3 (17 instances), 333.0 MB for Gemma-3 (28 instances), and 30.5 MB for Phi-3 (26 instances) <ref:2606.17358#pg13>. Since OTRO instantiates an independent pool per client, the memory overhead scales linearly with the number of concurrent clients; at under 0.5 GB per client, a 256 GB CVM can support tens of concurrent clients without memory pressure <ref:2606.17358#pg13>. The initialization cost grows to ≈ 0.64 s (39.7% increase) for Llama-3.1 <ref:2606.17358#pg13>.

Detokenization Latency

The ORAM that protects the detokenization vocab table stores longer data blocks, since each token’s textual form is padded to the maximum vocabulary string length (e.g., Llama-3.1’s longest vocab entry is 256 B) <ref:2606.17358#pg11>. We do not observe any systematic impact on TTFT or decoding throughput attributable to detokenization ORAM <ref:2606.17358#pg12>. OTRO for detokenizer performs 23.10, 29.56, 33.55, and 21.38 ms/token for Llama-3.1, Qwen3, Gemma-3, and Phi-3 respectively <ref:2606.17358#pg12>.

Residual Leakage Quantification

OTRO with accesscount padding raises this residual uncertainty from 0 to 5.49 bits <ref:2606.17358#pg14>. In both configurations, OTRO replaces the fine-grained, per-token access pattern (which enables exact reconstruction) with coarse, length-correlated metadata <ref:2606.17358#pg14>. The residual identification risk for long prompts exists in any system that leaks input length, which every practical ORAM does, and is not a weakness introduced by OTRO <ref:2606.17358#pg14>.

Conclusion

OTRO removes this from the critical path in three steps: first, OTRO replicates the tables across a pool of independent SqrtORAM instances; second, an epoch-based rotation runs the rebuild of depleted instances asynchronously in the background while continuously serving incoming tokenizer requests from an available instance; and third, chunked tokenization interleaves the tokenization of prompt chunks with GPU prefill <ref:2606.17358#pg15>. Together, these techniques turn the bursty rebuild cost of SqrtORAM into background work that does not stall the serving pipeline <ref:2606.17358#pg10>. Our prototype on Llama-3.1, Qwen3, Gemma-3, and Phi-3 keeps TTFT overhead within 4.5% of the unprotected baseline while reducing the observable trace to prompt length alone <ref:2606.17358#pg12>. The paper concludes that workloadaware ORAM integration is a viable path to end-to-end confidentiality in production LLM-serving stacks >

--- Page 9 ---

The gist The CPU-side large language model (LLM) tokenizer is a critical security gap in LLM serving through a confidential computing stack with CPU and GPU trusted execution environments (TEEs).

Improvements for AI systems

  1. A robust defense against prompt reconstruction is achieved by deploying OTRO, which limits TTFT overhead to at most 4.5% while ensuring that tokenizer access patterns reveal nothing about which tokenizer entries are touched. This prevents an adversary from recovering the user prompt through address pattern leakage, a critical vulnerability in confidential LLM serving.

  2. The system can maintain high throughput for long-context models by employing chunked tokenization, which allows rebuilds to be overlapped with GPU prefill: Chunked tokenization effectively reduces the number of replicas by interleaving tokenization and GPU prefill. This ensures that the entire rebuild phase completes while the GPU is executing the prefill stage, mitigating latency stalls.

  3. The AI system gains improved privacy guarantees by ensuring that only the coarse epoch count is revealed through access-count padding, which replaces exact counts with a coarser measure, thus reducing residual leakage from 4.48 bits to 0.00 bits for short prompts under specific conditions.

Abstract

The CPU-side large language model (LLM) tokenizer is a critical security gap in LLM serving through a confidential computing stack with CPU and GPU trusted execution environments (TEEs). Tokenizers converts the prompts through table-driven lookups, and the resulting memory access patterns are a powerful source of side-channel leakage. Recent work demonstrates end-to-end recovery of user prompts from tokenizer access pattern on production Intel TDX. However, a drop-in use of the popular tree-based Oblivious RAMs (e.g., PathORAM) to prevent access-pattern leakage introduces about 13 times tokenizer slowdown, resulting in 10-58% higher time-to-first-token (TTFT). In this paper, we present OTRO, an efficient, oblivious tokenization path tailored to latency-critical LLM serving. OTRO relies on square-root ORAM for fast single-access lookups, but avoids its prohibitive O(N 2N) rebuild cost every sqrt N accesses through three key innovations. First, OTRO provides a pool of replicated square-root ORAM instances that utilize the read-only nature of tokenizer table. Second, an epoch-based rotation policy decouples accesses from rebuilds and pads each epoch with dummy accesses to its boundaries, minimizing observable information. Lastly, chunked KV-cache-aware tokenization further overlaps rebuilds with GPU prefill and minimizes the instance count. Implemented as modules in HuggingFace Tokenizers and nano-vLLM, running within a TDX-enabled CVM with an NVIDIA H100 GPU, OTRO limits TTFT overhead to at most 4.5%, keeps tokenizer-induced latency under 10% of total TTFT, and adds less than 0.5 GB of memory overhead while reducing the tokenizer's observable leakage across various model families and sizes.

Sources

Related papers