LoopServe: An Adaptive Dual-phase LLM Inference Acceleration System for Multi-Turn Dialogues

## Abstract

Abstract Multi-turn dialogues are essential in many real-world applications of large language models, such as chatbots and virtual assistants. As conversation histories become longer, existing large language models face increasing computational and memory challenges, which hinder their ability to provide efficient and responsive interactions. Most current acceleration methods either compress the context or optimize key value caching, but they often rely on fixed or position-based heuristics that do not adapt well to the dynamic and unpredictable patterns found in actual multi-turn conversations. As a result, these models cannot accurately identify and prioritize the most relevant context, leading to degraded response quality. In this paper, we present LoopServe, an adaptive dual-phase inference acceleration framework for large language models in multi-turn dialogues. LoopServe introduces two main innovations. First, it performs online sparsification during the prefilling phase by dynamically selecting the most important parts of the attention matrix for each new input. Second, it uses progressive key value compression during decoding by adaptively maintaining a relevant and efficient cache based on the most recently generated output tokens. We also propose a new benchmark with eleven multi-turn datasets that reflect realistic query positions and conversational dependencies. Extensive experiments demonstrate that LoopServe consistently achieves superior effectiveness compared to existing baselines and significantly accelerates LLM inference across a wide range of long-context dialogue tasks.

## 1 Introduction

Multi-turn dialogues are at the core of numerous real-world applications, from customer service chatbots to virtual assistants and collaborative agents.
These scenarios demand that large language models (LLMs) (Hadi et al., 2023; Deng et al., 2025; Li et al., 2024a; Zhou et al., 2024; van Renen et al., 2024)
not only generate coherent responses but also maintain contextual consistency across lengthy, evolving conversations. As the number of dialogue turns increases,
so does the computational workload.
For instance, processing a multi-turn dialogue comprising 10,000 tokens with Llama-3.1-70B (Grattafiori et al., 2024) can demand trillions of floating-point operations (FLOPs), quickly challenging the limits of real-time inference.
Despite the remarkable progress of LLMs such as GPT (Brown et al., 2020; Radford et al., 2018; 2019),
Llama (Grattafiori et al., 2024; Touvron et al., 2023),
and DeepSeek (DeepSeek-AI, 2024; 2025),
their inefficiency in handling multi-turn dialogues remains largely unaddressed.

In a typical multi-turn setting, each new user turn expands the conversation history, requiring the LLM to process ever-growing input sequences.
The model’s self-attention mechanism, which lies at the heart of the Transformer (Vaswani, 2017), needs to compute pairwise attention scores between every pair of tokens in the input.
Specifically, given an input sequence of length $n$, an LLM with $P$ parameters and a hidden dimension $d$, the time complexity of generating $m$ tokens is $\mathcal{O}(m((n+m)^{2}d+P))$.
For instance, in a 3-turn conversation with 5000 tokens per turn, the effective context length for the model reaches 15,000 tokens, resulting in quadratic growth in both computational cost and memory usage. This compounding effect of context accumulation makes real-time, cost-efficient inference increasingly difficult as the conversation progresses.
Different from single-turn tasks,
the context in multi-turn dialogues accumulates dynamically and queries may appear at the beginning, middle, or end of the input, causing attention patterns to shift unpredictably. The resulting attention matrices not only grow with each turn but also exhibit highly dynamic and input-dependent sparsity, exacerbating the inefficiency of current inference methods.

Recent research proposes accelerating LLM inference by reducing the computational burden of attention weight calculations during both the prefilling and decoding stages.
In the prefilling stage, where the attention matrix is computed for all token pairs, methods (Jiang et al., 2024a; Lv et al., 2024; Lai et al., 2025), such as Minference (Jiang et al., 2024a), use fixed pattern to sparsify the attention matrix to reduce quadratic computation.
During decoding, KV caches store precomputed Key and Value vectors to reduce redundant computation. Methods like H2O (Zhang et al., 2023), SnapKV (Li et al., 2024b), and AdaKV (Feng et al., 2024) cache tokens selected based on tokens at the end of the query. However, these approaches rely on static or position-based heuristics and cannot adapt to the dynamic, input-dependent patterns of real multi-turn dialogues.

Moreover, current evaluation benchmarks (Li et al., 2024a; 2025; Hsieh et al., 2024; Kim et al., 2025; An et al., 2023) for LLM acceleration misrepresent real-world dialogue scenarios.
Most benchmarks (Bai et al., 2024a; Li et al., 2025; Dacheng Li* & Zhang, 2023) assume queries are always placed at the end of the input and focus on single-turn tasks, which oversimplifies the problem and favors acceleration methods that exploit positional biases. As a result, approaches (Zhang et al., 2023; Li et al., 2024b; Feng et al., 2024)
that perform well on these benchmarks often fail to generalize to realistic dialogue scenarios where queries may appear at arbitrary positions and contextual dependencies span multiple turns.

In this paper, we propose LoopServe, an adaptive dual-phase LLM inference acceleration framework specifically designed for multi-turn dialogues. LoopServe features two core innovations: online prefilling sparsification and progressive KV compression. In the prefilling phase, LoopServe dynamically identifies and selects the most critical components of the attention matrix, focusing on the vertical and slash line patterns that contribute most to attention weights. Unlike fixed sparsification methods, LoopServe adapts in real time to maintain both efficiency and high attention fidelity. During decoding, LoopServe applies progressive KV compression by dynamically selecting and compressing relevant input tokens based on the most recently generated outputs. This strategy keeps the KV cache efficient and relevant throughout decoding, significantly reducing computational overhead without compromising output quality.
We also introduce a multi-turn long-context benchmark containing 11 datasets. This benchmark captures diverse query positions and multi-turn dependencies, offering a more realistic evaluation framework for dialogue scenarios.
The contributions of this paper are summarized as follows:

- •
We empirically reveal that attention patterns and key token positions in multi-turn dialogues are highly dynamic, limiting static sparsification and KV selection.
- •
We present LoopServe, a dual-phase LLM acceleration framework with online attention sparsification and progressive KV compression, improving multi-turn inference efficiency.
- •
We introduce a benchmark of 11 long-context multi-turn datasets with varied query positions and dependencies for realistic evaluation.
- •
Experiments on 11 multi-turn datasets demonstrate the superior performance of LoopServe.

## 2 Preliminary and Related Work

### 2.1 Large Language Models

LLMs like GPT (Brown et al., 2020), Llama (Grattafiori et al., 2024), and DeepSeek (DeepSeek-AI, 2024; 2025) excel at context understanding and reasoning, enabled by large-scale training and the Transformer architecture (Vaswani, 2017). Transformers are effective due to Multi-Head Self-Attention (MHSA), which captures both local and global token dependencies.
Given an input sequence $X=[x_{1},x_{2},\cdots,x_{n}]$ with embeddings $\mathbf{X}\in\mathbb{R}^{n\times d}$, the MHSA computes query vectors $\mathbf{Q}^{i}\in\mathbb{R}^{n\times d_{k}}$, key vectors $\mathbf{K}^{i}\in\mathbb{R}^{n\times d_{k}}$,
and value vectors $\mathbf{V}^{i}\in\mathbb{R}^{n\times d_{v}}$ for the $i$-th attention head as $\mathbf{Q}^{i}=\mathbf{X}\mathbf{W}_{Q^{i}},\mathbf{K}^{i}=\mathbf{X}\mathbf{W}_{K^{i}},\mathbf{V}^{i}=\mathbf{X}\mathbf{W}_{V^{i}}$,
where $\mathbf{W}_{Q^{i}}$, $\mathbf{W}_{K^{i}}$, and $\mathbf{W}_{V^{i}}$ are learnable matrices.
Each $i$-th attention head $\mathbf{Z}^{i}$ as :
$\mathbf{Z}^{i}=\textsf{Attention}(\mathbf{Q}^{i},\mathbf{K}^{i},\mathbf{V}^{i})=\textsf{Softmax}\left(\frac{\mathbf{Q}^{i}(\mathbf{K}^{i})^{\top}}{\sqrt{d_{k}}}\right)\mathbf{V}^{i}.$
Next,
outputs from $h$ heads are concatenated and projected:
$\mathbf{Z}=\textsf{Concat}(\mathbf{Z}^{1},\mathbf{Z}^{2},\dots,\mathbf{Z}^{h})\mathbf{W}_{O},$
where $\mathbf{W}_{O}$ is a learned projection.
For text generation, LLMs use an autoregressive process: given $X=[x_{1},\ldots,x_{n}]$, the model predicts the next token $x_{n+1}$ by modeling
$P(x_{n+1}|x_{1},x_{2},\cdots,x_{n})=\textsf{Softmax}(\mathbf{h}_{n}\mathbf{W}_{\text{out}}+\mathbf{b}_{\text{out}})$,
where $\mathbf{h}_{n}$ is the state at step $n$. The next token $x_{n+1}$ is sampled from this distribution and appended to the sequence. Generation continues until an end-of-sequence token or a maximum length is reached.

### 2.2 Efficient Long-Context Inference

The performance of LLMs degrades with long input contexts, due to
the quadratic complexity of self-attention, which scales as $O(Lhn^{2})$ for $L$ layers, $h$ heads, and sequence length $n$ (Li et al., 2024a). It makes long-sequence processing prohibitively expensive.

Context Compression Methods.
Context compression methods reduce the effective sequence length, transforming lengthy inputs into more manageable representations. Filtering-based approaches such as LLMLingua (Jiang et al., 2023), LLMLingua-v2 (Pan et al., 2024), and CompAct (Yoon et al., 2024) focus on identifying and preserving high-relevance content, allowing models to process only critical information. In contrast, RAG-based (retrieval-augmented generation) methods (Zhao et al., 2024; Jiang et al., 2024b; Wang et al., 2025; Chen et al., 2025; Edge et al., 2024) construct knowledge graphs or extract semantic triples from the input, synthesizing them into condensed forms for LLMs. These strategies substantially decrease computational and memory costs, but may sacrifice fine-grained details, potentially affecting output quality.

Also, to reduce computational burden, KV-based approaches minimize the number of attention weight calculations during both prefilling and decoding, summarized in Table [3](https://arxiv.org/html/2507.13681v2#A1.T3) in the Appendix.

Prefilling-stage Optimization.
Self-attention requires $O(n^{2})$ computation for an input of length $n$. Recent methods such as Minference (Jiang et al., 2024a), FlexPrefill (Lai et al., 2025), and CritiPrefill (Lv et al., 2024) use binary masks $\mathbf{M}\in\{0,1\}^{n\times n}$ to zero out less important attention weights:
$\min\,\left|\mathbf{{A}}^{j}_{i}-\mathbf{\hat{A}}^{j}_{i}\right|,s.t.\ ,\mathbf{\hat{A}}^{j}_{i}=\textsf{Softmax}\left(\frac{\mathbf{Q}^{j}(\mathbf{K}^{j})^{\top}}{\sqrt{d_{k}}}-c(1-\mathbf{M})\right)$, where $c$ is a large constant that suppresses masked entries. This reduces complexity to $O(\alpha n^{2})$ per head, with $\alpha\ll 1$. However,
Minference (Jiang et al., 2024a) and CritiPrefill (Lv et al., 2024) rely on fixed attention patterns or block selection, while FlexPrefill (Lai et al., 2025) adjusts sparsity globally with simple heuristics. However, our experiments (Section 3) show that attention patterns are highly input-dependent and dynamic, so these static or coarse methods struggle to adapt in multi-turn scenarios.

Decoding-stage Optimization.
During autoregressive generation, KV cache methods such as H2O (Zhang et al., 2023), SnapKV (Li et al., 2024b), AdaKV (Feng et al., 2024), and others (Ge et al., 2024; Li et al., 2024b) select important tokens to store, reducing redundancy. These approaches assume that critical tokens are near the end of the input, performing well on benchmarks like LongBench (Bai et al., 2024a; b), where queries are always placed last. However, as analyzed in Section [3.2](https://arxiv.org/html/2507.13681v2#S3.SS2), their effectiveness drops when queries appear elsewhere, underscoring the need for adaptive, context-aware KV selection in real dialogue.

## 3 Motivational Experiments and Insights

To clarify the core challenges in accelerating LLM inference for multi-turn dialogues, we conduct motivational experiments in Section [3.1](https://arxiv.org/html/2507.13681v2#S3.SS1) and [3.2](https://arxiv.org/html/2507.13681v2#S3.SS2). They reveal how attention patterns are dynamically sparse and how query position influences acceleration effectiveness. Building on these findings, we introduce the LoopServe system, specifically designed to address these real-world challenges.

### 3.1 Key Point 1: Uncertain Attention Patterns

As investigated previously, attention head matrices are highly sparse Jiang et al. (2024a). Existing acceleration methods (Xiao et al., 2024; Feng et al., 2024; LI et al., 2025; Li et al., 2024b) often rely on sparsifying attention matrices or selecting important KV tokens based on the assumption that attention patterns are fixed and can be identified offline. In reality, these patterns are highly variable across inputs, heads, and layers, limiting the effectiveness of such approaches, as reveled as follows.

Figure: (a) Vertical and slash lines.
Refer to caption: x1.png

Motivational Observation 1: Only 10% of vertical and slash lines can collectively account for most (e.g., 90%) of the attention weight.
As shown in Figure [1](https://arxiv.org/html/2507.13681v2#S3.F1) (a),
in an attention matrix, a vertical line (column) indicates a single token attended by all others, common for special tokens like separators or keywords. A slash line (diagonal) shows each token mostly focusing on its nearby tokens, reflecting local attention patterns.
We analyze this using the SAMSum QA dataset (Bai et al., 2024a) and the Llama-3.1-8B-Instruct with $n_{h}$ heads. For each query $X_{i}$ of length $n_{i}$, each $k$-th attention matrix $\mathbf{A}^{k}_{i}$ contains $n_{i}$ vertical lines $\mathcal{V}^{k}_{i}$ and $n_{i}$ slash lines $\mathcal{S}^{k}_{i}$. The total attention weight for a slash line $s^{k}$ is $\sum_{(a,b)\in s^{k}}\mathbf{A}^{k}_{i}[a][b]$, and for a vertical line $v^{k}$, it is $\sum_{(a,b)\in v^{k}}\mathbf{A}^{k}_{i}[a][b]$.
We select the top $\eta\cdot 2n_{i}$ slash and vertical lines ($\mathcal{\hat{S}}^{k}_{i}$, $\mathcal{\hat{V}}^{k}_{i}$) based on their total weights. For each head $k$, we compute the ratio of weight within these lines:
$r^{k}_{i}=\frac{1}{|\mathcal{D}|}\sum_{X_{i}\in\mathcal{D}}\frac{\sum_{(a,b)\in\mathcal{\hat{S}}^{k}_{i}\cup\mathcal{\hat{V}}^{k}_{i}}\mathbf{A}^{k}_{i}[a][b]}{n_{i}}.$
Averaging over all $n_{h}$ heads yields the mean ratio. As shown in Figure [1](https://arxiv.org/html/2507.13681v2#S3.F1) (b), higher $\eta$ increases cumulative attention weight. Figure [1](https://arxiv.org/html/2507.13681v2#S3.F1) (c) shows that for both Llama and Mistral, just 10% of slash and vertical lines account for 90% of total attention, indicating highly concentrated attention and enabling efficient selection by focusing on these sparse lines.

Motivational Observation 2: The positions of the top vertical and slash lines within the same head vary across different user inputs.
For a model $M_{\theta}$ with $n_{h}$ attention heads and dataset $\mathcal{D}={X_{i}}$, we select the top $\eta\cdot 2n_{i}$ vertical and slash lines ($\mathcal{\hat{V}}^{k}_{i}$, $\mathcal{\hat{S}}^{k}_{i}$) for each input $X_{i}$ and attention head $k$. For any pair of queries $X_{i}$, $X_{j}$, the overlap of their selected lines under head $k$ is: $r^{k}_{i,j}=\frac{|\mathcal{\hat{S}}_{i}^{k}\cap\mathcal{\hat{S}}_{j}^{k}|+|\mathcal{\hat{V}}_{i}^{k}\cap\mathcal{\hat{V}}_{j}^{k}|}{|\mathcal{\hat{S}}_{i}^{k}\cup\mathcal{\hat{S}}_{j}^{k}|+|\mathcal{\hat{V}}_{i}^{k}\cup\mathcal{\hat{V}}_{j}^{k}|}.$
Averaging over all heads and input pairs gives the mean overlap ratio:
$\frac{1}{n_{h}|\mathcal{D}|^{2}}\sum_{k=1}^{n_{h}}\sum_{X_{i},X_{j}\in\mathcal{D}}r^{k}_{i,j}$.
Using the SAMSum QA dataset (Bai et al., 2024a) and models Llama-3.1-8B-Instruct and Mistral-7B-Instruct-v0.3, with $\eta$ ranging from 0.1 to 0.3, Figure [1](https://arxiv.org/html/2507.13681v2#S3.F1) (d) and Figure [7](https://arxiv.org/html/2507.13681v2#A1.F7) in Appendix show that for most heads, the overlap remains below 0.5. This indicates that the most important lines differ significantly depending on the input, even within the same head. As a result, important lines cannot be reliably determined offline for use during online inference.

Motivational Observation 3: For an input $X_{i}=[C_{i}^{1},C^{2}_{i}]$ split into two segments, the top vertical and slash lines within the same head differ between $C^{1}_{i}$ and $C^{2}_{i}$. Each segment shows its own local attention sparsity pattern.
As illustrated in Figure [2](https://arxiv.org/html/2507.13681v2#S3.F2) (a), the key vertical and slash lines in $C^{1}_{i}$’s attention matrix are largely absent in $C^{2}_{i}$, which displays distinct local patterns. To verify this, we use the SAMSum QA (Bai et al., 2024a) dataset and Llama-3.1-8B-Instruct.
For each $X_{i}$ in dataset $\mathcal{D}$, we split it into $[C^{1}_{i},C^{2}_{i}]$ and extract the attention matrices $\mathbf{A}^{k}_{C^{1}_{i}}$ and $\mathbf{A}^{k}_{C^{2}_{i}}$ for each head $k$. After selecting the top-$\eta$ important slash and vertical lines for each ($L^{k}_{C^{1}_{i}}$, $L^{k}_{C^{2}_{i}}$) for ( $\mathbf{A}^{k}_{C^{1}_{i}}$, $\mathbf{A}^{k}_{C^{2}_{i}}$),
we compute the overlap rate:
$r^{k}_{C_{i}^{1}\to C_{i}^{2}}={\sum_{l\in L^{k}_{C^{1}}}\mathbb{I}(l\in L^{k}_{C_{i}^{2}})}/{|L^{k}_{C_{i}^{2}}|},$
where $\mathbb{I}$ indicates whether a line from $C^{1}_{i}$ is also important in $C^{2}_{i}$.
Averaging across data gives the mean overlap line rate for each head.
Figure [2](https://arxiv.org/html/2507.13681v2#S3.F2) (b) shows that, for different $\eta$, the overlap in important lines between $C^{1}_{i}$ and $C^{2}_{i}$ is consistently low and unstable. This confirms that each segment exhibits unique local attention patterns.
This finding indicates that using only a segment (such as the last window or last few tokens) to predict important attention patterns for the whole input is unreliable. As a result, acceleration methods like Minference (Jiang et al., 2024a), SnapKV (Li et al., 2024b), H2O (Zhang et al., 2023), and Keyformer (Adnan et al., 2024), which rely on such assumptions, struggle to deliver consistent performance in real-world scenarios.

### 3.2 Key Point 2: Question Position Matters.

Motivational experiments indicate that both prefilling based methods and decoding phase acceleration methods, which depend on offline sparse pattern discovery or fixed sparse patterns, tend to underperform in practical scenarios. However, their reported outcomes on existing benchmarks are often similar to those of large language models that use full attention. Why does this discrepancy occur?
The main reason is that benchmarks like Longbench (Bai et al., 2024a; b) always place the user question $q_{i}$ at the end of the input $X_{i}=[C_{i},q_{i}]$, so the LLM answers $q_{i}$ based on context $C_{i}$. In this setup, acceleration methods only need to focus on the last observation window (near the question), which makes it easier to identify context tokens relevant to the question, thus partially mitigating the unpredictability found in real-world input patterns.

Figure: (a) Attention map.
Refer to caption: x5.png

Motivational Observation 4: Relying only on the last observation window cannot reliably identify important input tokens for generating the output.
Recent methods like H2O (Zhang et al., 2023), SnapKV (Li et al., 2024b), and AdaKV (Feng et al., 2024) select the top-$B$ important tokens $\hat{X}_{i}$ from $X_{i}$ based on attention between each input token and the last observation window $X^{obs}_{i}$ (the last $n_{s}$ tokens), formally as $\hat{X}_{i}=\arg\max_{\hat{X}_{i}\subseteq X_{i}}\sum_{j=1}^{n_{h}}\sum_{a\in\hat{X}_{i}}\sum_{b\in X^{obs}_{i}}\mathbf{A}^{k}_{i}[a][b]$.
However, the true top-$B$ tokens $\hat{X}^{*}_{i}$ for generating the output $Y_{i}$ should be selected based on their attention to the output tokens: $\hat{X}^{*}_{i}=\arg\max_{\hat{X}_{i}\subseteq X_{i}}\sum_{j=1}^{n_{h}}\sum_{a\in\hat{X}_{i}}\sum_{b\in Y_{i}}\mathbf{A}^{k}_{i}[a][b]$.
We measure the overlap $r_{i}$ between $\hat{X}_{i}$ and $\hat{X}^{*}_{i}$ ($B$ is set to 10% of $|X_{i}|$), using Llama-3.1-8B-Instruct and LongEval’s topic retrieval set, where the instruction $q_{i}$ is placed at the beginning, middle, or end of $C_{i}$.
As shown in Figure [2](https://arxiv.org/html/2507.13681v2#S3.F2) (c), the average overlap of important tokens is highest when the question is at the end, but much lower when it appears in middle or the beginning. This demonstrates that focusing only on the last part of the input misses relevant information unless the question is placed last.

Similarly, as shown in Figure [2](https://arxiv.org/html/2507.13681v2#S3.F2) (d), SnapKV and AdaKV match the original model only when the question is at the end. Their performance drops sharply when the question appears earlier, since they rely on the last tokens for context selection. This shows that current methods are overly dependent on input order and do not generalize well when question positions vary.

## 4 Multi-turn Long-Context Benchmarks

Existing benchmarks,
such as NumericBench (Li et al., 2025), LongBench (Bai et al., 2024a; b), and LongEval (Dacheng Li* & Zhang, 2023)
focus on single-turn tasks and place user queries only at the context end,
which do not reflect the complexity of real-world, multi-turn conversations (LI et al., 2025).
We introduce a benchmark of 11 long-context multi-turn datasets with varied query positions and dependencies.
Specifically, each $m$-turn instance is defined as
$\mathcal{D}={\mathcal{I}_{i}=[(C_{i,1},q_{i,1},a_{i,1}),\dots,(C_{i,m},q_{i,m},a_{i,m})]}_{i=1}^{|\mathcal{D}|}$,
where $C_{i,j}$ is the context at turn $j$ (possibly empty), $q_{i,j}$ is the user query, and $a_{i,j}$ is the LLM-generated answer.
We ensure diversity by: (1) Query Position: For each turn, the query $q_{i,j}$ can appear at the beginning, end, or between paragraphs of $C_{i,j}$, reflecting more realistic query placements.
(2) Query Relevance: Answers $a_{i,j}$ may depend on any subset of current and previous contexts $\{C_{i,1},\ldots,C_{i,j}\}$, with variable subset sizes, simulating diverse real-world dependencies.
We construct multi-turn benchmarks for several tasks, including question answering, summarization, and few-shot learning. For construction procedures and detailed benchmark statistics, please refer to Appendix [A.5](https://arxiv.org/html/2507.13681v2#A1.SS5).

## 5 LoopServe System

Figure: Figure 3: Framework overview of LoopServe.
Refer to caption: x9.png

As shown in Figure [3](https://arxiv.org/html/2507.13681v2#S5.F3),
we propose LoopServe, an adaptive dual-phase system that performs online attention sparsification during the prefilling phase and progressive KV compression during the decoding phase.
For an $m$-turn input $\mathcal{I}_{i}=\{X_{i,j}\}_{j=1}^{m}$, where $X_{i,j}$ is the context or query in the $j$-th turn, LoopServe generates each answer $y_{i,j}$ using these two steps.

Step 1. Online Attention Head Sparsification in Prefilling.
In Algorithm [1](https://arxiv.org/html/2507.13681v2#alg1) (line 3-5) in Appendix,
for each new input $X_{i,j}$ and all inputs $X_{i}=\left(\cup_{j^{\prime}=1}^{j-1}{(X_{i,j^{\prime}}\cup y_{i,j^{\prime}})}\right)\cup X_{i,j}$,
we get $\hat{X}_{i,j}=[y_{i,j-1},X_{i,j}]$ as the new appended input in the $j$ turn.
Then, for each $k$-th attention head, we first compute the attention matrix $\mathbf{A}^{k}_{i}[\hat{X}_{i,j}]\in\mathbb{R}^{\hat{n}_{i,j}\times n_{i}}$,
and then select the slash lines $\mathcal{\hat{S}}^{k}_{i,j}$ and vertical lines $\mathcal{\hat{V}}^{k}_{i,j}$ that collectively recover at least $\alpha$ of the total attention weight in $\mathbf{A}^{k}_{i}[\hat{X}_{i,j}]$.

Step 2. Progressive KV Compression in Decoding.
As described in Algorithm [1](https://arxiv.org/html/2507.13681v2#alg1) (lines 7–14) in Appendix,
after every re-selection interval $n_{d}$ tokens, the framework uses the ProgressiveSelection Algorithm [3](https://arxiv.org/html/2507.13681v2#alg3) to compute a subset of input tokens $\hat{X}^{k}_{i}\subseteq X_{i}$ for each attention head $k$.
these selected tokens $\hat{X}^{k}_{i}$ are important for output generation. At each decoding step, LoopServe leverages the compressed KV cache $\{\mathcal{\hat{S}}^{k}_{i,j^{\prime}},\mathcal{\hat{V}}^{k}_{i,j^{\prime}}\}_{j^{\prime}=1,k}^{j,n_{h}}$ to generate the output sequence $y_{i,j}$.

### 5.1 Online Attention Sparsification in Prefilling

As shown in Key Point 1 in Section [3.1](https://arxiv.org/html/2507.13681v2#S3.SS1), attention sparsity patterns are highly dynamic, making static or offline selection ineffective.
To address this, we propose an online adaptive algorithm that, during prefilling, selects a subset of slash and vertical lines to recover at least an $\alpha$ fraction of the total attention weight for each head, which can be reused in later dialogue turns.

###### Definition 1 (Online Prefilling Sparsification Problem) .

Given the LLM model $M_{\theta}$ with $n_{h}$ attention heads, the input
$X_{i}=\left(\bigcup_{j^{\prime}=1}^{j-1}(X_{i,j^{\prime}}\cup y_{i,j^{\prime}})\right)\cup X_{i,j}$,
where $y_{i,j^{\prime}}$ is the answer for $X_{i,j^{\prime}}$ and $X_{i,j}$ is the current turn’s input. We denote the concatenation of the previous answer $y_{i,j-1}$ and the current user input $X_{i,j}$ as $\hat{X}_{i,j}=[y_{i,j-1},X_{i,j}]$, whose corresponding attention matrix requires sparsification.
The $k$-th attention matrix between $X_{i}$ and $\hat{X}_{i,j}$ is denoted as
$\mathbf{A}^{k}_{i}[\hat{X}_{i,j}]\in\mathbb{R}^{\hat{n}_{i,j}\times n_{i}}$.
Let $\mathcal{S}^{k}_{i,j}$ (resp., $\mathcal{V}^{k}_{i,j}$ ) denote the set of all slash lines (resp., vertical lines) in $\mathbf{A}^{k}_{i}[\hat{X}_{i,j}]$.
The goal is to select a subset of slash lines $\hat{\mathcal{S}}^{k}_{i,j}\subseteq\mathcal{S}^{k}_{i,j}$ and a subset of vertical lines $\hat{\mathcal{V}}^{k}_{i,j}\subseteq\mathcal{V}^{k}_{i,j}$ such that together they recover at least an $\alpha$ fraction of the total attention weight in $\mathbf{A}^{k}_{i}[\hat{X}_{i,j}]$, where $\alpha\in[0,1]$.

$$ $\displaystyle\min\sum_{s\in\mathcal{\hat{S}}^{k}_{i,j}}l_{s}+\sum_{v\in\mathcal{\hat{V}}^{k}_{i,j}}l_{v},\quad s.t.\sum_{(a,b)\in(\mathcal{\hat{S}}^{k}_{i,j}\cup\mathcal{\hat{V}}^{k}_{i,j})}\mathbf{A}^{k}_{i}[a][b]\geq\alpha\cdot\hat{n}_{i,j},$ (1) $$

where $\hat{n}_{i,j}$ is the total attention weight of the matrix $\mathbf{A}^{k}_{i}[\hat{X}_{i,j}]$, and $l_{s}$ (resp., $l_{v}$) is the length of the slash line $s$ (resp., vertical line $v$).

###### Theorem 1 .

The prefilling sparsification problem is NP-hard. The proof is detailed in Appendix [A.6](https://arxiv.org/html/2507.13681v2#A1.SS6).

Algorithm.
Algorithm [2](https://arxiv.org/html/2507.13681v2#alg2) in Appendix [A.7](https://arxiv.org/html/2507.13681v2#A1.SS7) takes as input the concatenated sequence $\hat{X}{i,j}=[y_{i,j-1},X_{i,j}]$, where $y_{i,j-1}$ is the previous answer and $X_{i,j}$ is the current user input. It also requires the $k$-th attention head of the LLM $M_{\theta}$ and a sparsity threshold parameter $\alpha$. The output consists of the selected slash lines $\mathcal{\hat{S}}^{k}_{i,j}$ and selected vertical lines $\mathcal{\hat{V}}^{k}_{i,j}$.
The algorithm begins by sampling a subset $\tilde{X}_{i,j}$ from the concatenated input $\hat{X}_{i,j}$ to reduce computational cost. It then computes the query matrix $\mathbf{\tilde{Q}}^{k}_{i,j}$ for $\tilde{X}_{i,j}$ and the key matrix $\mathbf{K}^{k}_{i}$ for the full input $X_{i}$.
Next, all slash lines $\mathcal{S}^{k}{i,j}$ and vertical lines $\mathcal{V}^{k}_{i,j}$ are summarized based on $\mathbf{A}^{k}_{i}[\tilde{X}{i,j}]$ and sorted in descending order. Two empty sets, $\mathcal{\hat{S}}^{k}_{i,j}$ and $\mathcal{\hat{V}}^{k}_{i,j}$, are initialized to store the selected lines, while the overlap weights $ol_{s}$ and $ol_{v}$ are initialized to zero.
Algorithm [2](https://arxiv.org/html/2507.13681v2#alg2) then iteratively selects lines until the total recovered attention weight sum meets or exceeds $\alpha\cdot\textsf{sum}(\mathbf{A}^{k}_{i}[\tilde{X}_{i,j}])$. At each iteration, it compares the top slash line $s\in\mathcal{S}^{k}_{i,j}$ and the top vertical line $v\in\mathcal{V}^{k}_{i,j}$ based on their marginal contributions, $\Delta w_{s}=w_{s}-ol_{v}$ and $\Delta w_{v}=w_{v}-ol_{s}$. Since each slash line overlaps with only one vertical line, $\Delta w_{s}=w_{s}-ol_{v}$.
The line with the greater marginal contribution is added to its respective set ($\mathcal{\hat{S}}^{k}_{i,j}$ or $\mathcal{\hat{V}}^{k}_{i,j}$), and the overlap weights and total recovered weight are updated accordingly.
The loop terminates once the recovery condition is satisfied, and the algorithm returns the sets $\mathcal{\hat{S}}^{k}_{i,j}$ and $\mathcal{\hat{V}}^{k}_{i,j}$. The time complexity is $O(n_{i}|\tilde{X}_{i,j}|+n_{i}\log n_{i}+n_{i})$, as detailed in Appendix [A.7.1](https://arxiv.org/html/2507.13681v2#A1.SS7.SSS1).

###### Definition 1 (Online Prefilling Sparsification Problem) .

###### Theorem 1 .

### 5.2 Progressive KV Compression in Decoding

As shown in Section [3.2](https://arxiv.org/html/2507.13681v2#S3.SS2), fixed or last-token-focused decoding struggles when queries are not at the end of the input. To overcome this, we propose a progressive KV compression that selects important input tokens based on recent outputs, leading to greater overlap with truly important input tokens.

To verify this, we consider the LLM $M_{\theta}$ with $n_{h}$ attention heads, an input sequence $X_{i}$, a generated output sequence $Y_{i}$, and a window size $n_{w}$.
As in Section [3.2](https://arxiv.org/html/2507.13681v2#S3.SS2), we compute the ground-truth top-$B$ important tokens $\hat{X}^{*}_{i}\subseteq X_{i}$ using the output $Y_{i}$.
We then use observation windows, extracted from either $X_{i}$ or $Y_{i}$, to select the top-$B$ important tokens.
Specifically, given the window size $n_{w}$, the $-\frac{|X_{i}|}{n_{w}}$-th to $-1$ observation windows from $X_{i}$ are defined as
$X_{i}[n_{i}-m\cdot n_{w}:n_{i}-(m-1)\cdot n_{w}]$, $X_{i}[n_{i}-(m-1)\cdot n_{w}:n_{i}-(m-2)\cdot n_{w}]$, …, $X_{i}[n_{i}-n_{w}:n_{i}]$.
The 0-th to $\frac{|Y_{i}|}{n_{w}}$ observation windows from $Y_{i}$ are
$Y_{i}[0:n_{w}]$, $Y_{i}[n_{w}:2n_{w}]$, …, $Y_{i}[(m-1)\cdot n_{w}:m\cdot n_{w}]$.
For each observation window $X^{obs}_{i}$ from $X_{i}$ or $Y_{i}$, we select the top-$B$ tokens $\hat{X}_{i}\subseteq X_{i}$ following Section [3.2](https://arxiv.org/html/2507.13681v2#S3.SS2), and compute the overlap rate between $\hat{X}_{i}$ and the ground truth $\hat{X}^{*}_{i}$ as $\frac{|\hat{X}_{i}\cap\hat{X}^{*}_{i}|}{B}$.

Figure: (a) Important token overlapping.
Refer to caption: x10.png

We use LongEval (Dacheng Li* & Zhang, 2023) as in Section [3](https://arxiv.org/html/2507.13681v2#S3), experimenting with Llama-3.1-8B-Instruct and setting $B\in\{5\%,10\%,15\%\}\cdot|X_{i}|$. Figure [4](https://arxiv.org/html/2507.13681v2#S5.F4)(a) shows that important tokens selected from input blocks (block index $<0$) have low overlap rates, while those selected from output blocks ($\geq 0$) have much higher overlap. This indicates that using output tokens is more effective for identifying relevant input tokens.

We also observe that the overlap of important input tokens between output blocks decreases as the distance between blocks increases, which indicates that we can use the most recent output tokens to select important input tokens for the next output block.
Specifically, given the output sequence $Y_{i}$, we divide it into $n_{b}$ blocks, i.e., $Y_{i}=[Y^{1}_{i},\cdots,Y^{n_{b}}_{i}]$, where $Y^{j}_{i}$ denotes the $j$-th output block of size $\frac{|Y_{i}|}{n_{b}}$. For each block $Y^{j}_{i}$, we compute the top-$B$ important input tokens as:
$\hat{X}_{i,Y^{j}_{i}}=\arg\max_{\hat{X}_{i}\subseteq X_{i}}\sum_{k=1}^{n_{h}}\sum_{a\in\hat{X}_{i}}\sum_{b\in Y^{j}_{i}}\mathbf{A}^{k}_{i}[a][b]$.
Next, we compare the overlap $\frac{|\hat{X}_{i,Y^{j}_{i}}\cap\hat{X}_{i,Y^{j^{\prime}}_{i}}|}{B}$ of important input tokens between every pair of output blocks $Y^{j}_{i}$ and $Y^{j^{\prime}}_{i}$. As shown in Figure [4](https://arxiv.org/html/2507.13681v2#S5.F4) (b), for each block $Y^{j}_{i}$, the overlap of important input tokens between $Y^{j}_{i}$ and $Y^{j^{\prime}}_{i}$ (where $j^{\prime}>j$) gradually decreases as the block distance increases. Notably, the overlap between $Y^{j}_{i}$ and its immediate successor $Y^{j+1}_{i}$ is higher compared to earlier blocks such as $Y^{j-2}_{i}$. This indicates that tokens identified from $Y^{j}_{i}$ are highly relevant for the generation of $Y^{j+1}_{i}$.
Therefore, when generating $Y^{j+1}_{i}$, we can use the preceding block $Y^{j}_{i}$ to dynamically identify the top-$B$ important input tokens.
Based on this, we propose the following progressive KV compression algorithm.

Algorithm.
Algorithm [3](https://arxiv.org/html/2507.13681v2#alg3) firstly set the answer $y_{i,j}$ as empty and decoding step counter $n_{o}$ to 0 (line 1).
During the decoding loop, if the current step reaches either the empirically predefined decoding size 16 or a re-selection interval $n_{d}$ (line 3),
the algorithm extracts the most recent tokens from the input sequence $X_{i}$, i.e., $X^{obs}_{i}=X_{i}[|X_{i}|-n_{d}:|X_{i}|]$), and dynamically updates the compressed KV cache subset $\hat{X}^{k}_{i}$ for each $k$-th attention head (line 4-5). Specifically, for each head, we select top-$B$ tokens for each head as:
$\hat{X}^{k}_{i}=\arg\max_{\hat{X}^{k}_{i}\subseteq X_{i},|\hat{X}^{k}_{i}|=B|}\sum_{a\in\hat{X}_{i}}\sum_{b\in X^{obs}_{i}}\mathbf{A}^{k}_{i}[a][b],$
The LLM generates the next token using the compressed KV cache and the updated input, which is appended to both the input and output sequences (line 6-9). This process iterates until the LLM completes generation, returning the final answer $y_{i,j}$.

## 6 EXPERIMENTS

### 6.1 Experimental Settings

Datasets, Tasks, and Evaluation Metrics.
We design multi-turn long-context benchmarks.
Each instance contains multiple rounds with diverse query positions and dependencies.
It covers Question Answering, Summarization, and Few-shot Learning. Dataset statistics and each corresponding metric (e.g., F1, Accuracy, and Rouge-L) are in Table [4](https://arxiv.org/html/2507.13681v2#A1.T4) in Appendix [A.5.2](https://arxiv.org/html/2507.13681v2#A1.SS5.SSS2).

Baselines.
We compare our LoopServe with six state-of-the-art KV cache algorithms on two representation LLM base models,
including Llama-3.1-8B-Instruct (Grattafiori et al., 2024) and Qwen2.5-7B-Instruct (Team, 2024).
The KV cache methods include SnapKV (Snap) Li et al. (2024b), AdaKV (Ada) Feng et al. (2024), StreamingLLM (SLLM) Xiao et al. (2024), A-shape (A-S) Xiao et al. (2024), Tri-Shape (T-S) LI et al. (2025), and Minference (Minf) Jiang et al. (2024a).

Hyperparameter and Hardware Setting. All codes are executed on a Rocky Linux 8.10 machine with an 8-core Intel® Xeon® Gold 6542Y CPU, an NVIDIA H100 GPU with 80GB of memory, and 256GB of RAM.
For baselines, we use their suggested setting.
For main experiments in Section [6.2](https://arxiv.org/html/2507.13681v2#S6.SS2), for our LoopServe, we set $\alpha=0.955$, and $n_{d}=16$ as defaults, and we set the token budget $B=1024$ following Li et al. (2024b)  Feng et al. (2024) for all baselines and LoopServe.

**Table 1: Effectiveness Evaluation. The bold number indicates the best performance.**
| P | Data | Llama-3.1 | Qwen2.5 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Base | Snap | Ada | SLLM | A-S | T-S | Minf | Ours | Base | Snap | Ada | SLLM | A-S | T-S | Minf | Ours |  |  |  |
| Begin | QA | MFQA-en | 45.70 | 36.50 | 34.94 | 25.83 | 28.00 | 34.96 | 43.05 | 46.82 | 44.24 | 35.59 | 33.00 | 21.45 | 29.56 | 38.14 | 42.63 | 43.47 |
| 2WikiMQA | 31.68 | 29.31 | 28.73 | 22.05 | 19.42 | 24.20 | 28.57 | 35.11 | 37.86 | 34.54 | 33.83 | 23.19 | 22.11 | 32.90 | 35.33 | 37.52 |  |  |
| Musique | 17.16 | 14.29 | 14.80 | 9.76 | 4.22 | 8.18 | 14.92 | 18.81 | 18.22 | 14.74 | 13.95 | 8.68 | 5.92 | 12.15 | 15.15 | 16.63 |  |  |
| HotpotQA | 36.67 | 33.87 | 32.98 | 22.52 | 12.72 | 21.29 | 34.38 | 39.00 | 42.93 | 38.90 | 37.56 | 21.42 | 17.22 | 31.03 | 38.67 | 42.50 |  |  |
| NrtvQA | 13.40 | 13.42 | 8.67 | 5.22 | 7.61 | 9.19 | 13.47 | 14.03 | 13.63 | 11.05 | 10.18 | 6.82 | 7.57 | 10.45 | 10.78 | 14.36 |  |  |
| Qasper | 25.33 | 20.77 | 17.03 | 16.58 | 20.64 | 23.37 | 22.79 | 24.64 | 26.08 | 21.79 | 20.13 | 17.96 | 19.67 | 23.44 | 24.92 | 25.37 |  |  |
| SUM | MultiNews | 20.08 | 19.20 | 18.03 | 19.30 | 20.10 | 20.15 | 20.25 | 20.14 | 18.39 | 15.87 | 14.52 | 17.29 | 18.29 | 18.30 | 18.30 | 20.14 |  |
| GovReport | 25.25 | 18.36 | 16.53 | 17.98 | 24.16 | 24.13 | 24.55 | 24.90 | 20.93 | 16.80 | 15.86 | 15.90 | 22.28 | 21.90 | 20.86 | 23.60 |  |  |
| QMSum | 20.53 | 17.49 | 17.56 | 14.66 | 17.77 | 18.92 | 20.15 | 20.65 | 19.97 | 17.54 | 17.39 | 14.66 | 18.45 | 19.12 | 19.61 | 19.66 |  |  |
| FS | TREC | 46.99 | 46.74 | 45.23 | 46.23 | 41.21 | 46.99 | 45.48 | 47.99 | 65.08 | 64.07 | 63.32 | 62.65 | 60.30 | 56.28 | 64.07 | 65.33 |  |
| SAMSUM | 17.32 | 16.75 | 16.48 | 12.95 | 17.39 | 17.35 | 17.46 | 18.12 | 16.19 | 13.97 | 13.15 | 11.22 | 15.32 | 15.92 | 15.96 | 17.15 |  |  |
| Middle | QA | MFQA-en | 46.73 | 37.30 | 35.19 | 26.87 | 28.26 | 33.39 | 43.84 | 44.73 | 44.00 | 34.21 | 31.68 | 22.73 | 29.06 | 34.31 | 41.42 | 41.95 |
| 2WikiMQA | 34.10 | 31.71 | 29.90 | 25.59 | 18.77 | 27.26 | 32.50 | 34.25 | 27.80 | 22.32 | 22.69 | 14.19 | 20.18 | 26.15 | 25.40 | 27.01 |  |  |
| Musique | 16.30 | 13.68 | 14.05 | 8.59 | 3.17 | 9.51 | 15.39 | 17.48 | 10.05 | 7.37 | 7.15 | 3.32 | 4.92 | 8.38 | 8.76 | 9.13 |  |  |
| HotpotQA | 40.63 | 37.48 | 36.30 | 27.30 | 12.36 | 25.25 | 36.81 | 41.25 | 29.43 | 25.24 | 24.56 | 12.25 | 12.96 | 22.00 | 26.43 | 29.05 |  |  |
| NrtvQA | 15.29 | 13.06 | 10.64 | 7.26 | 7.14 | 10.10 | 13.98 | 15.25 | 14.82 | 11.88 | 11.83 | 9.04 | 7.68 | 11.24 | 11.75 | 15.21 |  |  |
| Qasper | 30.79 | 26.80 | 22.07 | 21.40 | 24.90 | 28.86 | 28.47 | 31.12 | 28.74 | 23.57 | 21.77 | 20.75 | 24.73 | 27.84 | 28.72 | 29.27 |  |  |
| SUM | MultiNews | 20.59 | 19.78 | 18.12 | 19.91 | 20.49 | 20.52 | 20.79 | 20.66 | 18.37 | 15.54 | 14.28 | 17.53 | 18.09 | 18.26 | 18.19 | 18.44 |  |
| GovReport | 24.08 | 18.39 | 15.92 | 18.09 | 23.50 | 24.01 | 23.74 | 22.88 | 20.54 | 16.24 | 15.25 | 15.99 | 21.00 | 21.55 | 20.70 | 20.68 |  |  |
| QMSum | 20.51 | 17.90 | 17.84 | 15.08 | 17.62 | 17.93 | 20.20 | 20.41 | 20.04 | 17.79 | 17.29 | 15.06 | 18.57 | 18.67 | 19.46 | 19.81 |  |  |
| FS | TREC | 50.00 | 50.00 | 48.74 | 50.25 | 50.00 | 50.76 | 52.27 | 56.03 | 64.07 | 62.06 | 60.81 | 63.32 | 63.82 | 40.71 | 64.07 | 65.33 |  |
| SAMSUM | 10.62 | 12.03 | 11.83 | 13.34 | 11.10 | 10.92 | 10.62 | 17.43 | 12.38 | 12.55 | 13.28 | 13.83 | 15.65 | 12.95 | 12.93 | 12.40 |  |  |
| End | QA | MFQA-en | 50.93 | 47.93 | 48.38 | 32.52 | 28.62 | 51.40 | 49.67 | 51.69 | 48.82 | 47.57 | 47.24 | 29.28 | 27.66 | 47.94 | 49.18 | 48.67 |
| 2WikiMQA | 42.43 | 42.34 | 41.96 | 37.20 | 25.19 | 39.54 | 41.75 | 44.05 | 42.70 | 42.25 | 41.24 | 32.89 | 26.50 | 37.54 | 41.34 | 42.24 |  |  |
| Musique | 29.39 | 28.07 | 29.01 | 20.96 | 7.80 | 26.44 | 23.56 | 31.60 | 24.18 | 23.08 | 22.39 | 11.82 | 8.68 | 17.65 | 24.34 | 24.82 |  |  |
| HotpotQA | 53.62 | 52.38 | 53.59 | 43.83 | 25.04 | 51.71 | 51.97 | 55.05 | 53.09 | 51.03 | 50.71 | 35.64 | 24.63 | 43.67 | 53.01 | 53.13 |  |  |
| NrtvQA | 25.76 | 25.50 | 24.58 | 19.28 | 14.19 | 23.90 | 23.87 | 25.87 | 19.07 | 17.90 | 16.75 | 14.08 | 11.41 | 14.39 | 18.37 | 19.86 |  |  |
| Qasper | 37.97 | 35.95 | 33.98 | 28.01 | 27.37 | 38.67 | 36.50 | 38.27 | 33.55 | 31.82 | 30.21 | 24.28 | 25.15 | 33.72 | 34.18 | 33.18 |  |  |
| SUM | MultiNews | 20.59 | 20.03 | 18.87 | 19.97 | 20.16 | 20.40 | 20.49 | 20.45 | 18.31 | 16.61 | 15.32 | 17.74 | 17.99 | 18.01 | 18.36 | 18.40 |  |
| GovReport | 23.90 | 20.10 | 18.54 | 18.04 | 23.17 | 23.35 | 23.92 | 24.27 | 21.21 | 18.06 | 17.09 | 16.95 | 21.53 | 21.82 | 21.28 | 21.10 |  |  |
| QMSum | 22.69 | 22.21 | 22.12 | 19.67 | 18.59 | 22.28 | 22.27 | 22.82 | 21.17 | 20.15 | 20.03 | 18.13 | 18.07 | 20.33 | 21.04 | 20.95 |  |  |
| FS | TREC | 59.05 | 58.54 | 58.54 | 58.54 | 52.51 | 59.55 | 59.05 | 60.31 | 68.34 | 66.08 | 66.59 | 67.84 | 63.82 | 67.59 | 68.85 | 68.34 |  |
| SAMSUM | 18.78 | 23.88 | 20.63 | 19.84 | 18.45 | 17.75 | 17.62 | 23.53 | 39.46 | 39.58 | 38.77 | 38.71 | 39.13 | 39.20 | 39.57 | 39.85 |  |  |

### 6.2 Main Experiments

Effectiveness Evaluation.
To evaluate LoopServe and baselines, we conduct experiments on the proposed 11 multi-turn long-context datasets across three tasks: QA, Summarization (SUM), and Few-shot Learning (FS).
For each dataset, we compare LoopServe with six state-of-the-art KV cache acceleration baselines and two base LLMs, using F1, Rouge-L, or Accuracy as appropriate.
As shown in Table [1](https://arxiv.org/html/2507.13681v2#S6.T1), LoopServe achieves the best or comparable results across most datasets and query positions.
Notably, LoopServe maintains strong performance regardless of query location, while baselines like SnapKV and AdaKV perform well only when the query is at the end. This highlights their reliance on positional heuristics, which limits generalization. In contrast, LoopServe’s adaptive approach consistently yields higher accuracy and quality, even as context length increases. These gains hold for both Llama-3.1 and Qwen2.5, showing LoopServe generalizes well across LLMs.

Efficiency Evaluation.
Beyond effectiveness, we also assess LoopServe’s generation efficiency. As shown in Figure [5](https://arxiv.org/html/2507.13681v2#S6.F5) (a), LoopServe delivers the highest efficiency.
This is achieved through efficient online sparsification, which selects only the most critical attention components, and adaptive KV compression, which maintains a compact, relevant cache. Together, these mechanisms reduce computation and memory usage, enabling fast and high-quality generation.

Ablation Study.
We explore LoopServe-D (progressive KV compression only) and LoopServe-P (online prefilling sparsification only) on three datasets (MF, 2WM, Qsp) using Llama and Qwen.
As shown in Figure [5](https://arxiv.org/html/2507.13681v2#S6.F5) (b) and Figure [7](https://arxiv.org/html/2507.13681v2#A1.F7) in Appendix,
LoopServe achieves the best performance, indicating both components are essential and complementary. This advantage holds across tasks, datasets, query positions, and model architectures.
The ablation study reveals that these two components are complementary: while each addresses a different bottleneck in LLM inference, their combination ensures robust adaptation to diverse input patterns and maximizes both efficiency and accuracy.

### 6.3 Parameter Sensitivity

We analyze all hyperparameters in LoopServe: attention sparsity threshold $\alpha$ in online prefilling, token budget $B$, and decoding interval $n_{d}$ in progressive KV compression.
Due to space limit, the analysis of the parameter $n_{d}$ is presented in Appendix [A.8.1](https://arxiv.org/html/2507.13681v2#A1.SS8.SSS1).

Threshold $\alpha$ in  Equation [1](https://arxiv.org/html/2507.13681v2#S5.E1).
The parameter $\alpha$ controls how much total attention weight is preserved in prefilling. Higher $\alpha$ keeps more information but increases computation; lower $\alpha$ boosts efficiency but may lose context.
We evaluate LoopServe on 2WikiMQA and Qasper, with Llama and Qwen backbones, across questions at the beginning (-B), middle (-M), and end (-E) positions, varying $\alpha\in\{0.980,0.985,0.990,0.995,1.00\}$. As shown in Figure [5](https://arxiv.org/html/2507.13681v2#S6.F5) (c) and Figure [8](https://arxiv.org/html/2507.13681v2#A1.F8) (a) in Appendix, LoopServe get the best accuracy and efficient for $\alpha$ between 0.99 and 1.00. Setting $\alpha$ too low hurts quality, while values close to 1.00 reduce efficiency gains. Overall, LoopServe is not overly sensitive to $\alpha$ within this range, allowing users to balance speed and quality.

Budget $B$.
The token selection budget $B$ in LoopServe’s progressive KV compression controls the trade-off between efficiency and output quality. We evaluate this on MultiFieldQA and Qasper with queries at the beginning, middle, and end. As shown in Figure [5](https://arxiv.org/html/2507.13681v2#S6.F5) (d) and Figure [8](https://arxiv.org/html/2507.13681v2#A1.F8) (b) in Appendix, increasing $B$ improves accuracy by preserving more relevant tokens, but gains are limited beyond 1024 tokens while computation and memory costs rise. Smaller budgets (256 or 512) reduce accuracy, especially for queries at the beginning or middle, as important tokens may be missed. End-position queries are less affected since key tokens are already cached. Overall, a budget of 1024–2048 tokens offers the best balance of performance and efficiency across all query positions.

Figure: (a) Generation latency.
Refer to caption: x12.png

## 7 Conclusion

In this paper, we propose LoopServe, an adaptive dual-phase LLM inference acceleration system designed for realistic multi-turn dialogues. By combining online attention sparsification and progressive KV compression, LoopServe addresses the limitations of static acceleration methods and adapts efficiently to dynamic conversational patterns. Our experiments on diverse, multi-turn benchmarks show that LoopServe significantly improves both inference speed and output quality compared to existing baselines, regardless of query position. This work provides a practical solution for efficient and effective LLM deployment in real-world dialogue scenarios.

## References

- Adnan et al. (2024)
Muhammad Adnan, Akhil Arunkumar, Gaurav Jain, Prashant J Nair, Ilya
Soloveychik, and Purushotham Kamath.
Keyformer: Kv cache reduction through key tokens selection for
efficient generative inference.
*Proceedings of Machine Learning and Systems*, 6:114–127, 2024.
- An et al. (2023)
Chenxin An, Shansan Gong, Ming Zhong, Xingjian Zhao, Mukai Li, Jun Zhang,
Lingpeng Kong, and Xipeng Qiu.
L-Eval: Instituting Standardized Evaluation for Long
Context Language Models, 2023.
URL [https://arxiv.org/abs/2307.11088](https://arxiv.org/abs/2307.11088).
- Bai et al. (2024a)
Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang,
Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, Yuxiao Dong, Jie Tang, and
Juanzi Li.
LongBench: A bilingual, multitask benchmark for long context
understanding.
In *Proceedings of the 62nd Annual Meeting of the Association
for Computational Linguistics (Volume 1: Long Papers)*, pp. 3119–3137,
Bangkok, Thailand, August 2024a. Association for Computational
Linguistics.
doi: 10.18653/v1/2024.acl-long.172.
URL [https://aclanthology.org/2024.acl-long.172](https://aclanthology.org/2024.acl-long.172).
- Bai et al. (2024b)
Yushi Bai, Shangqing Tu, Jiajie Zhang, Hao Peng, Xiaozhi Wang, Xin Lv, Shulin
Cao, Jiazheng Xu, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li.
Longbench v2: Towards deeper understanding and reasoning on realistic
long-context multitasks.
*arXiv preprint arXiv:2412.15204*, 2024b.
- Brown et al. (2020)
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla
Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell,
Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon
Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris
Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess,
Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever,
and Dario Amodei.
Language models are few-shot learners.
In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin
(eds.), *Advances in Neural Information Processing Systems*, volume 33,
pp. 1877–1901. Curran Associates, Inc., 2020.
URL
[https://proceedings.neurips.cc/paper_files/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf](https://proceedings.neurips.cc/paper_files/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf).
- Chen et al. (2025)
Sibei Chen, Ju Fan, Bin Wu, Nan Tang, Chao Deng, Pengyi Wang, Ye Li, Jian Tan,
Feifei Li, Jingren Zhou, et al.
Automatic database configuration debugging using retrieval-augmented
language models.
*Proceedings of the ACM on Management of Data*, 3(1):1–27, 2025.
- Dacheng Li* & Zhang (2023)
Anze Xie Ying Sheng Lianmin Zheng Joseph E. Gonzalez Ion Stoica Xuezhe Ma
Dacheng Li*, Rulin Shao* and Hao Zhang.
How long can open-source llms truly promise on context length?, June
2023.
URL [https://lmsys.org/blog/2023-06-29-longchat](https://lmsys.org/blog/2023-06-29-longchat).
- DeepSeek-AI (2024)
DeepSeek-AI.
Deepseek-v3 technical report, 2024.
URL [https://arxiv.org/abs/2412.19437](https://arxiv.org/abs/2412.19437).
- DeepSeek-AI (2025)
DeepSeek-AI.
Deepseek-r1: Incentivizing reasoning capability in llms via
reinforcement learning, 2025.
URL [https://arxiv.org/abs/2501.12948](https://arxiv.org/abs/2501.12948).
- Deng et al. (2025)
Cheng Deng, Luoyang Sun, Jiwen Jiang, Yongcheng Zeng, Xinjian Wu, Wenxin Zhao,
Qingfa Xiao, Jiachuan Wang, Haoyang Li, Lei Chen, et al.
Plm: Efficient peripheral language models hardware-co-designed for
ubiquitous computing.
*arXiv preprint arXiv:2503.12167*, 2025.
- Edge et al. (2024)
Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody,
Steven Truitt, Dasha Metropolitansky, Robert Osazuwa Ness, and Jonathan
Larson.
From local to global: A graph rag approach to query-focused
summarization.
*arXiv preprint arXiv:2404.16130*, 2024.
- Feng et al. (2024)
Yuan Feng, Junlin Lv, Yukun Cao, Xike Xie, and S Kevin Zhou.
Ada-kv: Optimizing kv cache eviction by adaptive budget allocation
for efficient llm inference.
*arXiv preprint arXiv:2407.11550*, 2024.
- Ge et al. (2024)
Suyu Ge, Yunan Zhang, Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao.
Model tells you what to discard: Adaptive KV cache compression for
llms.
In *The Twelfth International Conference on Learning
Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024*.
OpenReview.net, 2024.
- Grattafiori et al. (2024)
Aaron Grattafiori, Abhimanyu Dubey, et al.
The llama 3 herd of models, 2024.
URL [https://arxiv.org/abs/2407.21783](https://arxiv.org/abs/2407.21783).
- Hadi et al. (2023)
Muhammad Usman Hadi, Rizwan Qureshi, Abbas Shah, Muhammad Irfan, Anas Zafar,
Muhammad Bilal Shaikh, Naveed Akhtar, Jia Wu, Seyedali Mirjalili, et al.
A survey on large language models: Applications, challenges,
limitations, and practical usage.
*Authorea Preprints*, 3, 2023.
- Hsieh et al. (2024)
Cheng-Ping Hsieh, Simeng Sun, Samuel Kriman, Shantanu Acharya, Dima Rekesh, Fei
Jia, Yang Zhang, and Boris Ginsburg.
Ruler: What’s the real context size of your long-context language
models?
*arXiv preprint arXiv:2404.06654*, 2024.
- Jiang et al. (2023)
Huiqiang Jiang, Qianhui Wu, Chin-Yew Lin, Yuqing Yang, and Lili Qiu.
Llmlingua: Compressing prompts for accelerated inference of large
language models.
In *Proceedings of the 2023 Conference on Empirical Methods in
Natural Language Processing*, pp. 13358–13376, 2023.
- Jiang et al. (2024a)
Huiqiang Jiang, Yucheng Li, Chengruidong Zhang, Qianhui Wu, Xufang Luo, Surin
Ahn, Zhenhua Han, Amir Abdi, Dongsheng Li, Chin-Yew Lin, et al.
Minference 1.0: Accelerating pre-filling for long-context llms via
dynamic sparse attention.
*Advances in Neural Information Processing Systems*,
37:52481–52515, 2024a.
- Jiang et al. (2024b)
Wenqi Jiang, Marco Zeller, Roger Waleffe, Torsten Hoefler, and Gustavo Alonso.
Chameleon: a heterogeneous and disaggregated accelerator system for
retrieval-augmented language models.
*Proc. VLDB Endow.*, 18(1):42–52,
2024b.
URL [https://www.vldb.org/pvldb/vol18/p42-jiang.pdf](https://www.vldb.org/pvldb/vol18/p42-jiang.pdf).
- Kim et al. (2025)
Yekyung Kim, Jenna Russell, Marzena Karpinska, and Mohit Iyyer.
One ruler to measure them all: Benchmarking multilingual long-context
language models, 2025.
URL [https://arxiv.org/abs/2503.01996](https://arxiv.org/abs/2503.01996).
- Lai et al. (2025)
Xunhao Lai, Jianqiao Lu, Yao Luo, Yiyuan Ma, and Xun Zhou.
Flexprefill: A context-aware sparse attention mechanism for efficient
long-sequence inference.
In *The Thirteenth International Conference on Learning
Representations*, 2025.
URL [https://openreview.net/forum?id=OfjIlbelrT](https://openreview.net/forum?id=OfjIlbelrT).
- Li et al. (2024a)
Haoyang Li, Yiming Li, Anxin Tian, Tianhao Tang, Zhanchao Xu, Xuejia Chen,
Nicole Hu, Wei Dong, Qing Li, and Lei Chen.
A survey on large language model acceleration based on kv cache
management.
*CoRR*, abs/2412.19442, 2024a.
URL
[http://dblp.uni-trier.de/db/journals/corr/corr2412.html#abs-2412-19442](http://dblp.uni-trier.de/db/journals/corr/corr2412.html#abs-2412-19442).
- Li et al. (2025)
Haoyang Li, Xuejia Chen, Zhanchao XU, Darian Li, Nicole Hu, Fei Teng, Yiming
Li, Luyu Qiu, Chen Jason Zhang, Qing Li, and Lei Chen.
Exposing numeracy gaps: A benchmark to evaluate fundamental numerical
abilities in large language models, 2025.
URL [https://arxiv.org/abs/2502.11075](https://arxiv.org/abs/2502.11075).
- LI et al. (2025)
YUCHENG LI, Huiqiang Jiang, Qianhui Wu, Xufang Luo, Surin Ahn, Chengruidong
Zhang, Amir H. Abdi, Dongsheng Li, Jianfeng Gao, Yuqing Yang, and Lili Qiu.
SCBench: A KV cache-centric analysis of long-context methods.
In *The Thirteenth International Conference on Learning
Representations*, 2025.
URL [https://openreview.net/forum?id=gkUyYcY1W9](https://openreview.net/forum?id=gkUyYcY1W9).
- Li et al. (2024b)
Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli,
Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen.
Snapkv: Llm knows what you are looking for before generation.
*Advances in Neural Information Processing Systems*,
37:22947–22970, 2024b.
- Lv et al. (2024)
Junlin Lv, Yuan Feng, Xike Xie, Xin Jia, Qirong Peng, and Guiming Xie.
Critiprefill: A segment-wise criticality-based approach for
prefilling acceleration in llms.
*arXiv preprint arXiv:2409.12490*, 2024.
- Pan et al. (2024)
Zhuoshi Pan, Qianhui Wu, Huiqiang Jiang, Menglin Xia, Xufang Luo, Jue Zhang,
Qingwei Lin, Victor Rühle, Yuqing Yang, Chin-Yew Lin, et al.
Llmlingua-2: Data distillation for efficient and faithful
task-agnostic prompt compression.
*arXiv preprint arXiv:2403.12968*, 2024.
- Qin et al. (2024)
Yanzhao Qin, Tao Zhang, Tao Zhang, Yanjun Shen, Wenjing Luo, Haoze Sun, Yan
Zhang, Yujing Qiao, Weipeng Chen, Zenan Zhou, Wentao Zhang, and Bin Cui.
Sysbench: Can large language models follow system messages?, 2024.
URL [https://arxiv.org/abs/2408.10943](https://arxiv.org/abs/2408.10943).
- Radford et al. (2018)
Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al.
Improving language understanding by generative pre-training.
2018.
- Radford et al. (2019)
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya
Sutskever, et al.
Language models are unsupervised multitask learners.
*OpenAI blog*, 1(8):9, 2019.
- Team (2024)
Qwen Team.
Qwen2.5: A party of foundation models, September 2024.
URL [https://qwenlm.github.io/blog/qwen2.5/](https://qwenlm.github.io/blog/qwen2.5/).
- Touvron et al. (2023)
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne
Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric
Hambro, Faisal Azhar, et al.
Llama: Open and efficient foundation language models.
*arXiv preprint arXiv:2302.13971*, 2023.
- van Renen et al. (2024)
Alexander van Renen, Mihail Stoian, and Andreas Kipf.
Dataloom: Simplifying data loading with llms.
*Proc. VLDB Endow.*, 17(12):4449–4452,
August 2024.
URL
[http://dblp.uni-trier.de/db/journals/pvldb/pvldb17.html#RenenSK24](http://dblp.uni-trier.de/db/journals/pvldb/pvldb17.html#RenenSK24).
- Vaswani (2017)
A Vaswani.
Attention is all you need.
*Advances in Neural Information Processing Systems*, 2017.
- Wang et al. (2025)
Yubo Wang, Haoyang Li, Fei Teng, and Lei Chen.
Graph-based retrieval augmented generation for dynamic few-shot text
classification.
*arXiv preprint arXiv:2501.02844*, 2025.
- Xiao et al. (2024)
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis.
Efficient streaming language models with attention sinks.
In *The Twelfth International Conference on Learning
Representations*, 2024.
URL [https://openreview.net/forum?id=NG7sS51zVF](https://openreview.net/forum?id=NG7sS51zVF).
- Yoon et al. (2024)
Chanwoong Yoon, Taewhoo Lee, Hyeon Hwang, Minbyul Jeong, and Jaewoo Kang.
Compact: Compressing retrieved documents actively for question
answering.
*arXiv preprint arXiv:2407.09014*, 2024.
- Zhang et al. (2023)
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai,
Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, et al.
H2o: Heavy-hitter oracle for efficient generative inference of large
language models.
*Advances in Neural Information Processing Systems*,
36:34661–34710, 2023.
- Zhao et al. (2024)
Xinyang Zhao, Xuanhe Zhou, and Guoliang Li.
Chat2data: An interactive data analysis system with rag, vector
databases and llms.
*Proceedings of the VLDB Endowment*, 17(12):4481–4484, 2024.
- Zhou et al. (2024)
Xuanhe Zhou, Zhaoyan Sun, and Guoliang Li.
Db-gpt: Large language model meets database.
*Data Science and Engineering*, 9(1):102–111, 2024.

## Appendix A Appendix

### A.1 Important Notations Table

**Table 2: Summary of important notations.**
| Symbol | Definition |
| --- | --- |
| $X_{i}$ | Input sequence of tokens |
| $X_{i,j}$ | The $j$-turn input of $X_{i}$ |
| $Y_{i}$ | Output sequence of tokens |
| $y_{i,j}$ | The $j$-turn output of $X_{i}$ |
| $n_{i},n_{i,j}$ | Length of input sequence $X_{i}$ and $X_{i,j}$ |
| $m_{i},m_{i,j}$ | Length of output sequence $Y_{i}$ and $y_{i,j}$ |
| $M_{\theta}$ | LLM model |
| $n_{h}$ | The total number of attention head of $M_{\theta}$ |
| $\mathbf{Q}^{k}_{i},\mathbf{K}^{k}_{i},\mathbf{V}^{k}_{i}$ | Query, Key, and Value matrices |
| $\mathbf{A}^{k}_{i}$ | The $k$-th attention head $X_{i}$ |
| $\mathcal{S}^{k}_{i}$, $\mathcal{V}^{k}_{i}$ | Slash and vertical lines of head $\mathbf{A}^{k}_{i}$ |
| $\mathcal{\hat{S}}^{k}_{i},\mathcal{\hat{V}}^{k}_{i}$ | Selected slash lines and vertical lines |
| $n_{d}$ | Decoding interval |
| $B$ | Budget for input tokens |
| $\hat{X}^{k}_{i}$ | Selected important tokens for attention head $k$ |

Table [2](https://arxiv.org/html/2507.13681v2#A1.T2) provides detailed definitions of important notations appearing in this paper.

### A.2 Summary Table of KV-based approaches

**Table 3: LLM acceleration model comparisons, following LI et al. (2025). P and D denote whether the model has optimization in the Prefilling and Decoding phases, respectively. $n$ is the token size of the input, $m$ is the generation token size, and $c$ and $k$ are constants with $c,k\ll n$ and $c,k\ll m$.**
| Methods | P | D | KV Size | Prefilling | Decoding |
| --- | --- | --- | --- | --- | --- |
| LLMLingua Pan et al. (2024) | ✓ | $\times$ | $O(\alpha n)$ | $O(\alpha^{2}n^{2})$ | $O(\alpha nm)$ |
| A-shape Xiao et al. (2024) | ✓ | $\times$ | $O(n)$ | $O(kn)$ | $O(nm)$ |
| Tri-shape LI et al. (2025) | ✓ | $\times$ | $O(n)$ | $O(kn)$ | $O(nm)$ |
| MInference Jiang et al. (2024a) | ✓ | $\times$ | $O(n)$ | $O(kn)$ | $O(nm)$ |
| SLLM Xiao et al. (2024) | $\times$ | ✓ | $O(k)$ | $O(n^{2})$ | $O(km)$ |
| SnapKV Li et al. (2024b) | $\times$ | ✓ | $O(k)$ | $O(n^{2})$ | $O(km)$ |
| AdaKV Feng et al. (2024) | $\times$ | ✓ | $O(k)$ | $O(n^{2})$ | $O(km)$ |
| LoopServe | ✓ | ✓ | $O(k)$ | $O(kn)$ | $O(k(m-c)+nc)$ |

Table [3](https://arxiv.org/html/2507.13681v2#A1.T3) summarizes the time complexity for each KV-based approach.

### A.3 Supplementary Figure for Motivational Observation 2

Figure: Figure 6: Overlap rate of each head regarding different inputs of Mistral-7B-Instruct-v0.3
Refer to caption: x16.png

Figure [7](https://arxiv.org/html/2507.13681v2#A1.F7) shows that for most heads, the overlap of Mistral-7B-Instruct-v0.3 remains below 0.5.
Please refer to the detailed analysis in Section [3.1](https://arxiv.org/html/2507.13681v2#S3.SS1) motivational experiment 2.

### A.4 Supplementary Results for Ablation Study

Figure [7](https://arxiv.org/html/2507.13681v2#A1.F7) shows that LoopServe applied on Qwen2.5-7B-Instruct achieves the best performance, indicating the significance of both components.
Please refer to the detailed analysis in ablation study in Section [6.2](https://arxiv.org/html/2507.13681v2#S6.SS2).

### A.5 Long-context Multi-turn LongBench

Recently, various long-context benchmarks, such as NumericBench Li et al. (2025), LongBench Bai et al. (2024a), and LongEval Dacheng Li* & Zhang (2023) have been proposed to evaluate LLMs. However, these benchmarks have two main limitations: (1) They assume user queries always appear at the end of the input, which does not reflect real-world scenarios with queries at arbitrary positions. This bias favors KV-compression methods optimized for end-positioned queries, limiting their generalizability. (2) Most benchmarks are single-turn, overlooking the multi-turn dependencies crucial for realistic conversations LI et al. (2025).

To overcome these issues, we propose a multi-turn benchmark spanning 11 datasets with diverse query positions and interaction patterns, enabling more realistic long-context LLM evaluation.

#### A.5.1 The Design of Multi-turn LongBench

We represent each $m$-turn long-context data instance in our dataset using a structured format. Specifically, each data instance $\mathcal{I}_{i}$ consists of $m$ turns, where each turn contains a triplet of context, question, and answer. The complete dataset can be formally denoted as:

$$ $\mathcal{D}=\{\mathcal{I}_{i}=[(C_{i,1},q_{i,1},a_{i,1}),(C_{i,2},q_{i,2},a_{i,2}),\dots,(C_{i,m},q_{i,m},a_{i,m})]\}_{i=1}^{|\mathcal{D}|},$ $$

where $C_{i,j}$ is the context at the $j$-th turn of the instance $\mathcal{I}_{i}$, which can be empty, $q_{i,j}$ is the corresponding user question, and $a_{i,j}$ denotes the generated answer of the LLMs for $q_{i,j}$.
We design diverse formats for each multi-turn long-context data instance as follows:

- •
Diverse Query Positions:
For the $j$-th turn, given a context $C_{i,j}=\{C^{1}_{i,j},C^{2}_{i,j},\dots,C^{p}_{i,j}\}$ consisting of $p$ distinct paragraphs (e.g., segments),
the query $q_{i,j}$ can be positioned at various locations within $C_{i,j}$. Specifically, it can appear at the beginning of $C_{i,j}$, at the end of $C_{i,j}$, or between two segments $C^{k}_{i,j}$ and $C^{k+1}_{i,j}$.
Such a way addresses the limitation of existing methods, which only place the query at the end of the context. This placement may not accurately reflect real-world scenarios.
- •
Diverse Query Relevance:
At the $j$-th turn, the answer $a_{i,j}$ to question $q_{i,j}$ is derived from the contexts $\{C_{i,j^{\prime}}\}_{j^{\prime}=1}^{j}$.
In real user scenarios, the context sources for answering $q_{i,j}$ are diverse.
Instead of restricting $q_{i,j}$ to rely solely on $C_{i,j}$, we design the answer $a_{i,j}$ to $q_{i,j}$ to come from a subset of contexts $C_{q_{i}}\subseteq\{C_{i,j^{\prime}}\}_{j^{\prime}=1}^{j}$, with the size of the subset varying as $|C_{q_{i}}|\in\{1,2,\dots,j\}$.

#### A.5.2 Multi-turn LongBench Generation

**Table 4: Multi-turn dataset statistics.**
| Type | Dataset | $|D|$ | #Turn | Avg Token | Metric |
| --- | --- | --- | --- | --- | --- |
| QA | NQA | 500 | 3 | 30545.54 | F1 |
| Qasper | 500 | 3 | 5434.41 | F1 |  |
| MFQA-en | 500 | 3 | 7279.64 | F1 |  |
| HotpotQA | 500 | 3 | 13847.19 | F1 |  |
| 2WikiMQA | 500 | 3 | 7471.16 | F1 |  |
| Musique | 500 | 3 | 16587.56 | F1 |  |
| Summary | MultiNews | 500 | 2 | 2376.46 | Rouge-L |
| GovReport | 500 | 2 | 9324.43 | Rouge-L |  |
| QMSum | 500 | 2 | 12780.29 | Rouge-L |  |
| Few-shot<br>Learning | TREC | 199 | 2 | 2293.99 | Accuracy |
| SAMSUM | 199 | 2 | 3113.73 | Accuracy |  |

Based on the above format, we design multi-turn long-context benchmarks across various categories. Dataset details are in Table [4](https://arxiv.org/html/2507.13681v2#A1.T4). Construction methodology follows:

- •
Question Answering (QA). These datasets are derived from the single-document QA and multi-document QA tasks in LongBench Bai et al. (2024a; b), with each dataset comprising 500 instances. Each instance is structured into three turns. To construct these instances, we randomly select three question-answer pairs from a dataset in LongBench Bai et al. (2024a; b) as the foundation for the three turns. The associated contexts are then systematically modified through splitting and recombination, with additional irrelevant contexts incorporated. This meticulous design ensures that each instance satisfies the requirements for diverse query positions and diverse query relevance, as outlined in Appendix [A.5.1](https://arxiv.org/html/2507.13681v2#A1.SS5.SSS1).
- •
Summarization. These datasets are derived from the summarization tasks within LongBench Bai et al. (2024a; b). Each dataset comprises 500 instances, with each instance consisting of two turns. To enhance the diversity of the input, we randomly selected two instances from the original dataset and segmented their original contexts, subsequently recombining them into two turns. This process was carefully designed to ensure compliance with the diverse query relevance requirement outlined in Appendix [A.5.1](https://arxiv.org/html/2507.13681v2#A1.SS5.SSS1). Finally, we annotated the source paragraphs for traceability and introduced additional noisy contexts to further enrich the complexity and challenge of the dataset.
- •
Few-shot Learning. These datasets are derived from the few-shot learning tasks in LongBench Bai et al. (2024a; b). To fulfill the requirements of diverse query positions and diverse query relevance as outlined in Appendix [A.5.1](https://arxiv.org/html/2507.13681v2#A1.SS5.SSS1), we exclude instances containing fewer than four examples. For the remaining eligible instances, the examples are segmented and distributed across the first and second turns. The LLM is tasked with generating an initial response based on the examples provided in the first turn and subsequently refining its response in the second turn using the additional examples. Furthermore, the query is strategically positioned at the beginning, middle, and end of the examples to ensure diversity in query placement. To maintain the semantic integrity and structural completeness of the examples, regular expressions are employed for segmentation.

### A.6 Proof of Theorem 1

###### Proof.

The Online Prefilling Sparsification Problem (OPSP) can be proven NP-hard via a reduction from the Set Cover Problem, a well-known NP-hard problem.
The Set Cover Problem is defined as follows: given a universe $U=\{u_{1},u_{2},\dots,u_{m}\}$, a collection of subsets $\mathcal{P}=\{P_{1},P_{2},\dots,P_{n}\}$, the objective is to find a subset $\mathcal{P}^{*}\subseteq\mathcal{P}$ such that $\bigcup_{P_{i}\in\mathcal{P}^{*}}P_{i}=U$,
and the total cost $\sum_{P_{i}\in\mathcal{P}^{*}}|P_{i}|$ is minimized.
We map the elements of the Set Cover Problem to the OPSP as follows.
Each element $u\in U$ corresponds to an entry in the attention matrix $\mathbf{A}_{i}^{k}[\hat{X}_{i,j}]$ that needs to be covered. Each subset $P_{i}$ in $\mathcal{P}$ corresponds to a slash line $s$ or a vertical line $v$ in OPSP, which covers a subset of entries in the matrix.
The cost of selecting subset $P_{i}$ is mapped to the cost $l_{s}$ (for slash lines $s$) or $l_{v}$ (for vertical lines $v$) in OPSP. The Set Cover Problem’s requirement to cover all elements in $U$ is equivalent to requiring $\alpha$ in OPSP.
Therefore, if we can solve the OSOP optimally in polynomial time, we can solve the set cover problem in polynomial time.
∎

###### Proof.

### A.7 Algorithms of LoopServe System

Algorithm [1](https://arxiv.org/html/2507.13681v2#alg1), Algorithm [2](https://arxiv.org/html/2507.13681v2#alg2), and Algorithm [3](https://arxiv.org/html/2507.13681v2#alg3) of LoopServe System in section [5](https://arxiv.org/html/2507.13681v2#S5) are listed below.

Figure: Algorithm 1 LoopServe framework overview

Figure: Algorithm 2 Adaptive Prefilling Sparsification Framework

Figure: Algorithm 3 Progressive Decoding

#### A.7.1 Time Complexity Analysis of Algorithm 1

It is $O(n_{i}|\tilde{X}_{i,j}|+n_{i}logn_{i}+n_{i})$.
Firstly, it takes $O(n_{i}|\tilde{X}_{i,j}|)$ to compute the partial attention matrix $\mathbf{{A}}^{k}_{i}[\tilde{X}_{i,j}]$.
Then, it takes $O(n_{i}|\tilde{X}_{i,j}|)$ to summarize the values for each slash line and vertical line, and takes $O(n_{i}\log n_{i})$ for descending sorts.
Finally, the greedy selection loop runs in $O(n_{i})$.

### A.8 Supplementary Experimental Figure for Parameter Sensitivity

Figure: (a) Qwen-2.5-7B-Instruct.
Refer to caption: x18.png

#### A.8.1 The decoding interval n d n_{d} in Algorithm 3

The decoding interval $n_{d}$ controls how often LoopServe re-selects important input tokens during progressive KV compression. Smaller $n_{d}$ values enable frequent adaptation to changing output dependencies, improving accuracy in dynamic dialogues but increasing overhead from more KV cache updates.
We evaluate this on MultiNews and GovReport with Llama-3.1-8B-Instruct. and Qwen-2.5-7B-Instruct., covering questions at the beginning, middle, and end. As shown in Figure [8](https://arxiv.org/html/2507.13681v2#A1.F8) (c) and (d), moderate $n_{d}$ values (e.g., 16 or 32) strike the best balance, maintaining efficiency and robust generation quality. Very large $n_{d}$ reduces adaptivity, leading to lower performance on complex, multi-turn tasks.

### A.9 The Usage of LLMs for Paper Writing

We use GPT-4o and DeepSeek-R1 to polish our paper.

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Fairness & tuning of baselines. Authors “use suggested settings” for baselines while LoopServe has its own α, B, and n_d. Please clarify per-baseline tuning effort and whether baselines were re-tuned for the new multi-turn benchmark and non-end query positions.
soundness: 3
strengths: 1. Well-motivated and adaptive design. The paper presents clear empirical observations that attention is input-dependent and that query position strongly affects the success of KV heuristics; LoopServe’s two phases are designed to adapt in both prefilling and decoding to these realities.

2. Thorough evaluation and new benchmark. Results across 11 datasets and multiple tasks (QA, summarization, few-shot) demonstrate consistent effectiveness and latency gains; the benchmark’s varied query positions addresses a common weakness of existing long-context tests.
summary: This paper tackles efficient LLM inference for long, multi-turn dialogues, arguing that fixed or position-based heuristics used by many acceleration methods fail under realistic, shifting attention patterns. The authors propose LoopServe, a dual-phase system: (i) online prefilling sparsification that dynamically selects high-mass “vertical” and “slash” lines in the attention matrix to retain a target fraction of total attention weight, and (ii) progressive KV compression that repeatedly reselects important input tokens using the most recently generated outputs during decoding. They also introduce an evaluation suite of 11 multi-turn long-context datasets with queries appearing at the beginning/middle/end and cross-turn dependencies. Experiments on Llama-3.1-8B and Qwen2.5-7B show LoopServe maintains or improves quality across query positions and reduces latency, with ablations and sensitivity studies supporting the contribution.
weaknesses: 1. Baseline coverage. Table 1 compares against SnapKV, AdaKV, StreamingLLM, A-shape, Tri-shape, and MInference, but not H2O/Heavy-Hitter Oracle or Keyformer—both relevant KV-reduction methods the paper cites elsewhere. Including these would strengthen claims of SOTA performance.

---

confidence: 4
contribution: 2
initial_rating: 2
presentation: 2
questions: 1. What is the main difference compared to existing interence-time studies in terms of multi-turn scenarios for both efficiency and effectiveness?

See the question in Weaknesses.
soundness: 2
strengths: 1. The paper target on an important question in the era of LLMs, dealing with the efficiency problem in multi-turn scenarios, when the input context increases as the conversation goes on.

2. Some necessary preliminary experimental analysis is provided.
summary: This paper aims to facilitate the inference’s acceleration in multi-turn dialogue setting, and propose a dual-phase LLM framework with online attention scarification and progressive KV compression. Besides, an associated benchmark are constructed on top of the existing datasets. However, the motivation, comparison, and experimental settings are not clear.
weaknesses: 1. The main goal is to accelerate LLM’s inference latency in multi-turn scenarios, however, the experimental settings are not aligned. There is no detailed efficiency comparison with existing systems focus on multi-turn acceleration (Figure 5(a) only provide a small piece of efficiency compared with the base version). Besides, there are already existing multi-turn datasets in terms of conversational QA or RAG, what is the motivation to propose a new benchmark on top of the existing datasets? The construction details are lacked (only unclear description in the appendix) and lack of reliability evaluation.The author should be just claim what do they do but need to explain why this is necessary and effective as scientific contribution.

2. The proposed methods contain three iterations to achieve progressive decoding. Since this is done among inference time, what is the latency of such a pipeline and why this is deserved? There is no ablation studies and comparison with existing inference-time methods.

3. The paper emphasizes the focus on multi-turn, then why are the experiments conducted in single-turn datasets (e.g., 2WikiMQA, musique, hotpotqa)? I cannot understand the motivation to manipulate these datasets into multi-turn and then evaluate them, and only 3 turns interaction cannot ensure this can be thought as a multi-turn dialogue as the authors’ motivation in introduction. 

4. The readability is bad. Several complex algorithms are mentioned in the main content but describe in the appendix. The main content SHOULD BE SELF-CONTAINED. The main experiments table 1 is not clear. No explanation about what is begin, middle, and end in the column of “P”, and no basic information of baseline methods in the main content.

5. No implementation information is provided, and no information about how to use the dataset for evaluation, e.g., the split.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 2
questions: Q1: Have you analyzed query position distributions in actual multi-turn conversations (e.g., production chatbot logs, customer service transcripts) to establish how frequently queries appear at non-terminal positions in practice?

Q2: Have you tested whether increasing the observation window size k for baseline methods (e.g., k ∈ {512, 1024, 2048, 4096}) would close the performance gap, or is the improvement fundamentally about using output tokens versus input tokens?

Q3: What is the computational and memory overhead of LoopServe compared to baselines, and how do these costs scale with context length and generation length?

Q4: Have you evaluated LoopServe on any naturally-occurring multi-turn conversations beyond the synthetic benchmark to demonstrate that the approach transfers to realistic dialogue scenarios?
soundness: 2
strengths: ## Strength 1: Identification of Benchmark Bias and Adequate Motivational Analysis

The paper makes a legitimate and important observation about systematic bias in existing long-context benchmarks. By demonstrating that methods like SnapKV and AdaKV achieve strong performance when queries appear at the end but degrade significantly (often by 10+ points) when queries are repositioned to the beginning or middle, the authors expose a meaningful evaluation gap. This observation -- that the community has been evaluating on a narrow distribution of query placements that may not reflect diverse real-world scenarios --- is valuable regardless of whether their synthetic benchmark fully captures realistic multi-turn dynamics. This contribution should inform future benchmark design and evaluation practices.

The motivational experiments in Section 3, while not exhaustive, provide adequate empirical justification for the approach. The authors demonstrate that (1) attention weight concentrates in a small fraction of matrix components (10% of lines capturing 90% of weight), and (2) the specific important components vary substantially across inputs (overlap rates <50%), undermining static sparsification strategies. While a more thorough investigation would analyze these patterns across layers, models, and task types to characterize when and why variability occurs, the provided analysis is sufficient to motivate the need for adaptive selection methods. The visualizations effectively illustrate key concepts and the experimental design for these motivational studies is sound.

## Strength 2: Comprehensive and Well-Executed Experimental Evaluation

Within the scope of their evaluation, the authors conduct thorough and methodical experiments. They compare against six diverse baseline methods spanning different categories (observation-based, pattern-based, streaming), test on two model families (Llama-3.1-8B and Qwen2.5-7B), and systematically vary query positions across 11 datasets. The ablation studies convincingly demonstrate that both components of their system contribute to performance, and the parameter sensitivity analysis provides practical guidance for hyperparameter selection. The paper is clearly written with effective visualizations, and the results consistently show that LoopServe maintains stable performance across query positions while baselines exhibit position-dependent degradation. While the benchmark's realism is questionable, the experimental methodology itself is sound and the evaluation is more comprehensive than many papers in demonstrating consistent behavior across diverse settings.
summary: This paper addresses efficient LLM inference in multi-turn dialogues, where quadratic attention complexity creates computational bottlenecks as conversations lengthen. The authors present empirical evidence that attention patterns are highly sparse yet dynamic and input-dependent, and that existing acceleration methods (which use fixed patterns or position-based heuristics) fail when queries do not appear at the end of the input. They propose LoopServe, a dual-phase acceleration framework consisting of: (1) online attention sparsification during prefilling that dynamically selects important components of the attention matrix for each input, and (2) progressive KV compression during decoding that periodically re-selects cached tokens based on attention patterns from recently generated outputs rather than from final input tokens. The authors construct 11 multi-turn datasets from existing benchmarks with queries repositioned at beginning, middle, and end locations, and evaluate LoopServe against six baseline methods on Llama-3.1-8B and Qwen2.5-7B models. Results show LoopServe maintains performance across all query positions while baselines degrade significantly when queries are not at the end, with ablations confirming both phases contribute to the improvement.
weaknesses: ## Weakness 1: Lack of Real-World Validation and Circular Benchmark Design

The work lacks validation on authentic multi-turn dialogue traces. Instead of quantifying where user queries actually occur in real conversations, the authors construct multi-turn data by repositioning queries and recombining LongBench items. This supports controlled tests but risks circularity: the benchmark emphasizes scenarios where last-window methods underperform, and the proposed method is tailored for those scenarios. Evidence from real logs (or even a descriptive analysis of query position distributions) would strengthen practical significance.

## Weakness 2: Limited Design-Space Exploration and Practical Trade-Off Analysis

Although LoopServe includes a non-trivial online prefilling sparsification phase (with an NP-hardness proof and a greedy line-selection algorithm) and a progressive output-based KV compression phase, the paper does not thoroughly explore alternative design choices or stronger baselines. For example, it does not test larger or multiple input windows, alternative attention aggregation functions, or output-aware extensions of methods like SnapKV or AdaKV. The evaluation focuses on 7–8B models with a fixed B = 1024 budget and provides limited breakdown of computational or memory overhead, leaving scalability and deployment implications unclear. While the paper includes ablations and sensitivity analyses for parameters (α, B, and n_d), a broader exploration of trade-offs and clearer guidance on when the method’s benefits outweigh its added complexity would improve confidence in its practical impact.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: see the weakness part
soundness: 3
strengths: 1.A two-stage adaptive acceleration framework is proposed to address the dynamic characteristics of multi-turn conversations and solve the generalization problem of existing static methods (such as Minference and SnapKV).
2.In terms of empirical evidence, it is also relatively comprehensive. Through detailed exploratory experiments (such as attention sparsity analysis and query position impact analysis) and main experiments (covering 11 datasets and multiple baselines), the superiority of LoopServe has been demonstrated across various tasks, including Question Answering, Summarization, and Few-Shot Learning.
3.It contributes to the benchmark for multi-turn long-context conversations, makes up for the shortcomings of existing benchmarks, and is more in line with real-world dialogue scenarios.
4.It enables engineering practicality, providing algorithm details, complexity analysis, and parameter sensitivity experiments to facilitate reproduction and deployment.
summary: Multi-turn dialogues are essential in many real-world applications of large language models, such as chatbots and virtual assistants. As the conversation history grows longer, existing large language models face increasing computational and memory challenges that hinder their ability to provide efficient and responsive interactions. Innovation points are：First, it performs online sparsification during the prefilling phase by dynamically selecting the most important parts of the attention matrix for each new input. Second, it uses progressive key-value compression during decoding by adaptively maintaining a relevant and efficient cache based on the most recently generated output tokens.
weaknesses: 1.The format needs adjustments. For example, the legend of Subfigure 1d in Figure 1 obscures part of the image content, and Figure 1 is not fully explained in the main text. There is a spelling error in Section 3.1: "as reveled as follows" should be corrected to "as revealed as follows".
2.The formulation is not rigorous enough. The complexity of generating m tokens on the first page is given as O(m((n+m)²d + P)), but the prefilling and decoding stages are not clearly separated.This may be misleading and cause readers to misunderstand the complexity proportion of the two stages.
Some implementation details lack transparency. For example, in the online sparsification section (Page 6), there is no explanation of how “input subset sampling (RandomSelect)” is conducted or what sampling ratio is used.For the "reselection interval nd=16" in progressive KV compression, neither the basis for this setting nor the existence of ablation verification is provided. The lack of such details may affect the reproducibility of the method.
The NP-hardness proof in Appendix A.6 is relatively simplistic, as it fails to elaborate on the equivalence between line covering and set covering problems.
3.Details regarding the construction of the benchmark dataset need to be supplemented. The specific sources of the 11 datasets are not clearly specified (e.g., whether MFQA-en is modified based on an existing dataset, and what the modification ratio is).
4.Experimental Limitations: The method has not been tested on ultra-long contexts or low-resource devices, and the feasibility of its practical deployment remains to be verified; the latest methods (such as the improved version of StreamingLLM released at the end of 2024) are not included in the comparison baselines.


Decision: Reject