HShare: Fast LLM Decoding by Hierarchical Key-Value Sharing
Authors: Huaijin Wu
Lianqiang Li
Hantao Huang
Tu Yi
Jihang Zhang
Minghui Yu
Junchi Yan
Venue: ICLR 2025 Poster (2025)
Keywords: Large Language Model
Decode
Key-Value Sharing
Critical Token
Hierarchical
Primary area: foundation or frontier models, including LLMs
TL;DR: We propose a hierarchical critical KV cache indices sharing framework across layer, head, and query levels.

Abstract: The frequent retrieval of Key-Value (KV) cache data has emerged as a significant factor contributing to the inefficiency of the inference process in large language models. Previous research has demonstrated that a small subset of critical KV cache tokens largely influences attention outcomes, leading to methods that either employ fixed sparsity patterns or dynamically select critical tokens based on the query. While dynamic sparse patterns have proven to be more effective, they introduce significant computational overhead, as critical tokens must be reselected for each self-attention computation. In this paper, we reveal substantial similarities in KV cache token criticality across neighboring queries, layers, and heads. Motivated by this insight, we propose HShare, a hierarchical KV sharing framework. HShare facilitates the sharing of critical KV cache token indices across layers, heads, and queries, which significantly reduces the computational overhead associated with query-aware dynamic token sparsity. In addition, we introduce a greedy algorithm that dynamically determines the optimal layer-level and head-level sharing configuration for the decoding phase. We evaluate the effectiveness and efficiency of HShare across various tasks using three models: LLaMA2-7b, LLaMA3-70b, and Mistral-7b. Experimental results demonstrate that HShare achieves competitive accuracy with different sharing ratios, while delivering up to an $8.6\times$ speedup in self-attention operations and a $2.7\times$ improvement in end-to-end throughput compared with FlashAttention2 and GPT-fast respectively. The source code is publicly available at ~\url{https://github.com/wuhuaijin/HShare}.

Published as a conference paper at ICLR 2025
HSHARE: FAST LLM DECODING BY HIERARCHICAL KEY-VALU SHARING
Huaijin Wu 121, Liangiang Li Hantao Huang", Yi Tu' ,Jihang Zhang?, Minghui Yu², Junchi Yan
Shanghai Jiao Tong University, Shanghai, China 2 ByteDance Inc.
[wh]1201, yanjunchil {& edu. en {lilianqia lilianqiang, huanghantao, zhangj yuminghui exp expeeeeyeddncceeccom
ABSTRACT
The frequent retrieval of Key-Value (KV) cache data has emerged as a significant factor contributing to the inefficiency of the inference process in large language models. Previous research has demonstrated that small subset of critical KV cache tokens largely influences attention outcomes, leading to methods that either employ fixed sparsity patterns or dynamically select critical tokens based on the query. While dynamic sparse patterns have proven to be more effective, they introduce significant computational overhead, as critical tokens must be reselected for each self-attention computation. In this paper, reveal substantial similarities in KV cache token criticality across neighboring queries, layers, and heads. Motivated by this insight, propose HShare, hierarchical KV sharing framework. HShare facilitates the sharing of critical KV cache token indices across layers, heads, and queries, which significantly reduces the computational overhead associated with query-aware dynamic token sparsity. In addition. we introduce greedy algorithm that dynamically determines the optimal layer-level and head-level sharing con- figuration for the decoding phase. We evaluate the effectiveness and efficiency of HShare across various tasks using three models: LLaMMA-7b, LLaMA3- and Mistral-7b. Experimental results demonstrate that HShare achieves competitive accuracy with different sharing ratios, while delivering up to an 8.6x speedup in self-attention operations and 2.7x improvement in end-to-end throughput compared with FlashAttention2 and GPT-fast respectively. The source code is publicly available at https: pettps://githi //ggtttbgttttt/tt// com/ /wwhuaiiiiii HShharee
INTRODUCTION
The development Large Language Models (LLMs), like the GPT and LLaMA series (OpenAI, 2024: Touvron et al., 2023), has marked major breakthrough in artificial intelligence, dramatically improving performance in natural language processing tasks such as translation (Zhu et al., 2023; Pal al., 2024) and summarization (Zhang al., 2023; Liu al., 2023). However, in long-context scenarios, such as multi-turn dialogues (Yi et al., 2024; Teng et al., 2024), document-baa based question al., 2023; Rasool et al., 2024), and code completion (Yang al., 2023; Eghbali & Pradel, 2024), LLMs face significant speed challenges with token-by-token decoding. A key factor contributing this slowdown is the handling of the Key- Vel-V (KV) memory cache since as the context length expands, the size of this KV cache grows correspondingly. resulting in longer access times and increased memory overhead.
answering (Abdel-Nate
Existing works have introduced several approaches to address this issue. Since it has been demon- strated that a small portion of the tokens can dominate the accuracy of token generation, many works choose to only load these critical tokens into the KV cache to reduce the inference latency while maintaining accuracy. Among them, StreamingLLM (Xiao al., 2023) treats the initial tokens (also referred to sink tokens) and the recent tokens critical tokens and performs sparsity in a fixed pattern.
*Correspondence author. i equal contribution. Work was partly supported by NSFC (62222607). Shanghai Municipal Science and Technology Major Project (2021 20011222200002 Huaijin Wi's work was completed during her internship ByteDance.

---

Published as a conference paper at ICLR 2025
H2O (Zhang et al., 2024b) introduces greedy policy that dynamically retains balance of recent and heavy tokens. These two methods alleviate both storage and retrieval pressures through KV cache eviction. However, they tend to lose significant amount of historical information, leading to substantial decline in performance as their sparsity increases.
On the other hand, Quest (Tang et al., 2024) points out the criticality of tokens can change with different query tokens. To this end, Quest introduces a query-aware token sparsity algorithm, which uses the maximum and minimum values of each hidden dimension at page granularity measure the query-aware criticality. Similarly, DoubleSparse (DS) (Yang et al., 2024b) proposes to select critical tokens dynamically by calculating and sorting approximate attention weights with important channels only. Although these two methods only load critical tokens, they retain all the KV cache, allowing them to enhance speed while effectively maintaining accuracy. However, for Quest and DS, the requirement evaluation for each dynamic selection introduces computational overhead, which results in significant drawback of these approaches. Take DS as an example, with a sequence length of 2k and batch size of 8, the process of selecting important tokens consumes nearly 50% of the total runtime in their token sparse attention. The comparison of different methods is shown in Tab. 1.
In this work, we further observe that the criticality of KV cache tokens demonstrates significant similarity across different layers, heads within the same layer, and between adjacent queries. Building on this observation and to mitigate the computational overhead associated with the dynamic selection of critical tokens mentioned above, we propose HShare, a hierarchical key-value sharing framework that operates at three levels: layers, heads, and queries. Specifically, design a sharing configuration for the layer and head levels based on the similarity of critical KV eache token indices. To ensure the sharing accuracy, we compute the corresponding configuration online for each batch of samples after the prefilling phase, the configuration is then applied to the entire decoding phase. This online calculation introduces only a minor increase in the prefill phase's time without incurring any additional overhead during the decode phase. At the query level, we simply share critical token indices between adjacent queries, as their proximity results in higher similarity. By retaining the full KV cache, selectively loading only the critical portions, and implementing hicrarchical multi-level sharing. HShare maintains accuracy while reducing the time spent selecting critical KV tokens, significantly improving decoding latency compared to existing methods.
introduce an algorithm to
We use 1aaMA227b-chaa (Touvron et al., 2023), LLaMA3-70b (Dubey et al., 2024), and Mistral- 7b (Jiang et al., 2023a) to evaluate the accuracy of HShare across three benchmarks: GSM8K (Cobbe et al., 2021), COQA (Reddy et al., 2019), and LongBench (Bai et al., 2023). Experimental results demonstrate that, under the same token sparsity, HShare can maintain accuracy with different sharing ratios, offering competitive performance to state-of-the-art (SOTA) methods. Furthermore, evaluate the efficiency of HShare and the results show that HShare can achieve up 8.6x self-attention latency reduction compared with FlashAttention-2 (Dao, 2023) and 2.7x throughput improvement in end-to-end inference compared with GPT-fast (PyTorch, 2023). In summary, the contributions of this paper are:
We systematically analyze the criticality of KV cache tokens across all the levels: different layers, different heads within the same layer, and adjacent queries. Our empirical findings on LLaMA2-7b-chat show that all three levels exhibit substantial similarity.
We propose a hierarchical critical KV token indices sharing framework with a greedy algorithm dynamically determine the sharing configuration. To the best of our knowledge, this is the first work to introduce the concept of sharing critical KV cache token indices.
We evaluate HShare in terms of accuracy and efficiency, with results showing that it maintains model performance with different sharing ratios while achieving up to 8.6 reduction in self-attention latency and 2.7x x improvement in inference throughput.
2 RELATED WORK
2.1 LONG-CONTENT MODEL
Recently, significant efforts have been made to extend the context windows of LLM, both in academia (e.g., LongChat (Li et al., 2023a), Yann-LLMMA-2 (Peng et al., 2023)) and industry (e.g.. GPT-4 Turbo, which supports up to 128K tokens (OpenAI, 2024)). These extended-contex LLMs excel in tasks such multi-tum conversation comprehension and meeting summarization by providing
2

---

Published as a conference paper at ICLR 2025
Table Comparison of the selection of critical tokens in different token sparsity methods.
Methods
Selection mode
Efficiency
Memory cost
Accuracy
Streaming (Zhang et al., 2024b) H2O (Xiao et al., 2023)
Fixed pattern
High
Low
Low
Lonal
High
Low
Low
Quest (Tang ct al., 2024)
Dynamic
Low
High
Median
DS (Yang ct al., 2024b)
Dynamic
Median
High
High
HShare (Ours)
Dynamic+Sharing
High
High
High
enhanced in-context learning and improved performance on complex reasoning tasks. However, this advancement comes with notable trade-offs, including increased computational demands, higher memory usage, and greater bandwidth requirements, leading to elevated costs and longer per-token latencies (Pan et al., 2024; Chen et al., 2024b). For example, Pan et al. (2024) utilizes host SSD memory to alleviate the long sequence KV cache memory requirements at the expense of long latency whereas Chen et al. (2024b) offloads the attention computation on low-cost GPU devices to support economical long-sequence LLM inference. These solutions try to tackle the Long-context model from the computing system level, however, it could be better solved from algorithm advancements such LLM quantization (Liu al., 2024) and sparsification (Tang al., 2024).
2.2 EFFICIENT INFERENCE OF LLMS
Several techniques, such as speculative decoding (Leviathan et al., 2023; Miao al., 2024), parameter sharing (Chen et al., 2024a), and quantization (Lin et al., 2024b;a), have been proposed to improve inference efficiency. Here we focus on accelerating the attention mechanism, which poses significant time costs due to its quadratic complexity with respect to sequence length, particularly in long-context scenarios. Decoder-only transformers, trained with masked self-attention where each token depends only on preceding tokens, enable the use of key-valus activation caching (KV cache) to bypass redundant computations (Pope et al., 2023). However, the KV cache can grow significantly in size. For instance, during inference with the OPT-175B model (Zhang et al., 2022) using batch size of 512, a prompt length of 512, and an output length of 32, the KV cache demands 1. 1,2TB of memory for storage and communication just generate single token (Liu et al., 2024), which poses grand challenge for system memory and bandwidth. To tackle the challenge, one path is to reduce the KV cache storage by quantization 2-bit even 1-bit. Existing works (Liu et al., 2024) report to achieve 2-bit quantization without accuracy loss and (Zhang et al.. 2024a) quantizes the KV cache to 1 1-bit with minor accuracy loss. Another orthogonal path is focus only on the critical tokens in the KV caches, also known as token sparsity, which we will review in Sec 2.3.
2.3 SPARSE ATTENTION
Early works such as sparse transformer (Child et al., 2019), reformer (Kitaev et al., 2020), and longformer (Beltagy et al., 2020) made efforts to reduce attention complexity through training. Recently, Jiang al. (2023b) trained language model to compress prompts into smaller sets of gist to reduce memory pressure during caching. However, such a compression strategy requires retraining the large language model and also increases the overhead during inference.
On the other hand, many works (Ribar et al., 2023; Zhang et al., 2024b; Tang et al., 2024) propose post-training sparse attention, primarily leveraging the observation of sparse attention scores, which allows focusing on important tokens without compromising performance. StreamingLLM (Xiao al., 2023) identifies the initial and most recent tokens as critical, while Zhang al. (2024b;a) propose to adopt the accumulated attention score as the indicator to identify the critical tokens in the KV cache. MInference (Jiang et al., 2024) introduces a dynamic sparse pattern identification algorithm for prefilling acceleration. Additionally, Quest (Tang et al., 2024) uses min and max values to assess the importance of each KV cache page, computing only the most relevant pages, while DS (Yang et al., 2024b) focuses selecting critical KV tokens by utilizing only important channels. However, these methods incur additional computational overhead for determining importance. In contrast, our work aims to minimize the need for such additional computations by sharing critical KV cache token indices across multiple levels.
PROBLEM FORMULATION
We begin by defining the decoding self-attention process with selected critical key-value cache tokens, which we refer to as token sparsity attention. In the decoding stage, let the query matrix be denoted as Q Rixd the key matrix K R and the value matrix as V Roxd where n denotes the
3

---

Published as a conference paper at ICLR 2025
Layer B Head 12
Layer Head 22
(e)
Layer 9 Hiadd 9
(4)
Layer 9 Head
9.05
Sequence
Sequence
Query Sequence
Quary Sequence
0.04
10
5
15-
5
0.02
10
15
30
10
20
25
30
20
20
25
10
15
20
25
30
0.50
Key Sequance
Key Sequence
Key Sequence
Key Sequence
Prefill Head Similarity
Decode Head Similarity
Prefill Layer Similerity
Decode Layer Simi arity
12 16
Head Index
Layer inoex
Layer indox
04
& 3
Head
8
0 8
04
2
10 Head Index
20
20 Head Index
20 Layer Index
20 Layor Index
10
15
25
Figure 1: (a)- Illustrations of self-attention matrices from specific head in particular layer of the L.luMA2-7b-chaa model, corresponding to similar self-attention patterns observed across different layers and heads. (e)-(h) Similarity matrices of critical token indices across different heads and layers during the prefill and decode stages. The element in the i-th row and j-th column represents the similarity (Eq. 3) between the i-th head (layer) and the j-th head (layer). The red stars represent the top-k largest values the matrix.
sequence length. Here K,, represents the i-th row of key matrix, corresponding to the i-th token in the current sequence. With these notations, define the token sparsity attention.
Definition 3.1 (Token sparse attention, informal). Token sparsity attention only calculates the attention weights between the query matrix and the selected critical key tokens. Let Ne represent the number of KV critical tokens to be selected, and suppose we have the indices:
{ D2, ..,,...,,N,, I; [0,m] and .,2 We then select the rows (Kg E 5) corresponding to these indices from the key matrix to form new key matrix KeT E RNexd also apply the same operation to the value matrix to form a new
CT
(1)
value matrix VeT E Ndd, The token sparsity ratio is defined as Ne and the token sparse attention is computed through h the formula shown below:
(Q.Ken ddh
= softmax
VeT
Normally, each attention block independently evaluates and selects its critical KV cache tokens, resulting in corresponding set of indices. denoted as CT. We use the number of overlapping elements between two different to evaluate the similarity between them. Then the similarity between two critical KV cache token indices CT''A and CTB can be formally written as:
ICTA CTBBl
sim CTB)
max Maax(CCTll, (T)l)
here represents the cardinality of set and normally (CTA [CTB] = No. Next, define Key-Value sharing.
Definition 3.2 Key-Value sharing). Assuming that the critical KV cache token indices for attention block are denoted as CT if another attention block B directly reuses the indices from block A, represented CTB t CT'A, we refer this as key-value sharing between blocks and A. In this case, C'AA is utilized by attention block B to construct KoT and VeT-
METHOD
In this section, we first present the motivation of HShare, and then we introduce HShare in detail.
4.1 MOTIVATION
Previous works have pointed out all KV tokens hold equal significance, with a limited subset, known as critical tokens, contributing most to the attention output, and these critical tokens are found to be query-aware. In this paper, further present three observations, with insights shown in Fig. 1.
4

---

Published as a conference paper at ICLR 2025
Arog
layer
query!
quary/
queryhig
layarh
quegits
Figure 2: Share the same critical token indices between layers and heads.
Figure 3: Share the same critical token
indices between adjacent queries.
Similar critical tokens between adjacent queries: From Fig. (a))-dd), we observe that within individual attention heads, the distribution of critical KV cache tokens (those associated with larger values in the attention matrix) gradually shifts with changes in the queries. However, the critical tokens across adjacent queries remain largely consistent. This observation aligns with intuition, as minor variations in query length do not significantly alter the overall sequence length, suggesting that the attention distribution remains stable. The similarity between adjacent queries presents an opportunity to reduce computational overhead by reusing the same critical KV cache tokens for every k consecutive query.
The distribution of critical tokens results in different sparse patterns for attention heads. However, as illustrated in Fig. ((a)-(d), we can also see that some sparse patterns are consistently observed across various attention heads. For example, the sparse pattern of head 12 in layer 8 is very similar to that of head 22 in the same layer. Additionally, head and head 16 in layer also share a similar sparse pattern, indicating that the similarity between heads exists not only within the same layer but also across different layers. This uniformity suggests that a sparse pattern derived from one head can be effectively applied to others, enabling a shared strategy for selecting critical KV cache tokens. This approach further improve the speed and efficiency of the attention mechanism.
Similar aparse-patterus across different heads and layers:
Consistency relationships between prefill and decoding phases: Fig. I(e) and Fig. 1(f) present the head similarity matrices of layer 8 in terms of prefill stage and decoding stage, respectively. Fig. 1(g) and Fig. 1(h) present the layer similarity matrices of the whole network in terms of the prefill stage and decoding stage, respectively. We observe that the similarity matrix between prefill and decoding phases exhibits a remarkable consistency for both head-level and layer-level. This continuity underscores the potential that applying the hierarchical sharing strategy computed from prefill phase to the decoding phase.
Motivated by the above observations, we propose HShare, hierarchical sharing framework that shares the same critical KV cache tokens across queries, heads, and layers. HShare not only takes advantage of dynamic sparsity but also significantly reduces the computational overhead associated with critical tokens through an effective sharing mechanism.
4.2 HIERARCHICAL VEYUVALUE SHARING FRAMEWORK
Inspired by recent works (Zhang et al., 2024b; Xiao et al., 2023; Yang et al., 2024b), in this paper, select critical tokens from three perspectives: initial tokens (also referred as sink tokens), the most recent window, and significant tokens in the middle. The dark blue positions in Fig.2 and Fig.3 represent the indices of these critical tokens. Given that the decoding stage is autoregressive, each decoding step requires passing through all T. layers of the attention blocks. In the case of multi-head attention and group query attention, each attention block involves multiple parallel attention head H computations. Consequently, to generate tokens, total of L H attention computations necessary, resulting L x x n re-selections of critical tokens.
To reduce the overall time spent evaluating and selecting critical tokens and further accelerate the decoding, we introduce a hierarchical key-value sharing framework. This framework is designed to facilitate vey-value sharing from three perspectives: across layers. heads, and queries. Specifically, denote the attention computation of head in layer I of the query q as Ar then the key-value sharing between layers l and can be expressed as: CT CTAaga &- CTA, CTA
5

---

Published as a conference paper at ICLR 2025
Similarly, the key-value sharing between heads h1, h2 and queries ạı 92 can be expressed as: CT f Ca CTAIM + -CAAL,
It should be noted that since there is temporal dependency between the attention computations of layers and queries, it is necessary to satisfy 4 < l2 and q1 < 42 here.
Similar to the token sparsity ratio, we define the sharing ratio value less than equal 1, where a smaller value indicates a higher degree of sharing and greater computational savings. Let the total number of layers and heads be denoted ny and n,, respectively. Suppose ky layers and kú, heads share critical KV token indices with other layers or heads. The sharing ratios for layers and heads are then defined as ratio = ky and ratio, = Rss respectively. For query-level sharing, let the total number of decoding tokens (queries) be 72g and suppose ky queries bypass the selection of critical token indices by sharing key-value indices with other queries. The query-level sharing ratio is defined as ratio, independent, the total sharing ratio is given by:
Rh,
Av. Since the sharing across layers, heads, and queries is mutually
kt
kn nn
kgg ng
sharing ratio (1
(1 ny
x (1
4.3 ALGORITHM FOR SHARING CONFIGURATION DESIGN
For layer-level and head-level sharing, as demonstrated in Sec. 4,1, the similarity of the critical KV cache token indices shows consistency across the different queries. Therefore, we can design a sharing config- uration by caleulating the similarity of the critical token indices between layers and heads after prefilling, and then apply this configuration to the entire decoding phase.
Algorithm 1 Layer(Head) Sharing Algorithm
I: Input: layer(head) number n((n)), critical token indices matrix List L = {M1, M2, (.2,...((((())) share number ky (kk.
2: Initialize similarity matrix S +- zeros(n, n)
3: for i
(n,,) do
4: set, f set seltt,,llatte()
5: for j = 1 to 1 do
the layer-level as exam- ple for detailed explanation. After each prefill step, first obtain the critical KV cache token indices matrix list for all lay- ers L M1. My...., Mn, where ny rep- resents the number of layers. Next, we compute the pairwise similarities between the critical KV cache token indices of all layers, producing a similarity matrix St. Based on the desired sharing ratio, then perform key-value sharing between the most similar layers. Specifically, if the layer-level sharing ratio is 8, meaning that kj = - BB) x ny layers should share crit- ical KV token indices, we iteratively select the pair (i,j) with the highest similarity (where j <, i), allowing the i-th layer to reuse the indices of the j-th layer. Since layer i now reuses the critical token indices of another layer and does not compute its own, we remove the i-th row and i-th column from the similarity matrix.
set; set sea((M)..latten() 7: overlap - set, n set,
6:
Here,
8: S.j < overlap M,.numel0)
9: end for
10: end for
11: for == 1 to (nx) ) do
12: Initialize sharing config Cli] <
13: end for
14: for i (k,,) do
15: row now_index, column index argmax(S)
16: S[row_index, :}{-
17: S[;, wo.oowwine row_index] +- 0
18:
C'row < column_indes
19:
end for
20: Output: Sharing config C of layer(head).
Similarly, for all heads within each layer, we apply the same method to determine the sharing configuration. Note that each layer has its own head-level sharing configuration. Algo. 1 outlines the process calculating the similarity matrix and designing the layer (or head) sharing configuration. Formally, the output sharing configuration C represents:
J. if the i-th layer (or the i-th head) shares with the j-th layer (or the j-th head),
G ===1 i, if the i-th layer needs to compute critical tokens separately.
Since the sharing configuration can differ across samples, we compute it dynamically for each batch of samples.

---

Published as a conference paper at ICLR 2025
Table 2: Evaluation of different methods on GSM8K and COQA and the best result (exclude origin) in each column is highlighted in bold. Complexity refers to the theoretical time complexity for each method to select critical KV cache tokens, where (1) denotes constant time complexity, and 7' represents the theoretical computation time for dense attention mechanism.
Model
Architecture
Method
CSMBK((lexiblektiicu)
COQA 1 Complexity
Original
0.2297/0,2297
0,5997
StreamingLLMM
0.0591/0.0023
0.3577
H20
0.0986/0.01 0144/
0,4952
O(1)
Quest
0,0478/0,0462
0,5713
0.125'7
LLaMA2-7b-chat
MHA
DS
0.1713/0.1 1706
0.5978
0.06257
Ours (7/8-3/4-1/2)
0.1835/0.1721
0,5982
0.021T
Ours (3/4-3/4-1/2)
0.1803/0, 1703
0.5898
0.018T
Ours (1/2-1/2-1/2)
0.1524/0. 145
0,5672
0.008T
Original
0.8067/0. 8052
0.7085
Streamingl
0.3912/00535
0,5460
H20
1.5815/0.5588
0.6310
O(1)
Quest
0.4602/0. 4503
0.6955
0.1257
LLaMA3-70h
GQA
DS
0.741550.733 7,392
0.7045
0.06257'
Ours (778-3/4-1/2)
0.7536/0.746
0.7105
0.0217
Ours (3/4-3/4-1/2)
0.75 7437
0,7010
0.018T
Ours (1/2-1/2-1/2)
0.7415/0.7344
0.6960
0.00ST
Original
0.3821/0.30
0.6758
StreammngLLLM
0,1281/0,008 10.00085555
0,4818
H20
0,1857/0, 1766
0,5592
O(1)
Mistral-7b
GQA
Quest
1L344/00.1199
0.6378
0.1257
DS
0,3262/0.3221
0.6693
0,0625T
Ours (7/8-3/4-1/2)
0.3287/0_1233
0.6667
0.0217'
Ours (3/4-3/4-1/2)
0.3199/0.3
0.6560
0.018T
Ours (1/2-1/2-1/2)
0.2818/0.2684
0.6387
0.008T
Query-level. As discussed in Sec. 4.1, we observe that attention weights between adjacent query tokens tend to exhibit significantly higher similarity compared those between distant query tokens. Specifically, for query i and query i - 1, the importance rankings of the tokens from token 0 to token i are largely similar. Based on this observation, we group every a adjacent query to share a single critical token set, resulting in a sharing ratio of between queries. Fig.3 illustrates the sharing mechanism between two adjacent queries.
5
EXPERIMENT
5.1
ACCURACY EVALUATION
5.1.1 SETUP
We evaluate HShare on GSM8K (Cobbe et al., 2021), COQA (Reddy et al., 2019), and sixteen English datasets in LongBench (Bai et al., 2023). For our evaluation, we select three widely-used models: LLaMA2-7b-chat (Touvron et al., 2023), LLaMA3-70b (Gliwa et al., 2019), and Mistral-7b (Jiang et al., 2023a), representing a range of architectures from multi-head attention (MHA) to group query attention (GQA). As baselines, algorithms StreamingLLM (Xiao et al., 2023), H2O (Zhang et al., 2024b) and two query-aware token sparsity algorithms Quest (Tang al., 2024), DS (Yang al., 2024b). To ensure a fair comparison, in line with Xiao et al. (2023); Yang et al. (2024b), we keep dense attention to the prefill stage and apply sparee attention to all layers the decode stage. Here, we also include the vanilla attention as Original, which serves as the baseline representing lossless results, without applying any sparsity in either the prefill stage or the decoding stage.
include four state-of-the-arr methods: two KV cache eviction
5.1.2 RESULTS ON GSM8K, COQA
Datasets and Metrics. We use the L.MEEaal framework to conduct zero-shot inference on GSM8K and COQA. GSM8K consists of around 8,000 elementary school math problems and COQA is designed for evaluating dialogue-based question-answering systems. The average context length for these two datasets is approximately 500 and 2k respectively. Here we report the GSMSK with flexible exact-match accuracy and strict exact-match accuracy, while COQA with em score.
Inference Details. For fair comparison, all methods select N. 128 critical KV cache tokens and do token sparse attention, with a token sparsity ratio of approximately 1/4 and 1/16 for the two datasets respectively (since GSM8K consists of math problems, we select a higher sparsity
7

---

Published as a conference paper at ICLR 2025
Table Evaluation of different methods on sixteen English datasets in Longbench and the best result in each row (excluding the original) is highlighted in bold.
Method
Original
StreamingI.IMM
H20
Quest
DS
Ours (7/8-3/4-1/2)
Ours (3/4-3/4-1/2)
Ours (1/2-1/2-1/2)
Datasel
MultiNews
26.22
23.34
24.88
26.49
26.30
26.22
26,05
25,22
Musique
$.79
4.62
8.72
7.52
HotporQA
27.72
23.89
27.58
21.94
27.44 44
27.29
27.32
29.13
Qasper
13.80
16.96
2WikiMQA
31.18
29. 79.79
31.38
29.42
32.01
31.74
31,46
31.43
Repohench.P
52.14
48.06
51.11
50.24
48.44
51.33
50.79
51.63
TriviaQA
83.09
80.82
81.90
82.42
83.23
83.91
83.91
82.16
Trec
64.5
54.5
62.5
64.0
61.0
60.5
60.5
58.5
Qmsum
20.91
19.09
20.74
21.36
20.75
20.77
20.59
20.74
NarativeQA
18.83
13.62
17.01
18.21
17.54
17.15
17.31
16.66
GovReport
26.55
20.64
23.44
25.46
27.04
26.63
25.85
23.93
LCC
58.26
55.18
56.55
56.74
54.87
55.18
56.23
56.11
Passage Count
2.77
2.02
1.87
2.33
2.33
2.98
3.15
2.30
Samsum
41.01
37.87
40.18
40.91
41.30
40.66
39.77
40.02
Passage Retrieval-BB EN
6.5
4.0
5.0
6.5
6.0
6.5
6.0
6.0
MultieelQAAEE
36.15
23.69
33.64
31.99
35.83
36,65
34.08
32.37
Average
32.90
28.51
31.38
31.35
32.11
32.13
31.97
31.49
level, whereas COQA involves story-based question-answering so we choose lower sparsity level.) For HShare, we select critical tokens from three aspects, with 8 sink tokens, y 32 recent tokens, and 88 critical tokens in the middle. Following the approach in Yang et al. (2024b), load the heavy channel of the KV cache in 4-bit precision compute the approximate attention weights, then sort them to select the top-2 tokens in the middle. We evaluate the effectiveness of our proposed HShare using LLaMA2 ---ahaa LLaMA3-70b, and Mistral-7b, selecting three sharing ratios 7/8-3/4-1/2, 3/4-3/4-1/2 and 1/2-1/2-1/2 of HShare for comparison against other methods. Here a-b-c means HShare with layer-sharing ratio a, head-sharing ratio b, and query-sharing ratio c.
The results on GSM8K and COQA, shown in Tab. 2, indicate that HShare outperforms other KV cache eviction methods (StreamingLLMM and H2O). In addition, when compared to dynamic critical token selection approaches (Quest and DS), HShare can also achieve competitive performance with low complexity in selecting critical KV cache tokens. For instance, under the configuration of Ours(7/8- 3/4-1/2), the accuracy of HShare is slightly superior to those in Quest and DS, but the computational complexity of HShare only 16.8% and 33.6% of theirs, respectively. We also conduct experiments with token-sparse attention applied to both the prefill and decoding stages, the corresponding results can be found Appendix A.1.
Results.
5.1.3 RESULTS ON LONGBENCH
Datasets and Metries. We further use sixteen English datasets in LongBench to evaluate the performance of the proposed HShare across multiple long context benchmarks, including code completion tasks, few-shot learning tasks, document QA tasks, summarization tasks, and synthetic tasks. The metric used for each dataset can be found in Appendix A.2.
Inference Details. All methods select N, 512 critical KV cache tokens, with token sparsity ratio of approximately 1/8. Similarly, we select critical tokens from three aspects: = 16 sink tokens, y = 64 recent tokens, and 2 = 432 critical tokens in the middle. We conduct experiments on LLaMA2-7b-char with three sharing ratios of HShare: 7/8-3/4-1/2, 3/4-3/4-1/2 and 1/2-1/2-1/2.
Results. The results of sixteen English datasets in Longbench are shown in Tab. 3. We can find that HShare outperforms StreamingLLMM, H2O, and Quest by a notable margin, which demonstrates that HShare has the ability to maintain accuracy in long-context scenarios. Additionally, the results show that HShare could achieve competitive performance compared with DS under different sharing ratios. It is important to note that the sharing ratio of HShare serves as a hyperparameter that can influence the balance between effectiveness and efficiency. To further validate the performance of HShare, we also conduct experiments with token-spars attention applied to both the prefill and decoding stages. More detailed results and discussion can be found in Appendix A.3.
5.2 EFFICIENCY EVALUATION
5.2.1 SETUP
All experiments are conducted on a machine with Xeon(R) Platinum 8336C CPU, one A.00 GPU, and 128G RAM.
8

---

Published as a conference paper at ICLR 2025
Table 4: Attention operator latency (ms }) of different methods across various batch sizes and
sequence lengths.
BS Seqien
Flash
StreamingLLLM
H20
Quest
DS
Ours (7/8-3/4-/22) Ours (3/4-3/4-1/2) Ours (1/2-1/2-1/2)
8
1k
0.230
0.0.0
0.088
0,200
0.141
0.140
0.124
0.090
2k
0.830
0,038
0.093
0,460
0.241
0.191
0,160
0.120
4k
1,630
0.420
0.470
0.850
0.733
0.602
0.570
0.530
1k 0.440
0,030
0.089
0,280
0.233
0.161
0.120
0.093
2k 1,630
0.073
0.110
0.770
0.422
0.270
0.230
0.190
4k 3,230
0,800
0.850
2.21 1.350
1.080
1.041
0.990
Table 5: Throughput (1) of different methods across various batch sizes and sequence lengths.
Segien GPT-Fast StreamingLLM
H2O
Quest
DS
Ours (7/8-3/4-1/2)
Ours (3/4-3/4-1/2)
Ours (1/2-1/2-1/2)
lk
228
264
240
228
228
230
231
235
2k
188
252
234
206
213
220
222
226
118
201
212
214
217
16
374
465
441
410
423
428
430
439
2k
233
452
416
287
360
393
398
411
136
422
396
175
286
350
365
5.2.2 SELF-ATTENTIO OPERATOR SPEEDUP AND END-TO-END INFERENCE SPEEDUP
Inference Details. Following Yang et al. (2024b), we utilized PyTorch to approximate attention, selecting the top-2 tokens from the middle and further incorporating x initial indices and recent indices to form the complete set of critical token indices. The kernel for head-level sharing and the attention over critical KV tokens are designed using OpenAl Triton. Meanwhile, since HShare designs key value sharing between different layers and queries, we require an additional cache to store the critical token indices that need to be shared. Then for attention modules where the computation of critical token indices is bypassed due to sharing, we directly load the corresponding part from the cache. The additional storage required here is minimal, complexity of ((N2). As for end-to-end testing, our implementation is based on GPT-fast (Py Torch, 2023), with the full attention module being replaced by our token sparsity self-attention module. We conduct the self-attention latency evaluation on single A100 GPU with batch sizes 8, and 16 and sequence lengths ranging from 1k to 4k, with token sparsity ratio of 1/8.
only need to store integers with
Baseline. In line with accuracy evaluation, here we also use two KV cache eviction algorithms StreamingLLMI H2O and two query-aware token sparsity algorithms Quest, DS as our baselines. In addition, for self-attention operator speedup evaluation, we add FlashAttention2 (Flash) (Dao, 2023) as our baseline, which is an optimized dense attention mechanism designed improve the speed and efficiency and ranks among the fastest attention mechanisms. For end-to-end inference speedup evaluation, we further take GPT--ast (Py Torch, 2023) as the baseline for dense attention, which is acknowledged as the SOTA implementation for LLaMA models on the A100 GPU,
Results. Tab. 4 and Tab. 5 present the latency of attention operator and the throughput of end-to-end inference, respectively. For attention latency, we simulate the hierarchical sharing framework and average the latency over 1000 times self-attention com- putations. For end-to-end throughput, all results are averaged over 10 runs.
Trade-off between accuracy and efficiency
Average score longbench
450
Average
33 22
Throughout
-400
350
31
-30
Compared to dense attention, we can find that HShare consistently outper- forms Attention and GPT--fst, achieving up to an 8.6x acceleration in self-attention latency and up to a 2.7x increase in throughput. When we compare different token sparse atten- tion methods. it can be observed that KV cache eviction algorithms have a clear advantage in system efficiency compared to query-aware token sparsity algorithms. Specifi-
28
150
27
100
Original
SteamiingL1M
H20
Quest
0u0f778-314-122 3/4-122)
DS
0us 314-1))
Figure 4: The average score on Longbench and the end-to- end throughput (BS=16, Seqlen=4k) of different methods

---

Published as a conference paper at ICLR 2025
GSMBk/strict)
CODA
LCC
51.0
RepoBench-9
0.64
0
0.16
Accuns
02.0
AcCur
0.12
0.62
49.5
0.10
layer
49.0
0.06
query
48.3
314
112
2/4 Sharing ratio
1/2
124
1/4
314
48.0
1/ Sharing ratio
1/
Sharlng rabi
Sharing ratio
TriviaQA
Qasper
2WikMMutthooQA
GovReport
06.5
Accurac
$4.0
83.5
20
83.0
82.5
18
92.0
1P Sharing ralio
AH4
17
1/3
1/4 24
344
122
100
12
10
Sharing ratio
Sharing ratio
Sharing ratio
Figure 5: Results of HShare with different sharing ratios on eight datasets.
cally, StreamingLLM achieves the fastest speed as it applies fixed sparsity pattern. However, both StreamingLLM and H2O fall short terms of accuracy. In contrast, HShare could balance the trade-off between effectiveness and efficiency compared with other methods. For example, under the configuration of (7/8-3/4-1/2), HShare not only achieves competitive accuracy results over DS but also gains over a 9.17% improvement in end-to-end throughput when the batch size 16 and the sequence length is 2k. Notably, as the sequence length increases, the advantage of HShare will be further amplified, For example, when the batch size 16 and the sequence length is 4k, HShare 17.48% faster than DS.
To further illustrate the trade-of off between accuracy and efficiency, we present the average score on Longbench and the end-to-end to- throughput (BS=16, Seqlen=4k) of different methods in LLaMA2- 7b-chat. The results are depicted in Fig. 4. We can find from Fig. that the original model with the dense attention mechanism achieves the highest score over Longhench, albeit at the cost of the lowest throughput. On the other hand, StreamingLLM achieves the highest throughput, significantly outpacing other methods in processing efficiency but exhibits the lowest average score. Notably, method performs a balance between these two aspects, showing negligible performance degradation while maintaining relatively high throughput. This demonstrates the effectiveness of our approach in achieving competitive accuracy while enhancing processing efficiency compared to other methods.
5.3 ABLATION STUDY
HShare with different sharing ratios. We conduct ablation studies under different sharing ratios on eight datasets and the results are shown in Fig. 5. Specifically, for layer-level and head-level sharing, we selected sharing ratios of 3/4, 1/2, and 1/4. For query-level sharing, we group queries in sets of 2 and 4, corresponding to sharing ratios of 1/2 and 1/4, respectively. The results indicate that for all three levels, smaller sharing ratio tends to result greater accuracy loss on average, However, on certain datasets like TriviaQA and GSM8K, sharing subset of heads leads improved performance. Additionally, compared to head-level sharing, we observe that layer-level and query-level sharing have a greater negative impact accuracy. Overall, the sharing ratios 3/4-3/4-1/2 and 1/2-1/2-1/2 emerge as more reasonable options. More ablation studies can be found in Appendix A.4.
6 CONCLUSION AND DISCUSSION
In this paper, we first systematically analyze and reveal the similarity of critical KV cache tokens across layers, heads, and query levels. Then we introduce HShare, a hierarchical framework for sharing critical KV cache token indices at all three levels to reduce the overhead associated with selecting critical KV tokens. Additionally, we propose a greedy selection algorithm for efficient sharing at the layer and head levels. Extensive evaluations show that HShare preserves model accuracy with different sharing ratios while achieving up to 8.6x speedup in self-attention operations and 2.7x increase in end-to-end throughput compared with FlashAttention2 and GPT-fast respectively. To the best of our knowledge, HShare is the first work to introduce the concept of sharing critical KV cache token indices. At present, the selection of the sharing ratio remains relatively heuristic and leave the exploration of dynamically determining whether to share and how to select an appropriate sharing ratio for different tasks part of our future work.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Heba Abdel-Nabi, Arafat Awajan, and Mostafa Z Ali. Deep learning-basee question answering: survey. Knowledge and Information Systems, 65(4):1399 1485, 2023.
Peter Anderson, Xiaodong He, Chris Buehler, Damien Teney, Mark Johnson, Stephen Gould, and Lei Zhang. Bottom-up and top-down attention for image captioning and visual question answering. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 6077-6086, 2018.
Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, et al. Longbench: A bilingual, multitask benchmark for long context understanding. arXiv preprint arXiv:2308. 14508, 2023.
Tianyi Bao, Qitian Wu, Zetian Jiang. Yiting Chen, Jiawei Sun, and Junchi Yan. Graph out-of- distribution detection goes neighborhood shaping. In Proceedings of the 41st International Conference Machine Learning, ICML'24. JMLR.org. 2024.
Tianyi Bao, Xinyu Ye, Hang Ruan, Chang Liu, Wenjie Wu, and Junchi Yan. Beyond circuit connections: A non-message passing graph transformer approach for quantum error mitigation. In The Thirteenth International Conference on Learning Representations, 2025. URL https: // /ppenrevieww net/ forum? witmmmmiddxVVtteaa.....
Iz Beltagy, Matthew Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.051500 2020.
Lequn Chen, Zihao Ye, Yongji Wu, Danyang Zhuo, Luis Ceze, and Arvind Krishnamurthy, Punica: Multi-tenant lora serving. Proceedings of Machine Learning and Systems, 6:1-13, 2024a.
Shaoyuan Chen, Yutong Lin, Mingxing Zhang, and Yongwei Wu. Efficient and economic large language model inference with attention offloading. arXiv preprint arXiv:2405.01814 2024b.
Xinyan Chen, Yang Li, Runzhong Wang, and Junchi Yan. Mixsatgen: Learning graph mixing for sat instance generation. The Twelfth International Conference on Learning Representations, 2024c.
Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint #xXiv:9904 10509, 2019.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, al. Training verifiers solve math word problems. arXiv preprint [tti:2110.14166 2021.
Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. arXiv preprint rrXiiv2307.08691 2023.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang. Angela Fan, et al. The llama herd of models. arXiv preprint arXiv:2407.21783, 2024.
Aryaz Eghbali and Michael Pradel. De-hallucinator: Iterative grounding for Ilm-based code comple- tion. arXiv preprini arXiv:2401.01701, 2024.
Bogdan Gliwa, Iwona Mochol, Maciej Biesek, and Aleksander Wawer. Samsum corpus: A human- annotated dialogue dataset for abstractive summarization. arXiv preprint 191.2:1911.12237, 2019.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.06825, 2023a.
Huiqiang Jiang, Qianhui Wu, Chin-Yer Lin, Yuqing Yang, and Lili Qiu. Limlingua: Compressing prompts for accelerated inference of large language models. arXiv preprint 231.022310 2023b.
11

---

Published as a conference paper at ICLR 2025
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 Ilms via dynamic sparse attention. arXiv preprint arXiv:2407.02490, 2024. 2024.
Nikita Kitaev, tukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arXiv:2001.04453 2020.
Lucien F Krapp. Luciano A Abriata, Fabio Cortés Rodriguez, and Matteo Dal Peraro. Pesto: parameter-free geometrie deep learning for accurate prediction of protein binding interfaces. Nature communications, 14(1):2175, 2023.
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pp. 19274-19286, PMLR, 2023.
Dacheng Li, Rulin Shao, Anze Xie, Ying Sheng, Lianmin Zheng, Joseph Gonzalez, Ion Stoica, Xuezhe Ma, and Hao Zhang. How long can context length of open-source Ilms truly promise? In NeurlPS 2023 Workshop on Instruction Tuning and Instruction Following, 2023a.
Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat formula generation and a strong structure- structureharrdness-e hardness-aware baseline. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023b.
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023c.
Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha, and Junchi Yan. Fast 12t: Optimization consistency speeds up diffusion- based training-to- to-testing solving for combinatorial optimization. Advances in Neural Information Processing Systems, 2024.
Ji Lin, Jiaming Tang, Haotian Tang, Shang Yang, Wei-Ming Chen, Wei-Chen Wang, Guangxuan Xiao, Xingyu Dang, Chuang Gan, and Song Han. Awq: Activation-aware weight quantization for on-device Ilm compression and acceleration. Proceedings of Machine Learning and Systems, 87-100, 2024a.
Yujun Lin, Haotian Tang, Shang Yang, Zhekai Zhang, Guangxuan Xiao, Chuang Gan, and Song Han. Qserve: W4a8kv4 quantization and system co-design for efficient Ilm serving. arXiv preprint arXiv:2405.04532. 2024b.
Yixin Liu, Kejian Shi, Katherine S He, Longtian Ye, Alexander R Fabbri, Pengfei Liu, Dragomir Radev, and Arman Cohan. On learning to summarize with large language models as references. arXiv preprint arXiv:2305.1422. 2023.
Zirui Liu, Jiayi Yuan, Hongye Jin, Shaochen Zhong, Zhaozhuo Xu, Vladimir Braverman, Beidi Chen, and Xia Hu, Kivi: tuning-free asymmetric 2bit quantization for kv cache. arXiv preprint arXiv:2402.027500 2024.
Xupeng Miao, Gabricle Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rac Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, et al. Specinfer: Accelerating large language model serving with tree-based speculative inference and verification. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, pp. 932-949, 2024.
OpenAl. Introducing gpt-4o: our fastest and most affordable flagship mode, 2024. URL https: //platfomm openai. com/ docs/modee mooels. Last accessed 28 September 2024.
Proyag Pal, Alexandra Birch-Mayne, and Kenneth Heafield. Document-level machine translation with large-scale public parallel corpora. In The 62nd Annual Meeting of the Association for Computational Linguistics, pp. 13185-13197. Association for Computational Linguistics (ACL), 2024.
12

---

Published as a conference paper at ICLR 2025
Xiurui Pan, Endian Li, Qiao Li, Shengwen Liang, Yizhou Shan, Ke Zhou, Yingwei Luo, Xiaolin Wang, and Jie Zhang. Instinfer: In-storage attention offloading for cost-effective long-context Ilm inference. arXiv preprint (Xfv:22409004992 2024.
Bowen Peng, Jeffrey Quesnelle, Honglu Fan, and Enrico Shippole. Yarn: Efficient context window extension of large language models. arXiv preprin! S.Kiv:2309000077.. 2023.
Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently scaling transformer inference. Proceedings of Machine Learning and Systems, 5:606-624 6204,624,200 2023.
PyTorch. Accelerating generative ai with pytorch 2.0. https: http:://pstorcchoorr//.... accelerating--geneeeeeee geneinniieeeerrrriiieeeeeee
May 2023.
Zafaryab Rasool, Stefanus Kurniawan, Sherwin Balugo, Scott Barnett, Rajesh Vasa, Courtney Chesser, Benjamin M Hampstead, Sylvie Belleville, Kon Mouzakis, and Alex Bahar-Fuchs. Evaluating Iims on document-based qa: Exact answer selection and numerical extraction using cogtale dataset. Natural Language Processing Journal, pp. 100083, 2024.
Siva Reddy, Danqi Chen, and Christopher Manning. Coqa: A conversational question answering challenge. Transactions of the Association for Computational Linguistics, 7:249-266, 2019.
Luka Ribar, Ivan Chelombiev, Luke Hudlass- Galley, Charlie Blake, Carlo Luschi, and Douglas Orr. Sparq attention: Bandwidth-efficien I1m inference. arXiv preprint arXiv:2312.04985, 2023.
Jacwon Son, Jachun Park, and Kwangsu Kim. Csta: Cun-based spatiotemporal attention for video summarization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 18847-18856, 2024.
Jiaming Tang. Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikci, and Song Han. Quest: Query-aware sparsity for efficient long-context IIm inference, 2024.
Zeyu Teng. Yong Song, Xiaozhou Ye, and Ye Ouyang. Fine-tuning 11ms for multi- turli dialogues: Optimizing cross-entropy loss with kl divergence for all rounds of responses. In Proceedings of the 2024 16th International Conference on Machine Learning and Computing, pp. 128 128-133, 2024.
Kiran K Thekumparampil, Chong Wang, Sewoong Oh, and Li-Jia Li. Attention- graph neural network for sumi-super learning. arXiv preprint arviv / /03.033333333 2018.
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 1rX11 2023.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint 17 10903, 2017.
Huaijin Wu, Wei Liu, Yatao Bian, Jiaxiang Wu, Nianzu Yang, and Junchi Yan. Ebmdock: Neural probabilistic protein-protein docking via differentiable energy model. In The Twelfth International Conference on Learning Representations, 2024.
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 34:13266-13274 13279, 2021.
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. arXiv preprint arXiv:2309. /7453, 2023.
Guang Yang, Yu Zhou, Xiang Chen, Xiangyu Zhang, Tingting Han, and Taolue Chen. Exploitgen: Cemplate-augmentt exploit code generation based on codebert. Journal of Systems and Software, 195:1 2023.
Nianzu Yang, Huaijin Wu, Kaipeng Zeng, Yang Li, Siyuan Bao, and Junchi Yan. Molecule generation for drug design: a graph learning perspective. Fundamental Research, 2024a.
13

---

Published as a conference paper at ICLR 2025
Shuo Yang, Ying Sheng, Joseph E Gonzalez, lon Stoica, and Lianmin Zheng. Post-training sparse attention with double sparsity. arXiv preprint arXiv:2408.07092, 2024b.
Zihao Yi, Jiarui Ouyang, Yuwen Liu, Tianhao Liao, Zhe Xu, and Ying Shen. A survey on recent advances in Ilm-based multi-turn dialogue systems. arXiv preprini arXiv:2402.18013 2024.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205. 2000:200000008, 2022.
Tianyi Zhang, Jonah Yi, Zhaozhuo Xu, and Anshumali Shrivastava. Kv cache is bit per channel: Ef- ficient large language model inference with coupled quantization. arXiv preprint vrXiv2405.03911 2024a.
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, al. H2o: Heavy-hitter oracle for efficient generative inference of large language models. Advances in Neural Information Processing Systems, 36, 2024b.
Zixuan Zhang, Heba Elfardy, Markus Dreyer, Kevin Small, Heng Ji, and Mohit Bansal. Enhancing multi-document summarization with cross-document graph-based information extraction. In Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, pp. 1696-1707, 2023.
Xinhao Zheng, Yang Li, Cunxin Fan, Huaijin Wu, Xinhao Song, and Junchi Yan. Learning plaintext- ciphertext cryptographic problems via anf-based sat instance representation. Advances in Neural Information Processing Systems, 37:41649-41669 2025.
Wenhao Zhu, Hongyi Liu, Qingxiu Dong, Jingjing Xu, Shujian Huang, Lingpeng Kong, Jiajun Chen, and Lei Li. Multilingual machine translation with large language models: Empirical results and analysis. arXiv preprint arXiv:2304.0m 04675, 2023.
14

---

Published as a conference paper at ICLR 2025
A MORE EXPERIMENTS
A.1 MORE RESULTS ON GS8K, COQA
Table 6: Evaluation of different methods on GSM8K and COQA with sparse attention being applied to both prefill and decode stages. The best result (exclude origin) in each column is highlighted in bold. Complexity* refers to the theoretical time complexity for each method to select critical KV cache tokens, where (1) denotes constant time complexity, and represents the theoretical computation time for dense attention mechanism.
Model
Architecture
Method
CSMBK(fexiblc/tticc)))
COQA f Complexity*
Original
0.2297/0.223
0.5997
StreamingL.LM
0.0485/0.000
0.2515
H20
0.0558/1.108
0.3615
O(1)
Quest
0.0371/0.0364
0,5513
0.125T
LLaMA2-7b-ccat
MHA
0.1634/0.1622
0.6270
0,0625T
Ours (7/4-3/4-1/2)
0,158000 1482
0.6093
0.0217'
Ours (3/4-3/4-1/2)
0.1554/0, 1456
0.6013
0.0187'
Ours (1/2-1/2-1/2)
0.1319/0.0743
0.5960
0.00ST
Original
0.8067/0. 8052
0.7085
Streamingt
0.3897/00311
0.3473
H2O
0,4329/0,328
0.6100
0(1)
Quest
0.4708/0.44 4602
0.6900
0.1257
LLaMA3-70h
GQA
DS
0.7233/0.7 1195
0.7012
0.0625T
Ours (7/8-3/4-1/2)
0.7504/0.7483
0.7095
0.018T
Ours (3/4-3/4-1/2)
0.7460/0. 7445
0.7075
0.018T'
Ours (1/2-1/2-1/2)
0.7301/0.75 72221/
0.6912
0.008T
Original
0.3821/0.3813
0.6758
StreamingLLM
0.0849/0.0068
0,2905
H20
0.0902/0.0 0159
0.4225
O(1)
Mistral-7b
GQA
Quest
0.1302/0.088
0.6170
0.125T'
DS
0.3093/0.3063
0.6687
0.0625T
Ours (7/8-3/4-1/2)
0.3145/0.346
0.6631
0.018T
(3/4-3/4-1/2)
0.3101/0,301
0.6538
0.0187'
Ours (1/2-1/2-1/2)
0.2775/0.2707
0.6313
0.008T
Table 7: Evaluation of different methods sixteen English datasets in Longbench with sparse attention being applied to both prefill and decode stages. The best result in each row (excluding the original) is highlighted in bold.
Method
Original
StreamingLLMM
H2O
Quest
Ours (7/8-3/4-1/2)
Ours (3/-3/4-1/2)
Ours (1/2-1/2-1/2)
Darnset
MuluiNwws
26.22
22.93
22.24
24.83
Musique
8.65
4.56
6.32
6.65
7.16
8.15
7.63
7.41
HotpotQA
20.77
25.81
Qusper
21.88
14.01
14.13
17.14
21.94
21.14
22.13
21.39
2WIkIMQA
29.04
Repobench P
52.14
48.12
47.67
44.42
48.78
$0.22
49.67
48.88
TriviaQA
53.76
84.03
83.68
Tree
64.50
40.50
44.00
61.00
61.50
$9.00
$9.00
$7.50
20.28
NarrativeQA
18.83
9.52
11.83
14.53
15.76
15.29
16.05
16.40
GovReport
23.88
LOC
58.26
$2.41
$7.47
$3.99
57.75
$7.20
$6.29
$5.89
Passago-Connt
2.27
Samsum
41.01
37.37
38.57
40.67
41.48
42,06
40.73
40.13
Passage- Retrieval-ENN
6.0
MultnecdQA-EN
36.15
20.75
21.10
21.61
37.55
36.80
34.46
34.21
Average
32.90
32.07
We also conduct experiments with sparse attention applied to both the prefill and decoding stages. The results GSM8K and COQA are shown in Tab. 6. Compared to Tab. 2, the performance of most methods degrades due to the introduction of sparsity during the prefill stage. In this setting, HShare still significantly outperforms other KV cache eviction methods (StreamingLLMM and H20). On LLaMA2-7b-cha. HShare also incurs minimal accuracy loss while it achieves higher accuracy on LLaMA3-70b. We attribute this to the more redundancy in LLaMA3-70b for these tasks, where HShare may serves regularization role. Notably, we also observe a significant performance drop in H2O. We suspect this is because H2O performs topK operations based historical attention scores
15

---

Published as a conference paper at ICLR 2025
sharing ratio 3/4-3/4-1/2
sharing ratio 1/2-1/2-/2 goureport
gouroport
Zwikimee
Zwikimee
coq
coOp
18hham
random layer
random both random
gomby
tusper
gomby
garper
repobenchy
repobench-p
Figure 6: Comparison between HShare and random sharing at the layer level and head level. We take HShare as the 100% baseline and normalize the results of others accordingly.
to achieve sparsity. As a result, when sparsity is applied during the prefill stage, the topk operation during decoding accesses less historical information, leading to considerable accuracy loss.
A.2 DETAILS OF LONBENCH
We report MultiNews, Qmsum, GovReport, Samsum with rouge score; Musique, HotpotQA, Qasper, 2WikiMQA, TriviaQA, NarrativeQA, MultifeldQQAEN with F1 score; trec with classification accuracy; Dassage-Count, Eeesage-Retrievall exact-match accuracy; RepoBench-PP and LCC with similarity score.
A.3 MORE RESULTS ON LONGBENCH
Here, also conduct experiments with sparse attention being applied both prefill and decode stages. The results across the 16 commonly used English datasets from Longbench are shown in Tab. 7. It can be seen that HShare achieves the highest scores the most sub-datasets. On average, HShare outperforms StreamingL.LM, H2O, and Quest, and can still achieve competitive results with DS under sharing ratio 7/8-3/4-1/2. Compared with Tab. 3, the results show slight degradation, while H2O shows significant deterioration.
A.4 MORE ABLATION STUDIES
Ablation study on different sharing schemes. We further conduct ablation studies to evaluate layer(head) sharing scheme as shown in algorithm 1. We compare our greedy sharing scheme with random sharing scheme under the same sharing ratio and the corresponding results are shown in Fig. 6. The empirical results indicate that when critical token indices are shared by randomly selected layers and heads, the accuracy decreases significantly across all datasets, further validating the effectiveness of sharing critical tokens between similar layers and heads.
Table Performance HShare on MultiNews.
Sharing Ratio
1K
2k
3k
4k
Ours-7/8-3/4-1/2
27.78
27.18
25.87
23.51
Ours-3/4-3/4-122
27.77
27.55
25.73
22.49
Ours-1/2-1/2-122
26.58
25.93
24.65
19.99
Ablation study on different context lengths. To test our method in document summarization with varying context lengths, we conduct experiments on the MultiNews dataset, which belongs to the document summarization category. We evaluate the proposed HShare across different context lengths and sharing ratios. The results are presented in Tab. It should be noted that regardless of the length of the text, consistently selected 256 critical tokens. The results show that the score decreases as the context length increases, and similarly, higher degrees of sharing also lead to a decline in performance. This suggests that when dealing with long context lengths, more moderate sharing
16

---

Published as a conference paper at ICLR 2025
strategy is needed to maintain accuracy, whereas, for shorter texts, higher degree of sharing be applied.
Table 9: Attention latency (ms L) and GSM8K accuracy of HShare under different sharing ratios.
Sharing Ratio
Attention Latency(ms)
(SMe(([eexilesstiicc))
1/2
0.31
0.144/0.136
1/4
0.23
0,135/0,
1/8
0.19
0.132/0.074
1/16
0.10
0.107/0.032
Trade-off within HShare. In addition, we provide the attention latency and GSM8K accuracy of our proposed HShare under different sharing ratios in Tab. reveal the tradeoff between accuracy and efficiency within HShare.
B DISCUSSION OF POTENTIAL ADAPTATIONS
We believe HShare can effectively support transformer variants. HShare aims to optimize long sequence attention operations by sharing critical key and value indices between layers, heads, and queries. As such, convolutional or graph neural networks with attention can also benefit from the proposed HShare. Below are two examples of potential applications:
Convolutional neural network (CNN) with attention: (Son et al., 2024) proposes to adopt CNNs to extract image features and use To apply HShare in this network, we can predict the indices of critical features (similar to critical tokens), which can then be shared across heads and layers. The potential adaptation involves using only the critical features for attention computation. Since video input exhibits temporal redundancy across nearby frames, critical feature indices can also be shared across frames. HShare can further be applied to other CNN-related works, such as VQA (Anderson et al., 2018).
attention to identify crucial frames.
Graph neural network (GNN) with attention: Graph neural networks have been applied in various fields (Li al., 2023b;e; Chen et al., 2024e; et al., 2024; Bao al., 2024; Zheng et al., 2025) and Veličković et al. (2017) adopts multi-head attention to extract features from a set of input nodes. HShare can be seamlessly applied to identify critical nodes and share their indices across heads and layers (if multiple layers are used). Depending the problem, if the graph nodes are close and similar, the key indices these nodes can also shared across nodes, similar query sharing in HShare. Similar works (Thekumparampii et al., 2018; Wu et al., 2021) could also benefit from applying HShare to reduce computational load. Moreover, HShare demonstrates significant potential in graph-related tasks that leverage graph transformers, particularly those involving large-scale graphs or high computational complexity. This is especially relevant in fields such as biology, where tasks related to molecules and proteins are prevalent (Krapp et al., 2023; Wu et al., 2024; Yang et al., 2024a), as well as quantum-related applications (Bao al., 2025).
17


Reviews:
[{"review_id": "8QEfZ90ZD0", "reviewer": "Reviewer_mExh", "summary": "This paper explores the similarities in the KV cache tokens across neighboring queries, layers, and heads. Building on this finding, the paper introduces an advanced solution named HShare, which leverage a hierarchical framework for KV cache sharing. HShare enables the sharing of critical KV cache token indices across layers, heads, and queries, substantially reducing the computational load associated with query-aware dynamic token sparsity. Additionally, we propose a greedy algorithm that dynamically selects the optimal layer-level and head-level sharing configurations during the decoding phase. Emprical study was conducted to assess HShare's effectiveness and efficiency on various tasks using three models—LLaMA2-7b, LLaMA3-70b, and Mistral-7b. Experimental results reveal that HShare preserves accuracy while enhancing system efficiency.", "questions": "Please address the corresponding problem listed in the Weaknesses Section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- S1. This paper addresses a crucial and cutting-edge problem in the field, tackling the computational challenges associated with managing KV cache in long-context LLMs. \n\n- S2.  The techique solution is well-desgined. By optimizing the reuse and sharing of critical KV cache token indices across queries, layers, and heads, the proposed solution significantly reduces computational overhead without compromising accuracy.", "weaknesses": "- W1. The main concern I have is about the system-efficiency evaluation in Section 5.2. Concretely, I think the baseline is a little weak; we know FlashAttention could be the state-of-the-art implementation, but it is not equipped with advanced algorithm design for selective KV-cache usage. As motivated in the introduction, other methods also attempt to reduce the computation budget based on sparsity; I think the author should report the corresponding system efficiency with the same set of baselines in Section 5.1 to fully reveal the trade-offs introduced in Table 1. \n\n- W2. There are some trivial presentation issues. For example, on page 6, line 270, there is no space between \"across\" and \"layers\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OiksINEMkR", "reviewer": "Reviewer_ZRXS", "summary": "The authors conducted systematic experiments to analyze the similarity of KV cache selection among queries, heads, and layers. Capitalizing on these findings, they proposed a method that shares KV selection across the dimensions of query, head, and layer, thereby reducing the overhead of KV selection.", "questions": "Please refer to weakness points 1-4", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The sharing-based method proposed in this paper seems novel.", "weaknesses": "1.\tThe experiments only selected 6 out of the 16 commonly used English datasets from Longbench for evaluation, which may not be sufficient to draw solid conclusions. For example, the performance of H2O and Quest on these 6 datasets in Table 3 appears similar, whereas in the Quest paper, H2O showed significantly lower accuracy. This discrepancy may suggest that specific methods perform better on these six datasets. To clarify, the authors are encouraged to provide results across all datasets.\n\n2.\tIn terms of speedup, the authors analyzed the theoretical complexity of KV cache selection in Table 2. However, this analysis alone is insufficient to demonstrate that the proposed method significantly reduces computational overhead, as the selection cost may only account for a small portion of the entired decoding process. To strengthen this claim, the authors could provide direct evidence of decoding speed in experiments. Additionally, an experimental study on the trade-off between accuracy and speed would be valuable.\n\n3.\tThe authors provided only a speed comparison with FlashAttention. To better demonstrate the effectiveness of their method, comparisons with other query-aware dynamic token sparsity methods are necessary. \n\n4.\tThe authors mention using an approximate computation approach from Double Sparse ('Following the approach in Yang et al. (2024)') to calculate approximate attention weights in their implementation. As a result, it is unclear how much of the observed speed gain is attributable to HShare specifically versus the query-aware dynamic token sparsity method itself.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wh2l1uxISn", "reviewer": "Reviewer_DdXB", "summary": "The paper introduces HShare, a hierarchical key-value (KV) sharing framework to accelerate inference in large language models (LLMs). HShare exploits observed similarities in critical KV cache token usage across layers, heads, and adjacent queries to reduce the computational overhead of selecting query-specific tokens repeatedly. It introduces a method to share critical KV cache token indices within and across layers, heads, and queries and proposes a greedy algorithm to optimize layer- and head-level sharing configurations. Experiments demonstrate that HShare maintains accuracy while providing up to 8.6× speedup in self-attention and a 2.7× improvement in end-to-end throughput across various LLM architectures, including LLaMA and Mistral models.", "questions": "Can HShare effectively support transformer variants such as convolutional or graph neural networks? A brief discussion on potential adaptations would help generalize its usability.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The hierarchical sharing of KV cache tokens across heads, layers, and queries is an innovative approach to reducing latency in self-attention. HShare's observation of token reuse across different levels of attention blocks offers a new angle to address computational efficiency in LLM decoding. HShare's ability to maintain high accuracy while delivering substantial improvements in self-attention latency and throughput makes it significant for practical deployment scenarios. The method's compatibility with several model types suggests its value for LLM inference optimization.", "weaknesses": "While HShare achieves substantial speedup, the layer- and head-level sharing configurations are tested only on a few model architectures, leaving broader applicability unexplored. Additionally, its performance in tasks that demand highly dynamic attention, such as document summarization with varying context lengths, could be tested to reveal any potential trade-offs. Minor computational overhead remains from online calculation in the prefill phase, though this appears manageable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qI3DrC4FcX", "reviewer": "Reviewer_RqY3", "summary": "HShare aims to reduce computation complexity of key value caches of transformer-based LLMs by sharing theses caches between attention heads within a layer, the layers themselves and queries within a batch. They identify critical tokens from three areas: initial/sink tokens, most recent window and significant tokens in the middle. For each of three dimensions (head, layer, query) they identify elements in these dimensions that are similar (based on a self-defined metric: overlap of cached key-value pairs) and only compute the respective key-value cache once, which is then shared between the respective elements. The resulting reduction in computation improves the latency and throughput for most configurations while maintaining the accuracy.", "questions": "* line 49: What are \"heavy tokens\"?\n* line 137: \"However, such a compression strategy ... and also increases the overhead during inference.\" - In what regard? Wasn't the \n compression of prompts applied to reduce certain types of overheads, for example memory complexity?\n* Figure 2: On what query sequence is the figure based?\n* 5.2.2 Where does the query data come from?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* A big strength is the evaluation. There is a wide variety of datasets used with a reasonable number of models, which show some variance in model size and architecture. Four additional framework are chosen to serve as baseline for comparison. The evaluation not only focuses on accuracy, but on compute performance (latency, throughput) as well. The provided ablation study is also fair.\n* The main idea is presented clearly for the most part and is reasonable motivated with examples/microbenchmarks.\n* The reduction in computation complexity with a subsequent performance improvement seems like a relevant contribution.", "weaknesses": "* The language is a big issue. I had to read several sentences multiple times to make sense of them. So I suggest to improve the writing, so that language reads well.\n* The cache hierarchy is not discussed, i.e. the order in which the three dimensions are applied, which data they might share and so on. The individual levels are discussed in how they are constructed and their details, but not how they are applied together apart from that they are independent from each other (in their memory benefits), which contradicts the initial hierarchy claim.\n* some of the equations do not add much (eq. 4 and 5)\n* The performance of the original models without modification is kind of missing as a baseline for the evaluation.\n\nmore specific issues:\n* line 64: \"Although these two methods only load critical tokens, they retain all the KV cache\"\n  * That seems like a contradiction.\n* 2.1: recent efforts are from 2023 and 2024, but their downsides are discussed in a paper from 2022 - seems counterinituitive\n* line 248: \"Fig. 1(c) and Fig. 1(d)\" - I think these are not the correct subfigures: it should be 1e and 1f. I think \"Fig. 1(e) and Fig. 1(f)\" in line 250 is similarly wrong.\n* line 404: first time that the full name \"DoubleSparse (DS)\" was introduced; all previous mentions just refer to DS\n* table 3: I question the validity of computing an average from different types of scores (similarity, F1 and rouge).\n* I think the table and figure placement for the evaluation can be improved, i.e. moved closer to where they are discussed.\n\ndetailed/minor issues:\n* language:\n  * line 40/41: \"since the context length expands\" - probably better \"since as the context length expands\"\n  * line 43: \"to addressing this issue\" - I think it should either be \"to address this issue\" or \"for addressing this issue\".\n  * line 45: \"many works manage to only load these critical KV cache tokens\" - I think \"manage\" is the wrong word here, maybe better: \"many works choose to only load these critical tokens into the KV cache\"\n  * line 135: \"make efforts\" - should probably be past tense: \"made efforts\"\n  * line 136: \"Jiang et al. (2023b) trains\" - train (multiple authors as subject), or even better \"trained\"\n  * line 186: \"also the same operation for value matrix and form a new value\" - missing verb and general improvement: \"also apply the same operation to the value matrix to form a new value matrix ...\"\n  * line 265: \"layers of attention blocks\" - I think it should be \"layers of the attention blocks\"\n* typos:\n  * line 46: \"tokens(also\" - missing whitespace\n  * line 85: \"GSM8K Cobbe et al. (2021)\" - missing brackets around the reference, probably the wrong cite command is used\n  * line 120: \"scenarios.Decoder-only\" - missing whitespace\n  * line 143: \"MInference(Jiang et al., 2024)\" - missing whitespace\n  * line 182: \"i-th head(layer) and the j-th head(layer)\" - missing whitespace between \"head(layer)\", two times; alternatively you could also use \"head/layer\" or \"head|layer\" (also applies to other occurences of the same phrase)\n  * line 186: \"S}corresponding\" - missing whitespace\n  * line 210: \"HSahre\" -> \"HShare\"\n  * line 363: \"Sec.4.1\" - missing whitespace\n  * line 408: \"We use LM-Eval framework\" - missing \"the\" before \"LM-Eval\"\n  * Figure 6: x-axis label for TrivialQA is \"Sparsity Level\", when \"Sharing ratio\" is used for all other subfigures\n* references:\n  * \"Anze Xie Ying Sheng Lianmin Zheng Joseph E. Gonzalez Ion Stoica Xuezhe Ma Dacheng Li*, Rulin Shao* and Hao Zhang\" - author list is broken: wrong order, missing commas between the authors and please also remove the asterisks\n  * consider using title case for the titles", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QQHo8vRhbT", "reviewer": "Reviewer_Bqih", "summary": "This paper discusses HShare, a hierarchical framework that facilitates the sharing of critical KV cache token indices across layers, heads, and queries. From observed similarities in KV token criticality across different levels, HShare enables a more efficient sharing strategy. The paper also introduces a greedy algorithm to dynamically determine the optimal sharing configuration for the decoding phase. The experimental results demonstrate that HShare can maintain similar accuracy and improve the end-to-end throughput.", "questions": "1. What would be your suspected reason for the performance gain by enabling KV sharing in Figure 6?\n2. The sharing ratio can be more finely tuned. Do you think the sharing ratios would be dependent on the dataset and the task?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The problem is very practical and of high interest to the community, especially with limited computation resources\n2. A very comprehensive set of experiments to showcase the performance (latency and accuracy) on different datasets.\n3. Well-organized paper with adequate discussions on other existing methods.", "weaknesses": "1. The paper should have some figures that discuss the tradeoff between accuracy and efficiency", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)