acceptodds
Under review as a conference paper at ICLR 2027

Same Conversation, Different Tokens: Characterizing and Mitigating Token Drift for Efficient Multi-Turn LLM Serving

Abstract

Multi-turn LLM serving reuses cached KV states only when a new prompt extends the token sequence the engine has already processed. Applications, however, carry conversation history as text: rendering it through a chat template and encoding the result again can return the same conversation as a different token sequence, silently defeating prefix reuse. We call this divergence token drift and characterize it across six open models, three conversation datasets, and four languages. Re-encoding alone breaks the prefix in 4.6%–90.8% of requests at temperature 1.0, at a roughly constant rate per generated token, while template history rewriting breaks it on every request after the first in three of the six model configurations. Since reuse ends at the first mismatch, rebuilding history costs 4×–23× the prefill the new content alone would need, and the KV branches stranded by misses add 10%–122% to the live context's footprint while remaining indistinguishable from it under recency-based eviction. We design one technique per layer of the serving pipeline and integrate all three into vLLM: canonical generation at the sampler with CG-Recheck, a checker we design that constrains sampling to token sequences that survive re-encoding; token-level history (TLH) at the request interface, which carries earlier turns forward as the token IDs the engine produced; and DriftEvict, a KV-cache eviction policy that identifies a dead branch when a turn completes and reclaims it ahead of live context. The two preventive techniques raise cache hit rates where their layer can prevent the miss, and TLH improves time to first token (TTFT) the most; but both change what the model samples or sees and may lower output quality. DriftEvict leaves outputs unchanged and improves throughput and TTFT under high load on every evaluated model.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Token Drift, LLM Serving, Multi-Turn Inference, Prefix Caching, Tokenization, KV Cache Management

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_Um4KOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper shows how re-tokenization and chat templates break prefix-cache reuse across turns. It measures the extra prefill and KV-memory costs and tests three fixes in vLLM. DriftEvict evicts unused KV branches first without changing model inputs or sampling.

Critical strengths
  • The paper studies a real serving problem: unchanged conversation text does not guarantee a reusable token prefix. The measurements clearly show the extra prefill and KV-memory costs across models and languages.
  • The issue also matters for agent harnesses that omit earlier reasoning when rebuilding history. This case is not evaluated here, but it reinforces the practical relevance of the problem.
  • The evaluation reports quality regressions rather than treating every fix as harmless. DriftEvict leaves model inputs and sampling unchanged and gives useful latency gains under load.
Critical weaknesses
  • DriftEvict is tested with ordinary user replies and fixed rendering settings. A discussion of harness-side history changes and tool continuations would help clarify its scope.
  • The serving tests use one idle-time distribution and report mean TTFT. Tail latency and different idle times would give a fuller picture of the benefit.
Questions for authors
  1. Can DriftEvict account for harness-side changes, such as dropping earlier reasoning, when predicting which KV blocks will no longer be reused?
  2. Can you report tail TTFT from the existing runs? How sensitive are the gains to idle time?
3 comments
AuthorsOpenReview ↗

Q2 follow-up (idle-time sensitivity)

The idle-time runs are complete. We scaled every sampled idle time by 0.5× and 2×, which gives medians of 36.8 s and 147 s against 73.5 s in the main setting. We kept the sessions, arrival rates, and measurement window of Figure 3. Mean TTFT (s), baseline → DriftEvict, at the four arrival rates of Figure 3 (lowest to highest):

ModelIdle scaleRate 1Rate 2Rate 3Rate 4
Qwen3.8-27B0.5×0.80 → 0.821.40 → 0.732.13 → 1.402.93 → 1.92
1×0.72 → 0.721.03 → 0.721.91 → 1.143.12 → 2.07
2×1.04 → 0.781.80 → 0.702.85 → 1.563.80 → 2.94
Qwen3.5-4B0.5×0.31 → 0.290.33 → 0.340.36 → 0.340.46 → 0.40
1×0.29 → 0.290.34 → 0.310.40 → 0.311.30 → 0.45
2×0.32 → 0.250.50 → 0.280.81 → 0.352.15 → 1.08
GLM-4.7-Flash0.5×0.49 → 0.470.54 → 0.490.59 → 0.541.03 → 0.78
1×0.59 → 0.491.04 → 0.551.67 → 0.883.19 → 1.22
2×1.46 → 0.853.05 → 1.703.07 → 2.674.21 → 3.08

Idle time sets how long each conversation's KV states wait for its next request. At a given arrival rate, longer idle times therefore leave more conversations waiting to reuse their KV states.

Doubling idle time brings the gain to lower arrival rates. At 2×, DriftEvict improves both mean TTFT and decoding throughput at every tested arrival rate on all three models. At the lowest rate, mean TTFT falls from 1.04 to 0.78 s on Qwen3.8-27B, from 0.32 to 0.25 s on Qwen3.5-4B, and from 1.46 to 0.85 s on GLM-4.7-Flash. At the highest rate, throughput rises from 316 to 332, from 596 to 651, and from 349 to 357 tokens/s.

Halving idle time keeps the gain at the highest rate, where mean TTFT falls from 2.93 to 1.92 s, from 0.46 to 0.40 s, and from 1.03 to 0.78 s. The revised PDF reports these results in Section 4.2 and shows the full comparison in Appendix A.11 (Figure 10).

Thanks for the additional experiments. The tail-latency and idle-time results address my concerns. I also appreciate the clarification about reasoning removal in the GLM template. I’ll keep my weak accept recommendation.

Thank you for the follow-up and for your thoughtful review. We are glad that the tail-latency and idle-time results address your concerns. The revised PDF includes both (Appendix A.9, and Section 4.2 with Appendix A.11).

Reviewer_HWPwOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper investigates token drift in multi-turn LLM serving, where reconstructing conversation history from text produces token sequences that differ from those originally processed by the model, thereby reducing prefix KV cache reuse. The authors identify two sources of token drift: re-encoding drift and chat-template history rewriting. To address these issues, the authors propose three techniques at different layers of the serving pipeline: CG-Recheck for canonical generation, Token-Level History (TLH) for preserving historical token IDs, and DriftEvict for proactively reclaiming dead KV cache branches. Experiments on vLLM show improvements in cache hit rates and serving performance, while also revealing potential output quality degradation from the two preventive approaches.

Critical strengths
  1. The problem is important, and the motivation is clear. The paper identifies an overlooked inefficiency in multi-turn LLM serving and systematically distinguishes re-encoding drift from chat-template history rewriting. The evaluation across multiple models and languages demonstrates that token drift can lead to substantial prefill and KV cache overhead. The analysis of dead KV branches is particularly valuable.

  2. DriftEvict seems simple and efficient. DriftEvict provides a relatively lightweight solution that improves KV cache utilization without modifying model inputs or sampling behavior. The serving experiments demonstrate improvements in both TTFT and throughput under high load.

Critical weaknesses
  1. Incomplete model coverage in the serving evaluation. Although the paper characterizes token drift across six models, the serving evaluation only includes three of them. In particular, Gemma 4 is omitted despite being identified as a representative case where history rewriting dominates token drift.

  2. Insufficient analysis of the semantic consistency and deployment implications of TLH. TLH raises questions about semantic consistency when multiple matching histories exist, particularly in multi-client serving environments. The paper does not sufficiently analyze how often such ambiguities occur or whether restoring a different token history could introduce unexpected behavior.

Questions for authors
  1. Why is Gemma 4 excluded from the serving evaluation despite exhibiting severe history-rewriting-induced token drift? Can the authors provide serving performance results for Gemma 4, particularly for DriftEvict, to demonstrate that the proposed techniques generalize across different chat templates and model families?

  2. When multiple checkpoints match the same visible conversation history but contain different token sequences, how does TLH ensure semantic consistency?

  3. Could the authors compare DriftEvict against additional cache eviction strategies, such as policies that identify obsolete branches only upon the arrival of the next request? This would help clarify the specific benefit of proactive dead-branch identification.

  4. DriftEvict assumes that the rendering of completed history can be predicted at turn completion. How does this assumption extend to applications involving tool calls, dynamic template parameters, conversation editing, or other changes to prompt construction?

Reviewer_fwSyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates token drift in multi-turn LLM serving, arising from re-encoding generated text and chat-template history rewriting, which can prevent KV cache prefix reuse. The authors characterize its impact on cache misses, redundant prefill computation, and KV cache memory overhead across multiple models and languages. To address these issues, they propose three techniques CG-Recheck, Token-Level History (TLH), and DriftEvict, targeting different layers of the serving pipeline. Experiments on vLLM demonstrate improvements in cache hit rates, TTFT, and throughput.

Critical strengths

The paper identifies a practical inefficiency in multi-turn LLM serving and systematically quantifies its impact across different models, datasets, and languages.

The experiments consider cache hit rates, TTFT, throughput, and output quality under different workload conditions, providing useful insights into the performance and quality trade-offs of the proposed techniques.

Critical weaknesses

The paper's technical contributions appear largely incremental. Re-encoding drift and tokenization multiplicity have been studied in prior work, while canonical generation and token-level history preservation are also established techniques. CG Recheck primarily improves an existing canonicality checker, and TLH adapts token-preserving mechanisms to the serving interface. Although DriftEvict introduces a more distinct optimization, the three techniques seem relatively independent.

The evaluation primarily compares the proposed techniques against standard vLLM with prefix caching and LRU eviction. While CG Recheck is evaluated against existing canonical-generation checkers, the comparisons for TLH and DriftEvict are less comprehensive.

Although Table 1 and Figure 2 provide a partial breakdown of re-encoding drift and history rewriting, the evaluation does not fully isolate their individual and interacting contributions to serving overhead.

Questions for authors

Please refer to the weaknesses.

3 comments

As the discussion period draws to a close, we would like to check whether our responses and the DriftEvict-Late comparison address your concerns on the contributions, the comparisons, and the two sources of token drift. We would be glad to clarify any point or to add the breakdown of the two sources that you find most useful.

Thank you for the responses and additional experiments. The DriftEvict-Late comparison strengthens the evaluation, and the explanation of how the two drift sources interact is helpful. My main concern remains the overall contribution. CG-Recheck and TLH largely adapt established techniques, and while the characterization and DriftEvict offer practical value, I still find the overall advance incremental. I therefore maintain my current recommendation.

Thank you for the follow-up and for your time throughout the discussion. We are glad that the DriftEvict-Late comparison and the account of how the two drift sources interact were helpful, and we appreciate your feedback.

Comments on the paper

1 comment

We thank all reviewers for their time and constructive feedback. The revised PDF adds the following results.

  • DriftEvict-Late (HWPw Q3, fwSy W2): Figure 3 and Section 4.2 add a policy that identifies dead branches only when the conversation's next request arrives. Together with the Section 4.2 policy that evicts all generated KV states at turn completion, it separates DriftEvict's two decisions: which blocks to evict, and when.
  • Gemma 4 (HWPw Q1): Appendix A.10 (Figure 9) adds serving results on Gemma-4-26B-A4B.
  • Tail latency (Um4K Q2): Appendix A.9 (Figure 8) reports P95 TTFT.
  • Idle time (Um4K Q2): Section 4.2 and Appendix A.11 (Figure 10) scale every sampled idle time by 0.5× and 2×.

Reviewers HWPw and Um4K have indicated that these results address their main concerns. We remain available for further questions until the discussion period ends.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.