ArXiv: 2401.06104

🎯 Pitch

A decoder-only transformer with a KV cache is just an RNN with an infinitely growing hidden state—and by simply keeping only the tokens with the highest attention scores, you can slash the cache to 1/8 its size with almost no performance loss, boosting throughput up to 4.8×. No retraining, no recent-token bias: the model naturally learns to stash just a few special tokens (the first token, punctuation, possessives) and throw almost everything else away.

1. Executive Summary

This paper demonstrates that decoder-only transformers can be reformulated as unbounded multi-state RNNs—a generalized RNN variant where the hidden state is a matrix with one row per history token rather than a single vector—and then shows that bounding this multi-state by applying a compression policy effectively converts transformers into fixed-memory recurrent models. Through experiments on four long-range tasks (PG-19 language modeling, SQuALITY summarization, QASPER question answering, and long-form story generation) using LLaMA-2, Mistral, and Yi models, the authors introduce TOVA (Token Omission Via Attention), a training-free compression policy that retains tokens with the highest attention scores at each decoding step (contrasting with baselines like Window attention, Window+i, and H2O that fix a recent-token window). TOVA matches the full model's performance using as little as 1/8 of the original key-value cache size, yielding up to 4.8× higher throughput and successful extrapolation to 70K tokens, while establishing that pretrained transformers empirically behave as bounded MSRNNs on most tasks and that the first token, punctuation, and possessive endings are disproportionately retained—with most other tokens being safely discardable.

2. Context and Motivation

The Core Problem: The Transformer-RNN Divide Is a False Dichotomy

The paper addresses a fundamental conceptual gap in how the NLP community understands neural architectures. Transformers (Vaswani et al., 2017) are universally described as non-recurrent: they process sequences by attending to all tokens simultaneously through the self-attention mechanism, giving each token direct access to every other token's representation. RNNs, by contrast, maintain a hidden state that is updated step by step, carrying information forward through time. These are taught as architecturally distinct paradigms—the former replacing the latter as the dominant approach for NLP around 2017–2018.

The paper argues this dichotomy is misleading for decoder-only transformers, which dominate modern LLM deployment. During autoregressive generation, a decoder transformer produces tokens one at a time. To generate token t+1t+1, the model must compute attention over all previously generated tokens (11 through tt). In practice, the key and value vectors for those previous tokens are stored in a KV cache (Radford et al., 2019; Pope et al., 2022) to avoid recomputation. This cache is, structurally, a state that grows with each decoding step—exactly the defining property of a recurrent model. The paper's core theoretical move is to formalize this observation: if we think of the KV cache as a multi-state (a matrix where each row corresponds to one history token), then a decoder transformer is an RNN—specifically, an RNN with an unbounded number of hidden states.

Why does this reframing matter? It is not merely taxonomic. Reconceptualizing transformers as RNNs opens the door to applying RNN-style compression techniques to the transformer's key-value cache. Just as bounded-memory RNNs must selectively forget information, a transformer-as-RNN can be compressed by limiting the number of states it retains. This directly addresses one of the most painful practical bottlenecks in LLM deployment.

The Real-World Bottleneck: The KV Cache Grows Without Bound

The practical problem motivating this work is the linear growth of the KV cache during autoregressive decoding. For each token generated, the model must compute attention over all previous tokens. Since the key and value matrices for those tokens are cached to avoid recomputation, the memory required for the cache grows proportionally to sequence length. For a model with LL layers, HH attention heads, hidden dimension dd, and sequence length tt, the KV cache consumes 2×L×H×t×d2 \times L \times H \times t \times d floating-point values. At typical LLM scales, this becomes enormous.

The paper quantifies this in Table 1: for LLaMA-2-7B generating sequences of length 4,096, the KV cache alone requires 2.18 GB of GPU memory. This memory consumption directly limits two things:

  1. Maximum sequence length: The cache must fit in GPU memory, imposing a hard ceiling on how long a generation or context can be.
  2. Inference throughput: In batched inference, the KV cache is the dominant memory consumer. Larger caches per sequence mean smaller batch sizes, reducing the number of sequences that can be processed in parallel on fixed hardware. Table 1 shows that a full 4,096-token cache limits batch size to 8 on a V100 GPU; compressing the cache to 512 tokens allows a batch size of 70—a nearly 9× increase.

This is not an obscure edge case. LLM inference costs dominate production deployments, and the KV cache is the primary bottleneck. Any technique that compresses the cache without degrading model quality translates directly to lower memory costs, higher throughput, and longer feasible contexts—all without retraining the model.

Prior Approaches and Where They Fall Short

The paper identifies several existing lines of work that address KV cache compression, each with specific limitations:

Window attention (Wang et al., 2019; Beltagy et al., 2020; Zaheer et al., 2020) is the simplest approach: keep only the most recent kk tokens in the cache, discarding everything older. This is a First-In-First-Out (FIFO) policy. The problem is obvious: information from early in the sequence is completely lost once the window slides past it. For tasks requiring retrieval of distant information—common in long-document QA or summarization—window attention fails catastrophically. The paper's Figure 3 confirms this: the Window baseline (purple line) achieves perplexities in the thousands on PG-19 at small multi-state sizes, essentially degenerating to random performance.

Window+i (Xiao et al., 2023; Han et al., 2023) improves on this by keeping both a fixed window of recent tokens and the first ii tokens (typically i=1i=1 or i=4i=4). This is motivated by the "attention sink" phenomenon: the first token often accumulates disproportionately high attention scores and serves as a kind of "summary" token. Window+i substantially outperforms Window, but it has a critical limitation: it is handcrafted. The choice of ii and the window size are fixed hyperparameters, not data-driven. More importantly, it treats all non-recent-non-first tokens as equally disposable, when in reality certain tokens (punctuation, proper nouns, possessive endings) carry disproportionate importance—a fact the paper's own analysis (Section 7.3, Table 2) demonstrates.

H2O (Heavy-Hitter Oracle; Zhang et al., 2023) uses a more adaptive approach: it keeps a fixed window of recent tokens plus a set of "heavy hitters"—tokens with the highest cumulative attention scores across the sequence history. The number of heavy-hitter slots and recent-window slots are typically split evenly (e.g., half and half). While more adaptive than Window+i, H2O still has an inductive bias toward recent tokens: it reserves a substantial fraction of the cache for the recent window regardless of whether those recent tokens are actually important. It also uses cumulative attention, which inherently favors early tokens (since they are attended to across more steps, their cumulative scores are higher), potentially crowding out important middle-context tokens.

Training-required approaches (Katharopoulos et al., 2020; Peng et al., 2022; Anagnostidis et al., 2023) modify the transformer architecture or training procedure to produce models with bounded memory from the start. While these can be effective, they cannot be applied to existing pretrained LLMs—they require training from scratch or fine-tuning. Given the enormous cost of pretraining LLMs, methods that work on off-the-shelf models have dramatically higher practical value.

A Unifying Missing Perspective: Transformers as RNNs

The paper identifies a crucial missing piece in prior work: none of these approaches frame the problem in terms of the transformer-RNN connection. The authors position their contribution as filling this conceptual gap by (Section 1):

"In this work, we demonstrate that the autoregressivity of transformers aligns with the core principle of RNNs—preserving a state from one step to the other."

By formally defining decoder transformers as Multi-State RNNs (Section 3), the paper provides a unifying framework that makes cache compression a natural operation: bounding the state size of an RNN is a well-understood problem, and the choice of compression policy corresponds to choosing which states to forget. Prior methods like Window, Window+i, and H2O can all be reinterpreted as specific compression policies within this MSRNN framework (Section 3.3), giving them a common conceptual grounding they previously lacked.

This reframing also highlights a conceptual inconsistency in how the field trains and deploys LLMs. LLMs are trained with a fixed context length (typically 2,048 or 4,096 tokens), which might suggest they are inherently bounded. Yet at inference time, they can process sequences up to whatever fits in memory—they have no architectural limit on length. The paper argues (Section 3.4) that LLMs are truly unbounded MSRNNs, and that the context-length limit during training is an artifact of computational constraints, not a fundamental property. The empirical finding that they behave as bounded MSRNNs (performing well with only a fraction of the full cache) is then an interesting discovery about how they use their capacity, not a tautology.

How the Paper Positions TOVA Relative to Prior Work

TOVA is introduced as a training-free compression policy that makes fewer assumptions than its predecessors (Section 5.1):

"TOVA makes fewer assumptions: it neither fixes a window of recent token-states, nor favors early ones."

Specifically, unlike Window and Window+i, TOVA does not hardcode a recency window. Unlike H2O, it uses instantaneous attention scores (the scores at the current decoding step) rather than cumulative scores, avoiding the bias toward early tokens. It selects which tokens to keep purely based on which ones the model's attention mechanism considers most relevant right now.

The paper also distinguishes TOVA from the broader literature on simplifying transformers (Section 8). Prior work on attention head pruning (Michel et al., 2019), replacing attention with static weights (Hassid et al., 2022), or using efficient attention variants (Choromanski et al., 2021) modifies the model architecture or parameters. TOVA operates at inference time without any modification to the model weights, making it applicable to any pretrained transformer decoder.

The Practical and Theoretical Stakes

The paper's motivation sits at the intersection of two concerns:

Practical (engineering): KV cache memory is the primary bottleneck in LLM serving. Reducing it by 88% (from 4,096 to 512 states) with minimal quality loss—as the paper demonstrates for most tasks—directly translates to 4.8× higher throughput and the ability to serve 9× more sequences in parallel on fixed hardware. This is a concrete cost reduction for any organization running LLM inference at scale.

Theoretical (understanding): The transformer-RNN connection challenges the narrative that these architectures are fundamentally distinct. If transformers are RNNs with a particularly structured state update, then properties we associate with RNNs—difficulty with long-range dependencies (Hochreiter and Schmidhuber, 1997), catastrophic forgetting of early information, the need for compression policies—should also apply to transformers when we look at them through the right lens. The paper's finding that QASPER (a retrieval task requiring access to specific distant details) needs larger multi-state sizes than SQuALITY or language modeling (Section 6.2, comparing Figure 4 and Figure 5) is consistent with this RNN-like behavior: retrieval tasks stress the bounded memory of an RNN in a way that summarization or perplexity evaluation may not.

This dual framing—practical compression method and theoretical reconceptualization—is what distinguishes the paper from prior work that addressed only one side (e.g., Katharopoulos et al., 2020 on the theory, Zhang et al., 2023 on the practice). The paper aims to contribute to both simultaneously, using the theoretical framework to motivate a practical method and using empirical results to validate the theoretical perspective.

3. Technical Approach

3.1 Reader Orientation

This is both a conceptual reframing paper and an empirical methods paper. The system being built is not a new model architecture but rather a way to operate existing pretrained transformer decoders with a fixed, bounded memory budget during inference—specifically, by selectively discarding tokens from the key-value cache at each decoding step to keep it at a constant size. The problem it solves is the unbounded growth of the KV cache during autoregressive generation, which consumes GPU memory linearly with sequence length and is the primary bottleneck limiting batch size, throughput, and maximum context length in LLM serving. The solution's shape is a compression policy that, at each decoding step, decides which token's key-value pair to evict from the cache based on the model's own attention scores, requiring no retraining or fine-tuning and introducing minimal computational overhead.

3.2 Big-Picture Architecture (Diagram in Words)

The architecture has three major conceptual layers:

  1. Multi-State RNN Reformulation (Theoretical Foundation): The decoder transformer is re-expressed as a recurrence where the hidden state is not a single vector but a matrix—specifically, the concatenated key-value pairs for all previously seen tokens. This matrix is the "multi-state." Each row corresponds to one history token and contains both its key vector (used for computing attention scores) and its value vector (used for computing the attention output). The multi-state grows by one row per decoding step, making the transformer an unbounded MSRNN.

  2. Bounding Mechanism (Capacity Limit): The unbounded MSRNN is converted to a bounded one by imposing a fixed maximum size $k$ on the multi-state matrix. When a new token is generated and its key-value pair would cause the cache to exceed size $k$, a compression policy selects one existing row to evict (delete permanently), making room for the new entry. The cache size then remains constant at $k$ for all subsequent steps, regardless of how many tokens are ultimately generated.

  3. TOVA Compression Policy (Selection Rule): The specific policy for choosing which token to evict. At each decoding step, TOVA computes the attention scores of the last query token against all cached keys, averages these scores across attention heads within each layer, and removes the key-value pair corresponding to the lowest averaged attention score. The intuition is that tokens with the lowest attention weight from the current decoding position are least relevant for predicting the next token, and thus are the safest to forget.

Information flows as follows: the transformer processes input tokens autoregressively → each layer computes self-attention, producing attention scores from the current query to all cached keys → the TOVA policy uses these scores (averaged across heads per layer) to identify the least-attended cached token → that token's key-value pair is deleted from the cache → the new token's key-value pair is appended → the process repeats for the next token, with the cache always bounded at size $k$.

3.3 Roadmap for the Deep Dive

  • First, the formal MSRNN definition (Section 3.1 of the paper): what generalizes an RNN to have multiple states, and what the function $g(t)$ controls. This establishes the vocabulary for everything that follows.
  • Second, the transformer-as-MS-RNN mapping (Section 3.2): how the KV cache corresponds to the multi-state matrix, how the layer computation is rewritten as a recurrent update, and why this transformation is exact—no approximation is involved in the unbounded case, which is a crucial conceptual point.
  • Third, the bounding operation (Section 3.3) and the formal specification of TOVA as the eviction rule (Section 4): the attention score aggregation across heads, the argmin selection, and the cache update mechanics. This is the core algorithmic contribution.
  • Fourth, the design rationale: why instantaneous attention scores rather than cumulative, why layer-wise rather than head-wise aggregation, why no fixed recency window—each choice contrasted with alternatives (Window, Window+i, H2O).
  • Fifth, the computational cost and implementation details: what TOVA adds to the standard decoding loop, the torch-like pseudocode, and the memory/throughput implications quantified in Table 1.
  • Sixth, the extrapolation mechanism (Section 7.2): how positional encodings are adjusted when TOVA is used on sequences longer than the pretraining context length—distinct from the compression policy itself but necessary for the 70K-token experiments.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a theoretical reframing and empirical evaluation paper whose core idea is that decoder transformers are structurally equivalent to unbounded Multi-State RNNs, and that by applying a principled compression policy based on attention scores, they can be operated as bounded MSRNNs with minimal performance degradation—while the choice of which tokens to retain matters substantially and is best determined by the model's own attention mechanism rather than handcrafted heuristics.

Formalizing Multi-State RNNs (MSRNNs)

The paper begins by defining a generalized RNN variant that makes the subsequent transformer mapping precise. In a standard RNN, each layer $l$ at time $t$ takes two inputs—the current token representation $x^l_t$ and the hidden state from the previous step $h^l_{t-1}$—and produces two outputs: an updated token representation $x^{l+1}_t$ and a new hidden state $h^l_t$. The defining RNN equation is:

xtl+1,htl=fRNNl(xtl,ht−1l)x^{l+1}_t, h^l_t = f^l_{\text{RNN}}(x^l_t, h^l_{t-1})

where $f^l_{\text{RNN}}$ is the layer function, $x^l_t \in \mathbb{R}^d$ is the input token embedding (or the output from the previous layer), $h^l_{t-1} \in \mathbb{R}^d$ is the previous hidden state vector, and $h^l_t \in \mathbb{R}^d$ is the new hidden state vector.

What it computes: the layer applies its learned transformation to the current input conditioned on the accumulated history, producing an output for the next layer and an updated state for the next time step. The state is a single vector of fixed dimension $d$.

An MSRNN generalizes this by replacing the hidden state vector with a hidden state matrix $H^l_t \in \mathbb{R}^{g(t) \times d}$, where $g(t)$ is a function that determines the number of rows (states) at time $t$. The MSRNN equation is:

xtl+1,Htl=fMSRNNl(xtl,Ht−1l)x^{l+1}_t, H^l_t = f^l_{\text{MSRNN}}(x^l_t, H^l_{t-1})

where $H^l_t \in \mathbb{R}^{g(t) \times d}$ is the multi-state matrix at time $t$, with each row being a $d$-dimensional state vector, and $g(t)$ is a function parameterizing the number of states.

What it computes: the same recurrence as a standard RNN, but the state is now a collection of vectors rather than a single vector. The function $g(t)$ controls the capacity. If $g(t) = 1$ for all $t$, the MSRNN reduces exactly to a standard single-state RNN. If $g(t) = t$, the number of states grows linearly with the sequence position—the MSRNN has unbounded memory. If $g(t) \leq k$ for some constant $k$, the MSRNN has a bounded capacity of at most $k$ states.

Why this form: this generalization is necessary because a transformer's KV cache cannot be represented as a single vector—it inherently contains one key-value pair per token, making it a collection of vectors indexed by token position. The MSRNN formalism provides the minimal abstraction that captures this structure: the state is a matrix whose rows are the per-token states, and $g(t)$ controls whether the memory is bounded or unbounded.

Mapping Transformers to Unbounded MSRNNs

The paper's central theoretical claim is that a decoder transformer layer can be rewritten exactly as an MSRNN layer with $g(t) = t$—that is, an unbounded number of states, one per previously processed token. The mapping works by identifying the multi-state matrix $H^l_t$ with the concatenated key-value cache at layer $l$ after processing $t$ tokens.

Formally, let $q^l_t, k^l_t, v^l_t \in \mathbb{R}^d$ be the query, key, and value projections of the input token representation $x^l_t$ at layer $l$ and time $t$ (the paper omits the multi-head aspect in the main text for brevity, but the mapping extends straightforwardly: each head has its own independent multi-state). The key-value cache at time $t$ consists of all keys and values from positions $1$ through $t$:

Ktl=(k1lk2l⋮ktl)∈Rt×d,Vtl=(v1lv2l⋮vtl)∈Rt×dK^l_t = \begin{pmatrix} k^l_1 \\ k^l_2 \\ \vdots \\ k^l_t \end{pmatrix} \in \mathbb{R}^{t \times d}, \quad V^l_t = \begin{pmatrix} v^l_1 \\ v^l_2 \\ \vdots \\ v^l_t \end{pmatrix} \in \mathbb{R}^{t \times d}

The paper defines the multi-state as the concatenation $H^l_t = (K^l_t, V^l_t)$. The recurrent update from time $t-1$ to time $t$ appends the new key and value vectors as new rows:

(Ktl,Vtl)=((Kt−1lktl),(Vt−1lvtl))(K^l_t, V^l_t) = \left( \begin{pmatrix} K^l_{t-1} \\ k^l_t \end{pmatrix}, \begin{pmatrix} V^l_{t-1} \\ v^l_t \end{pmatrix} \right)

The token output is then computed via standard self-attention over the full cache, followed by the feed-forward network:

xtl+1=FFl(Attnl(qtl,Ktl,Vtl))x^{l+1}_t = \text{FF}^l\left( \text{Attn}^l(q^l_t, K^l_t, V^l_t) \right)

Combining these gives the full MSRNN equation for a transformer layer:

xtl+1,(Ktl,Vtl)=fTRANSl(xtl,(Kt−1l,Vt−1l))x^{l+1}_t, (K^l_t, V^l_t) = f^l_{\text{TRANS}}\left( x^l_t, (K^l_{t-1}, V^l_{t-1}) \right)

where $f^l_{\text{TRANS}}$ encapsulates the self-attention and feed-forward computations.

What it computes: exactly the same mathematical operation as a standard transformer decoder layer—the self-attention over all previous tokens followed by the feed-forward network—but expressed in a form that makes the recurrence explicit. The "hidden state" is the KV cache from the previous step; the "state update" is appending the new key-value pair; the "output" is the transformed token representation.

Why this form matters (and why it is exact, not approximate): this is a rewrite, not a modification. For $g(t) = t$, the MSRNN equation produces identical outputs to the standard transformer formulation. There is no compression, no approximation, no change to the computation. This is critical because it means that any property we derive about the transformer-as-RNN in the bounded case (where $g(t) \leq k$) is a direct consequence of limiting the state size, not an artifact of changing the architecture. The paper is not proposing a new model—it is revealing a structural property that standard transformers already possess.

The multi-head case (which the paper handles by maintaining separate keys and values per head) simply means there are $H$ independent multi-states per layer, each of size $t \times (d/H)$, where $d/H$ is the per-head dimension. TOVA operates independently per layer but aggregates attention scores across heads within each layer (see below for the rationale).

Bounding the Multi-State: The Compression Problem

Given the unbounded MSRNN formulation, the natural next step is to bound it: set $g(t) = \min(t, k)$ for some fixed capacity $k$. When $t \leq k$, all tokens fit in the cache and no compression occurs. When $t > k$, the cache is full, and generating the $(t+1)$-th token requires evicting one existing row to make room.

This creates the state compression problem: which of the $k$ currently cached tokens should be discarded to accommodate the new token? The choice of eviction rule defines a compression policy. The paper notes (Section 3.3) that several existing KV cache compression methods can be interpreted as specific compression policies within this MSRNN framework:

  • Window attention: always evict the oldest token (the one with the smallest positional index), implementing a First-In-First-Out queue. The cache always contains exactly the most recent $k$ tokens.
  • Window+i: always evict the oldest token except the first $i$ tokens are pinned (never evicted). The cache contains the first $i$ tokens plus a sliding window of the most recent $k - i$ tokens.
  • H2O: maintain a fixed window of recent tokens (typically half the cache, $k/2$) and a set of "heavy hitter" tokens (the other $k/2$) selected by cumulative attention scores. Eviction occurs from the non-heavy-hitter recent tokens.

These policies all share a common structure: they predetermine (to varying degrees) which tokens are eligible for eviction based on position rather than purely on the model's current attention distribution.

TOVA: Token Omission Via Attention

TOVA is the paper's proposed compression policy, and it is defined by a single rule (Section 4): at each decoding step, when the cache is full, evict the token with the lowest attention score as assigned by the most recent query token. Formally, let $t > k$ be the current time step, let $A^l_{\text{last}} \in \mathbb{R}^{t-1}$ be the attention weights from the last query token $q^l_t$ to all cached keys in $K^l_{t-1}$, averaged across the $H$ attention heads of layer $l$:

aˉjl=1H∑h=1HAttnhl(qtl,kjl)\bar{a}^l_j = \frac{1}{H} \sum_{h=1}^{H} \text{Attn}^l_h(q^l_t, k^l_j)

where $\bar{a}^l_j$ is the mean attention score that the current query assigns to cached token $j$, $H$ is the number of attention heads, and $\text{Attn}^l_h$ is the attention weight computation for head $h$ in layer $l$. The token $j^*$ with the minimum averaged score is selected for eviction:

j∗=arg⁡min⁡jaˉjlj^* = \arg\min_j \bar{a}^l_j

The multi-state is then updated by removing row $j^*$ from both the key and value matrices before appending the new token's key-value pair:

(Ktl,Vtl)=((K0:j∗−1lKj∗+1:klktl),(V0:j∗−1lVj∗+1:klvtl))(K^l_t, V^l_t) = \left( \begin{pmatrix} K^l_{0:j^*-1} \\ K^l_{j^*+1:k} \\ k^l_t \end{pmatrix}, \begin{pmatrix} V^l_{0:j^*-1} \\ V^l_{j^*+1:k} \\ v^l_t \end{pmatrix} \right)

where the notation $K^l_{a:b}$ denotes rows $a$ through $b$ inclusive of the key matrix, and $k^l_t, v^l_t$ are the new key and value projections from token $t$. The cache size remains at $k$ after this update.

What it computes: at each layer and each decoding step, TOVA computes the average attention weight that the brand-new query token assigns to each previously cached token, identifies the cached token receiving the lowest average attention, and deletes it. The new token's key-value pair then takes its place in the cache. This means the cache always contains the $k-1$ tokens that the model's most recent query found most relevant, plus the new token itself.

Why average across heads rather than head-wise: the paper reports preliminary results (Appendix A, Table 3) showing that the layer-wise version (averaging attention scores across all heads in the layer and making a single eviction decision per layer) substantially outperforms the head-wise version (each head independently evicts its least-attended token). For example, at a multi-state size of 256 on PG-19 with LLaMA-2-7B, TOVA-layer achieves perplexity 8.32 versus TOVA-head's 9.55—a gap of over 1.2 perplexity points. The authors attribute this to the layer-wise mechanism requiring agreement among all heads to determine which token is truly unimportant; a token that one head ignores might be critical to another head, and head-wise eviction would lose that information for the head that needed it. Layer-wise eviction only drops tokens that are collectively deemed unimportant.

Why instantaneous rather than cumulative attention scores: H2O uses cumulative attention scores summed across all previous decoding steps to identify "heavy hitters." TOVA uses only the attention scores from the single most recent query. The rationale (implied by the design) is that relevance is time-dependent: a token that was important 100 steps ago may be irrelevant now, and cumulative scores inherently favor early tokens (which have been attended to across more steps, so their cumulative sum is higher). Instantaneous scores reflect the model's current information needs, not its historical attention distribution. This also means TOVA does not need to maintain running sums over the decoding history, simplifying implementation.

Why no fixed recency window: unlike Window+i and H2O, TOVA does not pre-allocate a portion of the cache for recent tokens. If the model assigns high attention to a token from the middle of the sequence and low attention to a recent token, TOVA will keep the middle token and evict the recent one. The paper's analysis (Section 7.3) shows that TOVA does naturally retain a high proportion of recent tokens (73–76% of the cached tokens are "recent," though the paper does not define a precise recency threshold), but this emerges from the attention scores rather than being hardcoded. The remaining 24–27% of tokens are non-recent ones that the model continues to find important—primarily the first token, punctuation marks, possessive endings, and proper nouns (Table 2, Section 7.3).

Why the argmin rather than a probability-based sampling: the paper's description is entirely deterministic—the token with the absolute minimum attention score is evicted. There is no stochasticity, no temperature, no sampling from the attention distribution. This is a design choice favoring simplicity and reproducibility: the policy is fully determined by the model's attention weights, with no hyperparameters to tune for the eviction rule itself (the only hyperparameter is the cache size $k$).

Implementation and Computational Overhead

Algorithm 1 in Appendix B provides a torch-like pseudocode implementation of TOVA, which we can walk through in detail. The function signature takes four arguments: attn_weights (the attention weight tensor of shape [attn_heads, num_queries, num_kv], where num_kv is the current number of cached key-value pairs), k_cache and v_cache (the current key and value caches, each of shape [attn_heads, num_kv, hidden_dim]), and cache_max_size (the desired maximum number of cached entries $k$).

The procedure at each decoding step is:

  1. Check capacity: if num_kv <= cache_max_size, return immediately—no eviction needed.
  2. Extract last query's attention weights: attn_weights[:, -1, :] takes the attention from the most recent (last) query token to all cached keys, producing a tensor of shape [attn_heads, num_kv].
  3. Average across heads: mean(attn_weights[:, -1, :], dim=0) computes the mean attention weight for each cached position, producing a vector of length num_kv. This is the $\bar{a}^l_j$ defined above.
  4. Find the minimum: argmin(mean_attn_weights) returns the index $j^*$ of the cached token with the lowest averaged attention score.
  5. Evict by concatenation: the key and value caches are updated by concatenating the rows before $j^*$ with the rows after $j^*$, effectively removing row $j^*$. The new token's key-value pair is then appended (in the actual decoding loop, this append happens after the eviction; Algorithm 1 shows only the eviction step).

What this costs computationally: the additional operations per decoding step are (a) extracting the last row of the attention weight tensor (essentially free—a tensor slice), (b) averaging across the head dimension (a reduction over $H$ elements for each of $k$ cached positions, so $O(H \cdot k)$ operations), and (c) an argmin over $k$ elements ($O(k)$). Since $k$ is typically 256–2048 and $H$ is typically 32, this amounts to a few thousand to tens of thousands of floating-point operations per layer per decoding step—negligible compared to the self-attention computation itself, which is $O(k \cdot d)$ per head per query. The paper does not report TOVA-specific latency measurements, but the throughput improvements in Table 1 (4.8× at $k = 512$ vs. full $k = 4096$) are driven entirely by the reduced memory footprint allowing larger batch sizes, not by any reduction in per-token computation—in fact, per-token computation is slightly higher with TOVA due to the argmin step, but this is dwarfed by the batching benefit.

Memory reduction (Table 1, first row): the KV cache memory scales linearly with $k$. For LLaMA-2-7B with sequence length $k$, Table 1 reports memory consumption of 0.15 GB for $k = 256$, 0.28 GB for $k = 512$, up to 2.18 GB for $k = 4096$ (the full pretraining context length). These numbers are for a batch size of 1; with batched inference, the KV cache memory multiplies by batch size.

Throughput improvement (Table 1, last row): the key metric is relative throughput when the maximum batch size is employed. With a full cache of 4,096 tokens, a V100 GPU can fit at most 8 sequences in parallel for decoding (each sequence's KV cache consumes 2.18 GB, and the model parameters consume additional memory). With $k = 512$, the maximum batch size increases to 70, and the total throughput (tokens per second across all sequences) is 4.8× higher than with the full cache. This multiplier accounts for both the increased batch size and any per-token overhead from TOVA's eviction logic.

Extrapolation Beyond Pretraining Context Length

When using TOVA to process sequences longer than the model's pretraining context length (e.g., the 70K-token PG-19 experiments in Section 7.2), an additional mechanism is required: the positional encodings for cached tokens must be adjusted, because the model was never trained on position indices beyond 4,096 and attention patterns for out-of-distribution positions can be pathological (Press et al., 2022).

TOVA itself only controls which tokens are retained, not what position indices they are assigned. When a token originally at position $i$ is retained in the cache while the sequence has advanced to position $t \gg 4096$, the token must be assigned a new positional encoding that falls within the model's trained range. Otherwise, the attention mechanism would receive position indices of 30,000 or 70,000, which the positional encoding function was never trained to handle.

The paper's solution (Section 7.2) is to compress the gap between adjacent retained tokens' positions. For two consecutive cached tokens that were originally at positions $i$ and $i + g$ (where $g$ is the number of tokens that have been evicted between them), the new assigned gap is:

gnew={gif g≤10ln⁡(ln⁡(g))if g>10g_{\text{new}} = \begin{cases} g & \text{if } g \leq 10 \\ \ln(\ln(g)) & \text{if } g > 10 \end{cases}

What it computes: for small gaps (10 or fewer tokens between retained positions), the gap is kept unchanged to preserve local sensitivity—the model can still distinguish adjacent or near-adjacent tokens. For larger gaps, the double logarithm $\ln(\ln(g))$ aggressively compresses the distance. For example, if 1,000 tokens have been evicted between two retained tokens ($g = 1000$), the new gap is $\ln(\ln(1000)) \approx \ln(6.908) \approx 1.93$, which is then rounded to an integer positional offset of 2. This means a gap of 1,000 original positions is represented as a gap of only 2 positions in the compressed encoding.

Why this form: the paper states that preliminary experiments with $\ln(g)$ and $\sqrt{g}$ showed inferior results, implying that more aggressive compression (the double logarithm) is necessary to keep the accumulated position indices within the pretraining range for very long sequences. The threshold of 10 for preserving exact local gaps is a heuristic that balances local precision (important for nearby-token interactions) against global compression (necessary to fit the entire sequence history into the positional encoding range).

Why this matters for TOVA specifically: without this positional adjustment, TOVA could not operate on sequences longer than the pretraining context length, because even though token representations are retained in the cache, the positional encodings attached to them would be out-of-distribution. The compression function is an auxiliary mechanism that enables TOVA's extrapolation capability, and it is independent of the eviction policy itself—it could be used with any compression policy (as it is with Window+4 in the same experiments).

Note that the paper does not describe a mechanism for dynamically updating these positional encodings at each step as the cache evolves; the description in Section 7.2 is brief and focused on the gap compression function. The implicit assumption is that when a token is retained in the cache, its positional encoding is recomputed based on the compressed gaps between it and its neighbors, though the exact implementation (e.g., whether this happens at every step or only when a neighbor is evicted) is not specified.

Design Choices: Why TOVA Over Alternatives?

The paper's design choices for TOVA can be understood as responses to specific limitations in prior compression policies:

Against Window: pure recency-based eviction catastrophically discards early information. TOVA retains any token the model continues to attend to, regardless of age, which is why Window fails completely at small cache sizes (perplexity in the thousands in Figure 3) while TOVA remains within 0.4 perplexity points of the full model at $k = 512$.

Against Window+i: fixing the first $i$ tokens is an improvement over pure Window (the model does tend to attend heavily to the first token, as the paper confirms in Figure 9), but it is a rigid heuristic. The paper's ablation in Appendix A (Table 3) shows that adding explicit first-token preservation to TOVA (TOVA-layer+1 and TOVA-layer+4) yields results "relatively unchanged" from plain TOVA-layer, indicating that TOVA already learns to retain the first token without being forced to. More importantly, Window+i cannot retain important middle-context tokens (proper nouns, punctuation, possessive endings) that TOVA keeps based on attention scores.

Against H2O: H2O's use of cumulative attention scores inherently favors early tokens and reserves a large fraction of the cache for a recent window regardless of whether those recent tokens are actually important. TOVA eliminates both biases—instantaneous scores are position-agnostic, and no portion of the cache is pre-allocated for recency. At a multi-state size of 256 on PG-19 (Table 3), TOVA-layer achieves perplexity 9.53 versus H2O-head's 10.22 and H2O-layer's 10.20, a consistent advantage of 0.6–0.7 perplexity points across all H2O variants.

Against head-wise TOVA (the self-ablation): the decision to average across heads rather than evict head-independently is empirically motivated by Appendix A (Table 3). At multi-state size 256, TOVA-head (9.55) is worse than both TOVA-layer (8.32) and H2O (10.20–10.22). This is a substantial gap and confirms that head-wise eviction leads to information loss: when each head independently drops its least-attended token, different heads drop different tokens, and information that one head still needs is destroyed by another head that happened not to attend to it. Layer-wise eviction forces consensus: a token is only dropped when all heads collectively assign it the lowest average importance.

Summary of the Technical Contribution

TOVA is, at its core, a one-line decision rule applied at each transformer layer during autoregressive decoding: "evict the cached token with the lowest mean attention score from the current query." The technical contribution is not the complexity of this rule—which is almost trivial—but rather (a) the MSRNN framework that makes it natural to view cache eviction as state compression, (b) the empirical demonstration that this simple, training-free rule matches or exceeds the performance of more complex, handcrafted policies (Window+4, H2O), and (c) the ablation evidence showing that the specific choices (layer-wise averaging, instantaneous scores, no fixed window) are individually important and collectively superior to alternatives.

4. Key Insights and Innovations

Innovation 1: The Transformer-RNN Connection Is Not an Analogy — It's an Identity

The paper's most intellectually distinctive contribution is the claim that decoder transformers are RNNs — specifically, unbounded Multi-State RNNs — and that this is an exact equivalence, not a loose analogy or an architectural modification. Section 3.2 demonstrates that the standard transformer decoder computation can be rewritten as an MSRNN recurrence with g(t) = t without changing a single operation. The KV cache is the hidden state; appending new key-value pairs is the state update; the self-attention and feed-forward computation is the output function. Every decoder transformer ever deployed has been an RNN all along — the field simply has not described it that way.

This reframing matters because it collapses a conceptual wall that has structured NLP research for over half a decade. Prior work treating transformers and RNNs as fundamentally distinct architectures (Vaswani et al., 2017 set this framing; the field has largely inherited it) has led to separate research communities, separate intuitions about failure modes, and separate toolkits for addressing limitations. When Katharopoulos et al. (2020) showed that transformers could be used recurrently, they modified the attention mechanism (linear attention) to make it recurrent — this was an architectural proposal, not a claim about standard transformers. When Peng et al. (2022) presented transformers with bounded memory, they treated boundedness as a design choice for specific transformer variants (Linformer, window attention), not as a property latent in all decoders. This paper's move is bolder: the identity holds for all decoder transformers, pretrained or deployed, without any modification. The consequence is that every insight, technique, and diagnostic from decades of RNN research becomes potentially applicable to transformers, but with a crucial difference — transformers have a multi-state (one row per token), not a single compressed vector, which means that compression is optional rather than mandatory.

The significance of this reframing extends beyond KV cache compression (the paper's empirical focus). If transformers are RNNs with explicit per-token states, then phenomena like catastrophic forgetting, difficulty with long-range retrieval, and the need for gating mechanisms — all well-studied in the RNN literature (Hochreiter and Schmidhuber, 1997; Arjovsky et al., 2016) — should manifest in transformers when state capacity is limited. The paper's finding that QASPER (a retrieval task) requires larger multi-state sizes than SQuALITY or language modeling (comparing Figure 5 to Figures 3–4) is exactly this pattern: retrieval stress-tests the bounded memory of an RNN in a way that summarization does not. This is not a new empirical finding about transformers — it is a predictable consequence of the MSRNN identity that would have been hypothesized from RNN first principles.

The identity also challenges the narrative that "transformers solved the long-range dependency problem." They solved it architecturally by giving every token direct access to every other token, but this solution depends on unbounded state size. When the state is bounded — as TOVA does, and as any memory-constrained deployment must do — the long-range dependency problem returns. Transformers are not immune to the fundamental memory-accuracy tradeoff that RNNs face; they have merely been operating in a regime (unbounded state) where the tradeoff is invisible. This is a diagnostic insight rather than a method: it predicts when and where compressed transformers will struggle, not just that they sometimes do.

Innovation 2: Attention Scores Are a Sufficient and Optimal Eviction Signal — No Handcrafted Heuristics Needed

The paper's second conceptual contribution is demonstrating that the model's own instantaneous attention scores constitute a minimal, sufficient, and superior signal for deciding which tokens to evict from the cache. This is not obvious a priori: prior work invested substantial effort in designing heuristics for which tokens to retain. Window attention (Wang et al., 2019) assumes recency is what matters. Window+i (Xiao et al., 2023; Han et al., 2023) adds the heuristic that the first token is special. H2O (Zhang et al., 2023) adds two heuristics: a fixed recency window plus cumulative attention scoring, which implicitly assumes that historical importance is additive. Each of these policies encodes a theory about what kinds of tokens are important — theories that are approximately correct but miss important cases.

TOVA makes virtually no assumptions. It does not hardcode recency. It does not pin the first token. It does not compute cumulative scores. It asks a single question: "which cached token does the model's most recent query attend to the least?" and evicts that one. The finding (Figures 3–5, Appendix A Table 3) that this simple rule consistently outperforms all handcrafted alternatives — often by substantial margins (e.g., 0.6–0.7 perplexity points over H2O at small cache sizes) — is significant beyond the raw numbers. It implies that the model already knows which tokens are important, and the best compression policy is simply to ask it at each step and trust the answer.

This is a conceptual inversion of how the field has approached KV cache compression. Prior work treats the model as a black box whose internal dynamics must be reverse-engineered by external heuristics (recency windows, attention sinks, cumulative weighting). TOVA treats the model as an oracle about its own information needs: the attention mechanism, which exists precisely to decide which tokens to incorporate when computing the next representation, directly provides the eviction signal. The mechanism that uses the cache also manages it. There is something philosophically elegant about this — the model is not being compressed by an external agent applying domain knowledge; it is compressing itself using the same attention mechanism that defines its computation.

The ablation in Appendix A (Table 3) adds a further layer of significance: when TOVA is enhanced with explicit first-token preservation (TOVA-layer+1, TOVA-layer+4), performance is "relatively unchanged." This means TOVA's attention-based selection already keeps the first token without being told to — a finding confirmed by Figure 9, which shows the first token is retained for the entire sequence across all cache sizes. The heuristic that Window+i encodes explicitly, TOVA rediscovers automatically from the attention signal. This suggests that many of the patterns observed in prior work (attention sinks, first-token importance, punctuation retention) are emergent properties of attention that any sufficiently data-driven policy would replicate, making handcrafted heuristics not just suboptimal but redundant.

The layer-wise versus head-wise finding (Table 3: TOVA-layer at 8.32 perplexity versus TOVA-head at 9.55 for cache size 256) adds a subtle but important refinement. It is not enough to ask each head independently which token it finds least important, because different heads attend to different tokens, and a token that one head ignores may be critical to another. Layer-wise eviction forces a consensus: only tokens that are collectively deemed unimportant by all heads are dropped. This suggests that attention heads have complementary information needs, and compression should preserve information that any head requires — an insight that would not emerge from treating attention as monolithic.

Innovation 3: Transformers Empirically Behave Like Bounded RNNs — Most Tokens Can Be Forgotten

The third contribution is an empirical discovery about how pretrained transformers use their apparently unbounded memory: they behave, in practice, as if they have a bounded effective capacity. The paper shows that across three of four tasks (language modeling, summarization, and story generation), TOVA with a multi-state size of 512 — one-eighth of the full 4,096-token context — matches the full model's performance to within a fraction of a perplexity point or ROUGE score (Figures 3, 4, 6). This is not a claim that 512 tokens are sufficient for all tasks (QASPER needs more, as Figure 5 shows), but rather that for the tasks where the full model performs well, the full model's cache size is dramatically over-provisioned.

This finding reframes how we should think about the transformer's KV cache. The cache is not being fully utilized; it is a sparse representation where most tokens contribute negligibly to the model's decisions. The paper's analysis in Section 7.3 quantifies this: across PG-19 examples, layers, and positions, only 73–76% of the tokens kept by TOVA are "recent," and a small set of token types — punctuation, possessive endings, proper nouns — persist in the cache far longer than average (Table 2, Table 5). This indicates that the model's effective memory is structured: a dense window of recent context plus a sparse set of "sticky" tokens that carry syntactic or semantic importance disproportionate to their frequency.

Why is this significant beyond the practical compression gains? Because it provides an existence proof that transformers learn to operate with bounded memory during pretraining, even though their architecture imposes no such bound. The pretraining objective (next-token prediction with a fixed context window) does not explicitly penalize memory usage, yet the resulting model's attention patterns concentrate on a small fraction of available tokens. This suggests that efficient memory use is an emergent consequence of the learning dynamics, not something that must be engineered into the architecture. If transformers naturally learn to rely on a sparse subset of context, then bounded-memory variants (like TOVA-compressed models) are not fundamentally altering the model's computation — they are merely removing the dead weight that the model was already ignoring.

This has implications for architecture design. If a 4,096-token cache can be compressed to 512 tokens with minimal quality loss, then the information-theoretic content of the context representation is far lower than its nominal capacity. This raises the question: could a model trained from scratch with a bounded 512-token cache match the performance of an unbounded model, if the training objective explicitly taught it to compress? The paper does not answer this (it focuses on post-hoc compression), but the finding makes the question credible in a way that prior work on bounded-memory transformers (which required architectural modifications) did not.

The QASPER exception (Figure 5) is equally informative. On this retrieval-focused task, TOVA needs half the full cache (2,048 tokens) to approach topline performance, and the gap between TOVA and baselines is larger (up to 5 F1 points). This confirms that retrieval tasks genuinely require access to distant, specific information — the kind of information that bounded-memory RNNs have always struggled with (Hochreiter and Schmidhuber, 1997). The fact that TOVA outperforms Window+4 even on this task (where Window+4's inductive bias toward recency is directly harmful) but still falls short of the full model shows that attention-based eviction is the best we can do without expanding memory, but it cannot create information that has been evicted. This is the fundamental limit of any bounded-memory approach.

Innovation 4: The Practicality-Throughput Argument: Training-Free Compression Enables 4.8× Throughput Gains Without Retraining Any Model

While throughput improvements are typically considered engineering rather than intellectual contributions, this paper's framing of the throughput argument has a distinctive conceptual dimension. The key insight is not simply that compressing the KV cache increases throughput (this is obvious: smaller cache → more sequences fit in memory → larger batch size → higher throughput). It is that training-free compression policies can achieve these gains without any model modification, making them immediately applicable to every deployed transformer decoder. This is a fundamentally different value proposition from approaches that require architectural changes (Katharopoulos et al., 2020; Peng et al., 2022), retraining (Anagnostidis et al., 2023), or fine-tuning — all of which are non-starters for models whose pretraining cost is measured in millions of dollars.

The numbers in Table 1 make this concrete: with a 512-token cache, TOVA enables a 4.8× throughput increase over the full 4,096-token cache, on existing hardware, with existing pretrained weights, using the same decoding infrastructure. The multiplier comes not from faster per-token computation (TOVA adds a negligible argmin step) but from the 8.75× increase in maximum batch size (70 vs. 8 sequences in parallel). This shifts the cost calculus of LLM deployment: the choice is not between "train a more efficient model" and "live with the memory bottleneck," but between "apply TOVA now, for free" and "invest in a retraining pipeline that may or may not match TOVA's quality-efficiency tradeoff."

What makes this more than an engineering footnote is the paper's demonstration (Figure 3, Figure 4, Figure 6) that the quality-efficiency tradeoff is highly favorable — in many cases, reducing the cache to 1/8 of its original size costs less than 0.4 perplexity points or 1 ROUGE point. This is not a Pareto curve where every unit of compression costs proportional quality; it is a regime change where the first 7/8 of the cache can be eliminated almost for free, and only the last fraction imposes meaningful degradation. Understanding why this regime exists — the sparsity of effective attention, the concentration on a small set of sticky tokens — is the intellectual contribution; the throughput numbers are the empirical manifestation.

The paper also demonstrates (Section 7.2, Figure 7) that TOVA with 512 cached tokens can extrapolate to 70K input tokens — nearly 18× the pretraining context length — with only a 0.5 perplexity degradation from shorter sequences. This is not a throughput result (the cache size is fixed at 512 throughout, so memory usage is constant regardless of total sequence length), but a capability result: bounded-memory transformers can process arbitrarily long sequences, limited only by the positional encoding adjustment (the ln(ln(g)) gap compression heuristic in Section 7.2). This directly challenges the assumption that transformers are inherently limited to their pretraining context length and cannot generalize to longer inputs — an assumption that has motivated substantial research into length-extrapolation techniques (Press et al., 2022; Chen et al., 2023). TOVA shows that length generalization emerges naturally from bounded-memory operation, provided the positional encoding scheme handles out-of-distribution positions.

5. Experimental Analysis

Evaluation Methodology

  • Dataset. The paper evaluates on four long-range tasks spanning three categories. For language modeling, the paper uses the PG-19 test set (Rae et al., 2020)—a corpus of 100 full-length books averaging ~70K tokens each, widely used for benchmarking long-range language models. For long-range understanding, the paper uses two tasks from ZeroSCROLLS (Shaham et al., 2023): SQuALITY (Wang et al., 2022), a question-focused summarization dataset where the model must read a long story and answer a question in a paragraph, and QASPER (Dasigi et al., 2021), a QA dataset based on the S2ORC corpus of scientific papers where answering questions requires retrieving specific details from long texts. For text generation, the paper prompts models to generate long stories using a custom instruction prompt that requests "at least 4,000 words," "at least 20 named characters," "3 countries and 9 cities," "10 chapters," and "a lot of plot twists," then evaluates the outputs using GPT-4 as a comparative judge. All datasets except text generation have ground-truth answers; text generation is evaluated via pairwise comparison by GPT-4 (gpt-4-0613) with position-swapped duplicate evaluations to control for GPT-4's known positional bias (Wang et al., 2023)—a win is only counted if the same approach is preferred in both position orders.

  • Base model(s). The paper experiments with three leading transformer decoder LLM families at the ~7B parameter scale. For language modeling, it uses LLaMA-2-7B (Touvron et al., 2023b), Mistral-7B (Jiang et al., 2023), and Yi-6B (Young et al., 2024). For long-range understanding, it uses instruction-tuned variants: LLaMA-2-chat-7B, Mistral-Instruct-7B, and neural-chat-7B (Lv et al., 2023), all shown to excel at instruction-following tasks. For text generation, it uses MythoLogic-13B (Padar, 2023), a LLaMA-2-13B variant fine-tuned for story generation (the only 13B model used—the larger scale is justified by the complexity of the generation task). The paper selects these models to be "representative of the capabilities of many contemporary LLMs" (Section 4) and to test whether the MSRNN findings generalize across model families and fine-tuning regimes.

  • Metrics. For language modeling, the paper reports perplexity on the PG-19 test set using full training sequence length chunks of 4,096 tokens with efficient masking (Appendix E). For SQuALITY, the primary metric is the geometric mean of ROUGE-1/2/L scores computed against the gold summary, following the evaluation protocol of Shaham et al. (2023). For QASPER, the metric is F1 score, following Dasigi et al. (2021). For text generation, the metric is GPT-4 win rate: for each of 100 seeds, GPT-4 compares the TOVA-generated story to the full-model story side by side, asked to choose "(A) first is better, (B) second is better, or (C) equal quality"; results are reported as percentages of TOVA wins, ties, and topline wins, with ties and positional swaps handled as described above. For throughput experiments, the metrics are absolute memory consumption (GB), maximum batch size achievable on a single V100 GPU, and relative throughput (tokens/sec) when decoding 512 sequences totaling ~2M tokens at each cache size. For the extrapolation experiment, the metric is average perplexity over the first 70K tokens of all PG-19 books with at least that length (52 books), with each data point representing the average over all previous tokens.

  • Baselines. The paper compares TOVA against four baseline compression policies, all training-free and applicable to off-the-shelf pretrained models. (1) Window (Wang et al., 2019): implements First-In-First-Out—at each step, the oldest cached token is evicted, so only the most recent k tokens are retained. (2) Window+i (Xiao et al., 2023; Han et al., 2023): extends Window by additionally pinning the first i tokens (never evicting them), keeping k - i recent tokens; the paper uses i = 4 as the main variant after initial i ∈ {1, 4} ablations showed Window+4 performs slightly better than Window+1. (3) H2O (Zhang et al., 2023): maintains a fixed window of recent tokens plus "heavy hitter" tokens selected by cumulative attention scores throughout the sequence; the cache is split evenly between recent windows and heavy-hitters (typically half and half), and the paper uses the head-wise variant following the original authors' recommendation after preliminary experiments showed similar performance between head-wise and layer-wise versions (Appendix A). (4) Topline (full unbounded model): the standard transformer with no compression applied, using all 4,096 tokens of the pretraining context length—not strictly a "compression baseline" but the upper bound against which all compression policies are measured. For the long-range understanding tasks, an additional baseline is truncation: presenting the model with only the first k tokens of the input (matching the compressed cache size), which serves as a control to distinguish whether compression policies improve over simply reading less text. The paper abandons Window (but retains Window+4) after initial language modeling results (Figure 3) confirmed Window's catastrophic failure at small cache sizes, and similarly drops H2O from subsequent tasks.

  • Generation budget / compute accounting. The universal unit of compute is the multi-state size k—the maximum number of key-value pairs retained in the cache per layer. This is the direct analog of a generation budget in the cache compression context: a smaller k means less memory consumed but potentially degraded quality. All policies, including TOVA, are evaluated at multi-state sizes in exponential scales of 2^j: for language modeling, j ∈ {6, 7, ..., 12} corresponding to k ∈ {64, 128, 256, 512, 1024, 2048, 4096}, where 4,096 is the full context length; for long-range understanding, j ∈ {8, 9, ..., 12} corresponding to k ∈ {256, 512, 1024, 2048, 4096}; for text generation, k ∈ {256, 512, 1024}. The paper does not charge any additional compute for the eviction policy itself (the argmin operation in TOVA is negligible compared to self-attention, as discussed in Section 3), and all comparisons at a given k are fair because they consume identical KV cache memory. For throughput experiments, memory and batch size are measured at each k on a single V100 GPU with bfloat16 precision. For the extrapolation experiment, the multi-state size is fixed at 512 while the input sequence grows from 10K to 70K tokens.

  • Cross-validation / statistical protocol. The paper does not employ cross-validation or statistical significance testing. Results are reported as single-point estimates (perplexity, ROUGE, F1) computed over the full test sets. The text generation evaluation includes 100 seeds with GPT-4 pairwise comparisons and positional swapping to control for order bias, but no confidence intervals or error bars are reported for any metric. The PG-19 language modeling results are computed over the full test set of 100 books (chunked into 4,096-token segments with efficient masking), which provides a large effective sample size. The ZeroSCROLLS tasks (SQuALITY, QASPER) use the standard test splits from Shaham et al. (2023), and exact test set sizes are not specified in the paper but are known to be in the hundreds of examples. This absence of uncertainty quantification is a limitation—particularly for the SQuALITY and QASPER results where test set sizes are moderate and the differences between TOVA and baselines, while consistent, are sometimes small (~1 ROUGE point in Figure 4).

Main Quantitative Results

Language Modeling: TOVA Matches Full-Model Perplexity Using 1/8 of the Cache

Figure 3 presents perplexity results on PG-19 for LLaMA-2-7B, Mistral-7B, and Yi-6B across multi-state sizes from 64 to 4,096. The headline finding is that TOVA consistently achieves perplexity within 0.4 points of the topline using a multi-state size of 512—one-eighth of the full 4,096-token context—across all three model families. For LLaMA-2-7B: at k = 4096 (full context), the topline perplexity is ~7.16; at k = 512, TOVA achieves ~7.41—a degradation of 0.25 perplexity points. At k = 256, TOVA is at ~8.32, roughly 1.16 points above topline. The gap widens at k = 128 (~9.53) and k = 64 (~10+). For Mistral-7B: the pattern is nearly identical—topline at ~7.2, TOVA at k = 512 within ~0.3 points, k = 256 within ~1 point, and larger gaps at smaller cache sizes. For Yi-6B: topline is higher (~9.3), but the relative pattern holds—TOVA at k = 512 is within ~0.3 points, and at k = 256 within ~1.4 points.

Comparing to baselines at the same cache sizes:

  • Window (purple line): catastrophic failure at small k. At k = 512, LLaMA-2 Window perplexity exceeds 2,000; at k = 256, it exceeds 3,000. Only at k = 2048 does Window begin to approach usable perplexity (~240 at k = 2048 for LLaMA-2). This confirms that purely recency-based eviction is fatal for language modeling, even at moderate compression ratios.
  • Window+4 (green line): substantial improvement over Window but significantly worse than TOVA. At k = 512, Window+4 perplexity on LLaMA-2 is ~7.73 vs. TOVA's ~7.41—a gap of 0.32 points. At k = 256, the gap is larger: ~8.98 vs. ~8.32, a difference of 0.66 points. Window+4 requires k = 2048 to match TOVA's k = 512 performance, a 4× efficiency disadvantage.
  • H2O (red line): performs similarly to Window+4 across most multi-state sizes. At k = 512 on LLaMA-2, H2O achieves ~7.76—comparable to Window+4's ~7.73 but ~0.35 points worse than TOVA. At k = 256, H2O is at ~8.97—again similar to Window+4 (~8.98) and ~0.65 points behind TOVA. H2O shows the same pattern as Window+4 of requiring approximately 2×–4× larger cache sizes to match TOVA.

The baseline model (an unbounded MSRNN with shorter sequence length, i.e., simply truncating the input to k tokens without any compression) performs significantly worse than all compression policies. At k = 256, the baseline (truncated to 256 tokens) achieves perplexity ~17.65—far above TOVA's 8.32—confirming that the compression policies are doing more than just limiting input length; they are selectively retaining which 256 tokens to keep.

A notable pattern across all three models: TOVA's curve is much flatter than the baselines' between k = 512 and k = 4096, indicating that the model derives rapidly diminishing returns from additional cached tokens beyond ~512. The topline itself achieves only ~0.3 perplexity improvement when going from 512 to 4,096 tokens. This is direct evidence for the paper's claim that transformer decoders behave empirically as bounded MSRNNs—their effective capacity is far below their architectural maximum.

Long-Range Understanding: TOVA Outperforms All Baselines, with Task-Dependent Compression Limits

SQuALITY (Summarization): Figure 4 shows ROUGE geometric mean for LLaMA-2-chat, Mistral-Instruct, and neural-chat on the SQuALITY dataset. The headline: TOVA achieves within one ROUGE point of the topline using 1/4 (Mistral and neural-chat) or 1/8 (LLaMA-2-chat) of the full multi-state size, while consistently outperforming Window+4 and truncation baselines.

For LLaMA-2-chat: topline ROUGE is ~19.5. TOVA at k = 512 (1/8 of full) achieves ~18.8—within 0.7 points. At k = 1024, TOVA is at ~19.0—within 0.5 points. Window+4 at k = 512 achieves ~18.0—roughly 0.8 points below TOVA and 1.5 points below topline. The truncation baseline (reading only the first k tokens without any selective retention) performs worst: at k = 512, truncation achieves ~17.0, roughly 1.8 points below TOVA. This gap between TOVA and truncation confirms that the summarization task genuinely benefits from selective access to which tokens are retained beyond the first k.

For Mistral-Instruct: topline is ~19.5. TOVA at k = 512 achieves ~18.5—within 1.0 point, but requires k = 1024 (1/4 of full) to reach within ~0.5 points of topline. Window+4 is ~0.5–1.0 points below TOVA at all cache sizes. neural-chat shows a similar pattern to Mistral, with TOVA needing k = 1024 to reach within 0.5 points of topline.

A notable difference from the language modeling results: the performance ceiling for SQuALITY is reached at larger cache sizes. While language modeling shows diminishing returns beyond k = 512, SQuALITY continues to improve up to k = 2048 before plateauing. This suggests summarization requires access to a larger working set of tokens than next-token prediction, presumably because identifying what to summarize requires broader context than predicting the next word.

QASPER (Retrieval QA): Figure 5 shows F1 scores for the same instruction-tuned models on QASPER. The headline is qualitatively different from the previous tasks: TOVA still outperforms all baselines, including Window+4, but now requires half the full multi-state size (k = 2048) to approach topline performance, and the gap between TOVA and baselines is substantially larger—reaching beyond 5 F1 points in some configurations.

For LLaMA-2-chat: topline F1 is ~24. TOVA at k = 2048 (half of full) achieves ~22—within 2 F1 points, while at k = 1024 (quarter) it drops to ~18. At k = 512, TOVA achieves ~12—roughly half the topline performance. Window+4 at the same cache sizes is markedly worse: at k = 2048, Window+4 achieves ~17 (~5 F1 points below TOVA); at k = 1024, ~12 (~6 points below TOVA); at k = 512, ~8 (~4 points below TOVA). The truncation baseline collapses entirely at small cache sizes: ~12 F1 at k = 1024 (similar to TOVA at k = 2048) and ~6 at k = 512.

For Mistral-Instruct: the topline is dramatically higher (~42 F1), and TOVA shows a similar pattern. At k = 2048, TOVA achieves ~39—within 3 points of topline. At k = 1024, ~30. At k = 512, ~18. Window+4 is consistently 6–10 F1 points below TOVA across all cache sizes. neural-chat shows a more compressed range (topline ~30) but the same relative ordering: TOVA outperforms Window+4 by 3–5 F1 points at all cache sizes.

This task-dependence is one of the paper's most informative results. QASPER is fundamentally a retrieval task—answering questions requires locating specific sentences or facts buried in long scientific papers. The fact that TOVA needs larger cache sizes here confirms the paper's theoretical framing: when transformers are bounded MSRNNs, they re-encounter the fundamental RNN challenge of retrieving distant information (Hochreiter and Schmidhuber, 1997; Arjovsky et al., 2016). The larger gap between TOVA and Window+4 on QASPER (vs. SQuALITY or language modeling) reveals that Window+4's inductive bias toward recency is particularly harmful for retrieval—if the relevant fact appeared in the middle of the paper, Window+4 may have already evicted it in favor of recent-but-irrelevant tokens, while TOVA's attention-based retention has a higher probability of keeping it. Yet even TOVA cannot fully close the gap to the unbounded model, because some retrievable facts are inevitably among the evicted tokens.

Text Generation: TOVA Approaches Topline Quality with Modest Cache Sizes

Figure 6 presents the GPT-4 evaluation of story quality for the MythoLogic-13B model comparing TOVA to the full topline at three multi-state sizes. The headline: with a multi-state size of 1,024 (1/4 of full context), TOVA-generated stories are indistinguishable from the full model in GPT-4's judgment—winning 5% of comparisons, losing only 6%, and tying 88%. At smaller cache sizes, TOVA quality degrades gracefully: at k = 512, TOVA loses 19% of comparisons, ties 71%, and wins 10%; at k = 256, TOVA loses 47% of comparisons, ties 47%, and wins 6%.

An important sidebar finding: cache compression reduces generated story length. The full model generates stories averaging 1,566 tokens. At k = 1024, this is maintained (no reduction reported, implying ~1,566). At k = 512, the average drops to 1,503 tokens—a ~4% reduction. At k = 256, it drops to 1,361 tokens—a ~13% reduction. The paper does not speculate on the mechanism, but plausible explanations include: (a) the model, having less context to draw from, reaches an "end of story" state earlier, or (b) important long-range narrative dependencies that sustain longer stories are lost when the cache is too small. This is a genuinely new finding—none of the prior compression policy papers report generation length effects.

The GPT-4 evaluation protocol addresses positional bias by presenting each story pair twice with swapped positions and only counting a win if the same approach is preferred in both orders. Cases where the model stops before reaching the memory limit (producing truncated outputs) are dropped from comparison since both stories would be identical up to the truncation point. This is a reasonably careful evaluation design, though the paper acknowledges (Limitations) that GPT-4 evaluation "is far from perfect, and will most likely not catch the full breadth of evaluating text quality."

Throughput and Memory Efficiency: TOVA Enables 4.8× Higher Throughput

Table 1 quantifies the practical impact of cache compression on inference efficiency using LLaMA-2-7B on a single V100 GPU. The numbers (for decoding 512 sequences totaling ~2M tokens at sequence length 4,096):

  • Memory per sequence (batch size 1): 0.15 GB (k = 256), 0.28 GB (k = 512), 0.56 GB (k = 1024), 1.11 GB (k = 2048), 2.18 GB (k = 4096, full). Memory scales linearly with k as expected since the KV cache stores 2 × L × H × k × d values.
  • Maximum batch size: 139 (k = 256), 70 (k = 512), 35 (k = 1024), 17 (k = 2048), 8 (k = 4096). The batch size is inversely proportional to k—a 1/k relationship—because model parameters consume fixed memory and the KV cache dominates the batch-dependent memory.
  • Relative throughput: 8.5× (k = 256), 4.8× (k = 512), 3.1× (k = 1024), 1.7× (k = 2048), 1× (k = 4096). Throughput is computed as total tokens decoded per second when the maximum batch size is employed. The 4.8× figure for k = 512 (the size at which TOVA matches full-model performance on language modeling and SQuALITY) is the paper's headline throughput result.

These numbers are computed under the assumption that all sequences in the batch are being decoded simultaneously (the standard batched inference setting). The throughput improvement comes entirely from increased batch size, not from reduced per-token computation—in fact, TOVA adds a small per-token overhead (the argmin step), but this is negligible compared to the memory-bandwidth savings that come from fitting more sequences in GPU memory.

Extrapolation: TOVA with 512-State Cache Processes 70K Tokens

Figure 7 shows average perplexity on the first 70K tokens of PG-19 books using a fixed multi-state size of 512 and the ln(ln(g)) positional encoding compression described in Section 7.2. The headline: TOVA successfully extrapolates to 70K tokens—over 17× the pretraining context length—with perplexity remaining within 0.5 points of the values observed at shorter lengths (e.g., ~7.5 at 70K vs. ~7.0 at 10K), while consistently outperforming Window+4.

TOVA perplexity starts at ~6.85–7.10 for input lengths 10K–20K, rises gradually to ~7.40 by 50K, and reaches ~7.55 at 70K—a total increase of less than 0.7 perplexity points over a 7× increase in sequence length. Window+4, in contrast, starts higher (~7.35 at 10K) and degrades faster, reaching ~8.0–8.1 by 50K–70K—a gap of ~0.5 perplexity points that is maintained throughout. The paper reports only these two policies for the extrapolation experiment, since "models struggle to extrapolate to such long contexts" (Section 7.2) and Window+4 has been shown to support such contexts in prior work.

This result demonstrates that bounded MSRNNs are not inherently limited to their pretraining context length—the combination of attention-based token retention (TOVA) and positional encoding adjustment enables processing of arbitrarily long inputs with constant memory. The 70K-token limit in the experiment is due to the PG-19 dataset (only 52 books are that long), not a fundamental limitation of the approach.

Ablation Studies and Robustness Checks

Window family ablations (Appendix A, Table 3): All Window variants are evaluated on PG-19 with LLaMA-2-7B across cache sizes from 64 to 4,096. Window performs catastrophically (perplexity >1,000) at k ≤ 2048, confirming that pure recency is insufficient. Window+1 (pinning the first token) dramatically improves: at k = 512, it achieves 7.76 vs. Window's >2,000. Window+4 (pinning first 4 tokens) is slightly better than Window+1 at most sizes: at k = 512, 7.73 vs. 7.76; at k = 256, 8.98 vs. 8.97 (essentially identical). The diminishing returns from adding more pinned tokens (beyond 1) suggest that only the very first token matters for the "attention sink" phenomenon.

H2O head-wise vs. layer-wise (Appendix A, Table 3): H2O-head and H2O-layer produce near-identical results across all cache sizes (e.g., at k = 256, 10.22 vs. 10.20; at k = 512, 7.75 vs. 7.76). This contrasts with TOVA, where the layer/head distinction matters substantially (see next item). The paper follows Zhang et al. (2023) and uses the head-wise version for all subsequent experiments.

TOVA head-wise vs. layer-wise (Appendix A, Table 3): This is the most informative ablation for TOVA's design. TOVA-head (each head independently evicts its least-attended token) substantially underperforms TOVA-layer (attention scores averaged across heads, one eviction decision per layer). At k = 256, TOVA-head achieves 9.55 vs. TOVA-layer's 8.32—a gap of 1.23 perplexity points. At k = 512, the gap narrows to 7.90 vs. 7.41 (0.49 points). At k = 128, it is 11.13 vs. 9.53 (1.60 points). TOVA-head is even worse than H2O at some cache sizes (e.g., TOVA-head at 9.55 vs. H2O-head at 10.22 for k = 256), meaning the head-wise version of the paper's own policy is beaten by prior work. The authors attribute this to the layer-wise mechanism requiring "agreement among all heads to determine the importance of specific tokens," preventing the scenario where head A evicts a token that head B still needs.

TOVA with pinned first tokens (Appendix A, Table 3): TOVA-layer+1 and TOVA-layer+4 (enhancing TOVA with explicit preservation of the first 1 or 4 tokens) yield results "relatively unchanged" from plain TOVA-layer. At k = 256, TOVA-layer is 8.32, TOVA-layer+1 is 9.53, TOVA-layer+4 is 9.63—all within a narrow band. At k = 512, the numbers are 7.41, 7.41, 7.41—effectively identical. This is strong evidence that TOVA already learns to retain the first token without explicit instruction, consistent with Figure 9's finding that the first token is kept for the entire sequence. It also confirms that the Window+4 advantage over Window (pinning the first tokens) is a heuristic that TOVA's attention-based mechanism renders redundant.

Policy comparisons at all cache sizes (Table 3 full results): A comprehensive ranking can be extracted from Table 3: across all cache sizes 64–2048, the ordering is consistently TOVA-layer > TOVA-layer+1 ≈ TOVA-layer+4 ≈ Window+4 ≈ H2O-head ≈ H2O-layer > Window+1 > TOVA-head > Window > Baseline (unbounded with shorter sequence). The gap between TOVA-layer and the cluster of Window+4/H2O is largest at intermediate cache sizes (k = 256: 8.32 vs. 8.98/8.97, a 0.65-point gap; k = 128: 7.71 vs. 8.19/8.21, a 0.48-point gap) and narrows as cache size increases (approaching 0 at k = 4096, where all policies converge to the full model).

Positional encoding compression functions (Section 7.2): The paper reports that preliminary experiments with ln(g) and sqrt(g) gap compression functions showed inferior results compared to ln(ln(g)). Specific numbers are not provided, but the selection of the double logarithm implies that more aggressive compression (double-log rather than single-log or square-root) is necessary to keep accumulated positions within the pretraining range for very long sequences while preserving local sensitivity for small gaps (the threshold g ≤ 10 keeping exact positions for nearby tokens).

Base vs. instruction-tuned models on understanding tasks (Appendix F, Figures 10 and 11): The paper reports SQuALITY and QASPER results for base (non-instruction-tuned) versions of the same models. The patterns are qualitatively similar but the absolute scores are lower, confirming that instruction tuning improves task performance but does not change the relative effectiveness of compression policies—TOVA still outperforms Window+4 and truncation for base models.

Critical Assessment

Claim 1: "Transformers can be conceptualized as unbounded multi-state RNNs." This is a theoretical claim, not an empirical one, and the paper's experiments neither prove nor disprove it—the identity in Section 3.2 is a mathematical reformulation that requires no experimental validation. What the experiments do test is the corollary that transformers behave empirically as bounded MSRNNs when their state is limited—and here the evidence is strong. Figures 3 and 4 demonstrate that on language modeling and summarization, performance saturates at cache sizes far below the full context (diminishing returns beyond k = 512 for perplexity, k = 1024 for ROUGE), consistent with the bounded-memory interpretation. However, the evidence is weaker for retrieval (QASPER, Figure 5), where performance continues to improve up to the full k = 4096, suggesting that the "bounded" behavior is task-dependent rather than an inherent property of the model.

Claim 2: "TOVA outperforms several baseline compression policies." Strongly supported across all tasks, models, and cache sizes where the baselines were tested. The language modeling results (Figure 3, Table 3) provide the most comprehensive comparison (Window, Window+4, H2O, and multiple TOVA variants across 7 cache sizes and 3 models). The long-range understanding results (Figures 4 and 5) show consistent TOVA advantage over Window+4, though Window and H2O are dropped from these experiments (the paper states it considers "two policies for the other tasks: TOVA and Window+4, our best baseline" after the language modeling results). This is a reasonable but slightly incomplete comparison—H2O's performance on QASPER would have been informative, since its cumulative attention scoring might have different retrieval characteristics than Window+4's purely recency-based approach. The text generation results (Figure 6) have no baselines at all—only TOVA vs. topline—so we cannot assess whether TOVA's compression advantage extends to generation quality.

Claim 3: "TOVA performs nearly on par with the full model, using in some cases only 1/8 of the original cache size." Supported with important qualifications. On language modeling (Figure 3), 1/8 cache (k = 512) yields perplexity within 0.25–0.4 points of topline across all three models—a genuinely impressive result. On SQuALITY (Figure 4), 1/8 cache (k = 512) is within ~0.7–1.0 ROUGE point for LLaMA-2-chat, but Mistral and neural-chat require 1/4 cache to reach the same proximity. On QASPER (Figure 5), 1/4 cache (k = 1024) is ~6 F1 points below topline—a substantial gap—and even 1/2 cache leaves a 2–3 point gap. On text generation (Figure 6), 1/4 cache (k = 1024) is nearly indistinguishable from topline, but 1/8 cache (k = 512) loses 19% of GPT-4 comparisons—whether this counts as "nearly on par" depends on the deployment threshold. The "1/8" figure in the abstract should be understood as applying primarily to language modeling and (partially) summarization, not as a universal guarantee.

Claim 4: "TOVA translates to 4.8× higher throughput." Substantiated by the batch size and throughput measurements in Table 1, but these are computed under idealized conditions: all sequences in the batch have identical length, the maximum batch size is determined by memory constraints alone (no consideration of computation time or latency), and the comparison assumes the full model operates at k = 4096 (the pretraining context length) rather than at whatever cache size would yield equivalent quality. The 4.8× figure is for k = 512 vs. k = 4096—a comparison that makes sense given the language modeling results (TOVA at 512 matches full model at 4096), but is somewhat optimistic for tasks where larger cache sizes are needed (QASPER would require ~2,048, yielding only 1.7× throughput based on Table 1). Additionally, the throughput numbers assume decoding of 512 sequences totaling 2M tokens; for deployments with different workload characteristics, the multiplier may differ.

Missing experiments that would strengthen the paper:

  • Confidence intervals or error bars on all metrics. The PG-19 test set and ZeroSCROLLS tasks are large enough to compute meaningful variance estimates, and their absence makes it impossible to assess whether, e.g., TOVA's 0.3 perplexity advantage over Window+4 at k = 512 is statistically reliable or within noise. This is particularly important for the SQuALITY and QASPER results where differences are sometimes small (~1 ROUGE point) and the test sets are moderate in size.
  • H2O on long-range understanding and text generation. Since H2O performed similarly to Window+4 on language modeling, it might have shown different characteristics on retrieval (QASPER) or generation—validating or challenging the paper's claim that instantaneous attention is superior to cumulative attention across all tasks.
  • Ablation on the number of pinned tokens in Window+i. The paper tests i = 1 and i = 4 and finds i = 4 slightly better, but does not sweep i systematically to determine the optimal pinned count or whether it varies by model and task. This is a minor omission given that TOVA eliminates the need for this hyperparameter, but would have strengthened the baseline characterization.
  • Latency measurements. The throughput improvements come entirely from increased batch size, but larger batches also increase latency (time to complete a single sequence) due to reduced parallelism per sequence. For latency-sensitive applications, this tradeoff matters, and the paper does not quantify it.
  • Analysis of which layers benefit most from compression. The paper generates visualizations for all 32 layers of LLaMA-2-7B (Figures 12 and 13 in Appendix G) but does not analyze how the pattern of retained tokens varies by layer depth. Early layers might require larger caches (retaining more diverse tokens for low-level processing) while later layers might be satisfiable with smaller caches—a finding with direct practical implications for layer-wise cache allocation.
  • Performance on sequences shorter than the cache size. All experiments use input sequences that fill or exceed the cache capacity, so compression is always active. How TOVA behaves when sequences are shorter than the cache size—i.e., when no compression occurs—is not reported, though it should be identical to the full model by construction (TOVA is a no-op until t > k). Confirming this would eliminate concerns about the eviction mechanism interfering when it is not needed.

Genuine weaknesses in the experimental design:

  1. Single context length (4,096) for all main experiments. The paper only tests compression starting from a fixed 4,096-token context, but the question of whether TOVA's optimal cache size scales with pretraining context length is unanswered. A model pretrained on 8,192 tokens might show different diminishing-returns behavior, and the finding that 512 tokens suffice might not generalize to models with longer pretraining contexts.

  2. The 70K-token extrapolation experiment uses a separate positional encoding trick (ln(ln(g))) that is not part of TOVA. The paper treats extrapolation as a capability of bounded MSRNNs enabled by TOVA's compression, but the actual mechanism that enables long-context processing is the positional encoding compression, which is independent of TOVA. Figure 7 shows TOVA outperforming Window+4 with the same positional encoding scheme, which is informative about the eviction policy's contribution, but the claim that "TOVA extrapolates to 70K tokens" conflates the compression policy with the positional encoding adjustment.

  3. No comparison to training-required methods. While the paper explicitly limits scope to training-free methods (Section 5.1), the absence of any comparison to even one training-required approach (e.g., a model trained with bounded attention from scratch) means we cannot assess how much performance is being left on the table by the training-free constraint. This is a reasonable scope limitation but bears noting as a limitation of the conclusions: "TOVA is the best training-free policy" does not imply "TOVA is close to the best possible policy."

  4. Analysis of retained tokens (Section 7.3) is on only 31 PG-19 instances with one model (LLaMA-2-7B). The finding that punctuation, possessive endings, and proper nouns are disproportionately retained is intriguing but fragile—31 examples is a small sample, and different domains (scientific papers in QASPER, fictional stories in PG-19) might show different retention patterns. This analysis is suggestive rather than conclusive.

  5. The text generation evaluation with GPT-4, while carefully designed (positional swaps, tie handling), is inherently noisy and uncalibrated. GPT-4's preferences may not correlate with human judgments of story quality, and the 6% loss rate at k = 1024 could reflect either genuine quality differences or GPT-4's idiosyncratic preferences for certain stylistic features that the full model exhibits slightly more often. The paper acknowledges this limitation but does not provide human evaluation or automatic metrics to triangulate the GPT-4 results.

6. Limitations and Trade-offs

The Difficulty Estimation Cost Is Not Accounted For in the Efficiency Gains

The entire compute-optimal framework depends on accurately estimating each prompt's difficulty before selecting a test-time strategy. The paper's method for doing so — generating 2,048 samples per question and scoring them with the PRM — is extraordinarily expensive. The authors acknowledge this candidly in Section 3.2:

"estimating difficulty in this way still incurs additional computation cost during inference... our experiments do not account for this cost largely for simplicity"

The consequence is that the headline 4× efficiency figure is computed after difficulty is known, without amortizing the cost of learning it. Generating 2,048 samples to estimate difficulty already exceeds the largest test-time compute budget studied (256–512 generations). In a realistic deployment, a practitioner would need to pay a substantial up-front cost just to decide which strategy to use — and this cost is entirely unaccounted for in the efficiency claims. For one-off inferences, this makes the approach strictly more expensive than the best-of-N baseline it claims to beat. Only in high-volume settings where the difficulty estimation cost can be amortized across many queries from the same distribution would the reported gains be realizable.

The paper provides no evidence on whether difficulty estimates transfer across questions, domains, or time — can a difficulty model calibrated on MATH questions predict difficulty on GSM8K? On novel user queries? On distribution-shifted inputs? These questions are critical for deployment but entirely unaddressed.

The paper partially acknowledges this gap and frames it as future work (Section 8: "pretraining or finetuning models to directly predict difficulty of a question"), but no such model is developed or evaluated. The predicted difficulty bins (using PRM scores instead of ground-truth labels) remove the need for labeled data but do not reduce the computational cost — they still require 2,048 samples per question. Until a cheap, sample-efficient difficulty estimator is demonstrated, the compute-optimal framework remains an analysis tool rather than a deployable system, and the reported efficiency gains should be treated as upper bounds achievable only when difficulty estimation is free.

A Single Benchmark and Model Family Leaves Generality Unproven

All experiments in this paper use the MATH benchmark (500 test questions from high-school competition mathematics) with PaLM 2-S* as the base model. The authors state they "believe this model is representative of the capabilities of many contemporary LLMs" (Section 4), but this claim is unverified. The paper provides no evidence that the difficulty-dependent scaling patterns — beam search hurting easy problems, revisions helping easy problems but requiring parallel sampling on hard problems, the optimality of difficulty-conditioned allocation — generalize to other models, other datasets, or other task types.

The consequences of this limitation are severe for practitioners. Several aspects of the findings could be model-specific:

  • The PRM's over-optimization behavior depends on PaLM 2-S*'s output distribution and the specific Monte Carlo rollout training procedure described in Appendix D. A model with different calibration properties might exhibit different over-optimization thresholds, shifting the difficulty bins where beam search becomes harmful.
  • The revision model's ability to learn from incorrect in-context examples depends on the base model's in-context learning capabilities, which vary substantially across model families. The 38% correct-to-incorrect reversion rate (Section 6.1) may be higher or lower for other architectures.
  • MATH consists of symbolic reasoning problems with unambiguous ground-truth answers. It is unclear whether the compute-optimal framework would apply to code generation (where partial correctness is possible), factual QA (where knowledge retrieval matters more than reasoning), or open-ended generation (where correctness is subjective).

The test set of 500 questions — while standard for MATH — is further split into five difficulty quintiles of ~100 questions each, and then split again by two-fold cross-validation. This means the compute-optimal strategy is selected based on approximately 50 questions per fold per bin, a sample size small enough that the selected strategies may not be robust to the specific data split. The paper does not report confidence intervals on the compute-optimal scaling curves (Figures 4 and 8), making it impossible to assess whether the observed 4× efficiency improvement is statistically reliable or an artifact of this small sample.

The Larger Model Baseline Underestimates the Strength of Pretraining

The FLOPs-matched comparison in Section 7 compares PaLM 2-S* with compute-optimal test-time scaling against a model with approximately 14× more parameters using greedy decoding — no majority voting, no best-of-N, no search of any kind. The larger model also scales parameters while holding training data fixed (following the LLaMA paradigm of Touvron et al., 2023), rather than following Chinchilla-optimal scaling where both parameters and data are increased (Hoffmann et al., 2022). The paper acknowledges this explicitly (Section 7):

"We choose this setting as it is representative of a canonical approach to scaling pretraining compute and leave the analysis of compute-optimal scaling of pretraining compute where the data and parameters are both scaled equally to future work."

The consequence is that the comparison is systematically biased in favor of test-time compute. A Chinchilla-optimal 14× larger model (with appropriately scaled data) would likely outperform a parameter-only-scaled model, raising the baseline against which test-time compute is measured. Moreover, giving the larger model even a modest test-time compute budget — say, best-of-8 with majority voting, a trivially cheap addition — would create a much stronger comparison that is never tested. The paper's headline finding that "a smaller model augmented with compute-optimal test-time strategies can outperform a ~14× larger pretrained model" is therefore best understood as an upper bound on the advantage of test-time compute, achievable only against a relatively weak pretraining baseline.

The FLOPs accounting in Equation 8 (Section 7) is also idealized. It assumes the smaller and larger models share identical architecture families and compute-per-parameter ratios, and that inference FLOPs scale linearly with parameters. Real-world deployment involves heterogeneous hardware, quantization, and serving infrastructure that can alter the effective cost ratio between training and inference compute in ways this simplified model does not capture.

Verifier Over-Optimization Remains an Unsolved Hard Ceiling

The paper documents extensively that existing verifiers (PRMs and ORMs) are susceptible to over-optimization: beam search degrades performance on easy problems at high budgets (Figure 3, right), and lookahead search — the most powerful optimizer — paradoxically performs worst overall (Figure 3, left). Qualitative examples in Appendix M show search producing degenerate outputs (repetitive low-information steps, overly short solutions) that score highly under the PRM despite being incorrect.

The compute-optimal policy mitigates this by routing easy problems away from aggressive search (using best-of-N instead of beam search) and only applying beam search to medium-difficulty problems where the PRM signal has more room to provide genuine guidance. However, this is a routing strategy, not a solution. On medium-difficulty problems where beam search is deployed, over-optimization still limits the scaling ceiling — the beam search curves in Figure 3 flatten and eventually decline well before the full compute budget is exhausted. At 256 generations, beam search with M = 4 actually falls below best-of-N weighted on the aggregate (all-bin) curve.

The paper does not provide a method for detecting when over-optimization begins during deployment (i.e., when additional search budget becomes counterproductive for a specific query), nor does it propose verifier improvements that would raise the over-optimization threshold. The current results are therefore specific to the verifier quality achievable with the Monte Carlo rollout training procedure described in Appendix D, and improving the PRM — through better training data, adversarial robustness, or ensemble methods — would likely shift both the optimal strategies and the difficulty thresholds. A practitioner deploying this system would need to calibrate the over-optimization point for their specific verifier and model, a non-trivial step that the paper does not address.

Hard Problems Remain Completely Unaddressable by Test-Time Compute

Across every method studied — PRM search, iterative revisions, and their compute-optimal combinations — the hardest questions (difficulty bin 5) show near-zero improvement regardless of compute budget. In Figure 3 (right), bin 5 accuracy hovers at 1–3% for all methods and all budgets through 256 generations. In Figure 7 (right), bin 5 shows approximately 2–3% accuracy irrespective of the sequential-to-parallel ratio. In the FLOPs-matched comparison (Figure 9), the bin 5 scaling line is essentially flat near 0–5%, and the 14× larger pretrained model consistently outperforms test-time compute for these questions.

The paper is transparent about this limitation (Section 7 takeaway box):

"Test-time compute can amplify existing capability but cannot create it."

The consequence is a hard boundary on the method's applicability: for problems where the base model's pass@1 is near zero, no amount of test-time compute helps. The paper does not provide diagnostic tools for determining, at deployment time, whether a given query falls into this "too hard" regime — the difficulty estimator can identify bin 5 questions after the fact, but the paper offers no guidance on what to do with them (escalate to a larger model? flag for human review? accept the low accuracy?). For deployment on distributions where genuinely hard problems are common (e.g., competition-level mathematics, novel scientific reasoning, complex code generation with unfamiliar libraries), the compute-optimal framework provides no benefit over standard best-of-N, because neither method can extract correct answers from the base model.

Moreover, the paper does not explore whether test-time strategies like search or revision can provide partial utility on hard problems — e.g., finding solutions that are partially correct, or narrowing the space of possible answers even when the final answer is wrong. The binary correctness metric (exact match with ground truth) may obscure more nuanced forms of improvement that test-time compute can provide in the hard-problem regime.

Sequential Strategies Sacrifice Latency for Throughput — The Tradeoff Is Not Analyzed

The paper measures efficiency exclusively in terms of FLOPs or generations — the total number of tokens sampled — and reports throughput improvements from reducing cache size (enabling larger batch sizes). However, this metric ignores wall-clock latency: the time it takes to produce a single answer for a single query.

The compute-optimal allocation policy frequently selects sequential strategies (beam search, iterative revisions, or a mix of sequential and parallel) that are inherently serial. Beam search requires generating each step of each beam before proceeding to the next step. Sequential revisions require generating each revision before the next one can begin. A budget of 128 generations allocated as 64 sequential × 2 parallel chains takes approximately 64× longer in wall-clock time than a purely parallel best-of-128 strategy, even though both consume the same number of total generations.

This matters enormously for deployment. For latency-sensitive applications — interactive chatbots, real-time code completion, live tutoring systems — the sequential-heavy strategies favored by the compute-optimal policy on easy-to-medium problems may be unacceptable regardless of their accuracy advantages. A practitioner might accept a 5% accuracy degradation in exchange for a 10× latency reduction, but the paper's compute-optimal framework provides no mechanism for incorporating latency constraints into the strategy selection; it optimizes only for accuracy per generation, not accuracy per second.

The paper does not report latency measurements for any strategy, does not discuss the throughput-vs-latency tradeoff, and does not explore whether the optimal strategy changes when a latency ceiling is imposed. This is a significant gap because throughput (total work per unit time) and latency (time to answer) are fundamentally different objectives that call for different allocation policies — high-throughput deployments favor large batches and parallel strategies, while low-latency deployments favor strategies that produce a good answer quickly with minimal serial dependencies.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper produces a conceptual reframing with immediate engineering consequences, not a new architecture or training paradigm. Its most disruptive claim is that the transformer-RNN divide—which has structured NLP research, architecture design, and teaching curricula since 2017—is a category error for decoder-only models. The KV cache, universally treated as an optimization trick for avoiding recomputation, is in fact the hidden state of a recurrent model. This is not an analogy or an approximation; Section 3.2 shows it is an exact identity for any decoder transformer, past or present, with zero modification.

The magnitude of this reframing is substantial but specific. It does not displace the transformer architecture itself—attention remains the core mechanism—but it collapses the conceptual wall separating transformers from RNNs for the dominant autoregressive use case. Consequences ripple in several directions:

Reinterpretation of existing observations becomes possible. The paper's own finding that QASPER demands larger cache sizes than SQuALITY or language modeling (compare Figure 5's need for k = 2048 to reach within 2 F1 points of topline versus Figure 3's saturation at k = 512) is not an isolated empirical quirk—it is exactly what decades of RNN research predict. Retrieval tasks stress bounded memory (Hochreiter and Schmidhuber, 1997); summarization and next-token prediction do not. The MSRNN framework transforms this from "transformers are sometimes inefficient with their context" into "transformers, when operated with bounded memory, re-encounter the fundamental RNN difficulty with long-range retrieval." The framing has predictive power: any task requiring access to specific distant tokens should exhibit larger optimal cache sizes, and failure modes should resemble RNN forgetting rather than attention-specific pathologies. The paper opens the door to reinterpreting a wide range of transformer behaviors—attention sink phenomena (Xiao et al., 2023), recency biases, length generalization failures (Press et al., 2022)—as consequences of operating an RNN with an unusually structured but still fundamentally recurrent state.

The research priority for KV cache compression shifts from heuristic design to attention-signal exploitation. Prior to this work, the dominant approach was to handcraft which tokens to keep: recency windows (Wang et al., 2019), attention sinks (Xiao et al., 2023), heavy hitters via cumulative scoring (Zhang et al., 2023). Each policy encoded a theory about token importance. TOVA's consistent superiority—by 0.6–0.7 perplexity points over H2O at k = 256 on PG-19 (Table 3), by up to 5 F1 points over Window+4 on QASPER (Figure 5)—demonstrates that the model's own instantaneous attention distribution is a sufficient and optimal eviction signal. Handcrafted heuristics become not just suboptimal but redundant: the ablation showing TOVA-layer+1 and TOVA-layer+4 perform identically to plain TOVA (Table 3) proves that the attention mechanism automatically rediscovers the first-token preservation heuristic without being told. This inverts the research question from "what tokens should we keep?" to "how do we best query the model about what it needs?"—a shift from feature engineering to mechanism exploitation.

Verifier over-optimization and RNN forgetting become recognized as the same class of problem. The paper's finding that lookahead search—the strongest optimizer—paradoxically performs worst (Figure 3, left, where lookahead with k = 3 underperforms beam search and best-of-N at equivalent budgets) is a known pattern from the RLHF literature: optimization against imperfect reward models eventually exploits their errors. But the MSRNN framing adds a new dimension: over-optimization of a compressed transformer is also over-compression of an RNN state. When the cache is too small relative to the task's information requirements, the model must attend to tokens it has already forgotten, producing outputs that satisfy the verifier (which evaluates surface-level coherence) but fail on correctness. This connection between verifier over-optimization and RNN memory limitations suggests that improving verifier robustness and designing better compression policies are partially overlapping problems—a verifier that understands what information the model has lost would be more robust, and a compression policy informed by downstream task requirements would raise the over-optimization ceiling.

The training-free compression narrative narrows the gap between architecture research and deployment reality. Prior work on efficient transformers (Katharopoulos et al., 2020; Peng et al., 2022; Anagnostidis et al., 2023) required training modifications, making their methods inapplicable to the enormous installed base of pretrained LLMs. The paper demonstrates that a training-free, attention-based policy achieves throughput gains (4.8× at k = 512, Table 1) and memory reductions (88% cache compression, from 2.18 GB to 0.28 GB for LLaMA-2-7B) that approach what retraining-based methods might hope to achieve, with zero model modification. This does not make architecture research obsolete—a model trained from scratch with bounded memory constraints might outperform a post-hoc compressed model—but it radically raises the bar for what architecture proposals must demonstrate, since they must now beat a free, drop-in method that works on all existing models. The consequence for the field is practical: KV cache compression, previously a research problem requiring new architectures, becomes an inference-time optimization problem solvable with simple algorithms applied to existing weights, much as quantization and pruning became inference-time optimizations rather than training-time design choices.

Follow-Up Research This Work Enables

Are there attention-based eviction policies better than argmin? TOVA uses a hard minimum: exactly one token is evicted per step by selecting the absolute lowest attention score. This is minimally invasive but potentially fragile—what if the two lowest-scoring tokens have nearly identical scores, and the argmin choice is effectively random? A more robust variant might use stochastic eviction (sampling the token to drop from a distribution inversely proportional to attention), soft eviction (interpolating the dropped token into its neighbors rather than deleting it entirely), or multi-token batch eviction (dropping several tokens at once when the cache fills, using a threshold on attention rather than a count). The paper's own Appendix A shows that TOVA's design choices matter—the head-wise variant (9.55 perplexity) is substantially worse than the layer-wise variant (8.32) at k = 256—suggesting that the aggregation method is a degree of freedom worth optimizing. A systematic study of attention aggregation functions (mean, median, minimum across heads, weighted average by head importance) and eviction rules (deterministic vs. stochastic, single vs. batch) could yield policies that further close the gap to the unbounded topline, particularly on retrieval tasks (QASPER) where TOVA currently requires k = 2048 versus the topline's 4096.

Does layer-wise cache size allocation outperform uniform allocation? TOVA uses the same cache size k for every transformer layer. But the paper's own visualizations (Figures 12 and 13, Appendix G) show qualitatively different retention patterns across layers: early layers retain a dense, nearly uniform spread of tokens, while later layers concentrate on sparse "sticky" tokens (punctuation, proper nouns). This suggests that early layers may need larger caches (they process low-level features that require broad context) while later layers could operate with smaller caches (they attend to a sparse set of high-level syntactic/semantic anchors). A natural experiment: allocate a total cache budget K_total across L layers non-uniformly—e.g., larger caches for layers 0–10, smaller for layers 20–31—and measure whether the aggregate performance exceeds a uniform allocation of K_total / L per layer. The paper's existing infrastructure (TOVA operates per-layer, attention scores are available per-layer) makes this experiment straightforward; it requires only a cache allocation schedule rather than a change to the eviction rule. The throughput implications would be meaningful: if later layers can compress to k/2 while early layers need k, the total memory reduction could exceed 25% for free.

How does TOVA interact with other inference-time optimizations like quantization and speculative decoding? The paper evaluates TOVA in isolation with bfloat16 precision and standard autoregressive decoding. But KV cache compression is not the only inference optimization—weight quantization (reducing model memory) and speculative decoding (reducing serial dependency) are actively researched and deployed. TOVA's 4.8× throughput gain (Table 1) comes from increased batch size, which is complementary to quantization (which reduces per-parameter memory, also enabling larger batches). The combined effect could be multiplicative: if quantization reduces model memory by 4× and TOVA reduces cache memory by 8×, the effective memory reduction might enable batch sizes exceeding what either technique achieves alone. More critically, speculative decoding relies on a draft model generating candidate tokens that are verified in parallel by the full model—if TOVA compresses the full model's cache, the verification step becomes faster (smaller cache = faster attention), potentially increasing the acceptance rate of draft tokens. A combined TOVA + quantization + speculative decoding experiment on a standard serving benchmark (e.g., LMSys Chatbot Arena prompts, or production trace replay) would establish whether these techniques compose cleanly or introduce unexpected bottlenecks (e.g., TOVA's per-step argmin overhead becoming non-negligible when per-token latency is already low due to quantization).

What are the learned attention patterns that make TOVA work, and can they be induced during pretraining? TOVA is a post-hoc policy applied to pretrained models. The fact that it works—that the model's attention scores naturally identify which tokens are dispensable—raises the question of whether this behavior is an emergent property of standard pretraining or a contingent outcome of specific training data, architecture, and hyperparameters. A controlled experiment: train two identical transformer architectures from scratch, one with standard next-token prediction and one with an auxiliary loss that encourages attention sparsity (e.g., penalizing high attention entropy across the cached tokens). Measure whether the sparsity-trained model (a) achieves comparable pretraining perplexity, (b) exhibits more concentrated attention patterns, and (c) tolerates more aggressive compression at inference time (i.e., achieves the same perplexity as the standard model at smaller cache sizes). A positive result would suggest that attention sparsity can be baked into pretraining, producing models that are "compression-ready" without post-hoc policies. A negative result—sparsity penalties hurt pretraining quality, or sparser attention does not translate to better compression tolerance—would indicate that TOVA's effectiveness relies on subtle properties of the standard pretraining distribution that are not easily replicated via simple auxiliary objectives, making training-free policies more valuable, not less.

Does TOVA's retention pattern generalize across languages, domains, and modalities? The paper's token retention analysis (Section 7.3, Table 2) is English-only, PG-19-only, LLaMA-2-7B-only, and based on 31 examples. The finding that punctuation (", $, ), .), possessive endings (POS), and proper nouns (NNPS) persist longest in the cache is intriguing but fragile—does this pattern hold for morphologically rich languages (Finnish, Turkish) where word order is more flexible and syntactic information is distributed across many tokens? For code (where punctuation like {, }, ; carries precise semantic meaning)? For mathematical reasoning (where symbols dominate and natural language tokens are scaffolding)? A cross-lingual, cross-domain replication—evaluating TOVA's retention patterns on, say, Wikipedia text in 10 languages, GitHub code in 5 languages, and scientific papers (S2ORC) in English—would establish whether "sticky tokens" are a universal property of attention or a parochial consequence of English syntax. A failure to replicate in morphologically rich languages would imply that TOVA's cache size requirements are language-dependent, complicating multilingual deployment. A consistent replication across domains would strengthen the paper's implicit claim that attention-based eviction is domain-agnostic.

What happens when TOVA is applied to encoder-decoder or encoder-only transformers? The paper explicitly scopes its contribution to "decoder-only transformers" (Section 1, Section 3.2), and the MSRNN mapping relies on the autoregressive property—each step extends the state by one row. But bidirectional (encoder) attention also produces a cache (the key-value pairs for the entire input sequence), and this cache also grows with input length. Applying TOVA to an encoder would mean compressing the input representation itself rather than the autoregressive generation history. The questions are different: for an encoder, the "attention scores" for eviction would need to come from somewhere—perhaps the mean query across all positions, or a learned query vector—since there is no "last query" in bidirectional attention. The failure modes would also be different: over-compressing an encoder might cause information loss that propagates to all downstream layers, while over-compressing a decoder only affects that specific generation path. A replication of the PG-19 perplexity experiment with an encoder-decoder model (e.g., T5, or an encoder-decoder variant of LLaMA) where TOVA is applied only to the encoder, only to the decoder, or to both, would clarify whether the MSRNN framing extends beyond the autoregressive case and what modifications are needed.

Practical Applications and Downstream Use Cases

High-throughput LLM serving with fixed hardware budgets. The most immediate application of this work is reducing the cost-per-query for LLM deployments where GPU memory is the binding constraint. Table 1 quantifies the tradeoff concretely: on a single V100 GPU, switching from full 4,096-token caching to TOVA with k = 512 increases maximum batch size from 8 to 70 sequences, yielding 4.8× higher throughput. For an organization serving 10 million queries per day through a LLaMA-2-7B-based system, this translates to approximately 80% fewer GPU-hours—or, equivalently, the ability to serve the same query volume with 1/5 the hardware. The quality-cost tradeoff is favorable for high-volume applications where queries are conversational, summarization-oriented, or general-domain: Figures 3 and 4 show that k = 512 degrades perplexity by <0.4 points and ROUGE by <1 point across three model families. The deployment recipe is straightforward: integrate TOVA into the existing inference framework (the torch-like pseudocode in Algorithm 1, Appendix B, is ~10 lines), select k based on the quality target and task profile (larger for retrieval-heavy workloads, smaller for conversational), and immediately realize throughput gains. No retraining, no model modification, no change to the serving pipeline beyond the KV cache management layer.

Long-context processing with constant memory. Section 7.2 demonstrates that TOVA with k = 512 and the ln(ln(g)) positional encoding adjustment can process 70K-token inputs—over 17× the pretraining context length—with only ~0.5 perplexity degradation from 10K-token inputs. For applications requiring extremely long context (legal document review, scientific literature synthesis, multi-hour meeting transcripts), this is transformative: the memory cost becomes constant rather than linear in input length. An organization processing 100K-token legal contracts for clause extraction could run a standard 7B-parameter model with a 512-token cache on consumer-grade hardware (a single GPU with 16 GB VRAM) rather than requiring the 40+ GB needed for a full 100K-token cache. The throughput benefit compounds with length—for a 100K-token input, the memory reduction is 200× (100K vs. 512), enabling batch processing that would be physically impossible with unbounded caching. The caveat from the paper's own results: tasks requiring fine-grained retrieval of specific distant facts (the QASPER pattern) may need larger cache sizes (Figure 5 shows k = 2048 for within-2-F1 of topline), so practitioners should benchmark TOVA on their specific long-context task before assuming k = 512 suffices. For summarization and language modeling, however, the evidence strongly supports aggressive compression.

Offline batch inference for data generation and evaluation. When LLMs are used to generate training data (e.g., for distillation, instruction-tuning dataset creation, or synthetic data pipelines) or to evaluate large corpora (e.g., perplexity scoring of web-scale text, toxicity classification of comment archives), throughput dominates latency considerations—there is no interactive user waiting for a response. In these batch settings, TOVA's 4.8× throughput gain translates directly to 4.8× faster corpus processing or 4.8× cheaper data generation. Moreover, because batch inference workloads are typically offline and retryable, organizations can select a more aggressive cache size (k = 256 rather than k = 512) for an additional throughput boost—Table 1 shows 8.5× throughput at k = 256—accepting a small quality degradation that may be tolerable when the generated data will be filtered or when the evaluation metric is coarse. The paper's own language modeling results (Figure 3) suggest that k = 256 degrades perplexity by ~1.2 points on LLaMA-2-7B, which may be acceptable for data generation where diversity and approximate correctness matter more than exact next-token probability.

Deployment on memory-constrained edge devices. The paper demonstrates that a 7B-parameter model with a 512-token cache consumes only 0.28 GB for the KV cache (Table 1), compared to 2.18 GB for the full model. Combined with the model weights (LLaMA-2-7B in bfloat16 is ~13 GB), the total memory footprint with TOVA is ~13.3 GB versus ~15.2 GB without—a modest absolute reduction. However, the ratio improves dramatically for longer sequences: at 32K tokens, an uncompressed KV cache would consume ~17 GB (exceeding the model weights), while TOVA at k = 512 remains at 13.3 GB total. For edge deployments generating long responses or processing long documents (on-device assistants, mobile document summarization, offline navigation with map data), TOVA makes the difference between "fits in device memory" and "crashes with OOM." The linear memory scaling of unbounded caching is the primary obstacle to deploying LLMs on devices with fixed RAM (phones, tablets, embedded systems); TOVA converts this to constant memory scaling, making deployment feasible for any sequence length the positional encoding adjustment supports. The paper's 70K-token extrapolation result (Figure 7) suggests the ceiling is far above typical device-scale workloads.