TidalDecode: Fast and Accurate LLM Decoding with Position Persistent Sparse Attention
Authors: Lijie Yang
Zhihao Zhang
Zhuofu Chen
Zikun Li
Zhihao Jia
Venue: ICLR 2025 Poster (2025)
Keywords: efficient transformer serving
sparse attention decoding
Primary area: foundation or frontier models, including LLMs

Abstract: Large language models (LLMs) have driven significant advancements across diverse NLP tasks, with long-context models gaining prominence for handling extended inputs. However, the expanding key-value (KV) cache size required by Transformer architectures intensifies the memory constraints, particularly during the decoding phase, creating a significant bottleneck. Existing sparse attention mechanisms designed to address this bottleneck have two limitations: (1) they often fail to reliably identify the most relevant tokens for attention, and (2) they overlook the spatial coherence of token selection across consecutive Transformer layers, which can lead to performance degradation and substantial overhead in token selection. This paper introduces TidalDecode, a simple yet effective algorithm and system for fast and accurate LLM decoding through position persistent sparse attention. TidalDecode leverages the spatial coherence of tokens selected by existing sparse attention methods and introduces a few token selection layers that perform full attention to identify the tokens with the highest attention scores, while all other layers perform sparse attention with the pre-selected tokens. This design enables TidalDecode to substantially reduce the overhead of token selection for sparse attention without sacrificing the quality of the generated results. Evaluation on a diverse set of LLMs and tasks shows that TidalDecode closely matches the generative performance of full attention methods while reducing the LLM decoding latency by up to $2.1\times$.

Published as a conference paper at ICLR 2025
TIDALDECODE: FAST AND ACCURATE LLM DECOD- ING WITH POSITION PERSISTENT SPARSE ATTENTION
Lijie Yang*
Zhihao Zhang" Carnegie Mellon University zh 3 cmu edu
Zhuofu Chen Carnegie Mellon University zhuo fucêcs cmu edu
Carnegie Mellon University 1ijiey@andrew. cmu.edu
Zikun Li
Zhihao Jía
Carnegie Mellon University zi wikunl@cs menlecs. cmu. edu
Carnegie Mellon University zh whaihho@coo com.cmu.edc
ABSTRACT
Large language models (LLMs) have driven significant advancements across di- verse NLP tasks, with long-context models gaining prominence for handling ex- tended inputs. However, the expanding key-value (KV) cache size required by Transformer architectures intensifies the memory constraints, particularly during the decoding phase, creating significant bottleneck. Existing sparse attention mechanisms designed to address this bottleneck have two limitations: (1) they often fail to reliably identify the most relevant tokens for attention, and (2) they overlook the spatial coherence of token selection across consecutive Transformer layers, which can lead performance degradation and substantial overhead in token se- lection. This paper introduces TidalDecode, a simple yet effective algorithm and system for fast and accurate L.M decoding through position persistent sparse at- tention. TidalDecode leverages the spatial coherence of tokens selected by existing sparse attention methods and introduces a few token selection layers that perform full attention to identify the tokens with the highest attention scores, while all other layers perform sparse attention with the pre-selected tokens. This design enables TidalDecode to substantially reduce the overhead of token selection for sparse attention without sacrificing the quality of the generated results. Evaluation on a di- verse set of LLMSs and tasks shows that TidalDDecode closely matches the generative performance of full attention methods while reducing the L.LM decoding latency by up 2.1x. Code available at https//gtthhbb.com/rreee///////
INTRODUCTION
Large language models (LLMs) have revolutionized natural language processing (NLP) by achieving state-of-the-art performance on various tasks, including machine translation, summarization, and question-answering. Their ability to generate human-like text has made them indispensable across various domains, from academic research to industry applications (Touvron et al., 2023). As LLMs expand to handle more extended contexts, their potential applications increase dramatically. Long- context processing is vital for tasks such as thain-of-thouueee reasoning (Wei et al., 2023), document summarization (Huang et al., 2021), and retrieval-augeee augmented generation (Ram et al., 2023; Zhang et al., 2024b). However, extending context length further exacerbates the memory and compute bottlenecks inherent in the Transformer architectures.
LLM inference includes two stages: prefilling and decoding. The prefilling stage computes the activations for all input tokens and stores the keys and values for all tokens in the KV cache, allowing the LLM to reuse these keys and values to compute attention for future tokens. In each decoding stage, the LLM decodes one new token using all input tokens and previously generated tokens. The KV cache size grows linearly in the sequence length (Kwon et al., 2023). For instance, with a context length of 128K tokens, the KV cache of LLama2-77 7B with half precisinn can easily reach 64 GB
"qqual contribution
'The KV cache size is computed as: Layers*KV Heads Head Dim XSeq Len FP16 S (for K+V) 32 x 32 128 x 128K bytes 2 64 GB.

---

Published as a conference paper at ICLR 2025
creating substantial memory pressure for LLM serving. In addition, the LLM decoding stage is memory-bounde since decoding one new token requires accessing all previous tokens in the KV cache, making KV cache access the primary bottleneck for LLM decoding. This memory-bound nature severely limits the scalability and efficiency of L.L serving.
To address the memory bottleneck for KV cache access, recent work has introduced sparse atten- tion, which approximates full attention using a small portion of tokens with high attention scores. Compared full attention, sparse atlention reduces computation cost and memory access while preserving the LLM's generative performance (Ge et al., 2024; Zhang et al., 2023). Existing sparse attention techniques can be classified into two categories: eviction- and selection- based methods. First, eviction-basse sparse attention methods reduce memory usage for the KV cache by selectively discarding less relevant tokens from the KV cache, therefore reducing the number of tokens computed in attention mechanisms (Xiao et al., 2023; Zhang et al., 2023). While these methods decrease the size of the KV cache, they can be inadequate for tasks where critical information is carried by tokens that are prematurely evicted, such as the sat-ll--i--the-hysttalll tasks. On the other hand, selection-based sparse attention methods maintain all tokens in the KV cache, estimate their attention scores, and select small subset of tokens participate in each LLM decoding step. While these selection-based methods introduce various techniques to pinpoint relevant tokens, they often ignore the correlation of token selection across consecutive Transformer layers and introduce additional overhead for attention score estimation. Moreover, these approaches are prone to distribution shifts caused by appending sparsely attended, biased KV representations back into the cache.
This paper presents TidalDecode, a streamlined and efficient framework designed for fast and accurate LLM decoding, utilizing position persistent sparse attention (PPSA). key insight behind TidalDecode is the observation that tokens selected for sparse attention - based on their highest attention scores exhibit sigmificant overlap across consecutive Transformer layers within each decoding phase, which we refer to as spatial coherence. Instead of selecting tokens for sparse attention independently in each layer, TidalDecode introduces few token selection layers performing full attention to identify the tokens with the highest attention scores, which are shared across the following sparse attention layers, reducing the overhead of token selection. Empirical evidence shows that using just two token selection layers- one at the beginning and one in the middle - is sufficient to achieve high generative performance while minimizing computation and memory overheads. Additionally, to muche-correction mechanism that
address the KV cache distribution shift, TidalDecode introduces periodically refills the KV cache using full attention for all sparsely decoded tokens to mitigate bias in the KV representations.
Comprehensive evaluation with the LongChat-7b-vl15-2 Llama-3-88, Llama-3-70B, and Llama- 3.1-8B models on the
PG-19, and LongBench tasks demonstrates that TidalDecode can consistently achieve the best performance efficiency trade-off compared with the best existing sparse attention methods. We have implemented custom GPU kernels for PPSA and an end-to-end system for TidalDecode. Compared with existing full and sparse attention implementations, our system reduced the end-to-end inference latency by up 2.1x and 1.2x, respectively. In conclusion, our contributions are:
We propose TidalDecode, a streamlined and efficient algorithm and system for fast and high-quality LLM decoding, utilizing position persistent sparse attention.
To address KV cache distribution shifts, we introduce cache-correction mechanism that periodically refills the KV cache with using full attention for sparsely decoded tokens.
Empirically, we demonstrate the effectiveness and efficiency of TidalDecode through com- prehensive evaluation, showing that Teddl significantly outperforms existing sparse attention methods.
RELATED WORK
Long-context model. Efficiently handling long-context inputs essential for various LLM tasks in real-world applications such as document summarization, question answering, and dialogue systems (Wang et al., 2024). Recent advancements, including rotary positional encoding (RoPE) (Su et al., 2023), have enabled models to manage extended context lengths effectively. The Llama-3 model series supports up to 8K tokens, with enhanced versions such as and Llama 3.1 (AI, 2024b) extending this limit to 128K tokens. Additionally, proprietary L.MSs such
(AI, 2024a)
2

---

Published as a conference paper at ICLR 2025
000000000
KVCache
BLO 000
Top-k indices
Top-k k indices
Full Attention
Full Altention
Takan Solection
00 2, 3
Sparsa Attention
Sperse Attertion
Tokon Re- sol-sollaiio
[1, 4. 6
Sparse Attention
T2P
Attantion
15
39
16.0
Layer
Layer
Layer 2
(Q.K)
Layer 3
Layer 12 Layer 13
(Q. K)
Layer 14
Layer 31
Figure 1: An overview of the decoding step in TidalDecode, which performs full attention for the first two layers, full attention with token selection for the third layer and a middle layer, and position persistent sparse attention for all other layers.
GPT-4 Turbo and GPT-4o (OpenAI, 2024) support up 128K tokens, and Claude 3.5 Sonnet allows up to 200K tokens (Anthropic, 2024). While recent work has introduced efficient attention kernel implementation (Dao al., 2022; Dao, 2023), processing long-context inputs continues to be constrained by significant memory usage and computational costs from the extended KV cache. TidalDecode is designed to mitigate these challenges by reducing latency and memory overhead through an efficient strategy for selecting tokens with the highest attention scores and one-time intermediate re-calibration, ensuring both efficiency and high-qualin, output.
To alleviate the intrinsic computational and memory bottleneck in long-context LLM inference, recent works on sparse attention have approached this problem from two main perspectives: eviction- and selection-based methods.
Eviction-based sparse attention. Xiao et al. (2023); Zhang et al. (2024a) propose to reduce KV cache memory usage by evicting tokens that are considered less relevant during inference. These suffer from potential performance degradation, especially in tasks where every token may carry crucial information (e.g., thoele-in-the-haystae tasks), since tokens with high importance for future decoding step can be mistakenly evicted as the generation proceeds, which makes selection-based methods more popular choices in latest sparse attention works.
Selection-based sparse attention. Instead of evicting past tokens in the KV cache, Child al. (2019); Kitaev al. (2020); Choromanski et al. (2020); Tang al. (2024); Ribar et al. (2023) preserve full KV cache and only select important tokens to attend with the attention module on the fly. More specifically, Child et al. (2019) leverages fixed attention mask to select tokens while Tang et al. (2024); Ribar et al. (2023); Choromanski et al. (2020); Kitaev et al. (2020) aim to identify and retain the most relevant tokens each layer by approximating attention scores. Although these methods are more selective, they operate independently at each layer and are not guaranteed to obtain the ground-truth tokens with the highest attention scores, failing to capture token relevance patterns that persist across layers. Moreover, attention score estimation algorithms sometimes introduce unnecessary complexity, diminishing the practical efficiency gains they are designed to achieve. Improving upon prior works, TidalDecode leverages a shared pattern of most important tokens across consecutive layers to further reduce the computational overhead and memory access required for token selection.
METHODOLOGY
This section introduces TidalDecode, an efficient algorithm and system for fast LLM decoding using position persistent sparse attention and KV cache correction. Figure/ shows an overview of TidalDecode. TidalDecode uses the same prefilling mechanism as existing systems and performs full attention to compute the key-value (KV) cache for all prompt tokens. each decoding step, TidalDecode uses three types of attention layers: full attention, full attention with token selection, and position persistent sparse attention. First, TidalDecode performs full attention for the initial Transformer layers to avoid early performance degradation identified by prior work (Tang et al., 2024). Second, the layer immediately after full attention and a single middle layer (e.g., layer and 13 in Figure 1) perform full attention with token selection, where TedolDecode stores the inner
3

---

Published as a conference paper at ICLR 2025
product" between the current query and key vectors of all tokens in KV cache during full attention and then selects tokens contributing to the highest attention scores. Third, all other layers perform position persistent sparse attention, where only tokens selected from the previous token selection layer are loaded from the KV cache to perform attention computation.
3.1 POSITION PERSISTENT SPARSE ATTENTION (PPSA)
Attention mechanisms have been widely used in today's LLMs. For each attention head, the output is computed via scaled multiplicative formulation as follows.
A, Q;K,vVdd, H, softmax(A,)V,
where Qt K,, and Vi are the query, key, and value tensors for the i-th attention head. A₃ is matrix representing the attention scores between tokens, and H; is the output of the i-th attention head. Instead of attending all input tokens, existing sparse attention methods approximate attention computation by attending the query Q; to a subset of previous tokens with the highest attention scores. Prior work generally performs token selection for individual attention heads and Transformer layers, introducing high runtime overhead. For example, identifying the top-k tokens with the highest attention scores can introduce additional overhead and even take longer than computing full attention under certain circumstances (see Figure 6), thus diminishing the benefits of performing sparse attention.
The key insight behind TidalDecode's 's position persistent sparse attention is observation that tokens with the highest attention scores for consecutive Transformer layers highly overlap. We use the Llama-3-8B model and the needle-in-the-hayste
test the PG-19-mini dataset with context length 100K tokens to quantify this observation. We arbitrarily select 100 requests from the dataset, insert needles random depth, compute full attention, and analyze the correlation of attention scores patterns between different Transformer layers. We then report the head-wise cosine similarity for attention scores between adjacent layers in Figure 2a and the top-256 recall rate for different choices of token re-selection layer in Figure 2b. We observe that with only one token selection layer at the third layer, the average recall rates are less than 20% as shown in Figure 2b. However, as we choose an additional layer 13 to perform re-selection, the average recall rates boost to almost 40% due to the improvement on the token re-selection as shown in Figure 2a, where the token re-selection layer lies in the least correlated regions, identified by the red box.
Algorithm 1 TidalDecode
1: Input: Current embedding h, KV cache C, token budget m
2: Output: Logits
3: Initialize: / p=
Initialize the token buffer to store selected tokens
4: for each decoder layer do
5: q,k,u == f(Wakes h)
6: C.append(k,
7:
if is Full Attention Layer then
8:
= FullAttention(g, C[:))
Dense attention with the full KVCache
9:
else if i is Token Selection Layer then
10:
= FullAttention((g, C|:)
Dense attention with the full KVCache > Update token buffer
11:
K C.getKey, p arg Toggopp((g K) m)
12: else
SparsseAttentionng.C]))
Sparse attention with the tokens in the token buffer
14: end if
FFN(() 16:
end for
17:
logits = Im (e)
18:
return logits
Based on this observation, we design position persistent sparse attention to maximally leverage the token overlaps between consecutive Transformer layers to reduce the computation cost for token
We don't I store attention score as state-of-the-ar attention kernels don't ion't materialize the attention score. Since the softmax operation ordering invariant, we store the inner product value instead.
4

---

Published as a conference paper at ICLR 2025
0.40
0.35
08
0.30
0.8
Recall Rak
0.25
0.7
2 20
0.6
0.05
05
0.00
monor www. Geinau so oo Dud Noree CmM Part NON Re-selection Layer
Attention Head
(a) Cosine similarity of the attention scores for adjacent layers. The x-axis is the attention head index, and the y-axis corresponds to the correlation between layer and layer
(b) Recall rate by re-selection Layer, defined as the averaged overlap ratio between the tokens selected by TidalDecode and the ground truth ones across all sparse attention layers.
for the i-th entry.
By analyzing the attention score patterns from (00K-context-leee Haystack test conducted on PG-19-mini, shows the attention similarity between adjacent layers, where the least correlated region is identified by the red bounding box. 2b depicts the top-256 recall rates, indicating that different choices of re-selection layers have a high impact on the recall rates there is clear peak, delineating the optimal layers for token re-selection.
Figure 2:
Needle-in-the the-
selection while achieving high predictive performance. Algorithm shows the TidalDecode algorithm for interleaving full attention and PPSA layers. After the initial full attention layers, TidalDecode uses a token selection layer that computes full attention and selects tokens with the highest attention scores. To select tokens, TidalDecode stores the inner product (Q. K") on the fly together with full attention calculation. TidalDecode then selects the top è tokens with the highest inner product values to form token set T. Note that using the inner product to select top-k is equivalent to the post-softmax attention score as the softmax operator is ordering invariant. All PPSA layers after token selection layer computes sparse attention by only loading the keys and values for tokens in T, thus limiting the number tokens participating in attention computations and reducing memory access.
A straightforward approach to designing TidalDecode is to select the tokens T once after full attention and perform PPSA using the same set of tokens for all subsequent layers. However, our preliminary experimentation shows that using single token set for all Transformer layers reduces the LLM'' predictive performance by a large margin since distant Transformer layers are less correlated compared consecutive layers, shown in Figure 2. To address this issue, TidalDecode performs token re-selection in a middle layer, where TedalDecode recalibrates the selected tokens with the highest attention scores by applying full attention and re-selecting top-k token update T,, ensuring that token selection remains optimal for the remaining layers. This re-selection mechanism significantly boosts the model performance and promotes accurate and efficient PPSA throughout the model.
Extensive evaluation both small and large models wide range of datasets shows that using single middle layer for token re-selection sufficient to preserve the LLM's generative performance, while introducing small runtime overhead. However, deciding which layer to perform token re- selection critical to model performance. As shown in Figure 2, choosing different layers for token re-selection results in different recall rates, where layer 11 and 13 achieve optimal performance. Introducing one-time token re- selection at an optimal layer ensures the selected tokens are re- calibrated, effectively mitigating the drift in token importance and elevates accuracy from 15% (without re-selection) to almost 40%.
3.2 KV CACHE CORRECTION
For tokens decoded by sparse attention methods, their key/value representations can deviate from the original representation of full attention decoded ones, which refer to as polluted tokens. The problem can be further exacerbated as their KV pairs are added to the KV cache, resulting in the error accumulation distribution shift of the KV cache. This lead to model performance drop in scenarios where the generation length is fairly long. To this end, TidalDecode uses a correccoorootion mechanism shown in Figure 3 to periodically correct the polluted tokens in the KV cache. For
5

---

Published as a conference paper at ICLR 2025
0
KVCache
Every 7 7'stps
/ Polluted-+/
/
Corrected
TidalDecode
Figure 3: Cache Correction
every T decoding step performed by TidalDecode, there will be cache correction step through prefill over all polluted tokens to update their KV representations in the cache. The choice of 7 can be the level of thousands of decoding steps but also depend on different models and tasks. Notice that the cache correction step can be performed concurrently with the sparse decoding step. Nevertheless, we haven't 't used cache correction in our evaluations to make it fair comparison against existing methods.
EXPERIMENTS
4.1 EXPERIMENT SETTING
In this section, we conduct extensive experiments to assess both performance and efficiency of TidalDecode. Our evaluations are performed on widely used open-source models, including Llama-2- 7B Touvron et al. (2023) and Llama-3-8/700 Both models are pretrained decoder-only transformers, exhibiting similar yet distinct architectural features. For instance, Llama 3-8B incorporates group query attention (GQA), a feature not present Ilama 2-7B. In Section 4.2, we evaluate TidalDecode's performance various tasks, including seelle-in-the-hasttee LongBench. In Section 4.3, we write customized attention kernels and compare TidalDecode's kernel efficiency against existing state-of-the-art sparse attention methods. Finally, in Section 4.4, conclude our evaluations with a detailed sensitivity analysis on the choice of different token selection layers. We use TD+LX denote TedolDecode with layer X selected as the token re-selection layer throughout this section.
language modeling
PG-19, and
4.2 PERFORMANCE EVALUATION
To evaluate the effectiveness TidalDecode, we conduct thre key downstream NLP experiments: the needle-in -n--iin-ttt in-the-haystar (Peng et al., 2023) test, perplexity evaluation on the PG-19 19 dataset (Rae et al., 2019), and eight datasets in LongBench (Bai et al., 2023). These tasks provide robust benchmarks for measuring both sparse attention models' ability to retrieve critical information in challenging scenarios and their performance on long-context language modeling tasks.
4.2.1 NEEDLE-IN- HAYSTACK
Table 1: Results of 10k-context-length Needle-in-the-Haee Haystack test on LongChat-7b-vl..5 1-5-32... TeddlDecode achieves the same or better results than Quest (Tang et al., 2024) and significantly better results than cache eviction algorithms such as H2O (Zhang et al., 2024a), TOVA (Oren et al., 2024), and StreamingLLMM (Xiao et al., 2023). TidalDecode achieves full accuracy with only a 512 token budget.
Method / Budget
K=32
K=64
K= 128
K=256
K=512
H2O
0%%
1%
1%
1 1%
3%
TOVA
0%
1%
1%
3%
8%
StreamingLLM
1%
1%
1%
3%
5%
Quest 65%
99 %
99 %
99%
100%
TD+L7(Ours)
73%
92%
98%
99%
100%
The Needle-in-the. Hayttaa test assesses LLMs' ability to handle long-dependency tasks, which is particularly critical for sparse attention algorithms. Evietion-based methods (H20, StreamingI.LMM)

---

Published as a conference paper at ICLR 2025
Table 2: Comprehensive results of 10K- 32K-, and -00K-context-lennthh Seedle-in-the-Hayseee test on Llama-3-8B- Iee-Insttut-rrrriiie 1048k, 1i-ma-3.1-8B-I-see Gradient- 1048k with PG-19-mini dataset. Across all models, TidalDecode consistently outperforms Quest, showing that TidalDecode with only two token selection layers can effectively retain critical information. TidalDecode achieves full accuracy with 64, 64, and 128 tokens 10K-, 32K-, and 100K-context-lenge tests, which is only 0.6%, 0.2%, and 0. 0.1% of total input lengths, respectively.
and Llama-3-70h Inn-tttttt
Model (context length)
Method / Budget
K=32
K=64
K=128
K=256
K=512
Quest
74%
84%
99%
98%
100% %
Llama-3-8B (10K)
100
9 100%
TD+L13(Ours)
88%
98%
100%
TD+L.)((Orr))
92%
88%
94%
2696
99 100
Llama-3-8B (100K)
Quest
38%
50%
65%
1001
87%
25 20000 101
98%
ID+LI3(Ours)
86%
92%
100%
99 (,00)
TD+L11(OUrs)
84%
90%
92%
%,86
1886 356
Quest
74%
86%
94%
% 100
Llama-3.1-8B (10K)
28 100%
99 6000
TD+L13(Ours)
100 %
100 %
100%
TD+L14(Ours)
98%
100 %
100%
1001
1
Llama-3.1-8B (32K)
Quest
TD+LI3(Ours)
98%
78%
100% %
88%
100%
92%
1
3: 100
26 00001
26 9000 1
1001 111
8,000
5300
TD+L14(Ours)
80%
98%
% 000
1888 3336
26 0001
Quest
68%
72%
90%
Llama-3-70B (10K)
36 100
13 0001
TD+L14(Ours)
87%
93%
100%
99 2000
38 3000
TD+L31(Ours)
90%
97 %
100%
Quest TD+L14(Ours)
50%
80%
88%
92%
78%
Llama-3-70B (32K)
82%
98%
98%
100 %
100 %
TD+L31(OUrs)
80%
82%
92%
98%
100 %
may discard essential tokens, while selection-based approaches (Quest) often fail to consistently identify the ground-truth tokens with the highest attention scores in long contexts. Since Quest is the current state-of-the-art approach on this task that leverages an estimated attention score on the page level to identify important tokens for sparse attention, first run TidalDecode the same test as Quest on the LongChat- 7b- 1.5-32k model and obtained Table with competitive performance. To demonstrate the effectiveness of DedodDecode TidalDecode on tasks with 10K- 32K-, and (00K-context-windd window lengths with the Llama-3-70B, Llama-3-8B, Llama-3. 1-BB model using the PG-19-mini dataset, shown in Table 2. To ensure fairness, both TidalDecode and Quest use dense attention in the first two layers. In each test, we inserted random password within the text and tested whether the specific method could retrieve the password correctly.
ong-dependenncy tasks, we further evaluate
From Table TidalDecode consistently outperforms Quest and achieves full accuracy with an ex- tremely high sparsity (about 99.5% across all context lengths and models). These results demonstrate TidalDecode can achieve state-of-the-al performance with only two token selection layers. While Quest relies on page-level importance estimation for token selection, TidalDecode's exact selection with token reuse approach proves more effective for this task. Also, note that TidalDecode can reduce the token budget by up to 8x when achieving 100% accuracy compared with Quest. This further demonstrates that TidalDecode's exact token selection layer can obtain more relevant tokens than Quest.
4.2.2 LANGUAGE MODELING
Perplexity measures the negative likelihood of how well model predicts the next word in sequence, with lower values indicating better performance. We evaluate TidalDecode on Llama-3-8B 3-8B--nstrucc Gradient-1044 with the PG-19 dataset, which includes up to 100 books, providing comprehensive long-context benchmark.
As shown in Figure 4, TcdalDccode+99113// consistently achieves lower perplexity than Quest across all token budget options (2048, 4096). This indicates that TidalDecode's position persistent sparse attention mechanism effectively retain critical information without significantly sacrificing
7

---

Published as a conference paper at ICLR 2025
Perplexity with Context Length
Perplexity with Length
Perplexity (the lower the better
9.5
Full
Perplexity (the lower the better)
9.5
Fall
Quest TD+L13|ours)
Quest
TDoL13 TD L9Couss)
TD LBfouss
8.5
8.5
7.5
7.5
7.0
5000
10000 15000
20000 25000
30000
7.0
0
5000
10000 15000
20000
25000 30000
Input Context Length
Input Context Length
(a) Token Budget = 2048
(b) Token Budget
Figure 4: Perplexity evaluation on the PG-19 dataset from O to 32K tokens. The results compare TedalDecode with different token re-selection layers (L9, L13, L15) to Quest across token budgets (2048 4a, 4096 4b). Lower perplexity indicates better model performance. Full refers dense attention as baseline.
model accuracy, the sequence length grows, demonstrating its robustness for long-context inputs.
4.2.3 LONGBENCHI EXPERIMENT
Table 3: Performance comparison on eight LongBench datasets evaluating pangle/muuti-doccmeer QA, summarization, and retrieval tasks using Slama---BB-Instrueee Instruct-Gradient 1048k. Decod outperforms Quest at a 4096 token budget and achieves average score higher than full-weight attention. The maximum Fi-score for each task bold.
Method (KYTask
MFQA
NπQQ
Qasp
2Wiki
HotQA
QMSm
TrQA
PRe
Avg
Full
30.76
5.52
14.56
13.32
11.50
19.43
86.56
77.00
32.33
Quest (1024)
26.21
4.08
12.19
12.61
10.75
19.56
83.47
63.84
29.09
TD+L13
(1024)
28.57
7.63
11.11
13.56
9.82
20.37
79.78
75.17
30.75
Quest (4096)
28.92
3.74
13.63
12.83
12.15
19.36
85.91
72.50
31.13
TD+LI3 (4096)
30.94
6.19
13.85
14.40
13.71
19.48
86.30
78.00
32.86
We also evaluate TidalDecode LongBench, benchmark designed to test LLMs long-context tasks across diverse NLP domains (Bai et al., 2023). We focus on eight tasks: MultiFieldQA (MFQA) (Bai et al., 2023), NarrativeQA (NrtQA) (Kočiský et al., 2018), Qasper (Qasp) (Dasigi et al., 2021), 2WikiMQA (2Wiki) (Ho et al., 2020), HotpotQA (HotQA) (Yang et al., 2018). QMSum (QMSm) (Zhong al., 2021). TriviaQA (TrQA) (Joshi al., 2017), and Passage Retrieval (PRe) (Bai et al., 2023), which collectively composite a comprehensive evaluation benchmark in single/multi- document QA, summarization, and retrieval.
We evaluate all methods with Llama-3 3-B.- Instructt -rreructtrrriint----- 1048k. TidalDecode is compared against full-weight attention and Quest token budgets of 1024 and 4096. As shown Table 3, TidalDecode consistently outperforms Quest on all tasks at K 4096 and on five tasks at K = 1024. Surprisingly. TidalDecode, in most eases, matches or exceeds full attention baseline with notable utilization rate on input tokens: 14% NnQA, 50% MFQA. 80% on Qasp, 50% on 2WikiMQA, 32% on HotQA, 29% on QMSm, 35% on TrQA, and 33% on PRe. We hypothesize this is because TidalDecode's token selection process can filter out irrelevant information, thus leading to higher performance. We further include the results with cache correction in Appendix A.2.
These results demonstrate TidalDecode's 's generic ability to select tokens with the highest attention scores, achieving competitive or superior performance while significantly reducing token usage, making it ideal for long-context scenarios.
8

---

Published as a conference paper at ICLR 2025
10K
32K
100K
21
45
20
40
Latenc(mmc
Tancyims
Latoncy(ms)
19-
22
35
18
25
17
20
1000
3000
1000
3000
4000
1000
2000
4000
Budget
Budget
Token Budget
Quest TD(ours)
Figure 5: End-to-end latency results on Llama-2-7B model for Full attention baseline(Full), Quest, and (idalDecode(TD) when context length is 10K, 32K, and 100K, respectively.
4.3 EFFICIENCY EVALUATION
To show the efficiency TidalDecode, we write customized kernels for our approach and measure the end-to-end decoding latency. We conduct evaluation under the configuration of Llama-2-7B one Nvidia A100 (80 GB HBM, SXM4) with CUDA 12.2. We compare TedoeDecode with state-of-the-art full attention serving library FlashInfer (Ye al., 2024) and also the Quest implementation. As shown in Figure 5, we can observe that TidalDecode can consistently outperform full attention baseline and Quest by large margin under all token budgets and context lengths. TidalDecode achieves this through token pattern reuse to minimize the token selection overhead. Notice that the latest Llama-3 model shares the same architecture as Llama-2, except it uses Group-Query Query-Attention instead of Multi-Hcad-Attenioon However, this does not affect the relative efficiency comparison against Quest and full attention.
In Figure 6, we compare the overall attention latency between different methods on the Llama model with 32/64 layers. For the 32-layer Llama model, we have full attention layers + token selection layers + 28 sparse attention layers, while Quest has 2 full attention layers + 30 Quest attention layers. For the 64-layer Llama model, we have full attention layers + token selection layers 60 sparse attention layers, while Quest has 2 full attention layers 62 Quest attention layers. Thus, by completely removing the token estimation overhead the sparse attention layers, for the 32-layer and 64-layer Llama model under all context lengths, TidalDecode serving latency while bringing up to 5.56x speed-up ratio against the full attention baseline and 2.17x speed-up ratio against Quest. When the context length is 10K, Quest has higher latency due to the token selection overhead, which aligns with the end-to-end results Figure 5. In contrast, TidalDecode still achieves significant speed-up by utilizing the position persistent sparse attention mechanism. For the kernel-level analysis, please refer to Appendix A.5 for more details.
consistently achieve the lowest
4.4 SENSITIVITY ANALYSIS ON TOKEN RE-SELECTION LAYER
In this section, we conduct sensitivity studies for different choices of the token re-selection layer. As TidalDecode only has one token re-selection layer in the middle, it is critical to choose the best-performed one. As shown in Figure 7, we have two interesting findings: (1). Different choices of token re-selection layers can significantly affect the accuracy of the results (2). For models within the same model family, the optimal token re-selection layer is consistent over different tasks. In setup, the optimal token re-selection layer for the Llama-2-7B model is layer 7, while for the Llama-3-8B/Llama, 1-B model is layer 13. concurrent KV cache compression work also identifies that layer 13 is surprisingly important for their approach well (Shi al., 2024). For more detailed sensitivity results on the choice of different token re- e-selection layers, please refer to the appendix for more results.
5 CONCLUSION
To conclude, we introduce TidalDecode, an efficient LLM decoding framework with sparse attention. On observing the correlation of the pattern of tokens with the highest attention scores across different consecutive layers, TidalDecode proposes only select tokens twice: once at the beginning layers and once the middle layer to serve as a token re-selection layer. We find that using two token selection layers is necessary and sufficient to achieve high-generation quality. Additionally, by

---

Published as a conference paper at ICLR 2025
Full Attention
Taken Selection Layer
Sparse Attention
Quest Attention
Left bar: Full, Middle bar: Quest,
Right bar: TidalDecode
1.25
1.00
1.00
1.00
1,30
1,00
1.00
Relative Latency
Relative Latency
0.665
3..05
01.61
0.65
0.50
0.50
0.37
0.41
0.89
0.25
0.24
0.25
0.18
10K Context
32K Context
100K Context
10K Context
32K Context
100K Context
(a) 32 Layers
(b) 64 Layers
Figure 6: Overall attention latency results for different methods on the LLaMA model with (a) 32 and (b) 64 layers. We use the full attention model as a reference and show TidalDecode and Quest's overall attention latency ratio. For each group of the bar plots, the left/miiddlerriht bar denotes the full attention baseline, Quest, and TidalDecode, respectively.
LLaMA-2- 2---2-----Lnnhat
LLaMA-3.1-88 LLaMA-3-8B
LLaMA-2-7B-Ya
100
100
80
Accuracy
Accuracy(%)
60
60
40
20
20
0
10
20
30
Token re-selection layer index
Token re-selection layer index
(a) LLaMA-2 Model
(b) LLaMA-3 Model
Figure 7: Sensitivity study on the choice of different token re-selection layer. We evaluate LLaMA- 2-7B-LongChat, LLaMA-2-7B-Yam LLaMA-3-SB, and LLaMA-3,1-8D with TidalDecode with token budget of 256.
reusing the token patterns throughout the sparse attention layer, TedalDecode greatly reduces the token selection overhead, resulting in significant end-to-end speed-up ratio against existing methods. More interestingly, the optimal choice of the token re-selection layer is consistent across different tasks if the model is in the same model family.
ACKNOWLEDGMENTS
This research is supported by NSF awards CNS-2147909, CNS-2211882, and CNS-2239351, and research awards from Amazon, Cisco, Google, Meta, NVIDIA, Oracle, Qualcomm, and Samsung. The views and conclusions contained in this document those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of any sponsoring institution, the U.S. government any other entity.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Gradient AL
https://huggingff co/ gradientai/Llame 8B- Inw.:nntttt-rrrrieett----- 2024a. Accessed: 2024-09-
Llamm-3--b-inssmutt--ddddeee
26.
Meta AL. Llama 3.1: Advanced open-source language model.
3-1/, 2024b. Accessed: 2024-09-26.
Anthropic. Claude 3.5 sonnet.
3-aude--5--somee 2024. [Accessed 20-06-2024).
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. 2023.
Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv: I 1904. 10509, 2019.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint httt::2009.1497944 2020.
Tri Dao. Flashattention--2: Faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.08691 2023.
Tri Dao, Daniel Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness, 2022.
Pradeep Dasigi, Kyle Lo, Iz Beltagy, Arman Cohan, Noah A. Smith, and Matt Gardner. A dataset of information-secking questions and answers anchored in research papers. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilck Hakkani- -urr, Iz Beltagy. Steven Bethard. Ryan Cot- terell, Tanmoy Chakraborty, and Yichao Zhou (eds.), Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pp. 4599-4610, Online, June 2021. Association for Computational Linguis- tics. doi: 10. 10..1863/vvll 1/2021 I.a.ci-maiii...3655 URL https: htttps://aclatttoteet http://aaaaaanaoolc.ccoco orgpg//.rr222200 naacl - in.iinii.. 365/
Suyu Ge, Yunan Zhang, Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao. Model tells you what to discard: Adaptive kv cache compression for Ilms, 2024.
Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. Constructing a multi- hop QA dataset for comprehensive evaluation of reasoning steps. In Donia Scott, Nuria Bel, and Chengqing Zong (eds.), Proceedings of the 28th International Conference on Computational Linguistics, pp. 6609-6625, Barcelona, Spain (Online), December 2020. International Com- mittee on Computational Linguistics. doi: 10. 18.18653/v http:////00...oggmminna //aclanthology org 2020 coling-main. 580/.
URL https:
Luyang Huang, Shuyang Cao, Nikolaus Parulian, Heng Ji, and Lu Wang. Efficient attentions for long document summarization. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 1419-1436, Online, June 2021. Association for Computational Linguistics. doi: 10.18653/v1/2022 naacI-main. 12, URL https: / /acl antho ogy. org/ 2202 wwa.clllll--. -ma i n 112.
Mandar Joshi, Eunsol Choi, Daniel Weld, and Luke Zetteemoye.. TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension. Regina Barzilay and Min- Yen Kan (eds.), Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1601-1611, Vancouver, Canada, July 2017. Association for Com- putational Linguistics. doi: 10. 10.11863/11/1111111 URL https: / aaaaclaa aallhnhhhollg org/
P17 1177
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint ar arXiv:2001 XXiv:2001.04451,, 00451, 2020.
11

---

Published as a conference paper at ICLR 2025
Tomáš Kočiský. Jonathan Schwarz, Phil Blunsom, Chris Dyer, Karl Moritz Hermann, Gábor Melis, and Edward Grefenstette. The NarrativeQA reading comprehension challenge. Transactions of the Association for Computational Linguistics, 6:317-328, 2018. doi: 10.1162/tacl 00023. URL
httpss:/eat antholoooooooo 1 ogy- org/Q1 (trg//11-110 8-1033.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang. Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and lon Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023.
OpenAL. Introducing gpt-4o: our fastest and most affordable flagship model. openai. com/ docs /models, 2024. [Accessed 28-05-2024).
Matanel Oren, Michael Hassid, Yossi Adi, and Roy Schwartz. Transformers are multi-state RNNs, 2024. URL https: org. abs 2400 06104. arXiv:2401.06104.
Bowen Peng, Jeffrey Quesnelle, Honglu Fan, and Enrico Shippole. Yarn: Efficient context window extension of large language models, 2023.
Jack W Rae, Anna Potapenko, Siddhant M Jayakumar, Chloe Hillier, and Timothy P Lillicrap. Compressive transformers for long-range sequence modelling. arXiv preprint, 2019. URL https: 05507.
Ori Ram, Yoav Levine, Itay Dalmedigos, Dor Muhlgay, Amnon Shashua, Kevin Leywon-Brown, and Yoav Shoham. In-context retrieval-augmentedd language models, 2023. URL https:/ /arxiv. org/abs/ 2302. 00083.
Luka Ribar, Ivan Chelombiey, Luke Hudlass-Galle Galley, Charlie Blake, Carlo Luschi, and Douglas Orr. Sparg attention: Bandwidtt-rfffcieet I1m inference, 2023.
Zhenmei Shi, Yifei Ming, Xuan-Phi Nguyen, Yingyu Liang, and Shafiq Joty. Discovering the gems in early layers: Accelerating long-context Ilms with 1000x input token reduction. arXiv preprint arXiv:2409. 174222 2024.
Jianlin Su, Yu Lu, Shengfeng Pan, Ahmed Murtadha, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding, 2023.
Jiaming Tang. Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikci, and Song Han. Quest: Query-aware sparsity for efficient long-context Ilm inference, 2024. URL https: /tapp:///rxiiii //rxiv. org//bs//20 2406. 10774.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix. Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Ilama: Open and efficient foundation language models, 2023.
Xindi Wang, Mahsa Salmani, Parsa Omidi, Xiangyu Ren, Mehdi Rezagholizadeh, and Armaghan Eshaghi. Beyond the limits: survey of techniques to extend the context length in large language models, 2024. URL https: //arxi/avvivv org/ abs 2402. 02244.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models, 2023. URL https:/ //w./axvvvoo.o atrxivv.rrg/bbs//211111 atsp///ss/2220
11903.
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. arXiv, 2023.
Zhilin Yang. Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Conference on Empirical Methods Natural Language Processing (EMNLP), 2018.
12

---

Published as a conference paper at ICLR 2025
Zihao Ye, Ruihang Lai, Roy Lu, Chien- Yu Lin, Size Zheng, Lequn Chen, Tianqi Chen, and Luis Ceze. Cascade inference: Memory bandwidth efficient shared prefix batch decoding. https:/ flashinfer wttp:/ifeee.....2aaaa//a wwtpaaaa../aaae/aa cwwp///cccceeeeeeeeeeeeee inference.....e.. html. Accessed on 2024-02-
cascade- inference html, Jan 2024. URL https:
//fflashinfer.ai///0 ai / 01.
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song. Yuandong Tian, Christopher Ré, Clark Barrett, Zhangyang Wang, and Beidi Chen. Hдo: Heavy- hitter oracle for efficient generative inference of large language models, 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 genera- tive inference of large language models. Advances in Neural Information Processing Systems, 36, 2024a.
Zhihao Zhang, Alan Zhu, Lijie Yang, Yihua Xu, Lanting Li, Phitchaya Mangpo Phothilimthana, and Zhihao Jia. Accelerating iterative retrieval -argevee- language model serving with speculation. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scar- lett, and Felix Berkenkamp (eds.), Proceedings of the st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 21-27 Jul 2024b. URL https: http::/ss///p..eedi.ng.o
PMLR, mlrr.........m wrwssrrsssseee. /235s///v2//// 22455//haagg24cccc html.
Ming Zhong, Da Yin, Tao Yu, Ahmad Zaidi, Mutethia Mutuma, Rahul Jha, Ahmed Hassan Awadallah, Asli Celikyilmaz, Yang Liu, Xipeng Qiu, and Dragomir Radev. Qmsum: A new benchmark for query-based multi-domain meeting summarization, 2021. URL https:////////m... //arxivv. orgg /abs/ 2104. 05938.
13

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 EXTENDED LONGBENCH FOR LLAMA-3-8BB 3-88---SS--STCTT
Table 4: Generation length for all tasks on LongBench evaluation.
Method (Kj/Tas
Single-Doc QA
Mulri-Doc QA
Summarization
Few-shot
Retrieval
Code Completion
MFQA
NnvQA
Qusp
2Wiki
HorQA
GovRep
QSum
TriQQA
PRe
RB
LCC
Avg
Gen Length (Tokens)
64
128
128
32
512
512
32
64
64
145
Table 5: Performance comparison on eleven LongBench datasets evaluating single/multi-documen QA, summarization, retrieval tasks, and coding completion using 1048k. TidalDecode outperforms Quest at 4096 token budget and achieves an average score higher than full-weight attention. The maximum F1-sco Fl-score for each task is in bold. Compared to Table 3, this table includes more results from summarization task (GovReport), coding tasks (RepoBench (RB) and LCC), and updated overall average scores.
Method (KYTask
Single-Doc QA
Multi-Doc QA
Summarization
Fow-shot
Retrieval
Code Completion
MFQA
NriQA
Qasp
Wiki
HoiQA
GovRep
QSum
TrivQA
PRe
RB
LCC
Avg
Full
30.76
5.52
14.56
13.32
11.50
16.77
19:43
86.56
77.00
43.97
44.88
33.11
Quest
(1024)
26.21
12.19
12.61
10.75
15.89
19.56
63,84
49.43
49.66
TD+L13
(1024)
28.57
7.63
11.11
13,56
9.82
16.41
20.37
79.78
75.17
43.29
40.67
31.49
Quest
(4096)
28.92
3.74
13.63
12.83
12.15
16.71
19.36
85.91
72.50
43.87
43.84
32.13
ID+L13 (4096)
30.94
6.19
13.85
14.40
13.71
16.78
19.48
86.30
78.00
44.54
44.27
33.50
In Table 5, TidalDecode still achieves the highest score on added summarization task GovReport, where the model generates 512 tokens for each question. For code completion tasks, when selecting top-4096 tokens, TedalDecode outperforms full attention and Quest on RepoBench and stays closely to full attention LCC. Notably, TidalDecode still achieves the highest average score across all eleven tasks.
A.2 LONGBENCH FOR LLAMA-3- 3-BBB--BBB-- 1----------ITTE -N-IRRUTTTT WITH CACHE CORRECTION
Performance of TidaDecode with Cache Correction on LongBench
80
Attention Methods
Full Weight
TD+ (4096)
60
TD+L13+CC18)
TD+L13+CCI4)
40
20
0
MFQA
NrtQA
Qasp
2Wiki
HotQA
QMSm
TrQA
PRe
Tasks
Figure 8: Cache correction (CC) is applied to TidalDecode for every 4/8 decoding steps following the description in Section 3.2, where perform forward pass with full attention generated tokens from the last correction to correct the polluted tokens in the KV cache. We measured the performance of Decode with cache correction the same eight tasks in Table 3 and compare that to full attention and basic TidalDecode with the same reselection layer (L13) and token budget (4096).
As illustrated in Figure 8, incorporating cache correction enhances the performance of the baseline TidalDecode (TD+L13+4096) across the same tasks in Table 3. Specifically, cache correction with a stride of 4 improves performance in five out of eight tasks, while stride of 8 yields improvements
14

---

Published as a conference paper at ICLR 2025
in six out of eight tasks. These results highlight the efficacy of cache correction in mitigating the adverse effects of polluted KV representations, which stem from sparse attention mechanisms and accumulate enrors ultimately degrading model performance. Furthermore, Table 4, the tasks evaluated exhibit a wide range of generated sequence lengths, from 32 tokens the single-document QA task HotQA 512 tokens in the summarization task QMSm. The consistent improvements observed across this spectrum of sequence lengths underscore the robustness and generalizability of cache correction in various tasks.
shown in
A.3 LONGBENCH FOR LLAMA 3. 1-88-188----- ----ISTUUCTT
Table 6: Performance comparison on eight LongBench datasets evaluating single/multi-documenl QA, summarization, and retrieval tasks using Llama-3.1 1.---a--..BBI-stttree The maximum Fi-score for each task is in bold.
Method
MFQA
NrtQA
Qasp
2Wiki
HotQA
QSm
TrQA
Pre
Avg
Full
27.02
25.59
13.05
16.64
16.86
23.88
91.48
97.67
39.02
Quest (1024)
22.35
14.89
12.44
14.24
14.12
23.86
81.71
95.73
34.92
TD+13 (1024)
23.70
23.25
11.14
13.53
13.72
22.69
92.35
92.15
36.57
Quest (4096)
26.34
21.17
11.99
15.61
16.26
23.61
90.73
96.35
37.76
TD+13 (4096)
25.89
26.29
12.65
16.86
15.94
23.27
90.22
95.47
38.32
TidalDecode and full-weight attention share the maximum scores for all tasks, achieving the best scores in three tasks (NrQA, 2Wiki, and TrQA). TidalDecode significantly outperforms Quest in 4/8 tasks (NrQA, Qasp. 2Wiki, and TrQA) and full-attention 3/8 tasks (NrIQA, 2Wiki, and TrQA). For other tasks, stay close to the full attention and also obtains higher average score than Quest.
A.4 END-TO-END EFFICIENCY EVALUATION RESULTS
Table 7: TidalDecode end-to-end efficiency results on LLaMA-2-7B
Full Attention
TidalDecode(ms)
Context Length
(ms)
K=32 K=64 K=128
K=256
K=512
K=1024
K=2048
K=4096
10K
19.22
16.94
17.18
17.15
16.98
16.96
17.32
17.19
17.63
32K
25.71
17.89
17.92
17.64
17.70
17.91
17.97
18.48
18.98
100K
45.70
21.26
21.09
21.38
21.19
21.13
21.38
21.65
22.34
Table 8: Quest end-to-end efficiency results on LLaMA-2-7B
Full Attention (ms)
TidalDecode(ms)
Context Length
K=32 K=64 K=128
K=256
K=512
K=1024
K=2048
K=4096
10K
19.22
20.39
19.86
19.44
19.35
20.18
19,91
20.23
21.09
32K
25.71
20.47
20.85
20.73
21.06
20.62
20.94
21.35
22.11
100K
45.70
24.93
25.18
24.77
24.90
24.84
25.10
25.77
26.17
15

---

Published as a conference paper at ICLR 2025
A.5
KERNEL LATENCY
Full Attention
Token Selection Layer
2.00
Sperse Attention
Quest Attention
Relative Latency
1.50
1.36
1.26
1.32
1.00
1.00
1.00
1.00
0.64
0.57
0.50
0.26
0.11
10K Context
32K Context
100K Context
The breakdown latency results for the full attention, token selection attention, sparse attention, and Quest attention kernels over 10K, 32K, and 100K context length. We use full attention latency reference and report other kernels' relative latency ratio. We use token budget of K=512 for TecadDecode and Quest across evaluations.
Figure 9:
In Figure 9, further break down the latency comparison for different attention modules to show why TidalDecode can bring significant speed-up consistently. We compare different attention modules, namely, the full attention layer, the token selection layer, TidalDecode's sparse attention layer, and the Quest attention layer over the 10K. 32K, and 100K context length. We can observe that, TidalDecode's sparse attention kernel can directly reuse previous token patterns, it completely removes the important token estimation overhead the Quest attention kernel, resulting in up 3.36x speed-up compared with the Quest implementation. On the other hand, even though TidalDecode's 's token selection layer has slightly higher latency, we only have two token selection layers even in the 70B LLaMA model that has 64 layers total.
16

---

Published as a conference paper at ICLR 2025
A.6 FULL SENSITIVITY STUDIES ON DIFFERENT TOKEN RE-SETCNIION LAYER
Table Sensitivity study of re-selection layer (RL. on 10K-context-length Needle-in-the-Hann -ayttea test for 1.AMA--322-B-Innttuu with TidalDecode. The best accuracy for each token budget (K) is in bold.
RL/K
32
64
128
256
512
TidalDecode+L2
2%
12%
14%
16%
30%
TidalDecode+L3
2%
6%
8%
10%
24%
TidalDecode+1A4
6%
14%
16%
20%
28%
1idalDeccode+1.5
2%
10%
22%
26%
36%
TidalDecodc+L6
18%
26%
26%
32%
46%
TidalDecodc+17
6%
10%
16%
18%
28%
TidalDecode++88
20%
20%
46%
60%
84%
TidalDecode+19
6%
12%
32%
58%
66%
TidalDeccod++110
44%
58%
50%
60%
64%
TdaalDecode+1111
4%
12%
16%
22%
28%
TidalDeccod=+1112
50% %
96
98%
98%
TidalDecoodc+113
42%
80%
94%
98% %
100 %
TidalDecodc++14
28% %
44%
54%
60%
72%
11d5
2%
8%
16%
22%
36%
TidalDeccde+L116
4%
16%
12%
22%
34%
1idalDeccoe+111
2%
6%
16%
20%
32%
TidalDecod++1118
2%
10%
12%
18%
28%
1
2%
6%
10%
18%
32%
TddlDeccole+1200
6%
10%
12%
18%
24%
TddlDDecode+121
6%
8%
10%
16%
26%
T'dalDDecode+1122
6%
0%
12%
12%
26%
T'dalDeecode+1.23
14%
14%
18%
26%
TidalDecode+124
2%
10%
16%
20%
28%
TidalDecodc+L25
4%
8%
14%
16%
22%
TidalDecode+L26
2%
10%
10%
22%
26%
TedalDecod++227
0%
10%
12%
22%
26%
Quest
46%
56%
72%
88%
96%
17

---

Published as a conference paper at ICLR 2025
Table 10: Sensitivity study of re-selection layer (RL) 10K-context-length Needle-n--the-Haastac test for LLaMA-3.1 1-----IInsttuc with TidalDecode. The best accuracy for each token budget (K) is in bold. Layer 13 and Layer 14 are the best two re-selection layers for accuracy.
RL/K
32
64
128
256
TidalDecode+L.
36%
38%
46%
58%
L3
8%
10%
14%
34%
T
0%
10%
16%
34%
15
14%
30%
52%
52%
T
8%
12%
28%
40%
TidalDecode+L7
6%
10%
10%
18%
34%
44%
50%
66%
TddllDecode++L99
64%
78%
82%
90%
TidalDecode++1100
56%
74%
84%
94%
I1dalDecodc+111
52%
76%
82%
86%
12dalDecode+L112
8%
10%
28%
40%
13dalDecode+L113
100
100%
100%
100%
TidalDecode+L14
98%
100%
100% %
100%
15dalDeccde++1.15
56%
78%
88%
96%
16dalDeccod++1.16
18%
46%
54%
72%
TidalDeccoe++1.17
64%
74%
86%
98%
TidalDecode+L18
64%
70%
74%
84%
TidalDecodc++119
58%
50%
60%
68%
TidalDecode+11220
68%
60%
62%
76%
TidalDecode+1211
40%
48%
48%
62%
TidalDecode+1.22
28%
38%
46%
56%
1:da
40%
46%
52%
64%
TidalDecodc++124
30%
46%
54%
66%
TidalDecodc+1225
40%
54%
50%
66%
T6dalDeccod++1266
34%
48%
62%
64%
TidalDeccod++1.27
38%
50%
54%
70%
TidalDecode+1128
30%
40%
56%
58%
TidalDecode+L229
32%
48%
56%
68%
TidalDecode+L330
36%
48%
52%
70%
TidalDecode+L31
30%
36%
42%
56%
18

---

Published as a conference paper at ICLR 2025
Table 11: Sensitivity study of re-selection layer (RL) on 10K-context-length Reedle-intthe-Hasttee test for LLaMA-3-70B-IInsrucc
1048k; we first run top_k 512 and filter out those layers that do not achieve full accuracy with TidalDecode. The best accuracy for each token budget (K) is in bold. Layer 14 and Layer 31 are the best two Re-selection layers for accuracy.
RL/
32
64
128
256
512
RL/K
32
64
128
256
512
L2
6%
L33
50%
87%
90%
93%
100%
L3
37%
L34
97%
L4
23% L35
70%
83%
100 %
100 %
100% %
L5
63% L36
50%
83%
97%
97%
100 %
L6
70% L37
90%
L7
90% L38
37%
83%
83%
80%
100%
L8
70% 1.39
87%
1.9
30% 1.40
50%
L10
83% 1.41
97%
LII
70% L42
53%
L12
63% L43
67%
L13
50% L44
83%
L14
87%
93%
100%
100%
100% L45
70%
L15
97% 1.46
63%
L16
63% 1.47
77%
L17
87% 1.48
97%
L18
50%
70%
83%
97%
100% L49
77%
L19
93% L50
70%
L20
87% L.51
93%
L21
53%
80%
93%
97%
100% L.52
77%
L22
97% L.53
70%
L23
53%
93%
97%
100%
100% L,54
60%
L24
33%
60%
77%
93%
100% L.55
53%
L25
80% L56
87%
L26
87% L.57
57%
L.27
50%
87%
93%
93%
100% L.58
50%
L,28
80%
83%
93%
87%
100% L.59
50%
L29
97% L60
57%
L30
33%
67%
80%
90%
100% L61
30%
L31
90
97 %
100%
100%
100% L62
43%
L32
27%
73%
80%
97%
100% L63
43%
19

---

Published as a conference paper at ICLR 2025
Table 12: Sensitivity study of re-selection layer (RL) 10K-context-length Needle-in-the-Haastee test for Jamaa-3-8B-Instrut---ii budget (K) is in bold. Layer Layer 13, and Layer 14 are the best three re-selection layers for accuracy.
1048k with TidalDecode. The best accuracy for each token
RL/K
16
32
64
128
256
512
TidalDecode+L2
78%
84%
76%
94%
88%
98%
TidalDecode+L3
0%
6%
10%
16%
28%
64%
T
2%
10%
16%
28%
68%
84%
10%
12%
32%
52%
72%
80%
TidalDecode+L6
4%
6%
10%
14%
16%
24%
TidalDecode+L7
2%
10%
10%
10%
14%
28%
TidalDecode+1_8
26%
64%
80%
90%
92%
96%
1ddllDeccde+119
52%
90%
96%
100 %
98%
100 %
TidalDecode+110
72%
76%
86%
94%
96%
100 %
IidalDecode+L11
56%
74%
94%
100 %
98%
98%
TidalDecode+L12
8%
14%
22%
44%
66%
94%
11
92 %
92
96 %
100 %
100% %
100%
11dalDccole+114
74%
68%
88%
98%
100 %
100 %
15dalDeccod++1115
74%
94%
92%
88%
100
100 %
16da
44%
50%
72%
66%
82%
94%
TidalDecode+L11
42%
60%
74%
82%
96%
96%
TidalDecooe++118
60%
72%
74%
74%
88%
98%
19dalDecode+1119
58%
74%
82%
84%
98 %
96%
TidalDecode+1120
64%
74%
96 %
78%
90%
98%
TidalDecode+1121
10%
38%
60%
66%
90%
94%
TidalDeccod++1222
60%
70%
68%
72%
82%
98%
TidalDecodd++1223
58%
78%
70%
86%
88%
98%
TidalDecodd++224
62%
58%
76%
70%
78%
92%
TidalDecode+1225
66%
86%
84%
82%
92%
100 %
T6dalDecode+1126
54%
64%
66%
80%
90%
94%
TidalDecode+1127
84%
80%
94%
96%
88%
100 %
TidalDecode+1288
66%
66%
76%
84%
94%
94%
TidalDccod++1299
72%
80%
88%
80%
90%
96%
TidalDecode+L330
80%
90%
86%
88%
96%
100
TidalDecode+L31
74%
90%
88%
84%
90%
96%
20

---

Published as a conference paper at ICLR 2025
Table 13: Sensitivity study of re-selection layer (RL) on 3k-context-length Needle-in-the-Hayyeee with TidalDecode. The best accuracy for each token budget (K) is in
test for LongChat-7b-vl.5-2 bold. Layer 7 serves the best re-selection layer for accuracy.
RL/K
32
64
128
256
TidalDecode+12
2%
2%
6%
54%
L
10%
52%
67%
78%
L
4%
36%
65%
76%
15
17%
87%
94%
99%
1odalDecode+16
70%
96%
99%
99%
TidaDDccod++17
80 %
98%
100% %
100%
TddalDecode+1..8
58%
82%
96%
96%
1
7%
31%
59%
71%
10d1
16%
59%
71%
78%
1IdalDecode+111
34%
61%
68%
77%
TrdalDecode+L12
17%
32%
53%
77%
1
5%
10%
28%
48%
T
24%
41%
57%
64%
15dalDecode+L115
37%
47%
62%
69%
16dalDeccoe++1.16
16%
24%
28%
46%
TidalDecode+11117
4%
4%
10%
34%
TidalDecod++L18
2%
3%
8%
15%
TidalDecod++L19
0%
1 1%
7%
19%
10dalDecode+1120
0%
3%
6%
20%
TidalDecode+L211
0%
2%
10%
19%
TidalDecode+1222
0%
4%
4%
18%
1:
0%
2%
5 5%
13%
TidalDecode+124
0%
2%
6%
21%
L5d
0%
2%
7%
16%
0%
1 1%
7%
19%
1:d1
0%
2%
4%
21% %
TidalDecode+1128
1%
2%
10%
17%
TidalDecode+L29
0%
3%
7%
16%
TidalDecode+L30
1%
1 1%
9%
15%
11dalDecode+L31
1%
2%
5%
16%
21

---

Published as a conference paper at ICLR 2025
Table 14: Sensitivity study of re-selection layer (RL) on 3k-context-length Needle-in-the-Haysee with TidalDecode. The best accuracy for each token budget (K) is in
test for Yam-Llama-2-7b- bold. Layer 7 serves the best re-selection layer for accuracy.
RLKK
32
64
128
256
512
TidalDecode+L2
0%
0%
0%
3%
25%
L
11%
26%
39%
65%
85%
TidalDecode+LA
5%
17%
34%
60%
92%
T5d5
16%
42%
65%
87%
96%
TidalDecode+16
73%
83%
89%
95%
100%
TidalDexodd++17
73%
95%
98% %
98 %
100%
TidalDeccode+1..8
87 %
92%
97%
94%
99%
TidalDecode++1.9
11
43%
60%
95%
1odalDeccde++110
12%
31%
58%
69%
93%
I1
20%
21%
46%
68%
97%
TddalDecode++11
2%
15%
28%
51%
92%
TidalDecode+L13
4%
5%
20%
34%
88%
TidalDecode+114
16%
20%
49%
53%
91%
TidalDeccode+1115
2%
25%
44%
56%
90%
16
10%
13%
21%
43%
86%
TidalDeccod++1.17
3%
4%
9%
16%
85%
TidalDecode+L188
0%
1%
2%
15%
84%
TidalDecoot++119
0%
2%
3%
7%
80%
TddalDeccode+1120
0%
2%
0%
7%
79%
TidalDecode+1221
0%
0%
%%
5%
77%
TidalDeccod++1.22
0%
0%
76%
T2dalDeccod=+1223
0%
0%
1%
7%
74%
TidalDecode++24
0%
2%
0%
9%
73%
TidalDecode+1225
0%
0%
2%
10%
71%
TidalDecode++226
0%
1%
1 1%
5%
70%
TidalDeccode+1227
0%
1%
3%
8%
68%
TidalDecode+L.22
0%
1%
0%
9%
67%
TidalDecode+L229
0%
0%
2%
8%
65%
TidalDecode+L330
0%
1%
1 1%
8%
64%
T
0%
0%
2%
10%
62%
22


Reviews:
[{"review_id": "F3ik6hnyuT", "reviewer": "Reviewer_oNeu", "summary": "This paper introduces TidalAttention, which uses a layer-wise selection approach to choose the top-k keys and values needed in top-k attention, thereby reducing the amount of KV cache requiring I/O.", "questions": "see cons.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The advantages of this paper are as follows:\n\n1) The logic is very clear, and the writing is well-structured. The figures and captions are precise, making it easy for readers to quickly understand.\n\n\n2) The focus of the paper is excellent, and I completely agree with it. Particularly with group query attention, KV cache storage is no longer a major issue; instead, the I/O for the KV cache in attention deserves attention. And I really like the mechanism cache correction.\n\n\n3) Most of the experiments are solid, although there is room for improvement. And the cuda kernel is good.", "weaknesses": "I think the paper has the following limitations or raises some questions for me:\n\n1) I believe there may be an issue with the dataset selection in the experiments. Since the authors’ method retains the full KV cache as opposed to KV cache eviction, it would be best to evaluate on datasets with longer outputs. If the dataset only outputs one token, as in NIAH, there should be no difference between eviction-based and selection-based sparse methods, which doesn't highlight the importance of maintaining the full KV cache. Additionally, some QA datasets in LongBench also have this issue. I recommend that the authors supplement more summarization datasets from LongBench (such as gov_report) and code completion datasets (like LCC and repo-bench).\n\n\n2) The authors claim that their kernel stores dot product instead of attn score, so I just wondering how this method works for group query attention. How can the authors decrease the IO of gqa if the queries in the same group with different top-k?\n\n\n3) The authors’ description of Quest is not very clear, and it would be beneficial to add citations for previous baselines in the tables.", "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": "xZavzAXMED", "reviewer": "Reviewer_9wNX", "summary": "The paper introduce a decoding method for sparse attention with pre-selected tokens. The method essentially performs full attention at lower layers and sparse selective attention at the upper layers to obtain the selected tokens, and then full-attention on reduced sets of tokens in the highest layers. The paper presents experiments to show that TidalDecode is competitive to full attention decoding while reducing latency.", "questions": "NA", "limitations": "", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper presents an optimization strategy to improve speed and latency by recognizing that the selected tokens in sparse attention remain consistent across layers, so that the selection process may only need to happen in lower layers.\n- The paper presents evaluation to show the method is competitive to some baselines on latency evaluation", "weaknesses": "- The writing and presentation of the paper significantly need improvement. There are too much unnecessary underlined texts.\n- The motivation and introduction are written unclearly, with too much irrelevant introductional texts.\n- The preliminary and methodology are written in confusing ways. There is a need to put clearer definition and better writing. \n\nGenerally, I would lean towards acceptance if the paper is revised thoroughly.", "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": "KDpUhQ3MWp", "reviewer": "Reviewer_oUXc", "summary": "This article introduces a new sparse attention mechanism, TidalDecode, which is an efficient selection-based attention computing mechanism for the second stage of LLM inference, specifically the decoding stage. The authors discovered through empirical experiments that there is a significant overlap among the Top-K tokens in the attention scores between consecutive Transformer layers. Thus, they propose performing full attention computation only in the initial and intermediate layers, while the other layers select the most relevant KV-cache to compute attention, achieving an efficient sparse attention mechanism. Experimental results across diverse LLMs and tasks demonstrate significant improvements in both decoding latency and the quality of generated results. The optimal choice of the token re-selection layer is consistent across different tasks if the model belongs to the same model family.", "questions": "1.Building on Weakness 1, an adaptive layer selection strategy seems necessary. Did the authors explore any strategies in this regard?\n2.I am quite curious about the actual application effects of KV Cache Correction. Were corresponding experimental validations conducted?\n3.In Table 3, it is interesting to note that on certain datasets like HotQA, the sparse attention mechanism sometimes outperforms the full attention mechanism. Is there a relevant explanation for this, or an empirical rationale behind it?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The article is written in a clear and comprehensible way, with strong consistency across empirical experiments, motivation, methodology, and the effectiveness of the proposed method.\n2.The method is simple yet effective, supported by extensive experimental and theoretical validations. A wide range of diverse experiments, including multiple LLMs and tasks, demonstrates the excellent performance of the proposed method.", "weaknesses": "1.The chosen token across different tasks for the same model family is almost consistent; however, the dramatic variation in performance between L12 and L13 in Table 7 presents a significant challenge for the method's generalization across different models and datasets. This variability could lead to catastrophic results when generalizing to other datasets.\n2.Regarding Figure 2a, the overlap results do not seem significant based solely on the visual representation. Please provide a detailed explanation of the information that can be interpreted from the figure.", "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": "hhj8XryNHN", "reviewer": "Reviewer_mweX", "summary": "The paper presents TidalDecode to enhance the efficiency and accuracy of large language models (LLMs) through position persistent sparse attention. TidalDecode introduces token selection layers to identify and retain the most relevant tokens, with other layers using sparse attention to manage memory and reduce computational demands. Empirical evaluations indicate that TidalDecode can achieve up to a 2.1× reduction in latency while maintaining comparable generative performance to full attention mechanisms.", "questions": "Please see weaknesses", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The proposed method is effective, maintaining the advantages of both eviction and selection-based sparse attention methods according to experiments.\nThe paper presents robust evaluations across various LLMs and tasks, including LongBench and Needle-in-the-Haystack tests. Results indicate that TidalDecode consistently performs well compared to state-of-the-art methods.", "weaknesses": "1. Definition of `spatial coherence`. The spatial coherence seems just come from nowhere. I can mostly understand it refers to the consecutive layers have significant attention overlaps. But there is not a `scientific definition` in this paper.\n2. Complexity of Implementation: TidalDecode's reliance on custom GPU kernels and specific layer configurations could limit its accessibility and adoption. Please provide pseudo code or GPU consumption data, it could make the results more clear.\n3. The proposed method can be considered as a kind of hierarchical attention, more related baselines can be included. such as [1,2]\n4. KV-cache correction seems to be crucial, no ablation study (or I just missed). Please provide the results without KV-cache correction.\n5. training details, e.g, learning rate, training tokens, GPU hours, etc. It would help the reproduction.\n6. Does `L` matter in different models? How to determine the optimal hyper-parameters. It would be appreciated if automatic prediction of `L` or a guideline for `L` selection across different model size, model architecture, etc.\n7. There might be some conflicts in the packages used in latex.\n\n[1] Chalkidis, Ilias, et al. \"An exploration of hierarchical attention transformers for efficient long document classification.\" arXiv preprint arXiv:2210.05529 (2022).\n[2] Yang, Zichao, et al. \"Hierarchical attention networks for document classification.\" Proceedings of the 2016 conference of the North American chapter of the association for computational linguistics: human language technologies. 2016.", "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)