PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Turn LLM Conversations under the Least-Recently-Used Policy: Mean-Field Asymptotics and Hit Ratio Approximation

Heyuan Yao, Chutong Gao, Yuan Lyu, Izzy Grosof, David Simchi-Levi

arXiv:2609.02027v1cs.PFmath.PR

TL;DR

Multi-turn LLM serving needs hit-ratio analysis because growing conversation histories compete for finite HBM under LRU. The paper models this system, proves a mean-field limit, and derives an estimator validated on Qwen3-8B serving experiments. The results provide a theoretical basis for analysis and practical guidance for memory-capacity provisioning.

  • Problem

    The paper addresses how to characterize HBM hit ratios when multi-turn KV-cache prefixes grow and finite capacity forces eviction.

  • Method

    It proposes a parsimonious multi-turn conversation model under LRU and analyzes it using mean-field asymptotics, then derives a practical estimator.

  • Results

    Theorem 3.1 proves h(N) → h(∞) as N →∞, where the limit is explicitly characterized by the mean-field hit ratio.

  • Takeaways & Limitations

    The characterization supports hit-ratio estimation and provides a theoretical foundation for analyzing multi-turn LLM services and guiding memory-capacity provisioning.

  • Takeaways & Limitations

    The theoretical analysis assumes whole-content LRU, whereas practical implementations may use block-level LRU with partial-prefix eviction.

Abstract

from arXiv · show

The major workloads in modern large language model (LLM) serving systems have shifted from single-shot LLM calls to multi-turn conversations, where new responses are generated based on the whole conversation history across all previous turns. The hit ratio, i.e., the average fraction of KV caches accessed directly from existing caches stored in high-bandwidth memory (HBM), is hence a crucial metric that governs system performance. Estimating the hit ratio is a highly nontrivial task due to the complex system dynamics, where the KV cache prefixes grow with turns and some must be evicted due to finite memory capacity. We formulate the system as a multi-turn conversation model under the least-recently-used (LRU) policy. Through a mean-field asymptotic framework, we prove that as the conversation arrival rate and the memory capacity grow proportionally to infinity, the hit ratio converges to a closed-form limit. Based on the characterization of the limit, we further propose a practical hit ratio estimator, and validate its accuracy by real LLM serving experiments on the Qwen3-8B model implemented on Ascend NPUs. Our results provide a theoretical foundation for the analysis of multi-turn LLM serving systems and a practical guideline for memory capacity provisioning.

1 Introduction

Multi-turn conversations make KV-cache reuse central to LLM serving, but growing histories and finite HBM capacity complicate hit-ratio analysis. The paper develops an LRU-based model, mean-field limit, estimator, and experimental validation.

  • Motivation: Multi-turn LLM workloads require carrying the full conversation history across turns, causing prolonged and growing context.Context caching stores and reuses generated KV caches to avoid repeated prefill work for shared histories.
  • Problem: The hit ratio measures the fraction of KV-cache content directly reused from HBM and is the target for long-run system optimization.The paper treats hit-ratio characterization as a prerequisite for optimizing context caching.
  • System dynamics: Finite HBM capacity forces eviction under LRU, making reuse depend on arrival rates, prompt timing, workload distributions, and capacity.The paper assumes whole-content LRU, where resident conversations are evicted when cache contents exceed capacity.
  • Contributions: The paper proposes a parsimonious multi-turn conversation model capturing key stochastic dynamics under LRU eviction.The model is designed as the foundation for subsequent asymptotic analysis.
  • Contributions: As conversation arrival rate and HBM capacity grow proportionally, the hit ratio converges to an explicit mean-field limit.The paper also derives a theoretically motivated estimator and validates it in Qwen3-8B serving experiments on Ascend 910B2 NPUs.

2 The Model

The multi-turn conversation model represents growing KV-block workloads and whole-content LRU management in finite HBM. Its asymptotic regime scales conversation arrivals and capacity together while imposing distributional assumptions.

  • The multi-turn conversation model: The MCM models conversations with random turn counts, prompt arrivals, and KV-block growth on a prefiller with capacity N blocks.New conversations arrive according to a Poisson process, and turn counts are independently distributed across conversations.
  • Model assumptions: The model assumes independence among turn-wise block increments, within-conversation interarrival times, and turn counts, with an exponential-moment workload condition and Lipschitz prompt-time CDF.Dependence across block increments of different turns may remain allowed.
  • LRU policy: Prefix reuse requires all preceding blocks to be available; a missing prefix block prevents reuse of its suffix blocks.The model therefore evaluates reuse at the conversation-prefix level rather than treating blocks independently.
  • LRU policy: Under whole-content LRU, prompts move resident conversations to the MRU end, and capacity violations evict complete conversations from the LRU end.The hit indicator is one when the prior-turn history is resident when the next prompt arrives.
  • Mean-field scaling: The mean-field regime scales HBM capacity N and conversation arrival rate linearly together while keeping other workload primitives unchanged.This proportional scaling is intended to produce a nondegenerate hit-ratio limit.

3 Main results

The paper proves a deterministic mean-field characterization of LRU hit ratios and uses it to construct a practical estimator. The analysis also accounts for unhashable tail blocks and implementation differences.

  • Mean-field analysis: The normalized displacement path of a tagged conversation converges to a deterministic mean displacement curve over every finite time horizon.The curve tracks cumulative KV-block mass inserted or refreshed ahead of the tagged content after its last access.
  • Scope boundary: Real implementations may use block-level LRU and permit partial-prefix eviction, unlike the whole-content policy analyzed here.The paper discusses this implementation difference in the appendix.
  • Mean-field analysis: The characteristic time T_C is the inverse mean displacement at 1, representing when displaced mass fills the entire normalized cache.The displacement curve is strictly increasing, so this inverse is well defined.
  • Main theorem: h(∞) = (A_H/A_R)F(T_C) defines the mean-field hit-ratio limit, and Theorem 3.1 states that h(N) converges to h(∞) as N →∞.The limit connects reusable history workload, total history workload, and the characteristic prompt-interarrival threshold.
  • Practical model: The practical MCM removes one unhashable partially filled tail block per non-final turn from reusable workload calculations.The corresponding practical displacement curve changes revisit displacement because that tail block cannot participate in prefix reuse.
  • Estimator: The estimator uses estimated arrival, workload, prompt-timing, and cache-capacity inputs to approximate the practical hit ratio.Its practical characteristic time is obtained from the estimated displacement equation with threshold N.

4 LLM Serving Experiments

The estimator is evaluated with public ShareGPT conversations using Qwen3-8B on Ascend 910B2 NPUs. Across controlled timing and arrival-rate experiments, it tracks empirical hit-ratio changes with small reported errors.

  • Setup: The evaluation uses 5,000 ShareGPT conversations, Qwen3-8B, five Ascend 910B2 NPUs, and 40 GB of prefiller HBM with N = 2,275 blocks.One NPU serves as the prefiller in the Prefill-Decode disaggregated setup.
  • Experiment design: Experiment 1 fixes λ0 = 1.5 and varies the target mean prompt interarrival time using an exponential clock.The posterior estimator substitutes the measured mean interarrival time for the target value.
  • Experiment design: Experiment 2 fixes µF = 135s and varies conversation arrival rate from 0.5 to 2.0.This setting is chosen because the realized mean interarrival time is closest to the target.
  • Results: Both estimators capture decreasing empirical hit ratios as either mean interarrival time or conversation arrival rate increases.The reported absolute error remains below 0.02, while relative error is below 10% when realized and target interarrival times closely match.

5 Conclusion

The paper develops a multi-turn conversation model for analyzing KV-cache hit ratios under LRU and establishes mean-field limits as system scale grows. It also derives practical guidance for hit-ratio estimation and HBM provisioning while clarifying architectural and modeling assumptions.

  • The paper proposes a parsimonious multi-turn conversation model under LRU that captures stochastic dynamics relevant to multi-turn LLM serving.
  • Mean-field analysis proves convergence of the hit ratio as conversation arrival rate and HBM capacity grow proportionally to infinity.
  • The mean-field characterization supports a practical hit-ratio estimator and memory-provisioning guidance, validated with Qwen3-8B experiments on Ascend 910B2 NPUs.
  • The model characterizes reuse through growing history content, turn-wise KV-block increments, prompt interarrival times, and conversation termination assumptions.
  • The intrinsic reuse potential hmax depends only on workload statistics and equals the continuation probability, equivalently determined by the mean number of turns.

C Extended mean-field results

The paper presents mean-field results for the multi-turn conversation model and extends them to a practical model for estimator development and empirical evaluation.

  • The analysis establishes convergence of the displacement process, characteristic time, and LRU hit ratio for the multi-turn conversation model.
  • The framework is extended to a practical multi-turn conversation model incorporating additional features of real LLM serving systems.
  • The resulting mean-field convergence characterizes a hit-ratio estimator whose accuracy is evaluated empirically.

C.1 Mean-Field Results of the MCM under LRU

The MCM-LRU analysis derives mean-field convergence for displacement, characteristic time, and hit ratio, then adapts the framework to practical unhashable tail blocks and proposes an estimator.

  • Mean-field displacement: The normalized tagged-conversation displacement process converges to a deterministic mean displacement curve under the MCM-LRU model.The curve is derived from contributions by pre-existing history content and newly generated KV blocks.
  • Characteristic time: The mean-field characteristic time TC is defined as d^-1(1), the unique time at which the mean displacement reaches the normalized HBM-capacity threshold.Characteristic-time convergence holds for each fixed turn state under the stated finite-horizon conditions.
  • Hit ratio convergence: The MCM-LRU hit ratio converges as HBM capacity and arrival-rate scaling N tends to infinity.The proof truncates the reusable-workload series and controls the tail as the truncation level grows.
  • Practical MCM: The practical MCM models one unhashable tail block per completed turn, excluding that block from prefix reuse while retaining it in physical displacement.Only Rj −1 history blocks are hashable when a conversation is revisited after turn j.
  • Estimator: The practical model has a unique practical mean-field characteristic time, and its limiting hit ratio motivates an estimator using available workload and system-dynamics information.The estimator remains applicable when only partial workload distribution and system-dynamics information is available.

D.1.2 Displacement Process Decomposition and the Mean Displacement Curve

The displacement process is decomposed into pre-existing history contributions and newly generated KV blocks, yielding a deterministic mean displacement curve.

  • Process decomposition: The representative displacement process combines displacement from pre-existing history blocks and newly generated KV blocks.The tagged displacement process has the same law for every fixed tagged turn state with Sj > 0.
  • Initial-prefix contribution: Pre-existing history contributes when active waiting intervals terminate during the observation window, with each interval weighted by min{t,w}.The waiting interval length is w, and its admissible stationary time-shift measure is min{t,w}.
  • New-block contribution: New-block displacement is generated by both new conversations and subsequent prompts from active conversations reaching later turns.The corresponding rates are determined by the conversation arrival rate, turn-state probabilities, and expected block increments.
  • Mean displacement curve: The mean displacement curve d is strictly increasing and Lipschitz-continuous, with slope bounded between λ0E[B] and λ0(E[B] + AH).Thus the curve increases at least with new-block growth and at most with new-block plus reusable-history contributions.

D.1.3 Sample Path Convergence of the Normalized Displacement Process

The normalized displacement process concentrates around its deterministic mean curve, with finite-size bounds establishing sample-path convergence as N grows.

  • Law invariance: For every fixed tagged turn state with Sj > 0, the tagged displacement process has the same law as the canonical displacement process.This reduces the convergence analysis to a single representative process.
  • Uniform convergence: The normalized displacement process converges uniformly on finite time horizons to d(t).The theorem provides concentration bounds and finite-size rates under a finite second-moment condition.
  • Proof strategy: The proof obtains sample-path control by combining pointwise concentration, monotonicity, Lipschitz continuity, and a union bound over a time partition.The partition is used to extend pointwise bounds to an L∞-difference over the full horizon.
  • Rates: The finite-size analysis yields an OP(N^-1/2) pointwise convergence rate for the normalized displacement process.A separate parameter choice establishes the stated sample-path convergence rate.

D.2 Proof of Theorem C.4

The characteristic-time proof controls tagged content size and displacement around deterministic times before and after TC, establishing convergence of eviction times.

  • Content-size control: The turn-j content size satisfies Rj = OP(1), so its normalized size Rj/N is asymptotically negligible.This follows because Rj is bounded by total lifetime block mass and its distribution is independent of N.
  • Eviction-time convergence: Concentration bounds imply that tagged content is resident at TC − ε and evicted by TC + ε with high probability.A union bound controls deviations at the two deterministic times together with the negligible content-size ratio.
  • Convergence result: The tagged turn-j characteristic time converges in probability to TC, with the finite-size rate derived from displacement concentration and content-size bounds.All terms in the bounding expression vanish as N tends to infinity.

D.3 Proof of Theorem C.5

The proof establishes hit-ratio convergence by combining an exact finite-size LRU representation with finite-turn and tail-workload error bounds. Sending system size to infinity and then truncation level to infinity yields the theorem.

  • Exact representation: The finite-N hit ratio is represented exactly using the characteristic time and the reuse indicators of turn histories.The representation relies on independence between tagged-conversation interarrival times, block increments, and the background displacement process.
  • Finite-turn approximation: A finite-turn proxy separates the approximation error into truncated finite-turn error and tail contributions beyond turn J.The finite-turn error is controlled through a Lipschitz bound for the interarrival-time distribution function.
  • Tail control: The tail workload T_J is bounded by E[B^2e^{θB}]e^{-θ(J+2)}, so it vanishes as the truncation level J increases.This bound uses independence between the conversation turn count and block increments, together with the fact that each turn generates at least one block.
  • Convergence: Theorem C.5 concludes that the whole-content LRU hit ratio converges as N →∞ under the stated MCM assumptions.The proof first fixes J, lets N grow, and then sends J to infinity using the vanishing tail workload.

D.4 Proof of Theorem C.6

The practical analysis adapts the displacement-process and characteristic-time arguments to hashable history blocks, which contain R_j−1 blocks rather than R_j. It then proves convergence of the practical hit ratio using analogous truncation and tail bounds.

  • Concentration: A normalized practical displacement-process deviation admits a finite-size tail bound for every fixed t and ε.The bound supports the subsequent characteristic-time convergence argument.
  • Practical displacement process: The practical displacement process preserves the Poisson background structure while replacing each reusable history contribution R_j with R_j−1.The new-block contribution remains unchanged, with normalized mean λ_0E[B]t.
  • Characteristic time: The practical characteristic time converges with an O(N^-1/2) rate because the reusable tagged content has size R_j−1.The threshold-sandwich argument remains valid since 0 ≤ R_j−1 ≤ R_j.
  • Hit-ratio convergence: Theorem C.6 bounds the difference between the practical finite-size hit ratio and its mean-field limit, then establishes convergence by sending N and the truncation level J to infinity.The practical tail workload T_J,hash vanishes as J increases.

E Theoretically-Motivated Estimator and LLM Serving Experiments

The paper evaluates its theoretically motivated estimators with ShareGPT workloads on Qwen3-8B serving hardware. Across experiments, the estimators track hit-ratio trends and remain close to measured values, while practical LRU behavior differs from the theoretical model in several respects.

  • Experimental setup: The experiments run Qwen3-8B on five Ascend 910B2 NPUs, reserving 40 GB of prefiller HBM for 2,275 KV blocks.The setup uses Prefill-Decode disaggregation with one prefiller and four decoders.
  • Model boundary: The practical vLLM LRU implementation differs from the theoretical model because recency depends on system events, and eviction can partially remove conversation suffixes.Blocks with nonzero reference counts may also be temporarily protected from eviction.
  • Workload: The ShareGPT measurement workload contains 5,000 conversations and 22,347 complete user-assistant turns, with mean conversation length 4.4694 and maximum 37 turns.The new-block distribution is descriptive and does not impose an i.i.d. assumption across turn indices.
  • Experiment 1: In Experiment 1, both estimators capture decreasing hit ratios as target mean interarrival time µ_F increases.The prior estimator uses the target exponential CDF, whereas the posterior estimator substitutes the measured mean interarrival time.
  • Experiment 1: Experiment 1 errors stay below 0.02 absolute and 16% relative, with both relative errors below 10% for 120 ≤ µ_F ≤165 s.Finite-horizon censoring and nonexponential realized interarrivals explain the differing prior and posterior estimates across regimes.
  • Experiment 2: In Experiment 2, both estimators capture decreasing hit ratios as λ_0 increases, with absolute errors below 0.015 and relative errors below 7%.The experiment fixes µ_F=135 s and varies the conversation arrival rate from 0.5 to 2.0.
Loading 2609.02027v1…