Avoiding Recomputation of Historical Tokens in Multi-Turn LLM Conversations

1. Defining the Problem: What Does “Repetition” Mean in Multi-Turn Dialogues?

When discussing whether algorithms can prevent Large Language Models (LLMs) from repeatedly wasting computation on historical tokens during multi-turn conversations, we must first distinguish between two types of “repetition.”

The first type is parallel computation during the training phase. Under the teacher forcing method, each position in the sequence has access to the ground truth prefix. Combined with a causal attention mask, the model can compute the loss for all positions in parallel in a single pass. However, this parallelism does not mean that all future tokens can be computed in one pass during inference, because future tokens do not exist yet and must be sampled autoregressively.

The second type is the repeated computation of historical prefixes during inference and multi-turn conversations. In multi-turn dialogues, historical messages, system prompts, and tool results must continuously influence subsequent responses and cannot be arbitrarily discarded. The issue is not whether to feed historical information into the model, but whether we need to repeatedly recompute the intermediate states (across various layers) of historical tokens. Ideally, intermediate states such as projection results and attention key-values (KV) of historical tokens can be cached. Subsequent turns then only need to compute the new tokens and participate in attention calculations using the existing cache.

Strictly speaking, an algorithm cannot make a model “completely forget history while retaining its effect.” However, through techniques like KV caching, prefix reuse, session-level caching, context compression, and Retrieval-Augmented Generation (RAG), we can avoid redundant forward passes for stable historical prefixes. The real optimization target is “repeated computation,” not the “historical information itself.”

2. Training Parallelism Does Not Mean One-Pass Inference

In a decoder-only autoregressive architecture, the computation graphs for training and inference are not identical. During training, given a complete sequence, the ground truth label for the next token at each position is known. The causal mask ensures that the $i$-th position can only attend to the first $i$ tokens. Consequently, linear transformations, attention computations, and loss calculations across all positions can be highly parallelized. This is why teacher forcing is highly efficient.

During inference, the model must generate the $n$-th token before using it as input to generate the $(n+1)$-th token. Although the first $n$ tokens are already determined when generating the $(n+1)$-th token at step $n$—allowing a single attention mask construction and forward pass for the prefix—this is merely the “prefix computation for the current step.” It does not mean the historical computations from all previous steps can be skipped. If the entire prefix is re-fed through the network for every newly generated token, the cumulative computation grows rapidly with sequence length.

This can be illustrated with rough complexity estimates. Let the sequence length be $n$ and the hidden dimension be $d$. The cost of a full recomputation for attention and linear layers at step $t$ includes terms on the order of $O(t^2d)$ and $O(td^2)$. Full recomputation step-by-step up to $n$ yields a cumulative cost of roughly $O(n^3d + n^2d^2)$. With KV caching, the prefix is prefilled once, and each subsequent step only processes a single new token. The primary cost becomes reading the historical cache and performing attention, dropping the cumulative complexity to approximately $O(n^2d + nd^2)$. While real-world results depend on the number of layers, attention heads, batch size, and cache management strategies, the performance gap between “cache reuse” and “full recomputation” cannot be simply ignored.

Claims that “text length has a minor impact on computational performance” only hold true in specific short-context scenarios, certain encoder-based models, or particular implementations. For long-context autoregressive generation, sequence length significantly impacts both attention computation and cache reads; it cannot be generalized. In engineering, performance should be measured based on the actual model architecture, context length, batching, and hardware conditions.

3. How Incremental Decoding and KV Caching Avoid Repetition

Autoregressive inference is typically divided into two phases: Prefill and Decode. In the prefill phase, prefixes such as system prompts, conversation history, and the current user input are fed into the model at once to compute and cache the KV states across all layers. In the decode phase, only the previously generated token is input at each step. The model uses the cached historical KV states to compute attention and outputs the next token.

The key point is that although historical tokens are not re-fed into the linear layers, their keys and values are preserved in the cache and still participate in the attention computation for new tokens. In other words, historical information is not discarded; only its projection and partial intermediate results are reused. The query vector of the new token interacts with the cached historical keys and values to obtain context. This way, the stable historical prefix in a multi-turn conversation only needs to be computed once. Subsequent turns can simply append new messages and model responses.

It is important to note that what is cached is the KV state of every layer and every attention head, not simply the raw text. Text caching only avoids network transmission or string concatenation; it does not prevent model forward passes. Only KV caching can avoid redundant projections. For long conversations, the memory footprint of the cache grows with sequence length, number of layers, number of heads, and precision. Therefore, engineering techniques like paged management, cache quantization, eviction policies, and expiration deletion are required.

4. Why Multi-Turn Conversations Still Repeat: Stateless Requests and Cache Invalidation

In a stateless request model, each turn concatenates the full history and sends it to the server, which treats every request as an independent task. Even if the model internally utilizes KV caching during a single generation pass, the historical prefix may still be re-prefilled across different requests. The root cause of this redundant computation lies not in the model’s algorithm, but in the request protocol and cache lifecycle: whether the session cache computed in the previous turn is retained, whether it can be hit by the next turn, and whether the cache key matches exactly.

A cache hit typically requires an exact prefix match, including the system prompt, role markers, historical message order, tool results, and model version. If the history includes dynamically inserted timestamps, randomly sorted retrieved chunks, or rewritten historical summaries, the prefix fingerprint changes, and the cache may be invalidated. Model version upgrades, tenant permission changes, or cache expiration also prevent direct reuse of old caches. Furthermore, caches may contain sensitive context, necessitating tenant isolation, access control, encrypted storage, and regular cleanup; unisolated caches cannot be shared across users.

Therefore, reducing multi-turn redundant computation requires two simultaneous actions. First, maintain a stable prefix by adopting an “append-only, no rewrite” approach to organizing conversation history, placing dynamic information in controlled positions. Second, enable the system layer to support session caching or prefix caching, using model version, prefix fingerprint, and tenant ID as cache keys. Modifying the model architecture alone cannot solve the redundant prefill problem inherent in stateless requests.

5. Feasible Optimization Paths

First, Session-Level KV Caching. Retain the KV states of the historical prefix within the same session. A new turn only pre-fills the new user message, and the decode phase generates the response and appends it to the cache. This is suitable for continuous, multi-turn scenarios with stable history, but requires managing cache capacity and expiration time.

Second, Prefix Reuse. Long prefixes like system prompts, fixed knowledge instructions, and tool usage specifications that recur across multiple requests can be cached and reused for exact matches. Prefix caching must verify the prefix fingerprint and enforce tenant isolation to prevent information leakage between users.

Third, Paged Cache Management. The KV cache for long conversations does not need contiguous large memory blocks. It can be dynamically allocated in fixed-size blocks, loaded, and evicted on demand to reduce fragmentation and peak memory usage. Combined with strategies like prioritizing active sessions and Least Recently Used (LRU) eviction, cache hit rates can be improved under limited resources.

Fourth, Context Compression and RAG. When history exceeds the window or caching costs become prohibitive, distant history can be compressed into summaries, structured memory, or key facts, while keeping the raw text of the most recent turns at the tail. Alternatively, relevant chunks can be retrieved and concatenated via RAG. Since compression alters the prefix and invalidates the cache, a layered structure can be designed: a fixed system prompt, a low-frequency updated rolling summary, a recent raw text window, and on-demand retrieved chunks. This controls length while keeping the reusable prefix as stable as possible.

Fifth, Cache Precision and Capacity Trade-offs. Storing the KV cache in lower precision reduces memory footprint but may impact generation quality. Shortening cache retention time saves resources but lowers multi-turn hit rates. Tuning should align with business requirements regarding Time To First Token (TTFT), throughput, cost, and consistency.

The following is logical pseudocode illustrating the cache reuse flow. It is framework-agnostic and does not represent an actual API:

def chat_turn(session, new_user_ids):
    prefix_ids = session.system_ids + session.history_ids
    cache_key = fingerprint(session.model_version, prefix_ids)
    kv = session_cache.get(cache_key)
    if kv is None:
        kv = model.prefill(prefix_ids)   # Compute the stable historical prefix in one pass
    else:
        kv = validate_and_truncate(kv, prefix_ids)  # Verify prefix and truncate
    input_id = new_user_ids[-1]
    reply_ids = []
    for step in range(max_steps):
        logits, kv = model.decode(input_id, kv, causal_mask=True)
        next_id = sample(logits)
        reply_ids.append(next_id)
        input_id = next_id
        if next_id == end_id:
            break
    session.history_ids += new_user_ids + reply_ids
    session_cache.put(
        fingerprint(session.model_version, session.history_ids),
        kv
    )
    return reply_ids

6. Engineering Trade-offs and Conclusion

Through algorithmic and system design, it is indeed possible to reduce the redundant computation of historical tokens in multi-turn conversations. However, there is no “zero-cost infinite history” solution. KV caching reduces redundant forward passes but increases storage and cache management overhead. Prefix reuse improves hit rates but requires request prefixes to remain stable. Summaries and retrieval control context length but may lose fine-grained details. Cache isolation ensures security but adds complexity to key design and lifecycle management.

In practice, several principles should be followed: distinguish between training parallelism and inference autoregression; prioritize incremental decoding and KV caching; design session caching and prefix reuse at the system layer; maintain stable prefixes to improve hit rates; combine summaries, retrieval, and sliding windows for long history; and enforce tenant isolation, expiration deletion, and capacity monitoring for caches. This is the only way to balance latency, compute cost, response quality, and security compliance. Ultimately, the optimization goal is not to make the model “stop reading history,” but to allow historical information to participate efficiently in computation via caching, avoiding redundant prefilling and projection.