Prompt Cache: Modular Attention Reuse for Low-Latency Inference

ArXiv: 2311.04934

🎯 Pitch

Prompt Cache slashes time-to-first-token by up to 70× by reusing precomputed attention states from common prompt modules like system messages, without changing model parameters—and LLMs don’t even need correct position IDs to use the cached data.

1. Executive Summary

This paper introduces Prompt Cache, an inference acceleration technique that reuses attention states across different LLM prompts by precomputing and storing the key-value states of frequently occurring text segments. The approach is evaluated on the LongBench suite using Llama2, MPT, and Falcon models, and employs a Prompt Markup Language (PML) to make reusable segments explicit as prompt modules—self-contained text units like system messages, documents, or templated instructions whose attention states are computed once and concatenated at inference time—along with an empirical finding that LLMs tolerate discontinuous position IDs when modules are assembled. On GPU-based inference with prompt modules stored in GPU memory, Prompt Cache reduces time-to-first-token latency by up to 10×; on CPUs, the reduction reaches up to 70×, with the latency advantage growing quadratically with sequence length while memory copy overhead grows only linearly. The approach preserves output accuracy within 2.5 percentage points of the baseline across all tested benchmarks, establishing that modular attention reuse is a viable acceleration strategy for long-context inference without modifying model parameters.

2. Context and Motivation

The Core Problem: Recomputing Attention States from Scratch for Every Prompt

The fundamental problem this paper addresses is the computational waste involved in serving large language models when different prompts contain identical text segments. Consider a typical LLM deployment: every time a user submits a query, the model processes the entire input sequence — including system messages, few-shot examples, template formatting, and provided context documents — from scratch. If a thousand users each ask the LLM questions that include the same 50-page legal document as context, the inference server performs the identical self-attention computation on those 50 pages one thousand times. This is the gap Prompt Cache aims to close.

The mechanism that makes this waste possible is the self-attention module at the heart of Transformer architectures. When processing an input sequence of length $n$, self-attention computes pairwise interactions between every token and every other token, yielding $O(n^2)$ computational complexity measured in FLOPs. Specifically, as the paper notes in Section 2.2, the prefill phase (processing the initial prompt before any tokens are generated) requires approximately $6nd^2 + 4n^2d$ FLOPs, where $d$ is the hidden dimension. For long-context prompts — legal documents, multi-page reports, extensive code repositories — this quadratic term dominates, and redoing it redundantly across prompts that share substantial content is a significant source of inefficiency.

This inefficiency exists even though the field has already adopted Key-Value (KV) Cache (Pope et al., 2022), the standard optimization for autoregressive generation. KV Cache eliminates intra-prompt redundancy: when generating tokens one-by-one during decoding, the attention states of previously generated tokens are cached and reused, so each new token only requires computing attention against the growing cache rather than the entire history. However, KV Cache is scoped to a single prompt. Once that prompt's generation completes, the cached states are discarded, and the next prompt — even if it shares 90% of its content with the previous one — starts computation from zero. Prompt Cache's insight is that this scoping is unnecessarily narrow: the attention states computed during one prompt's prefill phase have value for other prompts, if those states can be identified, stored, and correctly reassembled.

Why This Problem Matters: The Growing Dominance of Long-Context Inference

The problem of redundant prompt computation has become more acute for several converging reasons, which the paper discusses in its Introduction (Section 1):

Long-context applications are proliferating. The paper specifically calls out several domains where prompts routinely include large, overlapping documents:

• Legal analysis (Cui et al., 2023; Nay et al., 2023): attorneys querying LLMs about case law, contracts, or statutes, where the same legal corpus serves as context for many distinct questions.
• Healthcare (Steinberg et al., 2021; Rasmy et al., 2021): clinical decision support systems that include patient records, medical literature, or treatment guidelines as context, reused across different diagnostic queries.
• Education (Shen et al., 2021): tutoring systems that reference the same textbook chapters, problem sets, or curriculum materials across many student interactions.

In each of these domains, the input prompt is not just a short question — it includes one or more full documents that dominate the token count, and these documents are drawn from a fixed pool that is referenced repeatedly. A retrieval-augmented generation (RAG) system serving enterprise documents might embed the same company policy manual into hundreds of daily queries. Without cross-prompt reuse, the computational cost of these long-context applications is directly proportional to the number of queries, even though the bulk of each query's content is identical.

Prompt engineering has created reusable structural components. Beyond document context, the paper observes that the practice of prompt engineering itself introduces systematic reuse. Most deployed LLMs include a fixed "system message" that initializes the model's behavior — an instruction like "You are a helpful assistant that answers questions concisely" — prepended to every single prompt. Similarly, prompt templates (White et al., 2023) provide structured formats for specific tasks, and the paper notes these are "commonly used by LLM applications in robotics and tool learning" (Section 3.2.2), citing Driess et al. (2023) and Qin et al. (2023). A robotics LLM that translates natural language commands into robot actions might use the same template structure with only the specific command varying between prompts. The template text — which can be substantial in complex applications — is recomputed identically every time.

Inference latency directly impacts user experience. The paper frames its acceleration target as time-to-first-token (TTFT) — the duration between when a prompt is submitted and when the first output token appears. This is the phase where the entire prompt's attention computation occurs (the prefill phase). For long prompts, TTFT can dominate the user's perceived latency: waiting several seconds for the model to process a document before any response begins streaming is a poor experience, even if the subsequent token generation is fast. Prior work (Lew et al., 2018; Liu et al., 2023b) has established that response latency negatively affects user satisfaction in conversational systems, and the paper explicitly connects its TTFT reductions to this literature. Reducing TTFT from 900 ms to 90 ms, as Prompt Cache achieves in one configuration (Section 5.2.1), transforms the interaction from noticeably laggy to nearly instantaneous.

CPU and edge deployments magnify the problem. The paper evaluates on both GPUs and CPUs, and makes an important observation: "CPU inference benefits more significantly from Prompt Cache than GPU inference does" (Section 5.2.2). This is because attention computation is disproportionately expensive on CPUs — GPUs have massive parallelism for matrix operations, while CPUs must execute the $O(n^2d)$ attention computation sequentially. For resource-constrained environments such as edge devices or cloud servers without GPU access, prompt-level attention reuse is not just an optimization but a practical necessity for achieving interactive latency with long contexts. The paper's 70× CPU speedup on an Intel i9-13900K (Section 5.2.2) makes the difference between unusable multi-second delays and sub-second responses.

Memory bandwidth is a bottleneck, not just compute. The paper's architecture considers two memory tiers for storing cached attention states: GPU HBM (fast but limited, on the order of 40–80 GB) and CPU DRAM (slower but abundant, scaling to terabytes). This tiered storage model reflects the practical reality that attention state caching is constrained by memory capacity: Table 2 shows that a 1K-token document cached for Llama 70B requires 2.5 GB. Storing hundreds of such documents for a retrieval system would exceed GPU memory, forcing data movement from CPU to GPU. The paper's finding that even CPU-memory-stored modules (with host-to-device copy overhead) provide 1.5–3× speedups on GPUs (Figure 3) demonstrates that the computational savings from avoiding attention recomputation outweigh the memory copy penalty — but this is only true because the quadratic attention cost dwarfs the linear memory copy cost as sequence length grows (Figure 5). This insight connects the problem to the broader systems challenge of managing the memory-compute tradeoff in LLM serving.

Where Existing Approaches Fall Short

The paper identifies several prior strategies for accelerating LLM inference and explains why each is insufficient for the cross-prompt reuse problem.

KV Cache solves intra-prompt, not inter-prompt redundancy. As described in Section 2.2, KV Cache is the standard optimization for autoregressive generation: during decoding, the key and value tensors for all previously generated tokens are cached so that each new token's attention computation only needs to attend to the growing cache, not recompute from scratch. This reduces per-step FLOPs from $6nd^2 + 4n^2d$ to $6d^2 + 4nd$ — a dramatic improvement, especially as $n$ grows during generation. However, the paper explicitly notes the limitation: "KV Cache eliminates intra-prompt redundancy. Once that prompt's generation completes, the cached states are discarded." KV Cache provides no mechanism for sharing computed attention states between different prompts, even when those prompts have identical prefixes or shared segments. It is scoped to a single generation session.

Simple prefix sharing is insufficient for general reuse. The paper acknowledges that PagedAttention (Kwon et al., 2023) demonstrates "simple prefix sharing, where different prompts with an identical prefix share KV Cache." This works when multiple prompts share exactly the same beginning — for example, a common system message that appears at the start of every prompt. However, the paper argues this is too restrictive: "existing approaches are specific to certain scenarios, while we investigate attention reuse for general LLM prompts" (Section 2.2). In real-world prompts, shared segments can appear in any position — a document might be the second of three context documents, or a template might be followed by variable user input and then another shared module. Prefix-only sharing cannot handle these cases, and the paper's contribution is a framework that allows arbitrary-position reuse of modular, named text segments.

Embedding similarity-based reuse has limited applicability. The paper references AttMemo (Feng et al., 2023), which "reuse memorized attention states based on an embedding similarity metric." This approach identifies reusable KV states by comparing embedding vectors — if a new prompt's prefix has high embedding similarity to a previously cached prefix, the cached attention states can be reused. The paper does not criticize this work in detail but implicitly distinguishes Prompt Cache by its structural rather than similarity-based approach. Embedding similarity requires additional computation (computing and comparing embeddings) and introduces approximation error (a semantically similar but not identical prefix may not produce exactly correct attention states). In contrast, Prompt Cache's schema-based approach guarantees exact matching: a prompt module is either present (and its precomputed states can be reused exactly) or absent.

Attention state compression and pruning are orthogonal optimizations. The paper mentions two other lines of work: pruning superfluous KV cache data (Zhang et al., 2023) and compressing attention states (Liu et al., 2023b). These techniques reduce the memory footprint of cached states by discarding or approximating less important key-value pairs. The paper positions these as complementary rather than competing approaches: "compression methods for attention states remain an avenue for future research in prompt caching techniques" (Section 5.5). Prompt Cache's modular storage model is independent of whether individual prompt modules are stored at full precision or compressed — a compressed module still avoids recomputation costs.

General LLM serving systems do not address cross-prompt reuse. The paper notes that systems like DeepSpeed-Inference (Aminabadi et al., 2022) focus on multi-GPU parallelism, and FlashAttention (Dao et al., 2022) provides high-performance GPU kernels for attention computation, but both optimize the implementation efficiency of attention rather than eliminating redundant computation across prompts. Similarly, high-throughput serving systems like FlexGen (Sheng et al., 2023) optimize memory management and scheduling but do not introduce attention state reuse. Prompt Cache is described as "an orthogonal optimization strategy that augments existing systems" (Section 2.3).

How Prompt Cache Positions Itself Relative to These Limitations

The paper frames its contribution around two specific technical challenges that prior work did not solve, and which prevent naïve attention state reuse from working. Understanding these challenges is essential to understanding why Prompt Cache's approach is non-obvious and what makes it work.

Challenge 1: Positional encoding creates position-dependence. The paper states this directly in Section 3.1: "The attention states of a text segment can only be reused if the segment appears at the same position in the LLM input. This is because transformer architectures integrate unique positional embeddings into the (k, v) attention states." Every token in a Transformer receives a positional encoding — a vector that represents its absolute (or sometimes relative) position in the sequence — which is incorporated into the key and value computations. If the sentence "The patient reports chest pain" appears as tokens 100–104 in one prompt and as tokens 500–504 in another, the attention states will be different because the positional encodings differ, even though the token content is identical. This means raw text matching is insufficient for reuse: the states must be computed as if the text appears at a specific position, and then reassembled correctly.

Prompt Cache's solution to this is twofold. First, by defining prompt modules in a schema with fixed relative positions (Section 3.2.1), each module receives a predetermined starting position ID that is consistent across all prompts that import it. The paper explains: "The starting position ID is determined by the absolute location of the prompt module within the schema. For instance, if two preceding prompt modules have token sequence sizes of 50 and 60 respectively, the prompt module is assigned a starting position ID of 110" (Section 3.3). This means a module's attention states are computed exactly once, with correct positional encodings, and those encodings remain valid as long as the module appears in the same relative position within the schema-derived prompt.

Second, the paper leverages an empirical property it identifies: LLMs tolerate discontinuous position IDs. When prompt modules are concatenated from a schema, the position IDs jump — for example, a prompt might use modules at positions 0–100 and 200–300, with a "gap" for modules that were defined but not imported. The paper notes that "as long as the relative position of tokens is preserved, output quality is not affected" (Section 3.1). This is a critical enabler: without it, assembling a prompt from a subset of schema modules would be impossible because the position IDs would be inconsistent. The paper's accuracy results in Table 1 — showing that Prompt Cache preserves output quality within 2.5 percentage points across all tested benchmarks — provide empirical validation of this tolerance.

Challenge 2: Efficient recognition of reusable segments. Even if attention states could be reused in principle, a serving system needs to rapidly determine, for each incoming prompt, which segments match previously cached states. The paper frames this as a recognition problem: "The system must be able to efficiently recognize a text segment whose attention states may have been cached in order to reuse" (Section 3.1). String matching an arbitrary user prompt against a database of cached text segments is non-trivial — segments may appear in different positions, with slight variations (e.g., parameter substitutions), or in different combinations. Without a structured format, the system would need to run expensive similarity searches or substring matching for every prompt, which could negate the computational savings.

Prompt Cache's solution is the Prompt Markup Language (PML) — an explicit markup that makes reusable segments self-identifying. Instead of the system guessing which parts of a prompt are reusable, the prompt itself declares which modules it imports: <miami/> in the example in Figure 2 tells the system "use the cached attention states for the miami module." This shifts the burden of identifying reusable content from the inference server to the prompt author (or an automated compiler), and makes the recognition step essentially $O(1)$ — the system parses the PML tags and performs a direct cache lookup. The paper emphasizes that PML is not something users write manually for every query: "To simplify PML writing, Prompt Cache can automatically convert prompt programs from languages like Python into PML, eliminating the need for manual schema writing" (Section 3.2.4). This positions PML as an intermediate representation that can be generated from higher-level abstractions, much like how compilers generate machine code from source programs.

Challenge 3: Semantic independence and attention masking. An implicit challenge — one the paper discusses but does not frame as a distinct "challenge" in the same way as positional encoding — is that precomputing attention states for modules independently means the attention computation during encoding cannot attend across module boundaries. The paper characterizes this as an "attention masking effect" (Section 3.3): "Prompt Cache confines attention score computation to the span of each prompt module, masking the attention states across modules." This is an approximation relative to the baseline, where every token in the prompt attends to every other token (subject to causal masking). The paper acknowledges that this masking "can enhance or degrade output quality depending on the semantic independence of the modules." For modules that are truly independent (e.g., a system message and a user query about a different topic), masking prevents irrelevant cross-attention and may even improve quality. For modules with semantic dependencies (e.g., two paragraphs that reference each other), masking could hurt by preventing the model from establishing those connections.

This limitation motivates the scaffolding mechanism (Section 3.3): a set of prompt modules can be specified as a "scaffold" that is encoded together, sharing the attention span. When all modules in a scaffold are imported, the scaffold's joint attention states override the individual module states. This trades additional memory (storing both individual and scaffold states) for output consistency. The paper's accuracy benchmarks (Table 1) do not use scaffolding, demonstrating that for the evaluated tasks (document-based QA and summarization), the modules are sufficiently independent that masking has negligible impact on quality. However, the paper's acknowledgment of this limitation is important: Prompt Cache is not claiming that arbitrary text segmentation works without quality loss — it works when modules are chosen to be reasonably self-contained, and scaffolding provides a fallback for cases where they are not.

Positioning Summary: An Inference-Time Optimization with No Model Modification

The paper situates Prompt Cache within the broad space of LLM inference optimization, but distinguishes it through two key properties:

First, Prompt Cache operates entirely at the inference serving layer — it does not modify model weights, architecture, or training. This stands in contrast to approaches that train smaller models for faster inference (distillation, pruning, quantization) or modify attention mechanisms for efficiency (sparse attention, linear attention approximations). The paper states this explicitly in the abstract: "without the need for model parameter modifications." This is significant because it means Prompt Cache can be applied to any existing deployed model — including fine-tuned variants, domain-specialized models, and proprietary models available only through APIs (if the API exposes KV cache access) — without retraining or architecture changes. The only requirement is compatibility with KV Cache and support for discontinuous position IDs, which the paper shows requires minimal code changes ("approximately 20 lines of additional code are needed for each LLM," Section 4.2).

Second, Prompt Cache's gains are complementary to, not competitive with, other inference optimizations. The paper explicitly notes that it can work alongside FlashAttention (for efficient attention kernels), PagedAttention (for memory management and prefix sharing), multi-GPU serving systems, and KV cache compression techniques. The latency improvements reported in the evaluation (Figures 3 and 4) are additional to whatever baseline optimizations are already present in the HuggingFace Transformers inference pipeline. This modular compatibility is practically important because deploying Prompt Cache does not require abandoning existing inference infrastructure — it layers on top.

The paper's vision, stated in the conclusion, is that Prompt Cache serves "as a foundational component for future LLM serving systems" (Section 6), with enhanced cache management, replacement policies, and GPU memory optimization built around it. This positions the work not as a complete serving system but as an enabling mechanism that future systems can incorporate — analogous to how KV Cache itself became a standard component of virtually all LLM inference implementations.

3. Technical Approach

3.1 Reader Orientation

Prompt Cache is an inference-serving middleware that acts like a reusable attention-state library: before answering user questions, the system precomputes the internal "understanding" (key-value tensors) of common text blocks such as system messages, document passages, and prompt templates, stores them in memory, and when a user's prompt imports those blocks, the system stitches the precomputed understanding together with fresh computation only for the new, uncached parts—eliminating the $O(n^2)$ attention recomputation for content that has already been processed. The problem it solves is the cross-prompt redundancy in LLM serving where identical text segments (system prompts, shared documents, templated instructions) are processed from scratch hundreds or thousands of times across different user queries, and the shape of the solution is a schema-directed modular cache where attention states are computed exactly once per module with correct positional encodings and then assembled via concatenation at inference time, trading a linear memory copy cost for the quadratic compute cost of self-attention.

3.2 Big-Picture Architecture (Diagram in Words)

The Prompt Cache system has five major components connected in a feedforward pipeline:

1. Schema Parser and PML Compiler — Reads a schema definition written in Prompt Markup Language (PML) that declares which text segments are reusable. Extracts token sequences for each declared prompt module, assigns them fixed position IDs based on their layout in the schema, and manages parameter placeholders. This component is invoked once when a schema is loaded, not per-query.

2. Module Encoder — Takes token sequences and assigned position IDs from the schema parser and runs the LLM's prefill (full self-attention) over each prompt module independently, producing $(k, v)$ attention states. For parameterized modules, it substitutes <unk> tokens for parameter slots. These encoded states are stored in either GPU HBM or CPU DRAM, keyed by module name. This component runs offline when schemas are registered.

3. Prompt Parser — Receives an incoming user prompt (also written in PML, referencing a schema), validates that imported modules exist in the claimed schema, extracts the list of imported modules, and separates uncached text segments (new instructions, parameter arguments, text not in the schema) from cached module references. This component runs on every query.

4. Cache Retriever and Assembler — Fetches precomputed $(k, v)$ tensors for all imported modules from the memory store (GPU or CPU). If modules are stored in CPU memory and inference runs on GPU, this performs host-to-device memory copy. Concatenates the retrieved tensors into a single KV Cache using a buffered concatenation operator (to avoid redundant memory allocation). For parameterized modules, retrieves the $(k, v)$ states and identifies the position IDs of <unk> slots that need replacement.

5. Attention Computer (Uncached Segments) — Takes the concatenated KV Cache from the assembler as a pre-existing cache. Computes attention states from scratch only for uncached text segments (new user instructions, parameter argument tokens inserted into <unk> slots). This computation uses the concatenated cache so that uncached tokens can attend to cached module content. The output is the complete attention state for the entire prompt, after which standard autoregressive decoding proceeds identically to baseline KV Cache.

Information flows sequentially: schema definition → module encoding → prompt submission → module retrieval and concatenation → uncached attention computation → standard decoding. The critical property is that steps 1–2 happen once per schema (amortized across all prompts using that schema), while steps 3–5 happen per prompt but with computation proportional only to uncached content.

3.3 Roadmap for the Deep Dive

• First, the Prompt Markup Language (PML) itself — its syntax, how schemas and prompts are structured, how modules, parameters, unions, and nested modules model different kinds of reuse — because PML is the interface that makes modular reuse possible and defines the vocabulary through which all caching decisions are expressed.
• Second, the module encoding process — how token sequences are extracted, how position IDs are assigned (and why discontinuous IDs are critical), how parameterized modules handle <unk> substitution, and what the attention masking effect means — because encoding determines what exactly gets stored and how the LLM "sees" modules when they are assembled.
• Third, the cached inference procedure — the step-by-step process when a prompt arrives (parsing, cache retrieval, concatenation, uncached attention computation) — because this is where the latency savings are realized.
• Fourth, the implementation details for adapting Transformer architectures to discontinuous position IDs — the concrete code changes needed for RoPE, ALiBi, and embedding table-based position encoding, plus the buffered concatenation optimization — because these show that Prompt Cache works with existing models with minimal modification.
• Fifth, the scaffolding mechanism — the optional technique for encoding groups of modules together to preserve cross-module attention — because it represents the accuracy/performance tradeoff that Prompt Cache's masking introduces and how to recover full attention when needed.
• Sixth, the memory optimization strategy for batch inference — how Prompt Cache can reduce KV Cache redundancy in batched serving via pointer sharing — because it extends the benefit from latency reduction to throughput improvement.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a systems design paper whose core idea is that attention states of frequently reused text segments can be precomputed and concatenated at inference time, provided the segments are defined in a schema that fixes their positional encoding and the model tolerates discontinuous position IDs.

The Prompt Markup Language (PML): Making Reusable Segments Explicit

Framing and motivation. The central insight of Prompt Cache is that cross-prompt attention reuse is only practical if the system can efficiently identify which parts of an incoming prompt match previously cached states, and if those cached states have been computed with consistent positional encodings. PML solves both problems simultaneously: it makes reusable segments self-identifying through explicit markup tags, and it assigns fixed position IDs to each module within a schema so that encoding is positionally consistent across all prompts derived from that schema. The alternative — trying to retroactively discover reusable segments through string matching or embedding similarity — would incur computational overhead that could negate the latency savings of reuse itself.

Schema vs. prompt distinction. PML defines two document types:

• A schema (tagged with <schema name="...">) is a template that declares all possible prompt modules, their relative positions, and their hierarchical relationships. It serves as a contract: modules are defined here with fixed position IDs, and all prompts that reference this schema can import any subset of its modules knowing their attention states will be positionally consistent. Text in a schema that is not enclosed in <module> tags is treated as an anonymous module — always included in every prompt derived from that schema.

• A prompt (tagged with <prompt schema="...">) is a concrete instance that imports specific modules from a schema via self-closing tags (e.g., <miami/>) and adds uncached text (new instructions, questions, arguments to parameters). The prompt explicitly declares which modules it uses, making cache lookup an $O(1)$ tag-parsing operation rather than an $O(n)$ string matching problem.

Module definition and position ID assignment. A module in the schema is defined with <module name="..."> ... </module>. The text inside is tokenized by the target LLM's tokenizer, and the number of tokens determines the module's length. The starting position ID of each module is determined by the sum of token lengths of all preceding modules (including anonymous modules and sibling modules) in the schema's document order:

If two preceding prompt modules have token sequence sizes of 50 and 60 respectively, the prompt module is assigned a starting position ID of 110 (Section 3.3).

This means the position IDs are deterministic given the schema. Every prompt that imports module miami from the schema in Figure 2 will retrieve attention states computed with the same starting position ID, because miami always appears at the same logical offset within the schema layout. This is the mechanism that makes cross-prompt positional consistency possible.

Parameters: maximizing reuse through placeholder inlining. A parameterized module uses the <param> tag with two attributes:

• name: a string identifier for the parameter
• len: the maximum number of tokens that the argument can occupy

Within the module's text, the parameter appears as a named placeholder. When encoding the schema, Prompt Cache replaces the parameter with exactly len copies of the <unk> token (the model's unknown-token embedding), and records the position IDs of these <unk> tokens. When a prompt imports the module and supplies an argument (e.g., <trip-plan duration="3 days"/>), the system tokenizes the argument ("3 days"), assigns those tokens the position IDs that were reserved for the <unk> placeholders, computes attention states for only those argument tokens, and substitutes the resulting $(k, v)$ tensors into the precomputed module's KV Cache at the correct positions.

Two subtle design choices matter here:

1. The argument can be shorter than len. The paper notes that "trailing white spaces do not change the semantics" (Section 3.3), so the system pads the argument tokens with whitespace-equivalent positions up to len. This means the len attribute is an upper bound, not an exact required length, providing flexibility for short arguments.

2. Parameters serve double duty as "buffers." Beyond direct argument substitution, the paper notes that "a parameter can be used to create a 'buffer' at the beginning or end of a prompt module" (Section 3.2.2). This buffer allows users to insert completely arbitrary text into a positionally-fixed module without needing to define that text in the schema. It is effectively a "cutout" in the otherwise positionally-fixed schema layout where dynamic content can be placed.

Union modules: modeling mutual exclusion. The <union> tag groups modules that are mutually exclusive — in any given prompt, at most one module from the union can be imported. All modules within a union share the same starting position ID, and the union reserves the space for the largest child module (in token count). This has two practical benefits:

1. Position ID conservation. Instead of assigning unique non-overlapping position IDs to every possible module variant (which would consume the model's maximum context length more quickly), mutually exclusive options share the same position space. For a retrieval system with hundreds of documents, where each prompt includes only one document, a union allows all documents to be positionally equivalent without allocating unique position ranges to each.

2. System-level optimization hints. The paper notes that "the system can utilize this structure for optimizations, such as prefetching" (Section 3.2.3). If the system knows that documents A, B, and C are in a union and that a particular user session tends to request documents from this set, it can prefetch all three from CPU to GPU memory in anticipation.

Nested modules: hierarchical composition. PML supports nesting: a module can contain other modules or union groups as children, expressed as <module name="..."><child_module_name/></module>. This maps naturally to hierarchical prompts — for example, a "travel-plan" module might contain nested "destination" and "activities" modules. The position ID assignment respects the nesting hierarchy: child modules' position IDs are computed relative to their parent's starting position.

LLM-specific template compatibility. The paper introduces three dedicated tags — <system>, <user>, and <assistant> — that abstract away LLM-specific chat formatting. Different instruction-tuned models use different special tokens and formatting conventions (e.g., Llama2 uses [INST] and [/INST] delimiters). Prompt Cache dynamically translates these abstract tags into the target model's concrete template at compilation time, so a single PML schema can target multiple model architectures without modification.

Python-to-PML compilation. The paper provides a compiler that converts prompt programs written in Python (using frameworks like Guidance or LMQL) into PML schemas automatically. The mapping is straightforward:

• if statements → <module> tags (the conditional body becomes a named module)
• if-else or switch statements → <union> tags (branches become mutually exclusive modules)
• Function calls → nested modules (the function's template becomes a module with parameter slots for arguments)
• A decorator for parameter length constraints → the len attribute in <param>

This compilation step means that application developers can write prompts in familiar Python control flow without manually crafting PML — the schema serves as an intermediate representation, analogous to how compilers translate high-level languages into lower-level representations before optimization.

Module Encoding: Computing and Storing Attention States

Token sequence extraction. For each module defined in a schema, Prompt Cache tokenizes the text using the target LLM's tokenizer, producing a sequence of token IDs $t_1, \ldots, t_m$ where $m$ is the module's token length. For parameterized modules, parameter placeholders in the text are replaced with the <unk> token ID, repeated len times (where len is the parameter's declared maximum token length).

Position ID assignment. The starting position of a module is the sum of token counts of all preceding sibling modules and anonymous text in the schema, computed in document order. Formally, if modules $M_1, M_2, \ldots, M_k$ appear in order, and each $M_i$ has token length $\ell_i$, then $M_j$ receives starting position ID:

$p_j = \sum_{i=1}^{j-1} \ell_i$

where $p_j$ is the starting position ID of module $j$, $\ell_i$ is the token length of module $i$, and the anonymous text (if any) preceding all modules is treated as module $M_0$ with length $\ell_0$.

What it computes: a deterministic, schema-wide position mapping where every token in every module receives a unique position ID (except for union children that share position ranges). This mapping is computed once when the schema is loaded and reused for all prompts derived from the schema.

Why this form: the position IDs are derived from the schema's layout, not from any individual prompt's composition. This is the critical design choice that enables cross-prompt reuse — if position IDs were computed relative to each prompt's particular selection of modules, the same module would have different encodings in different prompts, preventing reuse. By fixing positions in the schema, each module always has the same position IDs regardless of which other modules are or are not imported alongside it.

Discontinuous position IDs. When a prompt imports only a subset of schema modules, the assembled token sequence will have "gaps" in position IDs — positions corresponding to unimported modules are skipped. For example, if a schema defines modules A (positions 0–49), B (50–99), and C (100–149), and a prompt imports only A and C, the assembled sequence has tokens at positions 0–49 and 100–149, with a gap of 50–99. The paper identifies this as a key enabling property: "LLMs can operate on attention states with discontinuous position IDs" (Section 3.1), and that "as long as the relative position of tokens is preserved, output quality is not affected." This property is not guaranteed by standard Transformer implementations — the paper explicitly adapts positional encoding mechanisms to support it (Section 4.2) — but the empirical finding (validated in Table 1) is that models tolerate these discontinuities without accuracy degradation.

Attention computation with masking. When encoding a module, the LLM's self-attention is computed only over that module's tokens — attention is not computed across module boundaries. The paper describes this as an "attention masking effect" (Section 3.3):

Prompt Cache confines attention score computation to the span of each prompt module, masking the attention states across modules.

This means that during encoding, each token in a module can attend to every other token in that same module, but cannot attend to tokens in other modules. This is an approximation relative to the baseline (where every token attends to every preceding token in the full prompt), and it has the same effect as the locally-masked attention used in architectures like Longformer (Beltagy et al., 2020). The paper explicitly draws this connection: "the approximation made by Prompt Cache is to limit the attention window to each prompt module," and notes that "employing such attention masks does not necessarily reduce output quality" — it can even "introduce beneficial inductive biases by effectively filtering out irrelevant information."

Parameter handling during encoding. For parameterized modules, the <unk> tokens inserted during encoding are treated as regular tokens — they receive position IDs, and the LLM computes attention states for them as if they were content tokens. The resulting $(k, v)$ tensors for <unk> positions are stored along with the module's other attention states. When a prompt later provides an argument, these placeholder states are replaced by freshly computed states for the actual argument tokens, which use the same position IDs. This two-phase approach — encode with placeholders, replace at inference — ensures that the rest of the module's attention states (tokens surrounding the parameter) are computed correctly with respect to the expected position structure, even though the exact argument text is unknown at encoding time.

Storage format and memory placement. Encoded modules are stored as pairs of tensors $(K, V)$ where $K \in \mathbb{R}^{h \times n \times d_k}$ and $V \in \mathbb{R}^{h \times n \times d_v}$, with $h$ being the number of attention heads, $n$ the token length of the module, $d_k$ the key dimension per head, and $d_v$ the value dimension per head. The paper uses 16-bit floating point precision for storage to balance memory footprint and numerical accuracy. These tensors are stored in either CPU memory (host DRAM) or GPU memory (HBM), managed by the PyTorch memory allocator. When stored on CPU and accessed by GPU inference, the tensors are copied via host-to-device memory transfer — a linear-time operation that the paper shows is substantially cheaper than the quadratic attention computation it replaces (Figure 5).

Scaffolding: encoding modules jointly. The scaffolding mechanism provides an escape hatch from the independent-encoding limitation. A schema can declare a "scaffold" — a named group of modules that are encoded together in a single attention computation. Formally, if modules A, B, and C are in a scaffold S, Prompt Cache stores both the individual encodings (A alone, B alone, C alone) and the joint encoding (A+B+C together). At inference time, if a prompt imports all three modules, the joint encoding is used instead of concatenating the individual encodings. This means the attention states for these modules were computed with full cross-module attention — every token in A, B, and C can attend to every other token. The paper positions this as a memory-accuracy tradeoff: "Scaffolding trades off additional memory for output consistency, which may be useful for applications that need deterministic results" (Section 3.3).

Key design rationale. The encoding strategy reflects three deliberate choices:

1. Encode once, reuse many times. The cost of encoding (running self-attention over a module) is paid exactly once per module, regardless of how many prompts import it. For a document that appears in thousands of queries, the encoding cost is fully amortized.

2. Schema-relative positions, not prompt-relative positions. By fixing positions in the schema rather than dynamically assigning them per prompt, the system guarantees that a module's encoded states are always valid when that module is imported — no recomputation and no position translation. This is what makes the discontinuous position ID property necessary: different prompts import different subsets, creating gaps.

3. Independent encoding as the default, with scaffolding as a fallback. The default assumes modules are semantically independent enough that masking cross-module attention does not harm accuracy. The paper's Table 1 results validate this for document-based QA and summarization tasks. When independence does not hold, scaffolding provides a paid-for correctness guarantee — extra memory for extra attention context.

Cached Inference: Assembling Attention States at Query Time

Step-by-step inference pipeline. When a prompt arrives, Prompt Cache executes a five-stage assembly process (detailed in Section 3.4):

Stage 1: Prompt parsing and validation. The system parses the PML prompt to extract:

• The schema identifier (from the schema attribute of <prompt>)
• The list of imported modules (from self-closing tags like <miami/>)
• Parameter arguments (from attributes on imported parameterized modules)
• Uncached text segments (text outside any module tags, including new instructions at the end and text inserted into parameter slots)

The system validates that all imported modules exist in the referenced schema and that argument token lengths do not exceed declared parameter sizes.

Stage 2: Module KV cache retrieval. For each imported module, the system retrieves the precomputed $(K, V)$ tensors from the memory store. If modules are on CPU memory and inference runs on GPU, this triggers host-to-device memory copy. If modules are already on GPU memory, this is essentially a pointer dereference. The system also resolves unions: if a union child module is imported (e.g., <miami/> from a union of tokyo, miami, paris), the retrieval uses the union's shared position range rather than an individually assigned range.

Stage 3: Concatenation of cached states. The retrieved $(K, V)$ tensors for all imported modules are concatenated along the sequence-length dimension to form a combined KV Cache $(\tilde{K}, \tilde{V})$:

$\tilde{K} = \text{concat}(K_{A}, K_{B}, \ldots, K_{Z})$ $\tilde{V} = \text{concat}(V_{A}, V_{B}, \ldots, V_{Z})$

where $(K_A, V_A)$ through $(K_Z, V_Z)$ are the retrieved tensors for imported modules A through Z, and $\text{concat}$ concatenates along the sequence-length axis. The paper notes that "the order of concatenation does not matter due to the permutation invariance of transformers" (Section 3.4), since the position IDs embedded in the tensors encode absolute position independently of concatenation order.

Why concatenation works despite permutation invariance. The concatenation order is irrelevant because each $(k, v)$ pair carries its own positional encoding that was embedded during module encoding. When the model later uses this combined cache for attention computation, it computes attention scores based on query-key dot products that incorporate these positional encodings — the absolute positions are "baked into" the keys, so the model automatically attends to tokens at the correct positions regardless of how the tensors were concatenated in memory. This is a subtle but important property: it means the assembly step does not need to maintain any ordering invariant beyond ensuring that all tokens are present in the cache.

Stage 4: Computing uncached attention states. The remaining work is computing attention states from scratch for the prompt's uncached content:

• New text segments (instructions written directly in the prompt, not in any module)
• Parameter arguments (token sequences that fill <unk> placeholders)

The system identifies the position IDs for these uncached segments. For new text at the end of the prompt, the position IDs start from the next available position after all schema modules. For parameter arguments, the position IDs are exactly those that were reserved for <unk> tokens during module encoding. The system then passes the uncached token sequences, their position IDs, and the combined cache $(\tilde{K}, \tilde{V})$ to the LLM, which computes:

$k_{\text{new}} = W_k \cdot x_{\text{new}} + \text{pos\_enc}(p_{\text{new}})$ $v_{\text{new}} = W_v \cdot x_{\text{new}}$

where $x_{\text{new}}$ is the token embedding, $W_k$ and $W_v$ are the key and value projection matrices, $\text{pos\_enc}(p_{\text{new}})$ is the positional encoding for the assigned position ID $p_{\text{new}}$, and the attention computation uses $(\tilde{K}, \tilde{V})$ as the existing key-value cache so that new tokens attend to both cached and other new tokens. The resulting $(k_{\text{new}}, v_{\text{new}})$ tensors are appended to $(\tilde{K}, \tilde{V})$.

Stage 5: Standard autoregressive decoding. Once the full prompt's attention states are assembled, the system proceeds identically to baseline KV Cache decoding. For each generated token $t_{n+1}, t_{n+2}, \ldots$, the model computes attention using the growing cache and appends the new token's $(k, v)$ states. The paper emphasizes: "It is important to note that the computational complexity for generating subsequent tokens remains consistent with that of KV Cache, as prompt modules are not employed beyond the initial token" (Section 3.4). Prompt Cache only accelerates the prefill (time-to-first-token), not the per-token decoding.

Computational complexity analysis. The latency benefit of Prompt Cache over baseline KV Cache comes from replacing $O(n^2d)$ attention computation with $O(c)$ memory copy, where $n$ is the total prompt length and $c$ is the length of cached content. For a prompt with $c$ cached tokens and $u$ uncached tokens ($n = c + u$), the baseline prefill requires computing attention for all $n$ tokens, which costs approximately $6nd^2 + 4n^2d$ FLOPs. Prompt Cache prefill computes attention only for $u$ uncached tokens, costing $6ud^2 + 4u^2d + 4ucd$ FLOPs (where the $4ucd$ term comes from the uncached tokens attending to the cached keys), plus the memory copy cost for $c$ cached tokens' $(K, V)$ tensors. The memory copy cost is linear in $c$ (specifically, proportional to $2 \cdot c \cdot h \cdot d \cdot \text{bytes\_per\_element}$) while the attention computation it replaces is quadratic in $n$. As $c$ grows large, the savings dominate.

Handling parameters at inference time. For a parameterized module imported with an argument (e.g., <trip-plan duration="3 days"/>), the inference procedure incorporates two additional substeps during Stage 4:

1. Tokenization and length checking. The argument "3 days" is tokenized by the LLM's tokenizer. If the token count is less than the parameter's declared len, the system pads with whitespace-equivalent tokens up to len. If it exceeds len, this is a validation error (the schema enforces the upper bound).

2. Position ID substitution and attention computation. The argument tokens are assigned the position IDs that were reserved for the parameter's <unk> slots during encoding. The LLM computes $(k, v)$ states for these tokens, using the module's other cached states as the KV Cache so the argument tokens attend to surrounding module content (and vice versa). The resulting $(k, v)$ tensors replace the $(k, v)$ tensors that were originally stored for those position IDs from the <unk> encoding. The surrounding module states (tokens before and after the parameter) remain unchanged from their cached versions, because they were encoded with <unk> placeholders at those positions and the new argument tokens occupy the same positions.

Memory optimization in batch inference (Section 3.4, second paragraph). The paper identifies an additional optimization opportunity when serving multiple prompts in a batch. If several prompts derive from the same schema and import overlapping modules (e.g., all prompts share a common system message module), the system can share the cached KV tensors across prompts rather than duplicating them. Using PagedAttention (Kwon et al., 2023), this can be implemented as shared pointers: each prompt's KV cache entry for the shared module is a pointer to the same physical memory block. The benefit is twofold: reduced memory footprint per prompt (allowing larger batch sizes) and elimination of the memory copy for shared modules within a batch. The paper positions this as a throughput benefit: "Prompt Cache can implicitly improve system throughput by allowing more prompts to be processed in parallel" (Section 3.4).

Why Prompt Cache only accelerates TTFT, not per-token decoding. The paper is explicit about this scope limitation: "Prompt Cache diminishes the latency involved in producing the first token, or time-to-first-token (TTFT)" (Section 3.4). During decoding, each new token must attend to the full prompt plus all previously generated tokens — the prompt's cached states are already in the KV Cache regardless of whether Prompt Cache or baseline KV Cache was used for prefill. The per-token computation is $O((n + t) \cdot d)$ for both methods, where $t$ is the number of tokens generated so far. The benefit is concentrated entirely in the prefill phase, where baseline KV Cache does $O(n^2)$ work on every prompt while Prompt Cache does $O(u^2 + uc)$ work amortized over the cached modules. For a prompt where 80% of tokens are cached, this reduces prefill FLOPs by approximately 96% (since prefill cost scales with $n^2$, and $0.2^2 = 0.04$).

Adapting Transformer Architectures for Discontinuous Position IDs

Why adaptation is necessary. Standard Transformer position encoding implementations assume position IDs form a contiguous sequence 0, 1, 2, ..., $n-1$. Prompt Cache's modular assembly produces position IDs with gaps — modules are encoded at their schema-relative positions, and unimported modules leave position ranges unused. The paper adapts three positional encoding mechanisms to handle these discontinuities (Section 4.2).

Embedding table-based encoding (BERT, GPT-2). Early models use learned or fixed embedding tables where position ID $p$ maps to a vector $\text{pos\_enc}[p]$. These require no modification for Prompt Cache — the system simply looks up position ID 110 directly in the table even if positions 100–109 are unused. "No alterations" are needed (Section 4.2).

Rotary Position Embedding (RoPE) — Llama2, Falcon, CodeLlama. RoPE (Su et al., 2021) encodes position by rotating query and key vectors by an angle proportional to the position index. For token at position $p$ and dimension pair $(2i, 2i+1)$ in the attention head, the rotation is:

$\begin{bmatrix} q_{2i} \\ q_{2i+1} \end{bmatrix} \leftarrow \begin{bmatrix} \cos(p \cdot \theta_i) & -\sin(p \cdot \theta_i) \\ \sin(p \cdot \theta_i) & \cos(p \cdot \theta_i) \end{bmatrix} \begin{bmatrix} q_{2i} \\ q_{2i+1} \end{bmatrix}$

where $\theta_i = 10000^{-2i/d}$ is the base frequency for dimension pair $i$, $d$ is the head dimension, and $p$ is the absolute position.

The standard implementation computes rotation matrices on-the-fly assuming contiguous $p = 0, 1, 2, \ldots$. For Prompt Cache's discontinuous positions, the paper creates a lookup table of precomputed rotation matrices indexed by position ID:

We create a lookup table for each rotation matrix, enabling retrieval based on position IDs. (Section 4.2)

This means the system can request the rotation for position 110 without having computed rotations for positions 100–109. The memory overhead is storing one $d \times d$ rotation matrix per possible position (up to the model's maximum context length), which is negligible relative to KV cache memory.

Attention with Linear Biases (ALiBi) — MPT, BLOOM. ALiBi (Press et al., 2022) adds a static, non-learned bias to attention scores before softmax. For query at position $i$ attending to key at position $j$, the bias is:

$\text{bias}(i, j) = -m \cdot |i - j|$

where $m$ is a head-specific slope (geometrically spaced across heads). The bias penalizes attention between distant positions linearly.

For Prompt Cache's discontinuous positions, the absolute distance $|i - j|$ would be inflated by position gaps — two tokens that are semantically adjacent but separated by a gap of unimported modules would appear artificially "distant" to ALiBi. The paper addresses this by creating a lookup table that maps position ID pairs to the correct bias:

We design a lookup table to adjust the bias matrix according to the provided position IDs. (Section 4.2)

The exact adjustment is not specified in detail in the paper, but the implication is that the bias is computed relative to the logical token distances in the assembled prompt rather than the raw position ID differences, preserving the linear-bias property that ALiBi relies on for length extrapolation.

Buffered concatenation optimization. Beyond positional encoding adaptations, the paper implements an optimization for the concatenation operation that assembles module KV tensors. PyTorch's default concat operator allocates new memory for the resulting contiguous tensor, even if the inputs are already in memory. Since Prompt Cache concatenates the same module tensors thousands of times across different prompts, this would cause excessive memory allocation/deallocation overhead. The paper implements "a buffered concatenation operator that reuses memory when concatenating tensors" (Section 4.2). This operator pre-allocates a buffer sized for the maximum expected concatenated tensor and reuses it across prompts, avoiding repeated GPU memory allocations.

Code complexity. The paper quantifies the implementation burden as "approximately 20 lines of additional code are needed for each LLM" (Section 4.2). This small footprint is significant because it means Prompt Cache can be integrated into existing inference pipelines with minimal engineering effort — the adaptation is confined to the positional encoding module of the Transformer implementation and does not require modifying attention computation, layer structure, or model weights.

Scaffolding: Recovering Cross-Module Attention When Needed

The problem scaffolding solves. The default Prompt Cache encoding computes attention independently for each module, masking cross-module attention. For most of the document-based QA and summarization tasks in LongBench, the paper shows this has negligible accuracy impact (Table 1). However, when modules have strong semantic dependencies — for instance, if module A describes a person and module B describes an event involving that person, and the prompt asks about the relationship — masking could prevent the model from connecting information across modules.

Scaffolding mechanism. A scaffold is declared in the schema as a named group of modules:

<scaffold name="person-event">
  <module name="person-desc"> ... </module>
  <module name="event-desc"> ... </module>
</scaffold>

During encoding, Prompt Cache computes attention states for the scaffold as a single unit: the modules' tokens are concatenated with contiguous position IDs, and full self-attention is computed across all tokens. This produces a joint $(K_{\text{scaffold}}, V_{\text{scaffold}})$ tensor. The individual modules $(K_A, V_A)$ and $(K_B, V_B)$ are also stored separately, so modules can still be imported individually (without cross-attention) when the scaffold's full context is not needed.

At inference time, the prompt imports the scaffold rather than individual modules:

<prompt schema="...">
  <scaffold name="person-event"/>
  <user>What is the relationship between the person and the event?</user>
</prompt>

The system retrieves the joint tensor $(K_{\text{scaffold}}, V_{\text{scaffold}})$ instead of concatenating individual module tensors. This is a simple substitution in the cache retrieval step — the rest of the inference pipeline is unchanged.

Memory tradeoff. Scaffolding stores $1 + m$ entries for a scaffold of $m$ modules: one joint encoding and $m$ individual encodings. The paper characterizes this explicitly as a tradeoff: "Scaffolding trades off additional memory for output consistency" (Section 3.3). For a scaffold of two 500-token modules in Llama 7B, this adds approximately 500 MB of additional storage (one joint encoding of 1000 tokens at 0.5 MB/token from Table 2). The paper positions scaffolding as an opt-in mechanism for applications where cross-module attention is critical and memory is available.

Batch Inference Memory Optimization

The redundancy opportunity. When serving multiple prompts in a batch, if those prompts derive from the same schema and import overlapping modules, the system would naïvely store duplicate copies of the same module's KV tensors across prompts. For example, if all 32 prompts in a batch share the same 1000-token system message module, a naïve implementation would store 32 × 500 MB = 16 GB of redundant KV cache for Llama 7B.

Pointer-based sharing. The paper proposes using PagedAttention's virtual memory abstraction to eliminate this redundancy. Each prompt maintains a page table mapping logical KV cache positions to physical GPU memory blocks. For shared modules, multiple prompts' page tables map the same logical range to the same physical memory blocks — effectively sharing a pointer to the module's cached tensors. The paper notes:

Paged attention can resolve this issue by sharing the pointer to the same prompt module across different prompts, instead of duplicating the attention states. (Section 3.4)

This optimization does not require changes to Prompt Cache's encoding or inference procedures — it is purely a memory management optimization at the serving system level.

Throughput improvement. The paper claims that this optimization "can improve overall throughput by utilizing the larger batch size enabled by the reduced memory footprint" (Section 5.4). For a concrete example: if 100 requests each have a 2K-token prompt and all share a 1K-token module, the naive memory requirement is 100 × 2K tokens' worth of KV cache. With pointer sharing, it drops to 100 × 1K + 1 × 1K tokens' worth of cache — a 50% reduction. This frees GPU memory for larger batch sizes, which improves GPU utilization and overall throughput, even though individual prompt latency (TTFT) is unchanged. The paper positions this as an orthogonal benefit to the latency reduction: Prompt Cache reduces latency for individual queries, and pointer-based sharing increases the number of queries the system can process concurrently.

4. Key Insights and Innovations

Innovation 1: Cross-Prompt Attention Reuse as a First-Class Inference Primitive

The paper's most fundamental intellectual move is elevating attention state reuse from an intra-prompt optimization (KV Cache) to an inter-prompt system primitive. Before Prompt Cache, the field's mental model of LLM inference treated each prompt as an independent computation: you receive a prompt, you run self-attention over the entire sequence, you cache the results for autoregressive decoding, and then you discard the cache when generation completes. This was so ingrained that even systems which could share attention states across prompts — like PagedAttention (Kwon et al., 2023) — limited sharing to the special case of identical prefixes, implicitly assuming that general reuse was either impossible or not worth the engineering complexity.

Prompt Cache challenges this assumption at its root. The conceptual reframing is subtle but powerful: attention states are not ephemeral byproducts of serving a single prompt — they are reusable computational assets with value across queries. This is a shift in how we think about inference compute, analogous to how memoization transformed thinking about recursive algorithms. Just as memoization says "store the results of expensive function calls and reuse them when the same inputs occur," Prompt Cache says "store the results of expensive attention computations and reuse them when the same text segments occur." The difference is that memoization typically operates within a single program execution, while Prompt Cache operates across independent inference requests — it is cross-session, cross-user, cross-query caching of internal model states.

What makes this non-obvious is that attention states are position-dependent: the same text at position 100 yields different key-value tensors than at position 500. The naïve view would be that this makes cross-prompt reuse impossible, since a document might appear at different positions in different prompts. Prompt Cache's insight is that this position-dependence can be exploited rather than worked around: by fixing positions in a schema, the system ensures that a module's attention states are always computed at the same position, making them reusable without transformation. The discontinuous position ID finding — that LLMs tolerate gaps in position sequences — is the enabling empirical discovery that makes this exploitation possible, but the deeper conceptual innovation is the reframing of attention states as position-anchored, schema-scoped reusable assets.

The significance of this reframing extends beyond the specific implementation. It opens a design space for inference systems where caching, prefetching, eviction, and compression of attention states are first-class concerns, analogous to how CPU caches, disk caches, and CDNs manage data locality at different levels of the memory hierarchy. The paper gestures at this in its conclusion, envisioning "enhanced prompt module management and GPU cache replacement strategies" (Section 6). If attention states are reusable assets, then inference serving becomes a caching problem — with all the associated design questions about cache sizing, replacement policies, prefetching heuristics, and multi-level storage hierarchies — rather than a pure computation problem. This is a fundamental shift in how to architect LLM serving systems.

Comparison to prior work: KV Cache (Pope et al., 2022) established intra-prompt reuse as standard practice but scoped it to a single generation session. PagedAttention (Kwon et al., 2023) introduced prefix sharing as a special case of inter-prompt reuse but did not generalize beyond identical prefixes. AttMemo (Feng et al., 2023) explored similarity-based reuse but required embedding comparisons and introduced approximation. Prompt Cache is the first work to propose structural, exact inter-prompt reuse as a general mechanism, using explicit schema declarations rather than runtime similarity detection to identify reusable content. This structural approach is more reliable (exact matching, no false positives from similar-but-not-identical text) and more efficient (O(1) tag-based lookup vs. embedding computation and comparison), but requires the prompt author or compiler to declare reusable segments — it shifts complexity from the runtime system to the prompt design phase.

Tie to evidence: The quadratic scaling of the latency advantage in Figure 5 directly supports this reframing. If attention states were not worth caching, the memory copy overhead would dominate the computational savings. Figure 5 shows the opposite: attention computation cost grows quadratically with sequence length while memory copy grows linearly, meaning the caching advantage increases with prompt length. This empirical finding justifies treating attention states as cachable assets — the longer the cached content, the more valuable the cache.

Innovation 2: Schema-Defined Prompt Structure as the Interface for Modular Reuse

The second distinctive contribution is the idea that prompt structure should be made explicit through a formal schema language, and that this schema serves as the contract between prompt authors and the inference system for enabling reuse. Prior to Prompt Cache, prompts were typically treated as unstructured or semi-structured text — system messages, documents, and instructions were concatenated into a flat string with ad-hoc formatting conventions. Even when prompt templates existed (White et al., 2023), they were string-level abstractions with no semantic connection to the model's internal computation. Prompt Cache introduces the idea that a prompt's modular structure has computational significance: by declaring which segments are reusable, how they relate positionally, and which are mutually exclusive, the prompt schema provides the inference system with the information it needs to cache, assemble, and reuse attention states correctly.

This is a genuinely novel interface concept for LLM serving. It draws an implicit parallel to how compilers use type systems and module declarations to enable separate compilation: a C header file declares the interface of a module (function signatures, data structures) so that the compiler can compile callers independently, knowing the interface contract will be honored at link time. Similarly, a PML schema declares the "interface" of prompt modules (their names, positions, parameter slots, mutual exclusions) so that the inference system can precompute their attention states independently, knowing the positional contract will be honored when prompts import them. The schema is the header file for attention state reuse.

What distinguishes this from simple template systems is the bidirectional nature of the contract. Templates typically encode only "what text goes where" from the prompt author's perspective. PML schemas encode both "what text goes where" (for the prompt author) and "what position IDs correspond to each segment" (for the inference system). The schema's position ID assignment — computed once when the schema is loaded, based on token lengths and document order — is a deterministic mapping that both sides rely on. The prompt author doesn't need to know about position IDs, but the system uses them to guarantee cache correctness. This separation of concerns — human-facing module names and structures vs. system-facing position assignments — is what makes the interface practical.

The union construct is particularly innovative from a systems perspective. By declaring that modules A, B, and C are mutually exclusive and share the same position range, the schema provides the inference system with an optimization hint: these modules will never appear together in a prompt, so the system can allocate a single position range for all of them rather than unique ranges. This is not just a space optimization — it enables prefetching strategies (the system knows that if a user session tends to access union members, it should prefetch all of them) and informs cache eviction decisions (union members have correlated access patterns). Prior template systems had no way to express mutual exclusion of this kind because they operated at the string level without computational semantics.

Comparison to prior work: Prompt templates (White et al., 2023; Beurer-Kellner et al., 2023; Guidance, 2023) provide string-level reuse — they let users write "fill in the blanks" prompts where variables are substituted into a fixed text structure. But these systems are purely textual: they have no awareness of the model's internal computation, no concept of position IDs, and no mechanism for caching attention states. Prompt Cache's PML subsumes the template use case (parameters serve the same "fill in the blank" function) but adds the computational semantics that enable caching. The Python-to-PML compiler (Section 3.2.4) makes this relationship explicit: existing prompt programming abstractions (if statements, function calls) are compiled down to PML schemas, with PML serving as an intermediate representation that carries the caching semantics that higher-level languages lack.

Significance beyond raw performance: The schema interface is what makes Prompt Cache practical rather than theoretical. Without it, the system would need to infer reusable segments from prompts at runtime — a hard problem with ambiguous solutions. With it, reuse is explicit, deterministic, and verifiable. This design pattern — making computational structure explicit through a domain-specific language that separates human-facing concerns from system-facing optimizations — is broadly applicable beyond LLM inference. It suggests a future where prompt engineering tools generate not just text but also computational metadata (caching hints, parallelism specifications, constraint declarations) that inference systems can exploit.

Tie to evidence: The accuracy results in Table 1 implicitly validate the schema interface. The fact that Prompt Cache preserves accuracy within 2.5 percentage points across three different model architectures and multiple datasets shows that the schema's position ID assignments and independent module encoding produce attention states that are functionally equivalent to the baseline's full-context computation. If the schema contract were broken — if position IDs were inconsistent or module boundaries introduced artifacts — the accuracy would degrade substantially. The stability of the accuracy results is evidence that the schema interface works as designed.

Innovation 3: Discontinuous Position IDs as an Empirically Validated Enabling Property

The third contribution is the identification and empirical validation of a property that makes modular attention reuse possible: LLMs can operate on attention states with discontinuous position IDs without accuracy degradation (Section 3.1). This is not a technique or a design choice — it is a discovery about how trained Transformer models behave when their positional encodings have gaps. The paper presents it as an empirical finding ("our empirical finding that LLMs can operate on attention states with discontinuous position IDs"), and the entire Prompt Cache approach depends on it.

Why is this a discovery rather than an engineering assumption? Because standard Transformer implementations are designed for contiguous position sequences. Positional encodings — whether learned embedding tables, RoPE rotations, or ALiBi biases — assume that position IDs form an unbroken sequence 0, 1, 2, ..., n-1. The training data for all major LLMs consists of contiguous text with no position gaps. There was no a priori reason to expect that models would generalize to discontinuous position sequences — that a model trained on documents where position 100 always follows position 99 would correctly process a prompt where position 200 follows position 99 with positions 100-199 absent. This is a form of distribution shift in the positional encoding space, and the fact that models tolerate it without accuracy loss is a non-trivial empirical finding about the robustness of learned position representations.

The finding has important implications beyond Prompt Cache. It suggests that Transformers' positional encodings are more flexible than their training distribution would imply — that the model learns to use absolute positions as labels for ordering attention rather than as continuous coordinates that must be densely packed. This connects to theoretical work on positional encoding (Dufter et al., 2022) and suggests that models are learning position-invariant features from position-dependent encodings, rather than memorizing position-token associations. If this generalizes to other model architectures and training regimes, it opens the door to a broader class of modular composition techniques where precomputed model states are assembled from components with non-contiguous position ranges — not just for attention caching but potentially for model parallelism, continual learning, or multi-modal composition.

The paper's adaptation of positional encoding mechanisms for discontinuous IDs (Section 4.2) reveals something interesting about how different encoding schemes handle this property. Embedding table-based encodings (BERT, GPT-2) require "no alterations" — they support discontinuous lookups natively because position ID p maps directly to table entry p regardless of gaps. RoPE requires a lookup table for rotation matrices — an engineering change but not a conceptual one, since the rotation for position p depends only on p, not on p-1. ALiBi is the most interesting case: the bias depends on |i - j|, the distance between positions, which would be artificially inflated by position gaps. The paper notes that ALiBi requires "a lookup table to adjust the bias matrix" (Section 4.2) without specifying the exact adjustment, but the implication is that the bias must be computed relative to logical token distances rather than raw position ID differences. This means ALiBi is the encoding scheme most sensitive to the discontinuous position property — the paper implicitly identifies it as the architecture requiring the most careful adaptation.

Comparison to prior work: The discontinuous position ID property does not appear to have been systematically studied or exploited in prior LLM systems work. AttMemo (Feng et al., 2023) avoids the position problem by reusing attention states only for prefixes with high embedding similarity, which implicitly assumes similar positions. PagedAttention (Kwon et al., 2023) reuses KV cache across prompts with identical prefixes, which preserves contiguous positions. Prompt Cache is the first work to explicitly identify, validate, and exploit the tolerance for discontinuous positions as a mechanism for general modular attention reuse.

Tie to evidence: The accuracy results in Table 1 are the primary evidence for this property. Across Llama2 (RoPE), MPT (ALiBi), and Falcon (RoPE), Prompt Cache preserves baseline accuracy within 2.5 percentage points on all tested datasets. This shows that the discontinuous position ID property holds across multiple positional encoding schemes and model architectures, not just for one specific implementation. The qualitative examples in Figures 6-8 further demonstrate that outputs remain coherent and on-task, which would not be the case if the model were confused by position gaps — a confused model would produce garbled or off-topic outputs, not sensible code completions and personalized recommendations.

Innovation 4: Parameterized Attention State Reuse via Placeholder Substitution

The fourth contribution is a mechanism that extends attention state reuse from exact text matching to parameterized reuse, where the same module structure can be instantiated with different arguments while still benefiting from precomputed surrounding attention states. This is the <param> mechanism described in Section 3.2.2 and detailed in Section 3.3-3.4.

The conceptual innovation is recognizing that attention state reuse does not require the entire module to be static — only the position structure needs to be fixed. By pre-allocating position ranges for parameter slots (using <unk> tokens during encoding) and then substituting the actual argument tokens' attention states at inference time, Prompt Cache achieves a form of partial caching: the surrounding module content is fully cached, and only the parameter slots require fresh computation. This is more subtle than it appears, because the surrounding tokens' attention states were computed with <unk> tokens occupying the parameter positions — when the actual arguments are substituted, the surrounding states remain valid because they were encoded with the expectation that something (unknown at encoding time) would occupy those positions, and the exact content at those positions has bounded influence on the surrounding states due to the causal masking pattern.

This parameterization capability is what makes Prompt Cache applicable to templated prompts — which the paper identifies as a major use case in robotics, tool learning, and other structured LLM applications (Section 1). Without parameters, a template like "Plan a {duration} trip to {destination}" would need to be fully recomputed for each combination of duration and destination, since the exact text differs each time. With parameters, the template structure is encoded once (with <unk> placeholders for duration and destination), and only the argument tokens require new computation. This transforms the cost model: instead of paying $O(n^2)$ for the full template each time, you pay $O(a^2 + an)$ where $a$ is the argument length and $n$ is the template length, with $a \ll n$ in most cases.

The "buffer" use case for parameters — where a parameter at the beginning or end of a module serves as an insertion point for arbitrary uncached text — reveals a deeper design principle. It shows that Prompt Cache's caching granularity is not all-or-nothing: a module can be partially cached, with designated "cutouts" where dynamic content is inserted. This is analogous to how CPU caches handle cache lines with dirty bits — most of the line is clean (cached), but specific bytes can be marked dirty (needing write-back) — or how virtual memory systems handle demand paging where most of a page is resident but specific addresses may trigger page faults. The parameter-as-buffer pattern brings this "partial caching" concept to attention states, enabling a spectrum between fully cached (pure module import) and fully uncached (pure new text) where most applications will operate.

Comparison to prior work: Template-based prompting systems (White et al., 2023; Guidance, 2023) support parameter substitution at the string level, but perform the substitution before the prompt reaches the model — the entire filled-in template is then processed from scratch, gaining no computational benefit from the template structure. Prompt Cache's parameter mechanism performs substitution at the attention state level — the template is precomputed, and only the argument attention states are computed at inference time. This is a fundamentally different computational model: text-level substitution is "substitute, then compute everything," while attention-level substitution is "precompute the structure, then compute only the substitutions."

Tie to evidence: The parameterized prompt example in Figure 8 (trip planning) demonstrates the mechanism in practice. The <travel-plan> module with its duration parameter is imported with a specific argument ("a week"), and the output quality is preserved while TTFT latency drops from 75 ms to 54 ms on GPU. This is a concrete demonstration that the <unk> placeholder substitution works correctly — if the surrounding template text's attention states were invalidated by the substitution (because the <unk> encoding differed substantially from the actual argument encoding), the output quality would degrade. The preservation of output quality in Figure 8 is evidence that the surrounding states remain valid after argument substitution, validating the partial caching approach.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The primary evaluation uses the LongBench suite (Bai et al., 2023), a bilingual multitask benchmark for long-context understanding. The paper employs a curated subsample with context lengths ranging from 4K to 10K tokens, excerpted from 21 datasets across 6 task categories: multi-document question answering (NarrativeQA, 2WikiMultihopQA, MuSiQue, HotpotQA, TriviaQA, Passage Retrieval), summarization (GovReport, QMSum, MultiNews), and code completion (RepoBench, LongCoder). The documents within these datasets — wiki pages, news articles, meeting transcripts — are defined as prompt modules, while task-specific directives (the actual questions or instructions) are retained as uncached user text (Section 5.1).

• Base model(s). The evaluation spans three model families with distinct positional encoding mechanisms to demonstrate generality: Llama2 7B and 13B (Touvron et al., 2023), which use Rotary Position Embedding (RoPE); MPT 7B (MosaicML, 2023), which uses Attention with Linear Biases (ALiBi); and Falcon 7B (Penedo et al., 2023), which also uses RoPE. An additional model, CodeLlama 7B (Rozière et al., 2023), is used for the code generation application example. All models are selected to fit within the memory capacity of a single GPU (40 GB), ensuring the evaluation reflects realistic single-device deployment scenarios. The choice of three distinct positional encoding schemes (RoPE for Llama2/Falcon, ALiBi for MPT) is deliberate: it tests whether the discontinuous position ID property underlying Prompt Cache generalizes across encoding mechanisms.

• Metrics. The primary latency metric is time-to-first-token (TTFT) — the wall-clock time from prompt submission to the generation of the first output token — measured in milliseconds. This metric is chosen because Prompt Cache only accelerates the prefill phase; per-token decoding latency (time-to-subsequent-token, TTST) is identical to baseline KV Cache. For accuracy evaluation, the paper uses task-appropriate metrics from LongBench: F1 score for question-answering tasks (NarrativeQA, 2WikiMultihopQA, MuSiQue, TriviaQA), Rouge-L for summarization tasks (GovReport, QMSum, MultiNews), and accuracy for Passage Retrieval. All accuracy measurements use deterministic (greedy) sampling to ensure comparability between cached and non-cached runs.

• Baselines. The paper uses regular KV Cache (Pope et al., 2022) as the sole baseline for all comparisons. KV Cache and Prompt Cache share the exact same inference pipeline except for how attention states are computed during the prefill phase: KV Cache computes full self-attention over the entire prompt from scratch, while Prompt Cache retrieves and concatenates precomputed attention states for cached modules and computes attention only for uncached segments. This is described as sharing the "exact same inference pipeline except for attention state computation" (Section 5). The baseline does not employ any cross-prompt caching, prefix sharing, or attention state reuse — it is the standard HuggingFace Transformers inference with KV Cache enabled.

• Generation budget / compute accounting. Prompt Cache does not modify the number of generated tokens or the decoding strategy; it only affects prefill computation. Consequently, the paper measures latency at the system level (wall-clock time) rather than using abstract compute units (FLOPs, generations). The relevant "budget" is the prompt context length in tokens, which determines both the baseline attention computation cost and the data volume for cached module transfer. The paper evaluates across prompts averaging ~5K tokens from LongBench, and additionally uses a synthetic dataset with varied sequence lengths (Figure 5) to isolate how the latency advantage scales with prompt size. There is no tradeoff between generation quality and latency since the method is exact (modulo the attention masking approximation), so no compute-accuracy Pareto frontier is constructed — the evaluation measures latency reduction while verifying accuracy preservation separately.

• Cross-validation / statistical protocol. There is no cross-validation or train/test split for the latency experiments — all LongBench test examples are used. For accuracy evaluation, the paper uses the full LongBench test sets and reports aggregate metrics per dataset, comparing Prompt Cache results directly to KV Cache results under identical sampling conditions (deterministic greedy decoding). The paper does not report confidence intervals, error bars, or statistical significance tests for either latency or accuracy measurements. The accuracy benchmarks in Table 1 report point estimates for each model-dataset combination, and "outliers" (cases where cached performance exceeds baseline by more than 2.5 points) are marked in bold.

Main Quantitative Results

Latency Improvements on GPU Inference (Figure 3)

The headline finding is that Prompt Cache reduces TTFT by 1.5× to 3× when prompt modules are stored in CPU memory and by 5× to 10× when stored in GPU memory, evaluated across three NVIDIA GPUs (RTX 4090, A40, A100) using Llama 7B on eight LongBench datasets. The paper presents these as "upper and lower bounds of latency reductions possible with Prompt Cache," with actual deployment performance falling between these extremes depending on the mix of GPU and CPU memory used for module storage (Section 5.2.1).

Figure 3 shows consistently ordered bars across all eight datasets: the baseline (no caching) is highest, followed by Prompt Cache with CPU memory (yellow bars), followed by Prompt Cache with GPU memory (blue bars), which achieves the lowest latency. The consistent trend "across the datasets since the LongBench samples have comparable lengths, averaging 5K tokens" indicates that the latency reduction is driven primarily by prompt length and module storage location rather than dataset-specific content characteristics.

The gap between CPU-memory and GPU-memory Prompt Cache reveals the cost of host-to-device memory transfer. With modules on CPU memory, the system must copy cached KV tensors from host DRAM to GPU HBM before inference — a linear-time operation that the paper quantifies as 5.34 ms for a 5K-token attention state on GPU (Section 5.4). Despite this overhead, the 1.5–3× speedup over baseline shows that avoiding attention recomputation more than compensates for the transfer cost. With modules on GPU memory, this transfer is eliminated, and the remaining overhead is essentially a device-side memory concatenation — which the paper measures at 0.23 ms for 5K tokens — yielding the larger 5–10× speedup.

A specific configuration is highlighted for the RTX 4090 with Llama 7B at 3K context length: "Prompt Cache enhances TTFT from 900 ms to 90 ms" (Section 5.4). This represents a 10× reduction, bringing prefill latency from nearly one second — a noticeably laggy interaction — to under 100 ms, which is perceived as near-instantaneous.

Latency Improvements on CPU Inference (Figure 4)

On CPUs, the latency reductions are substantially larger: up to 70× on the Intel i9-13900K and up to 20× on the AMD Ryzen 9 7950X, evaluated across the same eight LongBench datasets using Llama 7B. The paper attributes the disparity between the two CPUs to memory bandwidth differences — the Intel system uses 5600 MT/s DDR5 RAM while the AMD system uses 3600 MT/s DDR4 RAM (Section 5.2.2) — though other architectural differences (core count, cache hierarchy) likely also contribute.

The key observation here is that "CPU inference benefits more significantly from Prompt Cache than GPU inference does" because of "the much greater latency of attention computation in the CPU, especially as the sequences become longer" compared to the relatively small difference in memory copy latency between CPU and GPU. GPUs have massive parallelism for matrix operations, making attention computation relatively fast even at O(n²) complexity; CPUs must execute the same operations sequentially, making the quadratic term far more punishing. Prompt Cache replaces that quadratic computation with linear memory copy, and the ratio of quadratic-to-linear cost is much larger on CPU than GPU — hence the larger speedup factor.

The paper notes that datasets with "a larger proportion of uncached prompts, such as TriviaQA" show higher latency (the cached speedup is smaller), confirming that the benefit scales with the fraction of prompt content that is cached. This is expected from the cost model: uncached tokens still require full attention computation, so a prompt with a high fraction of uncached content approaches the baseline cost.

Accuracy Preservation (Table 1)

Table 1 reports accuracy metrics across eight LongBench datasets for four model configurations: Llama2 7B, Llama2 13B, MPT 7B, and Falcon 7B, each compared between baseline KV Cache and Prompt Cache. The paper's stated criterion is that "Prompt Cache preserves output accuracy within 2.5 percentage points of the baseline across all tested benchmarks" (Section 5.3), and the results largely support this claim, though with notable exceptions.

Scanning across the 32 comparisons (8 datasets × 4 models), the vast majority fall within ±2.5 points of the baseline. The paper marks "outliers" in bold where cached performance is higher than baseline by more than 2.5 points. These include: NarrativeQA with Falcon 7B (baseline 7.14, cached 8.87, difference +1.73 — wait, that is within 2.5; rechecking: the paper states "We mark the outliers as bold, of which the performance is higher than 2.5 compared to the counterpart"). The bold entries in Table 1 appear to be: Llama2 13B on MuSiQue (10.03 vs. 12.14, +2.11 — actually this is within 2.5 as well), and the paper's exact threshold is ambiguous from the table alone. The table does show several cases where cached performance is lower than baseline by more than a point, including Passage Retrieval with Llama2 7B (7.50 vs. 4.25, -3.25) and 13B (9.08 vs. 6.50, -2.58), suggesting that the accuracy preservation is dataset-dependent and not perfectly symmetric.

The paper provides no analysis of which datasets show larger deviations or why, beyond the general statement that attention masking "can enhance or degrade output quality depending on the semantic independence of the modules" (Section 3.3). The Passage Retrieval degradation (the largest negative deviation, -3.25 for Llama2 7B) likely reflects a task where cross-document attention is important — retrieval requires comparing passages to identify the most relevant one — and the independent module encoding prevents the model from establishing these cross-passage comparisons during prefill.

Quadratic Scaling of Latency Advantage (Figure 5)

Figure 5 presents results on a synthetic dataset with varied sequence lengths, assuming all prompt content is cached, to isolate how the computational savings scale with prompt size. The curves show KV Cache's TTFT latency growing quadratically with sequence length (the O(n²) attention cost), while Prompt Cache's TTFT latency — which is essentially the memory copy cost plus the cost of computing attention for zero uncached tokens — grows linearly (the O(n) memory copy cost). The "gap between the two curves" — the latency advantage — "expands quadratically with sequence length," as the paper states.

This result is shown for three hardware configurations: Intel i9-13900K CPU, NVIDIA A40 GPU, and NVIDIA RTX 4090 GPU, all with Llama2 7B and prompt modules stored in CPU memory. The CPU curve shows the largest absolute advantage because the baseline attention computation is slowest, but the relative advantage (ratio of baseline to cached latency) also grows with sequence length on all platforms.

The paper also notes the effect of model size on the cache advantage: "moving from a 7B to 13B model at a token length of 3K added 220 ms latency [for baseline], whereas Prompt Cache added only 30 ms" (Section 5.4). This differential is because attention computation complexity scales with both sequence length and hidden dimension — specifically, $6nd^2 + 4n^2d$ FLOPs — while the memory copy cost for cached modules scales only with the KV tensor size, which is $2 \cdot h \cdot n \cdot d$ elements (linear in $n$ and $d$, but $d$ grows more slowly than $d^2$ for typical model sizes). The paper claims this means "Prompt Cache's advantage over KV Cache also quadratically increases with model size," though this is extrapolated from a single 7B-to-13B comparison rather than systematically tested across a range of model sizes.

End-to-End Latency Context

The paper acknowledges that Prompt Cache only reduces TTFT, not per-token decoding latency. For a concrete scenario on RTX 4090 with Llama 7B and 3K context, the paper provides: TTFT drops from 900 ms to 90 ms, while "the token generation time or the time-to-subsequent-token (TTST) remains consistent between KV Cache and Prompt Cache at an average of 32 ms per token, regardless of the token length" (Section 5.4). The paper argues that the 810 ms savings are equivalent to "the generation of 25 more tokens within the same timeframe," framing the TTFT reduction as meaningful for overall user experience even though it does not accelerate the body of the response.

Ablation Studies and Robustness Checks

Model architecture robustness (Table 1): The accuracy results span RoPE-based models (Llama2, Falcon) and ALiBi-based models (MPT), with the paper noting that all required only minor positional encoding adaptations (Section 4.2). The fact that accuracy is preserved across all three architectures — which use fundamentally different positional encoding mechanisms — serves as a robustness check for the discontinuous position ID property. If the property were fragile or architecture-specific, one would expect systematic accuracy degradation in at least one model family; the absence of such degradation across the board supports the paper's claim of generality. However, the sample size is small (one ALiBi model, two RoPE model families) and the paper does not test on learned absolute position embeddings (GPT-2 style) despite claiming in Section 4.2 that these require "no alterations."

Hardware platform robustness (Figures 3, 4): The latency improvements are demonstrated across three GPU architectures (RTX 4090 consumer-grade, A40 datacenter, A100 datacenter) and two CPU platforms (Intel and AMD), with consistent speedup patterns. The paper notes that the Intel CPU achieves a 70× speedup while the AMD achieves 20×, attributing this to memory bandwidth (5600 MT/s DDR5 vs. 3600 MT/s DDR4). However, the AMD system also uses a different CPU architecture (Zen 4 vs. Raptor Lake), different core counts, and different cache hierarchies — the single attribution to memory bandwidth is plausible but not isolated. A more controlled ablation (same CPU with different RAM speeds) would be needed to confirm this attribution.

Scaffolding as accuracy recovery (Section 3.3): The scaffolding mechanism is described as a method for recovering cross-module attention when modules are semantically dependent. However, the paper does not present any ablation results for scaffolding — no accuracy comparisons with and without scaffolding, no latency measurements for scaffold retrieval vs. individual module retrieval, and no quantification of the memory overhead vs. accuracy tradeoff. The mechanism is described architecturally but not evaluated experimentally. This is a notable gap: scaffolding is presented as the solution to the attention masking limitation, but without experimental validation, it remains a hypothetical capability. The accuracy results in Table 1 use only independent module encoding (without scaffolding), so the paper's accuracy preservation claim is specifically for the independent-encoding case — we do not know whether scaffolding would improve the cases where independent encoding shows degradation (e.g., Passage Retrieval).

Python-to-PML compilation (Section 3.2.4): The paper describes a compiler that converts Python prompt programs into PML schemas automatically, with if statements becoming <module> constructs, if-else becoming <union>, and function calls becoming nested modules. This is an important practical contribution — it means users do not need to write PML manually — but no evaluation of the compiler is presented. There are no measurements of compilation time, no examples of compiled output vs. hand-written PML, and no demonstration that compiled schemas achieve the same latency improvements as manually crafted ones. The paper's use cases (Figures 6-8) appear to use hand-authored schemas, not compiler-generated ones. The compiler remains an unimplemented concept or, at minimum, an unevaluated one in the context of this paper.

Batch inference memory optimization (Section 3.4): The paper describes how pointer-based sharing of KV cache blocks (via PagedAttention) can reduce memory footprint in batched inference, using the example of 100 requests sharing a 1K-token module reducing memory by 50%. However, no batch inference experiments are presented — there are no throughput measurements, no batch-size scaling curves, and no comparison of memory consumption with and without pointer sharing. The optimization is described conceptually but not evaluated, making it a projected benefit rather than a demonstrated one.

Parameter mechanism correctness (Figure 8): The trip-planning example in Figure 8 demonstrates parameterized reuse qualitatively — the output quality is "juxtaposed" between cached and non-cached generation — but the paper provides no systematic accuracy evaluation for parameterized modules. There is no measurement of how accuracy scales with parameter argument length, how accuracy degrades when argument length approaches or exceeds the declared len (which should be a validation error), or whether the <unk> placeholder substitution introduces artifacts for certain argument types. The qualitative example supports the claim that parameterization works, but a quantitative ablation (e.g., accuracy across a range of parameter lengths and types) would be needed to characterize robustness.

Negative result: no scaffolding evaluation. As noted above, the absence of scaffolding experiments is a genuine limitation. The paper identifies attention masking as a potential source of accuracy loss (Section 3.3) and proposes scaffolding as the solution, but does not demonstrate that scaffolding actually resolves accuracy degradation in practice. This is particularly relevant for the Passage Retrieval results in Table 1, where Llama2 7B shows a -3.25 accuracy drop — would scaffolding recover this? The paper leaves this question unanswered.

Negative result: accuracy is not always preserved within 2.5 points. While the paper's stated claim is accuracy preservation within 2.5 points, Table 1 shows at least one case (Passage Retrieval with Llama2 7B, 7.50 → 4.25, -3.25) that violates this bound, and borderline cases for Llama2 13B on Passage Retrieval (9.08 → 6.50, -2.58). The paper does not discuss these deviations or analyze their causes. The Passage Retrieval task likely requires cross-document attention to compare and rank passages, which the independent module encoding prevents, and the paper would be strengthened by acknowledging this failure mode explicitly and demonstrating whether scaffolding mitigates it.

Critical Assessment

Claim 1: Prompt Cache reduces TTFT by up to 10× on GPU and up to 70× on CPU.

Where the evidence stands: This claim is well-supported by Figures 3 and 4, with measurements across three GPUs and two CPUs on eight LongBench datasets. The 10× GPU figure corresponds to GPU-memory-stored modules (the upper bound), the 1.5–3× figure corresponds to CPU-memory-stored modules (the lower bound), and the paper is transparent about this range. The 70× CPU figure is demonstrated on the Intel i9-13900K with DDR5; the 20× figure on the AMD system shows this is hardware-dependent.

What is actually demonstrated vs. claimed: The experiments measure TTFT latency specifically for the prefill phase on prompts where all documents are defined as cached modules — the LongBench documents are pre-encoded as prompt modules, and only task instructions remain uncached. This is a best-case scenario for Prompt Cache, since the fraction of cached content is maximized. In a realistic deployment, prompts would include a mix of cached and uncached content determined by the application's reuse patterns, and the achieved speedup would fall between the bounds shown but could be closer to the lower bound if uncached content is substantial.

The paper does not report what fraction of prompt tokens are cached vs. uncached in the LongBench experiments, making it difficult to calibrate expectations for other workloads. If the typical LongBench prompt is 90% document content (cached) and 10% task instruction (uncached), the reported speedups are for a cache-hit ratio of 0.9. A workload with 50% uncached content would see correspondingly smaller benefits, proportional to the fraction of attention computation still required.

Missing experiments: The paper does not systematically vary the cache-hit ratio and measure latency as a function of the fraction of cached content. This would be a straightforward synthetic experiment — fix prompt length, vary the fraction of tokens drawn from cached modules — and would produce a curve showing how the latency advantage degrades as more content is uncached. Without this, the reported "up to X×" numbers are upper bounds that cannot be extrapolated to arbitrary workloads.

Claim 2: Prompt Cache preserves output accuracy without significant loss.

Where the evidence stands: Table 1 provides accuracy comparisons across 32 configurations (8 datasets × 4 models) and shows that most fall within ±2.5 points of baseline. This broadly supports the claim for the tested task types (document QA, summarization) and model architectures.

What is actually demonstrated vs. claimed: The accuracy preservation is demonstrated for a specific task distribution — long-document QA and summarization where modules are independent documents — and a specific encoding configuration (independent encoding, no scaffolding). The paper's claim of "accuracy preservation" is implicitly scoped to these conditions, but the text does not make this scoping explicit. The attention masking effect (Section 3.3) means that accuracy preservation depends on "the semantic independence of the modules," and the paper does not characterize which datasets or tasks require cross-module attention.

The Passage Retrieval result (Llama2 7B dropping from 7.50 to 4.25) is a genuine accuracy loss that violates the 2.5-point threshold and goes unremarked. This is a task where cross-document comparison is essential — retrieval inherently requires comparing passages — and the independent encoding prevents this. The fact that accuracy degrades on exactly the task that most requires cross-module attention suggests the attention masking effect is not negligible for all use cases. The paper's claim should be qualified: accuracy is preserved for tasks where modules are semantically independent; for tasks requiring cross-module reasoning, accuracy may degrade, and scaffolding (unevaluated in this paper) may be necessary.

Missing experiments: The paper does not evaluate accuracy in a controlled configuration where cross-module attention is known to be important (beyond Passage Retrieval, which shows a hint). A synthetic task where the correct answer depends on information distributed across modules — for example, a question whose answer requires combining facts from documents A and B — would cleanly test the attention masking effect. Without such an experiment, we do not know the ceiling of accuracy loss that independent encoding can cause, or at what degree of cross-module dependency scaffolding becomes necessary.

Claim 3: The latency advantage grows quadratically with sequence length and model size.

Where the evidence stands: Figure 5 clearly shows the quadratic vs. linear scaling for sequence length, and the 7B-to-13B comparison provides a single data point for model size scaling. The theory is sound: attention computation is O(n²) while memory copy is O(n), so the ratio grows as O(n).

What is actually demonstrated vs. claimed: The "quadratically increases with model size" claim (Section 5.4) is extrapolated from two model sizes (7B and 13B) and conflates two effects: the increase in hidden dimension $d$ (which makes attention compute scale as $d^2$ while memory copy scales as $d$) and the increase in number of layers (which scales both compute and memory linearly). The 7B-to-13B comparison shows a 220 ms baseline increase vs. 30 ms Prompt Cache increase, which is consistent with the quadratic claim, but a single data point does not establish a scaling law. The paper would need measurements at 1B, 3B, 7B, 13B, 30B, and 70B scales (within a single model family to control for architecture) to characterize the scaling relationship reliably.

Missing experiments: A systematic sweep of model sizes within one architecture family (e.g., Llama2 at 7B, 13B, and 70B) would validate (or refine) the quadratic scaling claim. The paper does not run this experiment, likely because 70B models exceed the single-GPU constraint, but distributed inference results would strengthen the scaling argument considerably.

Claim 4: Prompt Cache is applicable across model architectures with minimal modification.

Where the evidence stands: The paper adapts three positional encoding mechanisms (embedding tables, RoPE, ALiBi) and demonstrates accuracy preservation on RoPE models (Llama2, Falcon) and ALiBi models (MPT) with "approximately 20 lines of additional code" per model (Section 4.2).

What is actually demonstrated vs. claimed: The adaptation is demonstrated for three specific model families, all in the 7B parameter range, all using HuggingFace Transformers. The "20 lines" figure is an estimate that the paper does not break down by architecture or verify for models beyond the tested set. The paper does not test on embedding-table-based models (BERT, GPT-2) despite claiming they require "no alterations" — this is a theoretical claim, not an empirical one. The claim is therefore supported for RoPE and ALiBi models in the tested size range, but should be considered unvalidated for other positional encoding schemes and model scales.

Missing experiments: Testing on a GPT-2-style model (learned absolute position embeddings) would validate the "no alterations needed" claim. Testing on a much larger model (Llama2 70B) would demonstrate that the adaptation scales to production model sizes. The paper does neither.

Summary of conditionalities

The paper's claims hold well when:

• Prompt modules are semantically independent (most document QA, summarization)
• A high fraction of prompt tokens come from cached modules
• The inference server can pre-encode schemas offline
• GPU memory is available for module storage (for the large speedups)
• Models use RoPE or ALiBi positional encoding

The claims are weaker or untested when:

• Tasks require cross-module attention (e.g., passage retrieval, multi-hop reasoning across documents)
• The cache-hit ratio is low (many uncached segments)
• Schema definition overhead is included in the cost model (schema encoding time is not measured)
• Models use other positional encoding schemes
• Latency-critical applications require acceleration beyond TTFT (per-token decoding is unaffected)
• The application requires dynamic prompt construction that does not map cleanly to pre-defined modules

The most significant gap between claims and evidence is the absence of scaffolding evaluation. The paper identifies attention masking as a potential source of accuracy loss and proposes scaffolding as the solution, but never measures whether scaffolding actually recovers accuracy in practice. Without this, the accuracy preservation claim is limited to the independent-encoding case and the tested task distribution, and the paper's strongest accuracy results (Table 1) may not generalize to tasks requiring cross-module reasoning. The Passage Retrieval result — the only task in the benchmark suite that explicitly requires comparing documents — showing a larger accuracy drop than any other task is consistent with this limitation. A reader should understand that Prompt Cache's accuracy guarantees are task-dependent and that the scaffolding mechanism, while architecturally sound, is experimentally unvalidated.

6. Limitations and Trade-offs

6.1 Prompt Cache Only Accelerates the Prefill Phase, Not Per-Token Decoding

The assumption or constraint. The paper is explicit that Prompt Cache's benefits are confined to the prefill phase — the computation that processes the input prompt before any tokens are generated. As stated in Section 3.4, "Prompt Cache diminishes the latency involved in producing the first token, or time-to-first-token (TTFT)." The per-token decoding latency, called time-to-subsequent-token (TTST), is identical between Prompt Cache and baseline KV Cache because both methods use the same autoregressive decoding procedure once the prompt's attention states are assembled. The paper acknowledges this scope: "the computational complexity for generating subsequent tokens remains consistent with that of KV Cache, as prompt modules are not employed beyond the initial token."

The consequence. The practical impact of this limitation depends on the ratio of prefill time to total generation time. For applications with long prompts but short outputs — such as document classification, single-answer QA, or content moderation — the prefill dominates and TTFT reduction translates directly to end-to-end latency improvement. For applications with long outputs — such as story generation, detailed explanations, or code generation producing hundreds of tokens — the prefill is a small fraction of total latency, and Prompt Cache provides diminishing overall benefit. The paper provides a concrete data point in Section 5.4: on RTX 4090 with Llama 7B at 3K context, TTFT drops from 900 ms to 90 ms, while TTST remains 32 ms/token. The 810 ms savings equals the time to generate approximately 25 tokens. If the LLM generates 500 output tokens (16 seconds at 32 ms/token), the 810 ms TTFT savings represent only a ~5% end-to-end improvement. For streaming applications where users perceive the initial response latency most acutely, the TTFT reduction may be disproportionately valuable despite being a modest fraction of total generation time — but the paper's latency claims should not be misinterpreted as end-to-end speedups.

What evidence exists in the paper. Section 5.4 provides the above RTX 4090 numbers. Figure 5 focuses exclusively on TTFT scaling, not end-to-end latency. The paper does not measure or report end-to-end latency for any of the LongBench tasks, which makes it difficult for practitioners to estimate the effective improvement for their specific workload without knowing their typical output lengths. The batch inference discussion in Section 3.4 briefly mentions that pointer-based sharing could improve throughput (by enabling larger batch sizes), but this is not a latency improvement per-query — it is a throughput improvement from higher concurrency.

Mitigation status. The paper does not attempt to extend Prompt Cache to decoding acceleration. It positions the work as complementary to other optimizations that target decoding, and notes in the Conclusion (Section 6) that "GPU primitives for sharing attention states across concurrent requests" could reduce TPOT as well as TTFT, but this is future work. The limitation is inherent to the approach: during decoding, each new token must attend to the full accumulated cache, and the cached prompt modules are already present in that cache regardless of whether Prompt Cache or baseline KV Cache was used for prefill. There is no obvious mechanism for Prompt Cache to accelerate the per-token computation beyond what KV Cache already provides.

6.2 The Attention Masking Approximation Breaks Cross-Module Reasoning, With No Experimental Validation of the Proposed Mitigation

The assumption or constraint. Prompt Cache encodes each prompt module independently, confining attention computation to the span of each module. The paper acknowledges that this introduces an "attention masking effect" (Section 3.3): "Prompt Cache confines attention score computation to the span of each prompt module, masking the attention states across modules." This is an approximation relative to the baseline, where every token in the prompt attends to every other token. The paper states that this masking "can enhance or degrade output quality depending on the semantic independence of the modules," and proposes scaffolding — a mechanism where groups of modules are encoded together with full cross-module attention — as the solution for cases where modules are semantically dependent. However, Section 3.3 describes scaffolding architecturally without presenting any experimental evaluation of it: "At the cost of additional memory, we allow users to specify 'scaffolds', which are sets of prompt modules that are encoded together... When all prompt modules in a scaffold are imported in a prompt, the attention states of the scaffold overrides the individual attention states."

The consequence. The accuracy results in Table 1 are generated without scaffolding, using only independent module encoding. This means the paper's accuracy preservation claim applies specifically to tasks where modules are sufficiently independent that cross-module attention is not necessary. For tasks that require cross-module reasoning — connecting facts distributed across multiple documents, comparing passages, or resolving references between modules — independent encoding may degrade accuracy, and the paper provides no evidence about whether scaffolding can recover it. The Passage Retrieval results in Table 1 are the clearest signal of this limitation: Llama2 7B drops from 7.50 to 4.25 (-3.25), and Llama2 13B drops from 9.08 to 6.50 (-2.58), both outside the paper's stated 2.5-point threshold. Passage Retrieval inherently requires comparing passages to identify the most relevant one — the one task in the LongBench suite most dependent on cross-document attention — and it shows the largest accuracy degradation. The paper does not discuss this result or analyze why it deviates, leaving practitioners without guidance on whether (a) this represents a fundamental limitation of independent encoding, (b) scaffolding would fix it, or (c) the task is just noisy at low accuracy levels.

More broadly, the paper does not characterize what "semantic independence" means operationally — there is no metric, heuristic, or test that a practitioner can use to determine whether their modules are independent enough for Prompt Cache to work without quality loss. The scaffolding mechanism is architecturally sound but experimentally unvalidated: no accuracy measurements, no latency cost measurements, and no memory overhead quantification are provided for scaffolded modules. A practitioner deciding whether to adopt Prompt Cache cannot know whether their task requires scaffolding, what the memory cost of using scaffolding would be, or whether scaffolding even solves the accuracy problem it is designed to address.

What evidence exists in the paper. Table 1 provides accuracy results for independent encoding only, showing Passage Retrieval degradation that the paper does not discuss. Section 3.3 describes scaffolding conceptually. There is no scaffolded accuracy evaluation, no scaffolded latency measurement, and no comparison of independent vs. scaffolded encoding on any task. The paper does not analyze which LongBench tasks might require cross-module attention or measure the degree of cross-module dependency in any task.

Mitigation status. The paper identifies scaffolding as the architectural solution but does not evaluate it. This is a significant gap because scaffolding is the mechanism that would make Prompt Cache applicable to cross-module reasoning tasks — without validation, the approach's accuracy guarantees are implicitly limited to tasks with independent modules, and the scaffolding mechanism is effectively a design proposal rather than a demonstrated capability. The paper does not flag scaffolding evaluation as future work; it is presented as a feature of the system, but one that remains unmeasured.

6.3 Schema Encoding Cost Is Unaccounted For in the Headline Latency Numbers

The assumption or constraint. The latency reductions reported in Figures 3, 4, and 5 measure TTFT during inference after prompt modules have been encoded and stored in memory. The paper does not account for the one-time cost of encoding schemas — running the full self-attention computation over each prompt module to produce the cached (k, v) tensors. This encoding step requires computing attention for every module in the schema, which collectively may represent a substantial computation. The paper mentions encoding in Section 3.3 ("The first time the attention states of a prompt module are needed, they must be computed and stored in the device memory, which we refer to as prompt module encoding") but does not measure its cost or include it in any reported performance metric.

The consequence. The omission of encoding cost is acceptable for workloads where schemas are encoded once and reused many times — the cost is amortized across all prompts that import those modules. However, the paper does not characterize the amortization threshold: how many prompts must reuse a module before the encoding cost is recovered by inference savings? This depends on the module's size (encoding cost scales as O(n²) for a module of length n) and the fraction of prompts that import it. For a deployment with a dynamic document pool where new documents are added frequently, the encoding cost could be significant relative to the total inference volume. For a RAG system that ingests thousands of new documents daily, encoding all of them into prompt modules might consume considerable GPU time before any inference latency is saved. The paper provides no framework for modeling this tradeoff or determining whether a given workload's reuse patterns justify the encoding investment.

Additionally, the schema itself must be parsed and tokenized, position IDs must be assigned, and modules must be stored in memory. These are one-time costs per schema, but for applications with many schemas or dynamically generated schemas (e.g., from the Python-to-PML compiler), the cumulative overhead could be non-trivial. The paper does not measure schema parsing or module tokenization time.

What evidence exists in the paper. Section 5.4 provides memory copy latency measurements (3.79 ms for host-to-host, 5.34 ms for host-to-device, 0.23 ms for device-to-device for 5K tokens), which represent only the retrieval cost at inference time. The encoding cost — computing the attention states in the first place — is not measured anywhere. Table 2 provides memory overhead per token but not encoding latency per token. The paper does not report encoding time for the LongBench schemas, the total number of schema modules encoded across all experiments, or the inference-to-encoding compute ratio. Figure 5 shows only inference-time latency for already-encoded modules.

Mitigation status. The paper does not discuss encoding cost amortization or provide a model for the encoding-inference cost tradeoff. The Conclusion (Section 6) mentions "GPU cache replacement strategies" and "prefetching" as future system-level optimizations, which implicitly acknowledge that module management (when to encode, when to evict, when to prefetch) is a concern, but no analysis of encoding cost or amortization is provided. For practitioners, this means the headline "8× GPU speedup" numbers assume that modules are already encoded — the actual speedup including the amortized encoding cost depends on workload-specific reuse frequency, which is not characterized.

6.4 The Memory Overhead of Attention State Caching Limits Applicability to Large Models and Document Collections

The assumption or constraint. Prompt Cache stores precomputed (k, v) attention states for every prompt module, and the memory required scales with the total number of cached tokens across all modules. Table 2 quantifies the per-token memory overhead: Llama 7B requires ~0.5 MB per token, Llama 70B requires 2.5 GB per 1K tokens, and Falcon 180B requires 4.53 MB per token — meaning that a 1K-token document cached for Falcon 180B would consume approximately 4.5 GB. These numbers assume 16-bit floating point precision and account for storing both key and value tensors across all attention heads and layers.

The consequence. The memory constraint creates a fundamental tension between the desire to cache many documents (to maximize reuse opportunities) and the limited capacity of GPU HBM (typically 40–80 GB for datacenter GPUs). For Llama 70B, caching just 16 documents of 1K tokens each would consume 40 GB — the entire memory capacity of an A100. This means that for large models and large document collections, GPU memory storage is infeasible, and modules must be stored in CPU DRAM with host-to-device copying at inference time. CPU memory can scale to terabytes and accommodate much larger caches (a 1000-document collection for Llama 70B would require ~2.5 TB, feasible on a server with sufficient RAM), but the latency advantage drops substantially when modules are fetched from CPU rather than GPU memory — from 5–10× to 1.5–3×, as shown in Figure 3.

The paper acknowledges this in Section 5.5: "Conversely, for larger models like Llama 70B, caching a 1K length module would command a substantial 2.5 GB of memory per document, which leaves CPU memory as the only option for prompt module storage." However, the paper does not evaluate Prompt Cache with any model larger than 13B — all latency and accuracy experiments use 7B or 13B models. The claim that Prompt Cache works for larger models is based on the theoretical memory-per-token calculation, not on empirical evaluation. For Falcon 180B, the memory overhead is severe enough that even CPU memory may be strained for large document collections, and the host-to-device transfer cost (proportional to 4.53 MB/token × number of cached tokens) could become a significant fraction of the latency savings. The paper does not characterize where the crossover point lies — at what model size and cache size does the memory copy overhead negate the computational savings?

What evidence exists in the paper. Table 2 provides per-token memory overhead for several model sizes. The latency experiments in Figures 3, 4, and 5 use only 7B models (Llama2 7B, with one 13B comparison in Table 1 for accuracy). The paper notes in Section 5.1 that it uses "LLMs that fit within the memory capacity of a single GPU (40 GB)," which explains why larger models were not tested but also means the scaling claims for model size are extrapolated rather than measured. Figure 5 shows that the latency advantage grows with model size (7B → 13B adds 220 ms for baseline vs. 30 ms for Prompt Cache), which is consistent with the theoretical scaling, but the memory constraint is not reflected in any latency measurement — the experiments that would reveal memory pressure (large models running with CPU-memory-stored modules, or eviction under memory constraints) are not conducted.

Mitigation status. The paper identifies KV cache compression (Zhang et al., 2023) as "an avenue for future research in prompt caching techniques" (Section 5.5) to reduce memory overhead but does not implement or evaluate any compression approach. The suggestion of a caching hierarchy using both GPU and CPU memory (Section 4.1) and the mention of "GPU cache replacement strategies" (Section 6) indicate awareness of the memory management problem, but these are presented as future work rather than evaluated features. For practitioners, the memory overhead numbers in Table 2 provide a concrete basis for estimating whether their model size and document collection can fit in available memory, but the lack of evaluation beyond 13B and the absence of cache eviction strategies mean that deploying Prompt Cache at production scale requires solving memory management problems that the paper identifies but does not address.

6.5 Evaluation Is Limited to a Single Benchmark Suite and Model Scale Range, With No Demonstration on Production-Scale Deployments

The assumption or constraint. All latency and accuracy experiments use the LongBench suite with models in the 7B–13B parameter range. The hardware evaluation spans consumer and datacenter GPUs (RTX 4090, A40, A100) and two CPU platforms, which provides hardware diversity but does not test Prompt Cache in the deployment scenarios where its benefits would be most impactful: large-scale serving with hundreds of concurrent users, models at 70B+ scale, or dynamic workloads with varying cache-hit ratios. The paper states in Section 4 that it uses "LLMs that fit within the memory capacity of a single GPU (40 GB)" and notes that "Prompt Cache can benefit systems aiming for high throughput as well via reduced computation" (Section 2.3) but does not evaluate throughput, concurrency, or multi-GPU serving.

The consequence. Several practical questions about Prompt Cache's real-world deployment remain unanswered. First, the paper does not evaluate how Prompt Cache interacts with batching: the batch inference memory optimization described in Section 3.4 (pointer-based sharing of KV cache blocks) is not measured. Would the reduced memory footprint from shared modules actually translate to larger batch sizes and higher throughput, as claimed? Second, the paper does not test Prompt Cache in a multi-user serving scenario with realistic request patterns — varying cache-hit ratios, interleaved requests from different schemas, and bursty workloads that might stress the cache retrieval pipeline. Third, the evaluation does not include models at the scale where Prompt Cache's theoretical advantage is largest (Section 5.4 claims the advantage "quadratically increases with model size"), meaning the most compelling use case — accelerating inference for very large models with long contexts — is extrapolated rather than demonstrated. Fourth, the paper does not compare Prompt Cache to alternative acceleration techniques (FlashAttention, continuous batching, quantization) in combination, making it difficult to assess whether the speedups are additive or overlapping.

Additionally, the LongBench datasets represent a specific task distribution (document QA, summarization, code completion) and module structure (self-contained documents). The paper's qualitative examples (Figures 6–8) demonstrate applications with more complex schema structures (nested modules, unions, parameterization), but these are not evaluated quantitatively for accuracy or latency at scale. The paper's strong accuracy preservation claim is based on document-QA tasks where modules are independent; it is unclear whether the same accuracy preservation would hold for the more complex, interdependent module structures shown in the use cases.

What evidence exists in the paper. All latency numbers come from single-prompt inference on LongBench. Throughput, batching, concurrency, and multi-GPU experiments are absent. The accuracy evaluation covers 8 LongBench tasks on 4 model configurations, all in the 7B–13B range. The qualitative use cases (Figures 6–8) show single-example outputs with latency numbers but no aggregate accuracy metrics. The paper does not report 95th or 99th percentile latency, which is critical for production serving where tail latency determines SLO compliance. The batch memory optimization (3.4) is described with a hypothetical example (100 requests, 2K tokens, 1K shared) but not benchmarked.

Mitigation status. The paper does not claim to evaluate production-scale deployment, but it also does not adequately scope its claims. The abstract states improvements "ranging from 8× for GPU-based inference to 60× for CPU-based inference," which is accurate for the measured TTFT in the evaluated configurations but may not generalize to the throughput, tail latency, or combined-optimization scenarios that production deployments care about. The paper's positioning of Prompt Cache as "a foundational component for future LLM serving systems" (Section 6) appropriately frames it as a mechanism to be integrated into larger systems rather than a complete serving solution, but the evaluation should be read as a demonstration of the mechanism's potential rather than a validation of production readiness.

6.6 The Discontinuous Position ID Property Is Validated Only on RoPE and ALiBi Models at Small Scale, With No Analysis of Failure Modes

The assumption or constraint. Prompt Cache depends on the empirical finding that "LLMs can operate on attention states with discontinuous position IDs" without accuracy loss (Section 3.1). The paper validates this by demonstrating accuracy preservation on Llama2 (RoPE), MPT (ALiBi), and Falcon (RoPE) at 7B scale. However, the paper does not analyze why these models tolerate position gaps, what properties of the positional encoding or training distribution enable this tolerance, or under what conditions it might fail. The adaptations described in Section 4.2 for RoPE and ALiBi are presented as straightforward engineering changes (lookup tables for rotation matrices and bias terms, respectively), but the paper does not test edge cases: very large position gaps (e.g., jumping from position 100 to position 10,000), long sequences of consecutive gaps, or prompts where the cached and uncached segments interleave densely.

The consequence. Without understanding the limits of the discontinuous position ID property, practitioners cannot predict whether Prompt Cache will work for their specific model architecture, training procedure, context length, or prompt structure. The property is validated on two encoding families (RoPE and ALiBi) but not on learned absolute position embeddings (BERT, GPT-2, OPT), which the paper claims require "no alterations" in Section 4.2 but does not test. This claim is theoretical — learned embedding tables support discontinuous lookups by design — but the model's training may not have exposed it to discontinuous position sequences, so generalization is not guaranteed. A GPT-2 model trained exclusively on contiguous text might exhibit degraded attention patterns when given position IDs with large gaps, even though the embedding table lookup is technically valid.

The accuracy results in Table 1 show that for the tested configurations, the property holds within ~2.5 percentage points for most tasks. However, this validation is at the aggregate accuracy level — the paper does not analyze where the model makes errors with Prompt Cache vs. baseline, whether the errors are concentrated at position boundaries between cached and uncached segments, or whether the errors correlate with gap size. The Passage Retrieval degradation (7.50 → 4.25 for Llama2 7B) could reflect either the attention masking effect (cross-module attention disabled) or a position-discontinuity artifact — the paper does not disentangle these. A controlled experiment that varied position gaps while holding module content and masking constant would isolate the position discontinuity effect, but no such experiment is reported.

What evidence exists in the paper. Table 1 provides indirect validation through accuracy preservation across three architectures. The implementation adaptations in Section 4.2 demonstrate that discontinuous position IDs can be supported with minimal code changes. There is no analysis of attention patterns at position boundaries, no measurement of how gap size affects accuracy, and no testing beyond 13B scale. The paper does not discuss whether the property might degrade with model scale (a model with more attention heads and layers might be more sensitive to position inconsistencies) or with fine-tuning (a domain-adapted model might have learned position-specific features that break under gaps).

Mitigation status. The paper treats the discontinuous position ID property as an empirical finding rather than a claim requiring proof. The accuracy results in Table 1 serve as the validation, and the paper does not attempt to characterize boundaries, analyze failure modes, or test additional encoding schemes. The property is a genuine discovery — prior work had not identified or exploited it — but the paper's validation is narrow (two encoding families, one model scale range, one benchmark suite). For practitioners using models outside the tested set, particularly very large models, non-standard positional encoding schemes, or heavily fine-tuned models, the discontinuous position ID property should be validated on their specific configuration before relying on it for production inference.

7. Implications and Future Directions

How This Work Changes the Landscape

Prompt Cache does not introduce a new model architecture, training objective, or attention mechanism. It shifts the conversation about LLM inference efficiency from how to make attention computation faster to whether attention computation is necessary at all for content that has already been processed. This is a genuine reframing rather than an incremental speedup. The field's existing optimization toolkit—FlashAttention, PagedAttention, quantization, pruning, speculative decoding—all accept the premise that every prompt must be processed from scratch. Each technique makes that processing faster, more memory-efficient, or more parallel, but none challenges the fundamental assumption that the prefill phase is unavoidable. Prompt Cache challenges exactly that assumption: it demonstrates that for prompts with reusable structure, the prefill phase can be bypassed almost entirely for cached content, replacing O(n²) attention computation with O(n) memory copy.

The magnitude of this shift should not be overstated. This is not a paradigm shift on the order of the Transformer itself or the discovery of scaling laws—it is a systems-level insight that applies to a specific, though large, class of LLM workloads. The paper is careful about scope: Prompt Cache accelerates only the prefill phase, only for prompts that can be expressed via a schema, and only when the schema's modules are semantically independent enough that attention masking does not degrade output quality. Within that scope, however, the reframing is powerful. It converts inference from a pure-computation problem into a caching problem, opening a design space—cache sizing, replacement policies, prefetching heuristics, multi-level storage hierarchies—that the LLM serving community has barely begun to explore.

The contribution is also a reconciliation of conflicting practical intuitions about LLM deployment. System builders have long observed that production prompts are highly repetitive—the same system messages, document pools, and template structures appear across thousands of queries—but until Prompt Cache, there was no principled mechanism for exploiting this repetition at the model level. Prefix sharing in PagedAttention (Kwon et al., 2023) captured the special case where prompts share an identical beginning, but the general case—arbitrary shared segments appearing at different positions across prompts—was considered intractable due to positional encoding constraints. Prompt Cache shows that it is not only tractable but can yield order-of-magnitude latency improvements, by making two non-obvious moves: fixing positions in a schema rather than per-prompt, and empirically discovering that models tolerate the resulting discontinuous position IDs. This converts a vague intuition ("redundancy exists") into a concrete mechanism ("precompute, store, and concatenate attention states by module").

The paper also makes verifier-free attention state reuse a first-class concept. Prior work on cross-request attention reuse—specifically AttMemo (Feng et al., 2023)—used embedding similarity heuristics to identify reusable states, introducing a verification step (computing and comparing embeddings) that added overhead and approximation error. Prompt Cache's schema-based approach eliminates verification entirely: modules are identified by explicit markup tags, making reuse an O(1) cache lookup rather than a similarity search. This is a structural rather than heuristic approach to reuse, analogous to how compiled languages use type signatures rather than runtime type checking to guarantee correctness. The schema is a correctness contract, not a probabilistic guess.

What research directions become more attractive as a consequence of this work? First, attention state management as a systems problem: caching, eviction, prefetching, compression, and tiered storage of attention states are no longer speculative—they have a demonstrated mechanism (Prompt Cache) and a measured benefit (up to 10× TTFT reduction on GPU). This invites follow-up work on cache replacement policies optimized for attention states (which have unique properties: position-anchored, schema-scoped, large per-entry memory footprint), compression techniques that exploit the structure of key-value tensors across layers, and memory allocators designed for variable-sized attention state blocks. Second, schema-based prompt engineering: the idea that prompt structure carries computational semantics (not just textual semantics) suggests a new role for prompt authoring tools, where schemas serve as compiler intermediate representations that encode both human-readable structure and machine-exploitable caching hints. Third, modular LLM architecture: if attention states can be assembled from independent modules without accuracy loss for sufficiently independent content, this suggests that LLMs might be trained to be robust to modular attention assembly in the first place—a "cache-aware" training objective that explicitly encourages the model to tolerate attention masking at module boundaries.

What directions become less attractive? The paper provides evidence that sophisticated runtime methods for detecting attention state reuse—embedding similarity search, dynamic prefix matching, online clustering of prompts—may be unnecessary complexity. Prompt Cache achieves exact, reliable reuse through a simple structural contract (the schema) at zero runtime search cost. Unless a deployment cannot express its prompts in a schema (e.g., fully free-form user input with no reusable structure), the structural approach is strictly simpler and more efficient than heuristic detection. This suggests that research effort is better spent on schema design, compilation, and optimization than on runtime similarity-based reuse detection. Additionally, the paper implies that purely faster attention kernels (FlashAttention and its successors) have a ceiling on how much they can improve prefill latency—they make O(n²) faster by a constant factor, while Prompt Cache reduces it to O(n) for cached content. For workloads with high cache-hit ratios, architectural attention reuse offers asymptotic gains that kernel optimization cannot match, suggesting that the two approaches are complementary but that attention reuse deserves at least as much research investment as kernel tuning for long-context serving.

Follow-Up Research This Work Enables

Systematic characterization of the discontinuous position ID boundary. The paper validates that models with RoPE and ALiBi tolerate position gaps at 7B–13B scale on LongBench tasks. A strong follow-up would systematically vary gap size (position jumps of 100, 1K, 10K, 100K tokens), gap frequency (one gap vs. many interleaved gaps), and module position within the sequence (gap at the beginning, middle, or end of the assembled prompt) while measuring both aggregate accuracy and per-position attention entropy. This would establish the operating envelope: at what gap magnitude does the property break down? Does it degrade gradually or fail catastrophically? Does model scale matter—does a 70B Llama2 model, with more attention heads and layers, exhibit different tolerance than a 7B model? The experiment should include models with learned absolute position embeddings (GPT-2 family), which the paper claims require "no alterations" but never tests, to validate or falsify that claim. A negative result—e.g., finding that GPT-2 accuracy degrades above a gap of 512 tokens—would establish a boundary condition that practitioners need to know.

Scaffolding evaluation and cross-module attention recovery. The paper describes scaffolding as the mechanism for recovering cross-module attention but does not evaluate it. A direct experiment would construct a synthetic task where the correct answer depends on information distributed across two or more modules (e.g., "Document A states revenue was $X; Document B states costs were$Y; what was profit?"), compare accuracy with independent encoding vs. scaffolded encoding, and measure the memory overhead of storing both individual and scaffold states. This would answer: does scaffolding actually recover cross-module attention to baseline levels? Is the recovery complete (within statistical noise of baseline) or partial (some residual accuracy gap)? How does accuracy scale with the number of modules in a scaffold—does a 10-module scaffold maintain quality? The Passage Retrieval result in Table 1 (Llama2 7B dropping 7.50 → 4.25 without scaffolding) provides a natural starting point: re-run Passage Retrieval with the document set encoded as a scaffold and measure whether accuracy returns to baseline. A negative result—scaffolding does not fully recover accuracy—would indicate that the attention masking approximation causes irreversible information loss that joint encoding cannot repair, fundamentally limiting Prompt Cache's applicability to interdependent modules.

Cache replacement policies for attention states under memory pressure. Prompt Cache identifies the memory capacity constraint (Table 2: 0.5 MB/token for Llama 7B, 2.5 GB per 1K tokens for Llama 70B) but does not implement or evaluate cache eviction. A systems follow-up would implement and benchmark multiple replacement policies—LRU, LFU, size-aware variants, schema-aware policies that exploit union structure (evict all members of a union together), and predictive prefetching based on access patterns—on a workload with realistic query traces from a RAG system or document QA service. The key metric is effective TTFT under a fixed memory budget as a function of cache-hit ratio; the research question is whether simple policies (LRU) suffice or whether attention-state-specific policies (e.g., evicting the largest modules first to free space for many small modules, or prioritizing modules that appear in union groups with correlated access) yield significant improvements. The experiment should measure both CPU and GPU memory configurations, since the two tiers have different capacity-latency tradeoffs, and should include churn (new modules being encoded and added to the cache while old ones are evicted) to reflect production dynamics. The paper's encoding cost—unmeasured in the current work—should be included in the total-cost accounting: encoding a new module after a cache miss adds a one-time latency penalty that must be amortized over subsequent hits.

Prompt Cache with retrieval-augmented generation (RAG) at production scale. The paper identifies RAG as a natural application but does not evaluate it. A strong follow-up would deploy Prompt Cache in a realistic RAG pipeline: a retrieval system serves documents from a large corpus (e.g., 10K Wikipedia articles or a legal document database), each retrieved document is treated as a prompt module, and user queries are served with the retrieved documents as context. The experiment would measure end-to-end latency (including retrieval time, module encoding on first access, and TTFT) as a function of corpus size, document length distribution, and query rate. Key questions: at what corpus size does the memory overhead of caching all documents exceed available CPU RAM? What is the amortization threshold—how many queries must reference a document before the encoding cost is recovered by inference savings? How does Prompt Cache compare to the alternative of using a smaller retrieval context (fewer documents per query) to reduce baseline prefill latency? This experiment would bridge the gap between the paper's microbenchmarks and the production RAG scenarios it claims to benefit.

Training models for modular attention tolerance. Prompt Cache's attention masking is an approximation that works because the tested models happen to tolerate it for independent modules. A more principled approach would be to train models to expect modular attention assembly, making the tolerance explicit rather than incidental. A training-experiment follow-up would modify the pretraining or fine-tuning objective to include attention masking over module-like boundaries—e.g., during training, randomly partition the input sequence into "modules" with masked cross-module attention and a special token indicating module boundaries—so the model learns to process modularized input without quality loss even when modules are semantically interdependent. The evaluation would compare Prompt Cache accuracy on cross-module reasoning tasks (like Passage Retrieval) between a standard model and a modularity-aware trained model, both using independent encoding without scaffolding. A positive result—the trained model matches baseline accuracy on interdependent modules where the standard model degrades—would eliminate the scaffolding tradeoff entirely, making Prompt Cache applicable to arbitrary prompt structures without the memory overhead of joint encoding. This connects to broader research on compositional generalization and modular neural architectures.

Prompt Cache for multi-modal and multi-turn inference. The paper evaluates text-only, single-turn prompts. A natural extension is to multi-modal models (where prompt modules might include encoded images, audio spectrograms, or video frames alongside text) and multi-turn conversations (where each turn's context includes the conversation history, parts of which are shared across turns—system messages, shared document context, previous turns that are identical across multiple conversation threads). For multi-modal models, the key question is whether the discontinuous position ID property extends to cross-modal position spaces (e.g., an image encoded at positions 0–255 and text at positions 1000–2000, with a gap) and whether attention masking across modalities introduces different artifacts than within a single modality. For multi-turn conversations, the experiment would model a customer-support scenario where multiple users have independent conversations with the same system prompt and shared knowledge-base documents, and measure whether reusing attention states for the shared context across conversation threads yields cumulative latency savings that scale with the number of concurrent sessions. The batch memory optimization (pointer sharing across prompts in a batch) becomes particularly relevant here, as concurrent conversations naturally form batches with high module overlap.

Practical Applications and Downstream Use Cases

Enterprise document QA and knowledge-base serving. The most direct application maps to the LongBench evaluation: an organization deploys an LLM to answer questions about a fixed corpus of documents—legal contracts, policy manuals, technical documentation, medical guidelines. The documents are encoded once as prompt modules and cached in CPU or GPU memory. When employees submit questions, the relevant documents are retrieved and assembled as modules alongside the query text. With Prompt Cache's CPU-memory configuration (1.5–3× TTFT reduction, Figure 3), a query that previously took 3 seconds to process documents before generating the first answer token now takes 1–2 seconds. With GPU-memory storage (5–10×, Figure 3), the same query drops to 300–600 ms—fast enough for interactive use. The paper's accuracy results (Table 1) show that for document QA tasks (NarrativeQA, 2WikiMultihopQA, MuSiQue), output quality is preserved within 2.5 points across Llama2, MPT, and Falcon, meaning the latency improvement does not trade off against answer quality. The memory overhead (Table 2) provides a concrete capacity planning tool: a 10K-document corpus averaging 2K tokens per document, cached for Llama 7B, would require approximately 10 GB of GPU memory or a trivial amount of CPU RAM, both well within typical server capacities.

Templated agent and tool-use systems with parameterized prompts. The paper's parameterization mechanism (Section 3.2.2) and the trip-planning example (Figure 8) directly apply to LLM-based agents that use structured prompt templates for tool invocation. Consider a robotics system where an LLM translates natural language commands into action sequences: the prompt includes a fixed system message (defining the robot's capabilities and output format), a library of available tool descriptions (gripper control, navigation, perception), and a parameterized command template where the specific user instruction fills the parameter slot. Without Prompt Cache, every command processes the entire template from scratch—the system message and tool descriptions are recomputed identically each time. With Prompt Cache, the system message and tool library are encoded once as modules. Each new user command only requires computing attention for the parameterized command slot (the user's specific instruction), reducing TTFT from hundreds of milliseconds to tens of milliseconds (the paper reports 75 ms → 54 ms on GPU for the trip-planning example, with a far more complex template). For latency-sensitive robotics applications where command-to-action delay must be minimized, this reduction is practically significant.

Educational and personalized tutoring systems with feature-based module selection. The personalization example (Figure 7) demonstrates a pattern where user profiles are constructed from a set of feature modules—grade level, proficiency, learning style, assessment type—with mutual exclusion within categories expressed via unions. An educational LLM serving thousands of students could pre-encode all possible profile descriptors (e.g., five grade levels, five proficiency levels, three learning styles, four assessment types = 17 modules total, far smaller than the student population) and assemble each student's prompt by selecting one module per union category plus the uncached question text. The memory overhead is tiny (17 modules × ~200 tokens each × 0.5 MB/token for Llama 7B ≈ 1.7 GB), and every student query benefits from full attention reuse for the structured profile content. The paper's accuracy preservation on diverse benchmarks and models (Table 1) suggests that the independent encoding of profile modules—where "grade level" and "learning style" are semantically independent categories—will not degrade output quality. The union mechanism also provides a clean way to manage feature categories: adding a new learning style only requires encoding one new module within the existing union's position range, not restructuring the entire schema.

Code generation and repository-level context. The code generation example (Figure 6) illustrates how Prompt Cache can apply to software development tools where an LLM needs access to multiple source files as context. Each source file (class, module, or function) is encoded as a prompt module. When a developer requests code generation that should reference existing code, the relevant modules are imported into the prompt alongside the generation request. On GPU inference with CodeLlama 7B, the paper reports TTFT dropping from 924 ms to 93 ms when all code context is cached—a ~10× reduction that transforms the interaction from a noticeable pause to near-instantaneous. For IDE-integrated coding assistants where latency directly affects developer flow, this makes the difference between a tool that interrupts concentration and one that feels responsive. The modular approach maps naturally to how code is organized: files, classes, and functions already have names and boundaries that correspond to prompt module definitions, and the union mechanism handles mutually exclusive choices (e.g., importing either the production or test version of a database module). The main practical constraint is memory: a large codebase with thousands of files would exceed GPU memory if all are cached, requiring either CPU-memory storage (with the lower 1.5–3× speedup) or a cache replacement policy that keeps only frequently-referenced files in GPU memory—a management problem the paper identifies as future work but does not solve.

When to Prefer Prompt Cache

The paper does not articulate a systematic decision rule comparing Prompt Cache against named alternative inference optimization techniques (FlashAttention, quantization, speculative decoding, PagedAttention alone). It positions Prompt Cache as an orthogonal and complementary optimization rather than an alternative to these methods, stating that it "can work with any Transformer architecture compatible with KV Cache" and that other techniques "optimize the implementation efficiency of attention rather than eliminating redundant computation across prompts" (Section 2.3). The paper's evaluation compares Prompt Cache only to baseline KV Cache with no cross-prompt reuse, not to alternative acceleration strategies in a head-to-head tradeoff framework.

The implicit deployment guidance from the paper's evidence is:

Prompt Cache provides the largest relative benefit when:

• A significant fraction of prompt tokens come from a limited, pre-identifiable set of reusable text segments (documents, system messages, templates, source files) that are referenced across many queries
• The reusable segments are sufficiently self-contained that cross-module attention is not critical for task accuracy (or sufficient GPU memory exists to use scaffolding as a fallback)
• Inference latency, particularly time-to-first-token, is the binding constraint on user experience—typical for interactive applications with long input contexts and short-to-medium output lengths
• The model and module storage fit within available memory: GPU HBM for maximum speedup (5–10×), CPU DRAM for moderate speedup (1.5–3×) with larger cache capacity

Prompt Cache provides diminishing or negligible benefit when:

• Prompts are predominantly unique and unstructured, with no recurring text segments that can be meaningfully modularized (e.g., free-form creative writing requests, one-off factual questions with no shared context)
• The output is extremely long relative to the input, making per-token decoding latency dominate end-to-end response time and diluting the impact of prefill acceleration
• Cross-module attention is essential for the task, the memory budget cannot accommodate scaffolding, and independent encoding causes unacceptable accuracy degradation (as hinted by the Passage Retrieval results in Table 1)
• The model is so large that even CPU memory cannot accommodate the required document cache (e.g., Falcon 180B with a 1,000-document corpus at 4.5 GB per 1K-token document would require ~9 TB, exceeding typical server RAM)

The paper does not provide the quantitative thresholds (minimum cache-hit ratio for net benefit, minimum reuse frequency to amortize encoding cost, maximum position gap before accuracy degrades) that would make this into a precise decision rule. Those thresholds would need to be established by the follow-up experiments outlined above.