OTRO: Oblivious Tokenization Path with Square-Root ORAM

summary

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).

In short

OTRO addresses a security risk where CPU-side LLM tokenizers leak information in confidential computing environments. It introduces an oblivious path using Square-Root ORAM, employing replicated instances and epoch rotation to decouple slow rebuilds from fast serving. This ensures that observing the system only reveals prompt length, preserving confidentiality while maintaining minimal latency overhead.

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 used across episodes

Reinforcement Learning (RL) — explained in 24 episodes
Retrieval-Augmented Generation (RAG) — explained in 16 episodes
Interpretability — explained in 15 episodes
Sample Complexity — explained in 15 episodes
Federated Learning — explained in 14 episodes
Generalization — explained in 13 episodes

This episode discusses

The paper

OTRO: Oblivious Tokenization Path with Square-Root ORAM · Read on arXiv

University of Southern California

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.

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.

More episodes

← Home