TokenSwift: Lossless Acceleration of Ultra Long Sequence Generation
Authors: Tong Wu
Junzhe Shen
Zixia Jia
Yuxuan Wang
Zilong Zheng
Venue: ICML 2025 poster (2025)
Keywords: Large Language Models
Lossless Acceleration
Ultra-Long Sequence Generation
Primary area: deep_learning->large_language_models

Abstract: Generating ultra-long sequences with large language models (LLMs) has become increasingly crucial but remains a highly time-intensive task, particularly for sequences up to 100K tokens. While traditional speculative decoding methods exist, simply extending their generation limits fails to accelerate the process and can be detrimental. Through an in-depth analysis, we identify three major challenges hindering efficient generation: frequent model reloading, dynamic key-value (KV) management and repetitive generation. To address these issues, we introduce TokenSwift, a novel framework designed to substantially accelerate the generation process of ultra-long sequences while maintaining the target model’s inherent quality. Experimental results demonstrate that TokenSwift achieves over $3 \times$ speedup across models of varying scales (1.5B, 7B, 8B, 14B) and architectures (MHA, GQA). This acceleration translates to hours of time savings for ultra-long sequence generation, establishing TokenSwift as a scalable and effective solution at unprecedented lengths.

TokenSwift: Lossless Acceleration of Ultra Long Sequence Generation
Tong Wu Junzhe Shen
Zixia Jia"
Yuxuan Wang'
Zilong Zheng'
Abstract
100000
TakenSwift 100K tokens
100k hours
Generating ultra-long sequences with large lan- guage models (LLMs) has become increasingly crucial but remains highly time-intensive task, particularly for sequences up to 100K tokens. While traditional speculative decoding methods exist, simply extending their generation limits fails to accelerate
TakitSwit
80000
Fast Generatiog
[TacenSwiff
Generation
Generated
40000
20000
process and can be detri- mental. Through an in-depth analysis, iden- tify three major challenges hindering efficient generation: frequent model reloading, dynamic key-value (KV) management and repetitive gen- eration. To address these issues, we introduce TOKENSWIFT, a novel framework designed to substantially accelcrate the generation process of ultra-long sequences while maintaining the tar- get model's 's inherent quality. Experimental results demonstrate that TOKEN achieves over 3 speedup across models of varying scales (1.5B, 7B, 8B, 14B) and architectures (MHA, GQA). This acceleration translates to hours of time sav- ings for ultra-long sequence generation, establish- ing TOKENSWIFT as a scalable and effective so- lution unprecedented lengths.
100
1.50
200
250 300
Time (minutes)
Figure 1. Comparison of the time taken to generate 100K tokens using autoregressive (AR) and TOKENSWIFT with prefix length of 4096 on LLaMA3. 1-8b. As seen, TOKENS WIFT accelerates the AR process from nearly 5 hours to just 90 minutes.
However, critical challenge impeding the practical deploy- ment of such applications is the extensive time required to produce ultra-long sequences. For instance, generating 100K tokens with LLaMA3.1-83 can take approximately five hours (Figure 1), duration that is impractically long for the development of sophisticated applications, let alone recent gigantic models such as LLaMA3.
(AI@ Meta, 2024) and DeepSeek-61 -6 IB (Liu et al., 2024a). Addressing this bottleneck is essential for harnessing the full potential of LLMs real-world scenarios.
A straightforward solution is to take advantage of recent suc- cess in speculative decoding (SD) (Leviathan et al., 2023; Chen al., 2023), which employs a draft-then-verify strat- egy expedite generation while preserving lossless accu- racy; see Appendix A and Section 5.1 for detailed back- ground and relevant literature. However, these methods are generally tailored for generating short sequences, e.g., Tri- Force (Sun et al., 2024a) and MagicDec (Chen et al., 2024a) are limited to generating 256 and 64 tokens, respectively. Directly extending their generation length to 100K tokens would inevitably encounter failures due KV cache budget constraints. Furthermore, even when applied optimized KV cache architectures such Group Query Attention (GQA), these methods yield only marginal acceleration gains for short-sequence generation, as evidenced in Ta- bles 1 and 3. This observation leads to a pivotal research question:
1. Introduction
Recent advances in large language models (LLMs), am- plified by their long context capacities (Wu et al., 2024; Ding et al., 2024), have demonstrated remarkable profi- ciency in intricate reasoning (Jaech et al., 2024; Guo et al., 2025), agentic thinking (Shinn et al., 2023; Yao al., 2023;
Li al., 2024a), and creative writing (Wang al., 2023; Mikhaylovskiy, 2023), etc. These advancements necessitate the ability to generate lengthy sequences, e.g., ol-like (Jaech et al., 2024) reasoning tends to generate protracted chain- of-thought trajectories before reaching final conclusions.
'Equal contribution 'State Key Laboratory of General Artifi- cial Intelligence, BIGAI, Beijing, China 'LUMIA Lab, Shang- hai Jiao Tong University. Correspondence to: Zilong Zheng <zizheng@ bigai.ai>.
Is it possible to achieve model-agnostic lossless accelera- tions, akin to those seen in short-sequence SDs, for generat- ing ultra-long sequences, with minimal training overhead?
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Lossless Acceleration of Ultra Long Sequence Generation
Multi-token Parallel Self-Drafting
Parallel Verification
Tree-base Attention
Candidates
LLM
is
LLM
He.
with
FFN
Sample
the
is the unele of is the uncle 'n is good to the father is the mother of
Partial KV Cache
with
sequence
ultra long
PFN
Contex tual Penality
uncle
cs
good
with
Longest Valid
[...] He
is the
PPN
In
Full
father of
Cache
Dynamic KV Budget
Token R Reutilization
First [S] KV Select
KV
row id
R-gram
frequency
Top-k
Importance
97475
is the father of is the mother of 2
5
Frozen
97476
Update n-gram
Tuned
Figure 2. Illustration of TOKENSWIFT Framework. First, target model (LLM) with partial KV cache and three linear layers outputs 4
logits in single forward pass. Tree-based attention then applied construct candidate tokens. Secondly, top-k candidate 4-grams retrieved accordingly. These candidates compose draft tokens, which are fed into the LLM with full KV cache to generate target tokens. The verification is performed hy checking if draft tokens match exactly with target tokens (Algorithm 1). Finally, we randomly select of the longest valid draft tokens, and update n-gram table and KV cache accordingly.
To answer this question, we conduct an in-depth analysis ($2) and identify three key challenges: (1) frequent model reloading: frequently reloading model for each token genera- tion introduces a significant delay, primarily due to memory access times rather than computation.
ing significant superiority over enhanced baselines.
2. TOKENSWIFT consistently achieves over 3 speedup compared to AR across varying prefix lengths, model architectures, and model scales in generating 100K to- kens, reducing the AR process from nearly 5 hours to 90 minutes on LLaMAA. 1-8b.
(2) Prolonged Grow- ing of KV Cache, the dynamic management of key-value (KV) pairs, which grow with the sequence length, adds complexity in maintaining model efficiency. (3) repetitive content generation, the issue of repetitive generation be- comes more pronounced as the sequence length increases, leading to degraded output quality.
3. TOKENSWIFT achieves progressively higher speedup compared AR as the generation length increases, while enhancing diversity in ultra-long sequence generation (as measured by Distinct-n (Li et al., 2016)).
Building on these insights, introduce our framework To- KENSWIFT, which utilizes n-gram retrieval and dynamic KV cache updates to accelerate ultra-long sequence gener- ation. Specifically, we employ multi-token generation and token reutilization to enable the LLM (i.e. target model) to draft multiple tokens a single forward pass, alleviating the first challenge of frequent model reloading ($3.2). As the generation progresses, we dynamically update the partial KV cache at each iteration, reducing the KV cache loading time ($3.3). Finally, to mitigate the issue of repetitive out- puts, we apply contextual penally to constrain the generation process, ensuring the diversity of output ($3.4).
2. Challenges
Accelerating long sequence generation is nevertheless a non- trivial task, even built upon prior success in speculative de- coding (SD). In this section, we identify critical challenges encountered in accelerating ultra-long sequence generation.
Challenge I: Frequent Model Reloading One fundamen- tal speed obstacle lies in the autoregressive (AR) generation scheme of L.M. For each token, the entire model must be loaded from GPU's storage unit the computing unit (Yuan et al., 2024), which takes significantly more time than the rel- atively small amount of computation performed (as shown in Table 2). Consequently, the primary bottleneck in generation stems from I/O memory access rather than computation.
In $4, we conduct extensive experiments to evaluate To- KENSWIFT across different model scales and architectures. In summary, we highlight our advantages as:
D When generating ultra-long sequence, such as 100K to- kens, the GPU must reload the model weights over 100,000 times. This repetitive process poses the challenge: How can we reduce the frequency of model reloading?
1. To the best of our knowledge, TOKENSWIFT is the first to accelerate ultra-long sequence generation up to 100K with lossless accuracy of target LLMs, while demonstrat-
2

---

Lossless Acceleration of Ultra Long Sequence Generation
Table 1. Experimental results of TriForce (Sun et al., 2024a) and MagicDee (Chen et al., 2024a) with default parameters on LLaMA3. 1-.b. The Batch Size of MagicDec is set to 1. The results on A100-80G and PG-19 using identical hyperparameters. The only difference is that their original experiments con- ducted on YaRN- L.A.NN--.MM2222-2 100-A227--12888 (MHA), while ours used
3.1. Overview
The overall framework is depicted in Figure 2. To- KENSWIFT generate a sequence of draft tokens with self- drafting, which are then passed to the target (full) model for validation using tree-based attention mechanism (See Appendix E for more tree-based attention details). This pro- cess ensures that the final generated output aligns with the target model's predictions, effectively achieving lossless acceleration.
LLaMA3. 1-8b (GQA).
Method
Gen. Len.
Draft Form
Speed Up
TriForce
256
Standalone Draft
1.02
Self-Speculation
1.20
TOKENSWIFT is lightweight because the draft model is the target model itself with a partial KV cache. This eliminates the need to train a separate draft LLM; instead, only y lin- ear layers need to be trained, where y + 1 represents the number of logits predicted in single forward pass. In ad- dition, during the verification process, once we obtain the target tokens from the target model with full KV cache, we directly compare draft tokens with target tokens sequentially to ensure that the process is lossless (He et al., 2024).
MagicDec
64
Standalone Draft
1.06
Table 2. Taking NVIDIA A100 80G and LLaMAB3 1-bb exam- plc, MAX refers to the scenario with a maximum context window 128K. The calculation method is from Yuan et al. (2024).
MEMORY
COMPUTATION
Bandwidth: 2.04e12 B/s
BFI6: 312e12 FLOPS MAX Operations: 83.9 GB
Model Weights: 15.0 GB
Loading Time: 7.4 ms
MAX Computing Time: 0.3 ms
3.2. Multi-token Generation and Token Reutilization
Challenge II: Prolonged Growing of KV Cache Previ- ous studies, such as TriForce (Sun et al., 2024a) and Mag- ieDec (Chen et al., 2024a) have demonstrated that, small KV cache budget can be used during the drafting phase to reduce the time increase caused by the loading enormous KV cache. While their one-time time compression strategy at the prefill stage can handle scenarios with long prefixes and short outputs, it fails to address cases involving ultra-long outputs, as the growing size of KV cache would far exceed the allocated length budget.
Multi-token Self-Drafting Inspired by Medusa (Cai et al., 2024), we enable the LLM to generate multiple draft tokens in a single forward pass by incorporating 7 additional linear layers. However, we empirically note that the additional linear layers should not be independent of each other. Specifically, we propose the following structure:
hi - fiha)) + ha, he f2(b)) + hi, hs - fa(h2) + ha, (I) lo 4, l,, la g(ho), g(hi), a(h2), g(ha),
where ho denotes the last hidden state of LLM, fa() repre- sents the i-th linear layer, h4 refers to the i-th hidden repre- sentation, g() represents the LM Head of target model, and I, denotes output logits. This structure aligns more closely with the AR nature of the model. Moreover, this adjustment incurs no additional computational cost.
>> To dynamically manage partial KV cache within limited budget during ultra-long sequence generation, the challenge lies in determining when and how to dynamically update the KV cache.
Challenge III: Repetitive Content Generation The de- generation of AR in text generation tasks - characterized by output text that is bland, incoherent, or gets stuck in repetitive loops - is a widely studied challenge (Holtzman et al., 2020; Nguyen et al., 2024; Hewitt et al., 2022). When generating sequences of considerable length, e,g., 100K, the model tends to produce repetitive sentences (Figure 5).
Token Reutilization Given the relatively low acceptance rate of using linear layers to generate draft tokens, we pro- pose method named token reutilization to further reduce the frequency of model reloads. The idea behind token re- utilization is that some phrases could appear frequently, and they are likely to reappear in subsequent generations.
>> Since our objective is lossless acceleration and repetition is an inherent problem in LLMs, eliminating this issue is not our focus. However, it is still essential and challenging to mitigate repetition patterns in ultra-long sequences.
Specifically, we maintain a set of tuples ((G, F)), where G = (I 1=.+ I.+n] represents an n n-gram and F denotes its corresponding frequency F within the generated token sequence S = { T1, .... 2 by time step & (f > n).. After obtaining (po...., P3} as described in $3.4, re- trieve the top-k most frequent re-ramm beginning with token arg max Po to serve as additional draft tokens.
3. TOKENSWIFT
To achieve lossless acceleration in generating ultra-long sequences, we propose tailored solutions for each challenge inherent to this process. These solutions are seamlessly inte- grated into a unified framework, Lee. TOKENSWIFF
Although this method can be applied to tasks with long
'The target model itself can also predict one logit, making the total number of logits 7 + 1. We take 7 = 3.
3

---

Lossless Acceleration of Ultra Long Sequence Generation
prefixes, its efficacy is constrained by the limited decoding steps, which reduces the opportunities for accepting n-gram candidates. Additionally, since the long prefix text is not gen- erated by the LLM itself, a distributional discrepancy exists between the generated text and the authentic text (Mitchell et al., 2023). As a result, this method is particularly suitable for generating ultra-long sequences.
Algorithm 1 TOKENSWIFT
Require:
Prompt p, target model M. decoding tree T, re-gram candidate number k; max budget size [B] of partial cache, cache initial size [S].
1: Prefill target model with KV cache Cyaul - Prefillas())
s.t. |Craal = len(p);
2: Prefill partial KV cache Cp
{C [0
[S[], 101sK war Equation (2), where
3.3. Dynamic KV Cache Management
|Cpl = |B];
3: at < - len(p).
Dynamic KV Cache Updates Building upon the findings
4: while st target length do
of Xiao et al. (2024), we preserve the initial |S] KV pairs within the cache during the drafting process, while progres-
5: if (ICrual - e) > |B] - |S| then
6: Dynamic KV Cache Update: Cp - {Crual:
sively evicting less important KV pairs. Specifically, we enforce fixed budget size [B) ensuring that the KV cache at any given time can be represented as:
(1], Iop-K (Crun)) (Cruill-
7:
end if
8: Multi-token Parallel Generation: Get penalized probabil-
ity pes w partial cache Cy.
KV ((Ko. Vol.... (Kpp Visti, (Kis +1 V 11HH)) oi. mi 11m-
9: Tree-based Attention: Construct g groups of candidate
where the first |S| pairs remain fixed, and the pairs from position [S] to [| - are ordered by decreasing importance. As new tokens generated, less important KV pairs are gradually replaced, starting from the least important ones at position [B| - 1 and moving towards position [S]. Once replacements extend beyond the |S] position, we recalculate the importance scores of all preceding tokens and select the most relevant [B] - |S] pairs to reconstruct the cache.
draft tokens (2 1 using decoding tree I and ps:3.
10: Token Reutilization: Select n-gram candidates {
with highest frequency, where dg arg max po ($3.2).
11:
Parallel Verification: Let draft tokens {d') 1 :-
{ Vi o {2'e))]_ and send {d} to M to get penal-
ized verification probabilities {g k==l"
12:
Sample target tokens V -(g")<<)
13:
Random select the longest accepted length of draft tokens
& E [dgm]d's = v 1:=1 by exactly match.
This process consistently preserves the critical information required for ultra-long sequence generation.
14:
Let st + len(y') ): yield: y²
15: Evict Cp to ensure the size of Cp is [B] and update Cyan-
Importance Score of KV pairs We rank the KV pairs based on the importance scores derived from the dot product between the query (Q) and key (K), i.e. QK"
16:
end while
The penalized sampling approach proposed in (Keskar et al., 2019) suggests applying penalty to all generated tokens. However, when generating ultra-long sequences, the set of generated tokens may cover nearly all common words, which limits the ability to sample appropriate tokens. There- fore, we propose an improvement to this method.
In the case of Group Query Attention (GQA), since each K corresponds to group of Q = (Qo.... ..., 11 direct dot-product computation is not feasible. Unlike methods such as SnapKV (Li et al., 2024c), we do not replicate the K. Instead, we partition the Q, as shown in Equation (2):
((+1))g) Σ
Specifically, we introduce fixed penalty window W and apply penalty value 0 to the most recent W tokens, denoted as W, generated up to the current position, as illustrated in Equation (3):
importance score,
Q,KK,
where for position i, Qj in the group Qi are dot-product with the same K, and their results are aggregated to obtain the final importance score. This approach enhances memory saving while preserving the quality of the attention mecha- nism, ensuring that each query effectively utilized without introducing unnecessary redundancy.
exp (l/(tt/t ((,())
P E, exp (L/(t I(L,))) T(I) = l W else 1.0, 0 (1,00),
(3)
where denotes temperature, 4 and p. represent the logit and probability of i-th token. This adjustment aims to maintain diversity while still mitigating repetitive generation.
3.4. Contextual Penalty and Random N-gram Selection
Contextual Penalty To mitigate repetition in generated text, we have explored various sampling strategies. However, with the significantly larger sequence length, the likelihood of repetition increases significantly (62). As a result, we de- cided to apply an additional penalty to the generated tokens to further mitigate repetition.
Random n-gram Selection In our experiments, we ob- serve that the draft tokens provided to the target model for
TThe subscript 3 here denotes tuple with indices 0, 2, The notation will be used similarly hereafter.
4

---

Lossless Acceleration of Ultra Long Sequence Generation
parallel validation often yield multiple valid groups. Build- ing on this observation, we randomly select one valid n- gram to serve as the final output. By leveraging the fact that multiple valid n-grams emerge during verification, we ensure that the final output is both diverse and accurate.
We use Distinct-n (Li et al., 2016) to measure the diversity of generated content, i.e., repetition. A higher value indicates greater diversity and lower repetition (Table 6).
Baselines We compare TOKENSWIFT with two baselines: TriForce The original TriForce (Sun et al., 2024a) em- ploys a static KV update strategy, which cannot accelerate the generation of 100K tokens. The results in Table 3 corre- spond to our improved version of TriForce, which incorpo- rates dynamic KV update 4. Medusa *: To ensure lossless- ness, we adopt the Medusa (Cai et al., 2024) training recipe and incorporate the verification method of TOKENSWIFT. Both Medusa heads and tree structure are consistent with TOKENSWIFT.
In summary, the overall flow of our framework is presented in Algorithm 1.
4. Experiments
In this section, we demonstrate the capability of To- KENSWIFT in accelerating ultra-long sequences generation.
4.1. Setup
We conduct experiments on a variety of models, including
The recent released MagicDec (Chen et al., 2024a) primar- ily focuses on acceleration for large throughput, and when the batch size is 1, LI a.M..... 1-8b does not exhibit any ac- celeration for short text generation, let alone for ultra-long sequences. Therefore, it excluded from our baseline.
(Peng et al., 2024), LLaMA3. 1-8b (AI@Meta, 2024) and Qwen2. (1. 5b, 7b, 1 14b) (Qwen et al., 2025). For all models, we use the Base version, as the output length of Instruct version is limited (Bai et al., 2024). The inference experiments are performed on the test set of PG-19 (Rae et al., 2020).
4.2. Main Results
The experimental results are presented in Table 3 and Ta- ble 4. We evaluate TOKENSWIFT at different generation lengths of 20K, 40K, 60K, 80K and 100K, reporting speedup x and acceptance rate a by taking the average and standard deviation of experiments to avoid randomness. Notably, the results for TOKENS and Medusa* show a balanced trade-off between speed and quality, in contrast to TriForce*, which suffers from low quality due to the absence of any repetition penalty.
Training and Inference Details We train linear layers in Section 3.2 using the first 8K tokens of training data, for datasets longer than 8K tokens, from PG-19 (Rac et al., 2020). The number of extra decoding heads is set to across all models.
Inference is performed on a single NVIDIA 11000SXM4 80GB. When generating 100K tokens, the models pre- filled with 2K, 4K 8K tokens as prompt from random sample of the PG-19 test set (See Appendix F.1 for abla- tion on prefill length). The maximum budget of the partial cache is determined by the length of the prompt. For further training and inference details, please refer to Appendix B.
TOKENSWIFT significantly outperforms all baselines across generation lengths. As shown in Table 3, across all lengths, TOKENSWIFT demonstrates superior acceler- ation performance compared to all baselines on models with different architectures (MHA, GQA). Moreover, To- KENS demonstrates remarkable robustness, showing virtually no impact when tested with varying prefix lengths,
Evaluation Metries We evaluate the overall acceptance rate and speedup for all methods. Unlike Leviathan et al. (2023), our acceptance rate a is defined as:
Longer generations amplify the speedup benefits. As the generation length increases, the speed improvement of To- KENSWIFT becomes increasingly evident. Two key factors drive this trend: Firstly, AR experiences longer KV cache loading times as the number of tokens grows, whereas To- KENSWIFT mitigates this issue by utilizing dynamic KV pruning. Secondly, the acceptance rate improves as the num- ber of tokens increases, primarily due to the higher n-grams acceptance rate. As the n-grams pool composed of gener- ated tokens grows larger, the candidate n-grams become more diverse and accurate (Figure 3).
a2 11+1)x77 X
(4)
where a, represents the number of tokens accepted at the i-th time step, + 1 denotes the number of draft tokens generated at each time step, and T represents the total number of time steps. The speedup is denotes as x, which is the ratio of AR latency to TOKENSWIFT latency, given by:
latency AR
(5)
latency TOKKNSWIF
Larger models yield greater speedup benefits. The im- pact of frequent model reloading varies with model scale,
where latency refers to the average time required to generate a single token.
"To compare with LLaMA3 . 1 1-8b, we pretrained a draft model based on MA33 1-8b. See Appendix C for details.
'The two can be converted into each other through computation.
5

---

Lossless Acceleration of Ultra Long Sequence Generation
Table Experimental results for aLMM and I.LMA3.1 under varying prefix lengths, generating sequences from 20K to 100K tokens. denotes the acceptance rate of all draft tokens (Equation (4)), while represents the speedup ratio relative to AR (Equation (5)), TriForce* refers to our improved version, and Medusa indicates the model we retrained (84.1).
Prefill Len, 2048
Prefill Len. 4096
Prefill Len. 8192
Prefill Len. 2048
Prefil Len. 4096
Prefil Len. 8192
Method
Gen. Len.
YaRN-LLeM12- 1aaaa2--b-a- 7b-12kk (MHA)
SLeM03, 1-0b (GQA)
x(> 1)
x(- 1)
x(> 1)
x(> 1)
x(> 12
x(> 1)
Medusa"
0.43
0.96
0.85
0.40
0.83
0.35
0.39
1.29
0.34
1.21
TriForce*
20K
0.80
1.50
0.89
1,51
0.22
1.36
0.89
1,13
0.89
1.08
0.99
1.16
TOKENSWIFF
0.73a6.0
2.
0.68
2.0
0.64.0.0 os
1.9
0.04
187:007
0.65.007
1.93
0.72g0.00
1.99
Medusa"
0.52
1.08
0.42
0.86
0.43
0.88
0.35
1.26
0.40
1.39
0.34
1.26
TrForee*
40K
0.84
1.64
0.93
1.67
0.96
1.49
0.93
1.18
0.94
0.99
0.99
1.18
WOKENSWIFT
0.82gc.00
g.00
0.79
p.00
0.79
2.00
0.72gs.07
g.19
0.73go.0s
2.47.0.32
0.81.o.30
2.54
Medusa"
0.59
1.18
0.95
0:15
0.91
0.35
0.40
1.42
0.34
ThiForee
60K
0.85
1.76
0.95
1.83
0,97
1.62
0.94
1.21
0.95
0.96
1.00
1.19
TOKENSWIFF
0.87
2.92
0.85
2.89
0.85
2.84
0.75ge.o:
1.73g
0.79_.006
2,88 g0.17
0.85
2.93
Medusa"
0.61
1.17
0.51
0.99
0.47
0.93
0.35
1.30
0.40
1.43
0.34
1.29
TrForce
80K
0.84
1.86
0.95
1.98
0.97
1.74
0.95
1,23
0.95
0.94
1.00
1.21
WOKENSWIFT
0.89
0.88
p.10
0.88
2.05
0.77g0.04
2.96
0.52:0.06
3.13
0.88
2.19
Medusa
0.62
0.99
0.47
0.91
0.35
0.41
1.45
0.34
TriForee
100K
0.82
1.91
0.96
2,14
0,97
1.86
0.95
1.25
0.96
0,92
0.99
1.22
TOKENSWIFT
0,90gs.02
g.25
0.90g..03
g.23
0.90
3.20
0.79ge.03
3.13
0.84g000
3.27
0.90
3.38
Table 4. Experimental results of TOKENSWIFT for Qwen2.5 across different scales under prefix length 4096, generating sequences from 20K 100K tokens. TAR and TroKEsSwUrt denote the actual time required (in minutes) for AR and TOKENSWIFT, respectively. Ar represents the number of minutes saved by TOKENSWIFT compared to AR.
Qwen2.5-1.5B
Owen2.5-7B
Qwen2,5-14BB
Gen. Len.
x(> 1)
TAx
Ay
x(> 1)
Tae
Trousssa
Ar
x(>
Tan
Troussvor
Ay
20K
0.69go.1:
1669
12.00
7.20
-480
0.6420.07
2,00g0.16
15.60
7,80
-7.80
0.6720.00
2.12g0.15
29.40
13.80
-15.60
40K
0.80ga.s
2.312000
36.00
15.60
-20.40
0.7720.05
2.6429.00
47.40
18:00
-29.40
0,7820.0
2.6820.10
89.40
33,60
-55.80
60K
0.852m04 2.69
73.80
27.60
-6..00
0.78
2.86
95.40
33.60
-61.0
0.822000
2.11
184.20
61.20
-123.00
80K
0.87c0.0
2.95+0.00
124.20
42.00
-82.20
0. 0.000.00
3.07
161.40
52.80
-108.60
0.83
3,20
312.60
97.80
-214,80
100K
0.89ga.07
3.13
187.80
60.00
-127.80
0.8220.00
3.23
244.20
75.60
-168.60
0.8420002
3,34
474.60
142.20
-332.40
as larger models require more time due to the increased pa- rameters. As shown in Table 4, TOKENSWIFT demonstrates robust performance across models of different scales, with the acceleration advantage becoming more pronounced for larger models. In particular, when generating 100K tokens, TOKENSWIFT saves up to 5.54 hours for 14B model.
20 201
201
235
42C
66
Ri
10cc
Gen Len.
30
(01
(2-00)
4.3. Ablation Studies
155
We conduct comprehensive ablation studies on To- KENSWIFT using ....MA3.1-0 1b... For all experiments, the prefix length is 4096.
30K
42C
60K
100c
Figure 3. Upper: The acceptance rate a for k = 20 and l: O, along with the n-gram acceptance rate B for k 20, plot- ted against varying generation lengths. Lower: The speedup x achieved at different generation lengths.
4.3. 1. TOKEN REUTILIZATION
This trend stems from the fact that, in ultra-long sequences, the KV cache cannot be compressed indefinitely. In contrast, TOKENS WIFT (k = 20) shows an increasing acceptance rute as the sequence length grows, demonstrating the effec- tiveness of token reutilization in reducing the frequency of model reloading.
We define the n-grum acceptance rate 3 similarly to Equa- tion (4). Let af denote the length of accepted n-gram candi- date at iteration i. Then B is given by: Σx- by (x+1)xx
d/. of
where, by
(6)
0, of < a;
From Figure 3. we observe that removing token reutilization (k = 0) leads to a significant decrease in both acceptance rate a and speedup x. Furthermore, as the generation length increases, the acceptance rate a for k- = 0 slightly drops.
4.3.2. DYNAMIC KV UPDATES
To evaluate the effectiveness of TOKENSWIFT'S dynamic KV update policy, we experiment with three different strate-
6

---

Lossless Acceleration of Ultra Long Sequence Generation
gies of managing KV cache during drafting:
Full Cache: Retaining full KV cache throughout drafting.
focepance
Partial Cache: Updating partial KV cache only once during the prefill phase.
0
10
20
30
50
100
700
500
1050
Dynamic Partial Cache: Dynamically updating KV cache as described in $3.3
3.5
For a fair comparison, token reutilization disabled (i.e. 0). As shown in Table 5, Partial Cache leads to low acceptance rate, resulting in reduced speedup. While Full Cache achieves a higher acceptance rate, its compu- tational overhead negates the speedup gains. In contrast, Dynamic Partial Cache adopted by TOKENSWIFT strikes balanced trade-off, achieving both high acceptance rate and sigmificant speedup. As result, Dynamic Partial Cache can effectively manage partial KV under ultra-long sequence generation.
2.
200
Figure 4. Upper: The acceptance rate a and n-gram acceptance rate 3 versus varying &. Lower: The speedup x versus varying k.
Table 7. Acceptance rate a (k = 0) and speedup x across dif- ferent tree configurations. Each configuration represented by a 4-digit array: they represent the number of candidates for different decoding heads in $3.2.
3,,3,, (Ours)
Gen. Len.
[3, 3,333
[1, 9, 9,
Table The ablation experiment results on KV management.
0.44
0.50
20K
x(>
1.34
0.53
1.56
Gen. Len.
Full Cache
Partial Cache
Dynamic Partial Cache
20K
x(> 1)
a
D.42
1.36
0.19
0.94
0.45
1.56
40K
x 1)
a
0.43
1.58
0.52
0.67
1.75
0.43
40K
x(> 1)
2x
0.42
1.42
0.16
0.43
1.75
x(>
0.43
1.75
0.53
0.78
1.88
0.42
60K
x(> 1)
0.42
1.45
0.18
1.19
0.42
1.88
80K
x(> 1)
80K
4
0.42
0.19
0.42
100K
a
0.42
0.57
0.40
x(>
x(> 1)
1.91
0.96
1.96
0.42
0,21
0.40
100K
x(>
Table 8. Distinct-n score across different penalty value 0. 1.0 in- dicate that no penalty applicd. We take W 1022 (See Ap- pendix F.2 for ablation on W).
Table 6. The ablation experiment results contextual penalty ing different sampling methods. Light cell represents the settings
adopted by ToKENSWIFT. We take 0 = 1.2, W 1024.
0
Distinct-1
Distinct-2
Distinct-3
Distinct-4
AVG.
Distinet-1
Distinct-2
Distinct-3
Distinct-4
AVG.
1.0
0.07
0.11
0.14
0.15
0.12
top-p
0.15
0.25
0.31
0.25
3.42
1.1
0.08
0.13
0.15
0.16
0.13
who penairy
0.09
0.15
0.18
0.20
0.16
3.53
1.2
0.41
0.71
0.81
0.82
0.69
y-samllnn
0.25
0.43
0.49
0.53
0.43
3.42
1.3
0.57
0.86
0,93
0.95
0.83
wào penaity
0.06
0.10
0.12
0.13
0.11
3.57
1.4
0.52
0.73
0.76
0.77
0.70
min-p
0.41
0.71
082
perarfly
1.5
0.74
0,96
0.98
0.99
0.92
4.3.3. CONTEXTUAL PENALTY
quality of ultra-long sequence generation.
As an orthogonal method to min-p, top-p, and sampling for mitigating the repetition, contextual penalty demon- strates effectiveness across different sampling methods.
In addition, we can find that the higher the diversity, the lower the speedup. Therefore, if TriForce combined with context penalty, the speedup in Table 3 will drop further.
As shown in Table 6, without contextual penalty, the di- versity of generated sequences significantly lower for all sampling methods. The most striking improvement emerges in min-p sampling (See Appendix D for more sampling de- tails), where the average Distinct-n score surges from 0. to 0.69 with only an 8% compromise in speedup. These results clearly highlight the impact of contextual penalty in mitigating repetitive token generation. It can seamlessly integrate with existing sampling methods to enhance the
4.4. Discussions
In this section, we explore the effects different hyperpa- rameters TOKENSWIFT.
4.4.1. TREE CONFIGURATION
Due to the mone-connuming nature of finding the optimal tree in Medusa (Cai et al., 2024) and its limited impact on

---

Lossless Acceleration of Ultra Long Sequence Generation
accelerating ultra-long sequences generation, we employ simple 3-ary tree in tree attention, See Appendix B for the tree structure.
sequences. This suggests that higher temperatures result in more diverse but less accurate output. On the other hand, speedup tends to remain relatively stable or slightly decrease with higher temperatures. The highest speedups, reaching around 3.4, are observed across all generation lengths with temperatures around 0.6 and 1.0, indicating that moderate temperature settings offer the best balance between speed and quality.
As shown in Table 7, [1, 9, 9] has the highest accep- tance rate but the lowest speedup. This is because more can- didates increase the acceptance rate, but also increase the verification burden. Similarly, by comparing [1,3, 3, 3, 3] and [3, 3, 3], we can find that the first head (i.e., the original head of target model) achieves relatively high pre- diction accuracy when using KV compression, so choosing the top-1 token as candidate is sufficient. To balance the trade-off of acceptance rate and verification efficiency, we adopt [1, , 3, 3, 3] as the configuration of TOKENSWIFT.
Table 9. Ablation results on varying temperatures. Using top-p sampling, with set to 0.9.
Gen. Len.
0.4
0.6
0.8
1.0
1.2
0.79
0.84
0.56
0.68
0.52
20K
x (>> 1)
2.25
2.34
1.80
2.10
1.72
4.4.2. N-GRAM CANDIDATES
0.85
0.88
0.73
0.81
0.69
As illustrated in Figure 4, increasing i enhances the n-gram acceptance rate /3 due larger pool of n-gram candidates. However, an excessive number of candidates can strain the verification process, leading to reduced speedup x.
40K
x (> 1)
2.76
2.80
2.60
2.80
2.52
0.87
0.89
0.80
0.84
0.77
60K
x (>> 1)
3.07
3,10
3.05
3.07
2.96
Interestingly. lower is does not always result in a lower 3. For instance, k 5 achieves a higher 3 than k = 20, resulting in both a higher acceptance rate a and greater speedup x. However, at k = 5, the lack of diversity among the candidates leads to increased repetition, which in turn degrades the quality of generation.
0.88
0.90
0.83
0.86
0.81
80K
x (>> 1)
3.26
3.29
3.29
3.28
3.22
100K
a
0.89
0.90
0.85
0.87
0.83
x (> 1)
3.39
3.41
3.45
3.42
3.42
4.5.1. CASE STUDY
4.4.3. PENALTY VALUE A
Figure 5 presents a case study on the impact of the contex- tual penalty. Without the Contextual Penalty, repetitions ap- pear at about 5K tokens, compared to 60K with the penalty applied. Additionally, generation without the penalty ex- hibits word- hord-for-worf repetition, whereas generation with the penalty primarily demonstrates semantic-level repetition, highlighting its effectiveness in mitigating redundancy.
As a key component of TOKENSWIFT, contextual penalty significantly reduces repetition in generated text. We ex- amine the effect of two parameters present in contextual penalty, i.e. penalty value f and penalty window W.
Table presents the impact of introducing contextual penalty on diversity. Without any penalty (0 1.0), the generated sequences exhibit severe repetition, with an average Distinet- score of only 0.12. As the value of I increases gradually to 1.2, the diversity improves significantly, highlighting the effectiveness of contextual penalty in enhancing the diversity of ultra-long sequence generation.
cone (proeree) soro Tot spring is now fill Bleem words are green, and villaga
the (priepph
the swodtest
of soors.
eafler alcom the
cabout wonk) .....
The boauty af gariin
wellder pacts cnennty
ol quat change great growth.
In (sbost
time great retewal great
worder great wender and
waging Stutes hive
the
fiine graat deligit
Thi boaity at suring is of guast chazge
formally oeganized,
4.5. Temperature
time great retewal great
great growth,
stards basztffll which
cillege Beoold
wouder. ... great wonder, ftmme grost deligit
Table presents the results of an ablation experiment in- vestigating the effect of varying temperature settings on the generation length, acceptance rate, and speedup during text generation. The experiment uses top-p sampling with fixed p of 0.9 and evaluates generation lengths ranging from 20K to 100K tokens, with temperature values spanning from 0.4 to 1.2.
30K
(abbat words)
Socoda
language,
Nooe: The contaious
ils Latt:
passape, but beea spilt into
oodem: po. ..... and
severd sectioss caster roading. and into hear
experiecce
wild Tound the
(about wordsd
woodlands the mountaiss,
should sach. The
contail seeds, each
mader encoumped take
loap. labout l0k worls).
eighth
time to sloaly
the imagns
foundi woodlands the mountuiss.
wild
of
From the results, it is evident that as temperature increases, acceptance rate generally decreases across all generation lengths. Specifically, acceptance rate drops from 0.79 at a temperature of 0.4 to 0.52 at a temperature of 1.2 for 20K- length generation, and a similar trend is observed for longer
experience
medt tation the human.
orther to deforat therodive and
(ngpee (00K).
thei lands
Without petalty
Panulty = 1-2
Figure 5. Case Study on LLAMA3. 1-8b. Left: fragments of gen-
crated text without Contextual Penalty. Right: fragments of gener- ated text with Contextual Penalty. The blue text is repetition part. See Appendix G for more cases.
8

---

Lossless Acceleration of Ultra Long Sequence Generation
5. Related Works
is limited scenarios characterized by long prefixes and short outputs, making them unsuitable for ultra-long se- quence generation tasks. In such tasks, which are the focus of our work, the need for efficient inference spans both extended input contexts and lengthy outputs, presenting challenges that existing methods fail to address.
5.1. Speculative Decoding
Recent advancements in speculative decoding have sig- nificantly accelerated large language model (LLM) infer- ence through diverse methodologies. Speculative decod- ing (Leviathan et al., 2023; Chen et al., 2023) tradition- ally leverages smaller draft models to propose candidate tokens for verification by the target model. Early works like SpecTr (Sun et al., 2023) introduced optimal transport for multi-candidate selection, while SpecInfer (Miao al., 2024) and Medusa (Cai al., 2024) pioneered tree-based structures with tree-aware attention and multi-head decoding to enable parallel verification of multiple candidates. Subse- quent innovations, such as Sequoia (Chen et al., 2024b) and EAGLE-2 (Li et al., 2024d), optimized tree construction us- ing dynamic programming and reordering strategies, while Hydra (Ankner et al., 2024) and ReDrafter (Cheng et al., 2024) enhanced tree dependencies through sequential or re- current heads. Hardware-awar optimizations, exemplified by SpecExec (Svirschevski et al., 2024) and Triforce (Sun et al., 2024a), further improved efficiency by leveraging hierarchical KV caching and quantized inference.
5.2. Long Sequence Generation
Recent advances in long sequence generation have focused on addressing the challenges of coherence, efficiency, and scalability in producing extended outputs. A pivotal contribution is the LongWriter (Bai et al., 2024) framework, which introduces a task decompasition strategy to generate texts exceeding 20,000 words. Complementing this, Temp-Lora (Wang et al., 2024b) proposes inference-time training with temporary Lora modules to dynamically adapt model parameters during generation, offering a scalable alternative to traditional KV caching. Similarly, PLANET (Hu et al., 2022) leverages dynamic content planning with sentence- bag-of-words objectives to improve logical coherence in opinion articles and argumentative essays, demonstrating the effectiveness of structured planning in autoregressive transformers.
Self-speculative approaches eliminate the need for exter- nal draft models by exploiting internal model dynamics. Draft& Verify (Zhang et al., 2024) and LayerSkip (Elhoushi et al., 2024) utilized early-exit mechanisms and Bayesian op- timization to skip layers adaptively, whereas Kangaroo (Liu et al., 2024b) integrated dual early exits with lightweight adapters. Sun et al. (2024b) and SpecDec++ (Huang al., 2024) introduced theoretical frameworks for bloek-level token acceptance and adaptive candidate lengths. Parallel decoding paradigms, such as PASS (Monea et al., 2023) and MTJD (Qin et al., 2024), employed look-ahear embeddings or joint probability modeling to generate multiple candidates in single pass, while CLLMMs (Kou et al., 2024) and Looka- head (Fu et al., 2024) reimagined autoregressive consistency through Jacobi decoding and n-gram candidate pools.
In addition, lightweight decoding-side sampling strategies have emerged for repetition mitigation. The foundational work on Nucleus Sampling (Holtzman et al., 2020) first demonstrated that dynamically truncating low-probability token sets could reduce repetitive outputs while maintain- ing tractable decoding latency. Building on this, Hewitt et al. (2022) introduced n-sampling explicitly linking can- didate set reduction to repetition mitigation by entropy- guided token pruning. Recent variants like Min-p (Nguyen et al., 2024) optimize truncation rules in real-time scaling thresholds to the maximum token probability. And Mirostat Sampling (Basu et al., 2021) further integrate lightweight Bayesian controllers to adjust 1) parameters on-the-fly. Our work systematically analyzing how parameterized sampling (e.g.. Top-p Min-p, y-sampling) balances computational overhead and repetition suppression in ultra-long sequence generation pipelines.
Retrieval-augmented methods like REST (He et al., 2024), and NEST (Li et al., 2024b) integrated vector or phrase re- trieval to draft context-aware tokens, often combining copy mechanisms with confidence-basee attribution. Training- centric strategies, including TR-Jacobi (Wang et al., 2024a), enhanced parallel decoding capability via noisy training or self-distilled multi-head architectures. System-level op- timizations such PipeInfer (Butler et al., 2024) and Narasimhan et al. (2024) addressed scalability through asyn- chronous pipelines and latency-aware scheduling, while Goodput (Liu et al., 2024c) focused on dynamic resource allocation and nested model deployment.
6. Conclusion
In this study, we introduce TOKENSWIFT, a novel frame- work designed to achieve lossless acceleration in generating ultra-long sequences with LLMs. By analyzing and address- ing three challenges, TOKENSWIFT significantly enhances the efficiency of the generation process. Our experimental results demonstrate that TOKENSWIFT achieves over 3x acceleration across various model scales and architectures. Furthermore, TOKENSWIFF effectively mitigates issues re- lated to repetitive content, ensuring the quality and coher- ence of the generated sequences.
Approaches such as Triforce (Sun et al., 2024a) and Mag- icDec (Chen et al., 2024a) incorporate KV cache compres- sion during the drafting phase. However, their applicability
9

---

Lossless Acceleration of Ultra Long Sequence Generation
Impact Statement
Chen, J., Tiwari, V., Sadhukhan, R., Chen, Z., Shi, J., Yen, I. E.-H., and Chen, B. Magicdec: Breaking the Latency- Throughput Tradeoff for Long Context Generation with Speculative Decoding. arXiv, abs/2408. 1049, 2024a.
This paper presents work aimed at advancing the field of Machine Learning, specifically in the context of improving efficiency and scalability in generating ultra-long sequences. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here. None of the ethical concerns we foresee require specific actions or warnings in the context of this work.
Chen, Z.., May, A., Svirschevski, R., Huang, Y.-H., Ryabinin, M., Jia, Z., and Chen, B. Sequoia: Scalable and ro- bust speculative decoding. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024b. URL https: openrevieweeeeeeeeepeeeee net forum 2id=rk21.9YGD12.
Acknowledgement
The authors thank the reviewers for their insightful sugges- tions improve the manuscript. This work presented herein is supported by the National Natural Science Foundation of China (62376031).
Cheng, Y., Zhang, A., Zhang, X., Wang, C., and Wang, Y. Recurrent drafter for fast speculative decoding in large language models. arXiv preprint arXiv:2403.099) 099999 2024.
Ding, Y., Zhang, L. L.,, Zhang, C., Xu, Y., Shang, N., Xu, J., Yang, F., and Yang, M. LongroPE: Extending LLM context window beyond 2 million tokens. In Forty-first International Conference Machine Learning, 2024. URL https:tt///// http:///perreeeeeeeeeeeeeee net ftr/moormm ?id= ONOt:XT.qqw.
References
Meta. The llama 3 herd of models, 2024. URLhttps:
//ai.meta metaa com / researreeeeeeee rch hhcpphhlllbbe cations/ the-1lame 11mma- --ee-----e----e of ofooeees...
Ankner, Z., Parthasarathy, R., Nrusimha, A., Rinard, C., Ragan-Kelley, J., and Brandon, W. Hydra: Sequentially- dependent draft heads for medusa decoding. In First Conference on Language Modeling, 2024. URL https: //openreview fatt/forrie PidFPb JirzvJG.
Elhoushi, M., Shrivastava, A., Liskovich, D., Hosmer, B., Wasti, B., Lai, L.. Mahmoud, A., Acun, B., Agarwal, S., Roman, A., Aly, A., Chen, B., and Wu, C.-J. Layer- Skip: Enabling early exit inference and self-speculative decoding. In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguisties ( (Volume I: Long Papers), pp. 12622-12642. Bangkok, Thailand, Au- gust 2024. Association for Computational Linguistics. doi: 10. 10.18655v1112022.cllloogog. 6.1. URL https: / / //aacaannhoooooo org. acl long. 681/.
Bai, Y., Zhang, J., Lv, X., Zheng, L., Zhu, S., Hou, L.,, Dong, Y., Tang, J., and Li, J. Longwriter: Unleashing 10,000+ word generation from long context Ilms. arXiv preprint arXiv:2408.07005: 2024.
Basu, S., Ramachandran, G. S., Keskar, N. S., and Varsh- ney, L. R. {MIROSTAT): A {neural} {text} {decoding} (algorithm) {that) (directly) {controls} (perplexity). In International Conference on Learning Representations, 2021. URL hwtpthttt//........ openrevieeeeeeeeeeeeeeeeeee ew. net/ forum ? Pid-w1G1J2b1y5_
Fu, Y., Bailis, P., Stoica, I., and Zhang, H. Break the se- quential dependency of L.IM inference using lookahead decoding. In Forty-first International Conference on Ma- chine Learning, 2024. URL https: /ttttp::://pppeeee openreview .net/ for.fmrrmmmomm -in.iiddeeeessoo....
Butler, B., Yu, S., Mazaheri, A., and Jannesari, A. Pipeinfer: Accelerating Ilm inference using asynchronous pipelined speculation. In SC24: International Conference for High Performance Computing, Networking, Storage and Anal- ysis, pp. 1-19, 2024. doi: 10. 10111////A444062024...00
Guo, D., Yang, D., Zhang, H., Song, J., Zhang, R., Xu, R., Zhu, Q., Ma, S., Wang, P., Bi, X., et al. Deepseek-r1: In- centivizing reasoning capability in Ilms via reinforcement learning. arXiv preprint arXiv:2501. 1294...9.4.. 2025.
Cai, T., Li, Y., Geng, Z., Peng. H., Lee, J. D., Chen, D., and Dao, T. Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads. In Forty-first International Conference Machine Learning, volume Abs/2401.10774. 2024.
He, Z., Zhong, Z., Cai, T., Lee, J., and He, D. REST: Retrieval-based speculative decoding. Duh, K., Gomez, H., and Bethard, S. (eds.), Proceedings of the 2024 Con- ference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies (Volume 1: Long Pupers), pp. 1582-1595, Mex- ico City, Mexico, June 2024. Association for Computa- tional Linguistics. doi: 10.:8655//1220022maaalllooe URL https: : /aaaaaaaanthlooooooc org/ 2024 na acl-long. 88/. 88//
Chen, C., Borgeaud, S., Irving, G., Lespiau, J.-B., Sifre, L., and Jumper, J. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.013/18 2023.
10

---

Lossless Acceleration of Ultra Long Sequence Generation
Hewitt, J., Manning, C. D., and Liang, P. Truncation sam- pling as language model desmoothing. In Findings of the Association for Computational Linguistics: EMNLP 2022. pp. 1414-3427, 2022.
Li, Wang, X.,, Ding, W., Wang, Z., Kang, Y., Jia, Z., and Zheng, Z. Ram: Towards ever-improving memory system by learning from communications. arXiv preprint arXiv: 12045, 2024a.
Holtzman, A., Buys, J., Du, L.,, Forbes, M., and Choi, Y. The curious case of neural text degeneration. In International Conference on Learning Representations, 2020. URL pictps://opereeee QyrFvH.
Li, M., Chen, X., Holtzman, A., Chen, B., Lin, J., tau Yih, W., and Lin, X. V. Nearest neighbor speculative decoding for LLM generation and attribution. In The Thirty- Annual Conference on Neural Information Processing Systems, 2024b. URL htt.tt:::/ppeeeiiiiieeeee /openevviwww neet net / /forum? (alummidd=e id=Ni 9kebsSTt.
net/ wett//oooumdddr/r//eeee
Hu, Z., Chan, H. P., Liu, J., Xiao, X., Wu, H., and Huang. L. PLANET: Dynamic content planning in autoregressive transformers for form text generation. In Muresan, Nakov, P., and Villavicencio, A. (eds.), Proceedings of the 60th Annual Meeting of the Association for Compu- tational Linguistics (Volume 1: Long Papers), pp. 2288- 2305, Dublin, Ireland, May 2022. Association for Compu- tational Linguistics. doi: 10. 10.11865/11222222cc--ooo. 163. URL https::/p/.......... http://aaannthlooo..oooooo 1 1-lcng.
Li, Y., Huang, Y., Yang, B., Venkitesh, B., Locatelli, A., Ye, H., Cai, T., Lewis, P., and Chen, D. SnapK LLM knows what you are looking for before generation. In The Tiirty-eighth Annual Conference on Neural Information Processing Systems, 2024c. URL https: /openre view. net//orum Ld==oE5440221..
Li, Y., Wei, F., Zhang, C., and Zhang, H. EAGLE-2: Faster inference of language models with dynamic draft trees. In Empirical Methods in Natural Language Processing, 2024d.
ac
Huang, K., Guo, X., and Wang. M. Specdec++: Boost- ing speculative decoding via adaptive candidate lengths. arXiv preprint arXiv:2405 2024.
Liu, A., Feng, B., Xue, B., Wang, B., Wu, B., Lu, C.,, Zhao, C., Deng, C., Zhang, C., Ruan, C., et al. Deepseek- v3 technical report. arXiv preprint arXiv:2412.19437 2024a.
Jaech, A., Kalai, A., Lerer, A., Richardson, A., El-Kishky, A., Low, A., Helyar, A., Madry, A., Beutel, A., Car- ney, A., et al. Openai ol system card. arXiv preprint 2rXiv:2412.16720 2024.
Liu, F. Tang, Y., Liu, Z., Ni, Y., Tang, D., Han, K., and Wang, Y. Kangaroo: Lossless self-speculative decoding for accelerating LLMs via double early exiting. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024b. URL ht.ps: openre view. wiew.net//// foret/ffomm? iididdd1ae 11oo0 4mDp.
Keskar, N. S., McCann, B., Varshney, L. R., Xiong, C., and Socher, R. Ctrl: A conditional transformer lan- guage model for controllable generation. arXiv preprint arXiv: 05858, 2019.
Kou, S., Hu, L.., He, Z., Deng, Z., and Zhang, H. CLLMs: Consistency large language models. In Forty-first Inter- national Conference on Machine Learning, 2024, URL https: https:://penreee htt::///pp/eeeeeeeee met/forumm? OVmh8H.
Liu, X., Daniel, C., Hu, L., Kwon, W., Li, Z., Mo, X., Che- ung, A., Deng, Z., Stoica, L., and Zhang, H. Optimizing speculative decoding for serving large language models using goodput. arXiv preprint arXiv:2406.1 14066, 2024c.
Miao, X., Oliaro, G., Zhang, Z., Cheng, X., Wang. Z., Zhang, Z., Wong, R. Y. Y., Zhu, A., Yang, L., Shi, X., Shi, C., Chen, Z., Arfeen, D., Abhyankar, R., and Jia, Z. Specinfer: Accelerating large language model serv- ing with tree-based speculative inference and verifica- tion. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, ASPLOS '24, pp. 932-949, New York, NY, USA, 2024. Associa- tion for Computing Machinery. ISBN 9798400703867. doi: 10. 10.1145/3620666 010222200666666333333 3651335. URL https: //doi. wttpo////...111//20//0 3651335.
Leviathan, Y., Kalman, M., and Matias, Y. Fast inference from transformers via speculative decoding. In Inter- national Conference on Machine Learning, pp. 19274- 19286. PMLR, 2023.
Li, J., Galley, M., Brockett, C., Gao, J., and Dolan, B. A diversity-promotin objective function for neural con- versation models. In Knight, K., Nenkova, A., and Rambow, O. (eds.), Proceedings of the 2016 Confer- ence of the North American Chapter of the Associa- tion for Computational Linguistics: Human Language Technologiess pp. 110-119, San Diego, California, June 2016. Association for Computational Linguistics. doi: 10. 10.18653/v1AN 1/166//11111--1144 1014. URL https://///. /aclantho logy.org///o worg/o1g16 6-1//111111111 60044//
Mikhaylovskiy, N. Long story generation challenge. In Mille, S. (ed.), Proceedings of the 16th International
Natural Language Generation Conference: Generation

---

Lossless Acceleration of Ultra Long Sequence Generation
Challenges, pp. 10-16, Prague, Czechia, September 2023. Association for Computational Linguittess. URLhttps: // //aclantthologe hwwphhhhoooo..rg/22333333 org/2023 inlg genchal .2/.
/ 0888628510e90-appeet
pdf.
Sun, H., Chen, Z., Yang. X., Tian, Y., and Chen, B. Triforce: Lossless acceleration of long sequence generation with hierarchical speculative decoding. In First Conference on Language Modeling, 2024a. URL https: openre www.:nee///oooo. rid-iid-- HVK6n13197.
Mitchell, E., Lee, Y., Khazatsky, A., Manning, C. D., and Finn, Detectgpt: Zero-shot machine- generated text de- tection using probability curvature. In International Con- ference Machine Learning, pp. 24950-24962. PMLR, 2023.
machine-generated
Sun, Z.., Suresh, T., Ro, J. H., Beirami, A., Jain, H., and Yu, F. Spectr: Fast speculative decoding via optimal transport. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (cds.), Advances in Neural Information Processing Systems, volume 36, pp. 30222- 30242. Curran Associates, Inc., 2023. URL https: / //ppoceedings..oo neuriss........p..p........ cc/ http:iissccpppppp___ii1e_
Monea, G., Joulin, A., and Grave, E. Pass: Parallel specula- tive sampling. arXiv preprint arXiv:2311. 2023.
Narasimhan, H., Jitkrittum, W., Rawat, A. S., Kim, S., Gupta, N., Menon, A. K., and Kumar, S. Faster cascades via speculative decoding. arXiv preprint arXiv:2405.19261, 2024.
/aapp:/0003/filee/63333666188882 pdf.
Nguyen, M., Baker, A., Kirsch, A., and Neo, C. Min p sampling: Balancing creativity and coherence at high temperature. arXiv e-prints, pp. arXiv-2407, 2024.
Sun, Z., Ro, J. H., Beirami, A., and Suresh, A. T. Optimal block-level draft verification for accelerating speculative decoding. arXiv preprint arXiv:2403. 2024b.
Peng, B., Quesnelle, J., Fan, H., and Shippole, E. YaRN: Ef- ficient context window extension of large language mod- els. In The Twelfth International Conference on Learning Representations, 2024. URL https: oppnreview .net wwr//oorumm///mm wiidddd=HHffllll
Svirschevski. R., May, A., Chen, Z., Chen, B.. Jia, Z., and Ryabinin, M. Specexec: Massively parallel speculative decoding for interactive LLM inference on consumer devices. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL tps: /ttp///ppeeeiieeeeeeeeeeeee net/ tete/foouuee forum? pir-uuumidd-haas-s 9dvG.
Qin, Z., Hu, Z., He, Z. Prakriya, N., Cong, J., and Sun, Y. Optimized multi-token joint decoding with auxiliary model for I1m inference. arXiv preprint aTXIv:2407.09722, 2024.
Wang. Y., Yang. K., Liu, X., and Klein, D. Improving pacing in long-form story planning. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023. URL https: http:p:///pperevieeeee wptp///eenrreeeeeee/eeeee wttpiiewww..eeeeeeeeemeeeeeeeeee forum Fid=KUSzNKRI2
Qwen, Yang. A., Yang, B., Zhang, B., Hui, B., Zheng, B., Yu, B., Li, C., Liu, D., Huang, F., Wei, H., Lin, H., Yang. J., Tu, J., Zhang, J., Yang, J., Yang. J., Zhou, J., Lin, J., Dang, K., Lu, K., Bao, K., Yang, K., Yu, L., Li, M., Xue, M.. Zhang, P., Zhu, Q., Men, R., Lin, R., Li, T., Tang, T., Xia, T., Ren, X., Ren, X., Fan, Y., Su, Y., Zhang, Y., Wan, Y., Liu, Y., Cui, Z., Zhang. Z., and Qiu, Z. Qwen2.5 technical report, 2025. URL https:ttp//......... waaaiiivoorrgoo.... abs/2412, 15115.
Wang. Y., Luo, X., Wei, F., Liu, Y., Zhu, Q., Zhang, X., Yang, Q., Xu, D., and Che, W. Make some noise: Un- locking language model parallel inference capability through noisy training. In Al-Onaizan, Y., Bansal, M., and Chen, Y.N. (eds.), Proceedings of the 2024 Confer- ence on Empirical Methods in Natural Language Process- ing, pp. 12914-12926, Miami, Florida, USA, November 2024a. Association for Computational Linguistics. doi: 10. 100116555/1122224mmmmmmmmmm
Rae, J. W., Potapenko, A., Jayakumar, S. M., Hillier, C., and Lillicrap, T. P. Compressive transformers for long- range sequence modelling. In International Conference on Learning Representations, 2020. htth:t/::// //op enreview.nen net www.orrrmimiiiiooooeeee
URL http::: acc lanthology org 2024. emnl manlp-maing 718/.
Wang, Y., Ma, D., and Cai, D. With greater text comes greater necessity: Inference-time training helps long text generation. In First Conference on Language Modeling, 2024b. URL https: openreview net forum ? #id=dj9x6JuiDe
Shinn, N., Cassano, F., Gopinath, A., Narasimhan, K., and Yao, S. Reflexion: language agents with verbal reinforce- ment learning. In Oh, A., Naumann, T., Globerson, A.,
Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 8634-8652. Curran Associates, Inc., 2023. URL https: //proceeding. ngs wtw.eeeeddinn......ie....e.... www.wnuuri.... wwtrriiss.ccppppppe cctpcccrppppccpceeece files
Wu, T., Zhao, Y., and Zheng, Z. An efficient recipe for long context extension via ing. The Thirty-eighth Annual Conference on Neural
positional encod-
12

---

Lossless Acceleration of Ultra Long Sequence Generation
Information Processing Systems, 2024, URL https: //operreeiww net/ forum? d
Xiao, G., Tian, Y., Chen, B., Han, S., and Lewis, M. Effi- cient streaming language models with attention sinks. In The Twelfth International Conference on Learning Repre- sentations, 2024. URL https::/....... /wwpnrppeeeeeeeeeeeeeeeeeeeeeeee net /Eorum NG7
Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K. R., and Cao, React: Synergizing reasoning and acting in language models. In The Eleventh International Conference Learning Representations, 2023. URL https: / wptp//veeeeeeeeeeeeeeeeeee net forum? d=WE_v L.YUL-X.
Yuan, Z., Shang, Y., Zhou, Y., Dong, Z., Zhou, Z., Xue, C., Wu, B.. Li, Z.. Gu, Q., Lee, Y. J., al. Lim inference veiled: Survey and roofline model insights. arXiv preprint arXiv:2402.16363, 2024.
Zhang, J., Wang. J., Li, H., Shou, L., Chen, K., Chen, G., and Mehrotra, S. Draft& verify: Lossless large language model acceleration via self-speculative decoding. In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Pro- ceedings of the 62nd Annual Meeting of the Associ- ation for Computational Linguistics (Volume 1: Long Papers), pp. 11263-11288 Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. 10.11653/w1/2024.acl// 607. URL https: http://222..c.11mmme1e -10711666677
13

---

Lossless Acceleration of Ultra Long Sequence Generation
A. Lossless Nature of Speculative Decoding
The speculative decoding (Leviathan et al., 2023; Chen et al., 2023) can easily be justified to be lossless and identical to sample from Qtanget alone, i.e,, PSD = Starget- Note that, given prefix X the next token sampled from:
Paraft norm (ma((0, qearget - Para f(
if u 1) > a,
15+1
otherwise,
where a is the acceptance rate given by
a(x) min 1.0, Starget (x)
p
If the draft token is accepted, we have
psp [an( (uzi accepted)) = [ = min(paraft, Starget).
If the token is rejected, have
pso(t)Xng = (1 (xx X12) ) mormm(max((. ( Para ft (11)))
Starget min Paraft: Itrrget)
(1 a)
Qtarget
min(pdrofts Itarget)
Therefore, the overall probability is given by
Psn(a|X11))
accepted) + (i Starget ((x (1))
Proved.
B. Additional Training and Inference Details.
B.1. Training Details
During training, only three linear layers are fine-tuned, while the parameters of the LLM remained fixed. The model was trained on an NVIDIA A100-SXM4-80GB GPU. The specific training parameters are outlined in Table 10.
Table 10. Additional training details. Note that these hyperparameters do not require extensive tuning.
LLaMA3. 1-8b
YaRN YaRN-LLaMA2 LLaMA2 70--7---11-0 128k
Owen2.5-1.5b
Qwen2 .5-b 5-
Qwen2 5 1-1b
optimizer
AdamW
betas
(0.9, 0.999)
weight decay
0.1
warmup steps
50
learning rate scheduler
cosine
num. GPUs
4
gradient accumulation steps
10
batch size per GPU num. steps
3
1
200
600
learning rate
Se-3
1e-3
training parameters
50.3M 13.4G
50.3M
7.1M
38.5M
78.6M
MAX kv cache size
53.7G
2.9G
5.9G
20.1G
B.2. Inference Details
For inference, we used A-grams to maintain consistency with multi-token generation. The specific inference parameters are presented in Table 11.
For the tree attention mechanism, we selected simple ternary full tree configuration, as depicted in Appendix B.2.
14

---

Lossless Acceleration of Ultra Long Sequence Generation
Table 11. lt stands for the maximum number of retrieved n-grams in token reutilization
k
temp.
top-p
min-p
penalty
penalty len.
LLaMA3.
0.1
1.2
MaBN--LaMM2--7211222
0.9
1.15
Qwen2.5-1, 5-1.50 5b
20
0.9
1.15
1024
Owen2.5-12
0.05
1.15
Qwen2.5-1 5-144
0.05
1.13
C. Pre-training Details of the Llama3.1 Draft Model
To serve as the draft model for LLaMA3 1-8b in TriForce, we pretrain tiny version of 250M parameters with the same tokenizer from LLaMA3. 1bbb. The model configuration is listed in Table 12. We train the model on Wikipedia (20231101.en) and part of C4-en for epoch.
Table 12, Configuration Llama 205M.
hidden.size
768
hidden_act
silu
intermediate
3072
max_ mox_pioition..cmm embeddings
2048
num_attention_haal
12
num key value heads
12
rope_theta
500000
vocab size
128256
D. Different Sampling Method
D.1. Introduction of Different Sampling Algorithms
Given a probability distribution P(rr/211,22 ......... .I-1) over the vocabulary V at position top-p sampling (Holtzman et al., 2020) first sorts the tokens in descending order of their probabilities. It then selects the smallest set of tokens whose cumulative probability exceeds a predefined threshold where perepp E (0, 1]. Formally, let V, c V be the smallest set such that:
Σ P(æ, 1|æ1, 22. x1-1) p. VE
/wi wike pedia
15

---

Lossless Acceleration of Ultra Long Sequence Generation
The next token Ee is then randomly sampled from this reduced Vp according to the renormalized probabilities:
P(æt = u| Lt ft EvEr, P(x+ v/ [11 F4-1)
for Vp-
Nguyen et al. (2024) introduced min-p sampling, which uses a relative probability threshold Pbase (0, 1] to scale the maximum token probability Pmaz determine the absolute probability threshold Pseated- Sampling is then performed on tokens with probability greater than equal to Pscated.
Formally, given the maximum probability over the token distribution Pmaz absolute probability threshold Pscaled calculated as:
m&X P(æt v/ 22, 22..... Iz-1), the
Pscoled
= Pbose X Pmaz-
The sampling pool min is then defined as the set of tokens whose probability is greater than or equal to Pseated?
Vmnn {v E V 2( (.,1),, > Pscaled).
Finally, the next token & is randomly sampled from the set Vmni according to the normalized probabilities:
2t EveVmin
for u e Vmnn-
I2-1)
The sampling pool of 1-sampling (Hewitt et al., 2022) is defined
V = aF e V P(u .......,II........... > n)
min (c, exp( ha.
where ne is the entropy of P(V J2, 1), a and hyperparameters.
D.2. Impact of Different Sampling Algorithms
We also explored the impact of different sampling algorithms with disable token reutilization, including top-p sam- pling (Holtzman et al., 2020), min-p sampling (Nguyen et al., 2024), and 7-sampling (Hewitt et al., 2022). As summarized in Table 13, TOKENSWIFT consistently demonstrates strong robustness across these methods. This versatility underscores its compatibility with wide range decoding strategies, making it suitable for diverse applications and use cases.
Table 13. Ablation results on various sampling methods with disable token reutilization.
top-p (p 0.9)
min-p
1--ampling =2c-4)
Gen. Len.
(p 0.1)
20K
a
0.68
0.66
0.56
x(>1 1)
2.10
2.01
1.85
40K
a
0.81
0.75
0.71
x ((> 1)
2.80
2.58
2.59
0.84
0.79
0.78
60K
((>>) 1)
3.07
2.94
2.99
80K
a
0.86
0.81
0.81
x(> 1)
3.28
3.15
3.24
0.87
0.82
0.84
100K
((> 1)
3.42
3.26
3.42
16

---

Lossless Acceleration of Ultra Long Sequence Generation
E. Tree-Bassd Attention
Tree attention is mechanism designed to process multiple candidate continuations during speculative decoding efficiently. Instead of selecting a single continuation as in traditional methods, tree attention leverages multiple candidates to increase the expected acceptance length in each decoding step. balancing computational demands and performance.
The mechanism uses a tree structure where each branch represents a unique candidate continuation. For example, if two heads generate top-2 and top-3 predictions, the Cartesian product these predictions results in 6 candidates, forming a tree with branches. Each token in the tree attends only to its predecessors, and an attention mask ensures that this constraint upheld, Positional indices are also adjusted to align with the tree structure.
The tree structure constructed by taking the Cartesian product of the predictions across all heads. head has 8). top predictions, then the tree structure consists of all possible combinations predictions across the heads. Each combination forms unique branch in the tree.
Let the total number of candidates (i.e., branches) in the tree be denoted as C, which the product of the number of predictions for each head:
C
I
Sk-
8-1
Each candidate is distinct sequence of tokens formed by selecting one token from each set of predictions from the heads. To ensure that tokens only attend to their predecessors (tokens generated earlier in the continuation), an attention mask is applied. The attention mask for the tree structure ensures that for each token at level k, can attend only to tokens in levels [0, 10......, 1]. This guarantees that each token's 's attention is directed solely towards its predecessors the tree. Formally, the attention mask Mj for each token at level k is defined as:
{ token j a predecessor of token i,
Ma(i.)
otherwise.
where je( 1 means that the token at position j can attend the token position i, and M& (i, means no attention is allowed from j i.
F. More Ablation Experiments
F.I. Ablation of Prefill Length
We disable token reutilization and conduct ablation study on the different prefix length, as shown Table 14. The experiment explores the impact of varying prefix lengths on the generation sequences of different lengths (from 20K to 100K). The results include two key metrics: acceptance rate (a) and speedup factor (x).
As the prefix length increases, the acceptance rate tends to stabilize, generally hovering around 0.35 to 0.39 across different sequence lengths, with a slight fluctuation depending on the specific prefix length. This suggests that while the acceptance rate does not dramatically change with longer sequences, remains relatively consistent.
Table 14, Ablation results on different prefill length disable token reutilization.
20K
40K
60K
80K
100K
Prefill Len.
X
Qk
X
X
X
X
2048
0.35
1.41
0.35
1.63
0.35
1.76
0.35
1.83
0.34
1.87
3072
0.31
1.23
0.31
1.42
0.31
1.55
0.31
1.64
0.30
1.69
4096
0.35
1.32
0.35
1.54
0.35
1.69
0.35
1.76
0.35
1.85
5120
0.32
1.29
0.31
1.46
0.31
1.57
0.31
1.65
0.31
1.70
6144
0.39
1.46
0.39
1.66
0.39
1.80
0.39
1.88
0.39
1.94
7168
0.36
1.42
0.37
1.62
0.36
1.74
0.36
1.82
0.36
1.88
8192
0.36
1.21
0.36
1.42
0.36
1.58
0.36
1.69
0.36
1.77
In terms of speedup, it shows that with longer prefix lengths, the model achieves progressively higher acceleration. For instance, a prefix length of 2048 achieves a speedup 1.41 for 20K tokens, but with 8192, the speedup reaches up to 1.77
17

---

Lossless Acceleration of Ultra Long Sequence Generation
for 100K tokens. This indicates that increasing the prefix length contributes better acceleration, especially for longer sequences, while maintaining relatively stable acceptance rate. The findings demonstrate the tradeoff between prefix length and model efficiency, where larger prefix lengths tend to result in greater speed.
F.2. blation of Penalty Window
We investigate the effect of penalty window size (W) on the performance of a model generating sequences of varying lengths (from 20K to 100K tokens). For each sequence length, we apply a penalty to generated tokens within sliding window of size W, and evaluate the impact on two key metrics: acceptance rate (a: and acceleration factor (x). Additionally, we assess the diversity of the generated sequences using the Distinct-n metric, where higher values indicate greater diversity.
Table 15. Ablation results penalty length (W).
20K
40K
60K
80K
100K
Penalty Len. (W)
a
X
Q
X
a
X
X
a
X
20
0.82
2.25
0.90
2.85
0.93
3.20
0.94
3.42
0.95
3.58
50
0.83
2.30
0.89
2.83
0.91
3.14
0.92
3.35
0.93
3.52
128
0.59
1.75
0.70
2.38
0.75
2.75
0.80
3.07
0.82
3.29
256
0.78
2.17
0.86
2.76
0.89
3.11
0.91
3.33
0.92
3.48
512
0.75
2.15
0.84
2.73
0.88
3.07
0.89
3.28
0.90
3.43
1024
0.66
2.01
0.75
2.58
0.79
2.94
0.81
3.15
0.82
3.26
2048
0.69
1.99
0.79
2.58
0.82
2.91
0.84
3.14
0.86
3.31
Table Distinct-n score with different penalty length W.
Penalty Len. (W)
Distinct-1
Distinct-2
Distinct-3
Distinct-4
AVG.
20
0.85
0.86
0.73
0.70
0.79
50
0.91
0.91
0.85
0.77
0.86
128
0.95
0.77
0.57
0.48
0.69
256
0.83
0.91
0.88
0.83
0.86
512
0.90
0.86
0.74
0.65
0.79
1024
0.79
0.86
0.77
0.71
0.78
2048
0.67
0.84
0.86
0.84
0.80
The results in Table 15 and Table 16 show a clear trade-off between the penalty window size and the model's performance. For smaller penalty window sizes, such as W 20, the model achieves higher acceptance rates and better acceleration, but this comes at the cost of lower diversity in the generated sequences (as indicated by lower Distinct-n values). As the penalty window size increases (e.g., W = 256 or W = 2048), the acceptance rate slightly decreases, but the model exhibits better diversity and still maintains significant speedup relative to the AR baseline. These findings suggest that larger penalty windows can help reduce repetitiveness and improve the diversity of long sequence generation, but they may also slightly reduce the model's efficiency and acceptance rate.
Table 15 also reveals that for each penalty window size, increasing the sequence length (from 20K to 100K tokens) generally results in higher acceleration and better diversity, with some fluctuations in acceptance rates.
G. More Cases
H. Training Loss Curve
18

---

Lossless Acceleration of Ultra Long Sequence Generation
(prompt)..... the literature which has been oevoted to him.
(prompt)....
of biography.
A mong the several nations of modem Europe, France stands in a class by herself. She is the great mother of ideas, the molder of the thoughts of men, the very fountain of civilization. France is, or should be, the hi higt type culture, the seat of the intellectual, the artistic, the literary, the scientific, and philosophical life of the world.
The Revolutionary Epoch in Europe.
If we examine the last half of the eighteenth century in Europe, find that it was marked by the most ex rdinary commotion
(about 5K words)....
In the eighteenth century, the Revolution was the result of the
revolt of the mob, and the Reign of Terror was the result of the revolt of the mob.
(about SOK words)..... hen Napoleon was boy, he was friend of the French people, and the Corsicans. Though bom a Catholic, he became a protestant, and for some time he live dived in the nei geighboroood of the French protestants.
The merican Revolution was the result of the revolt of the Revolutionary mob, and the R Reign of Terror was the result of the revolt of the Revolutionary mob.
(about 55K words).... In the eighteenth century, the Revolution was the result of the revolt of the mob, and the Reign Terror was the result of the revolt of the mob.
hen was a boy, he was fri end of the French people, and
the Corsicans. ......He He was also a friend of Rousseau, and his first publication was poem the verses of the great Swiss
(repeat to 100K).....
philosopher.
Without penalty
Penalty = 1-15
Figure 6. Case Study TaRN-LLaMA2-7b--2 Left: fragments of generated text without Contextual Penalty. Right: fragments of generated text with Contextual Penalty. The blue text is repetition part.
19

---

Lossless Acceleration of Ultra Long Sequence Generation
Shop
Pelative
Mice
Samvic LAb
5:25
5:7h
Mie 00,
6:125
Thi Jan 100
7
5:908
5:945
Sor A, 00896
0.5
5.5
5
120
200
400
500
600
(a) Cross Entropy Loss Training Curve of the First Linear Layer
Join_oe_Josa_2 1ag brinvee loss
Name
Eeveathed
Volue
Step
Time
Relettive
Famul 1,00
6:25
6:25
195
Mon Deo 17:52477
11 5it 64
The
7.
8.313
Thu, 12:m222
26
CHANGL
8:313
0:313
San
5.
(b) Cross Entropy Loss Training Curve the Second Linear Layer
86
Nome
Smrothhed
Value
Step
Time
Relattvee
10
Daratt 1,00
0,425
Monn
Harme22211
0.602
The 12:24
Affar
78
Qwent 74344
6.488
6.668
995
Ser Jan 06:96
39 Sine 580
74
72
8.6
6.4
100
20C
300
400
500
600
(c) Cross Entropy Loss Training Curve the Third Linear Layer
Figure 7. Cross Entropy Loss Training Curve of Linear Layers
20


Reviews:
[{"review_id": "6Ar9sdUP4U", "reviewer": "Reviewer_zJ1d", "summary": "The paper presents TOKENSWIFT, a framework to accelerate ultra-long sequence generation (up to 100K tokens) in large language models (LLMs) with lossless accuracy, addressing the time-intensive nature of such tasks (e.g., LLaMA3.1-8B taking 5 hours). It tackles three challenges—frequent model reloading, dynamic KV cache management, and repetitive content—via multi-token generation with token reutilization, dynamic KV cache updates, and a contextual penalty mechanism. Main findings include a 3x speedup across models (1.5B-14B) and architectures (MHA, GQA), reducing LLaMA3.1-8B’s 100K-token generation to 90 minutes, with improved diversity (Distinct-n) and superiority over baselines like TriForce* and Medusa*, as validated on PG-19.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your time and constructive feedback. We are encouraged by your positive assessment that ``our experiments convincingly demonstrate a 3× speedup``, ``the sensible design of our method for ultra-long sequence generation``, and ``the rigorous ablation studies on sampling methods, temperature, and penalty windows``. Below, we address their concerns point-by-point.\n\n>**Q1:** though “minimal training cost” lacks detailed quantification beyond training three linear layers (§3.1), slightly weakening its evidential strength. \n\n**A1:** Thank you for highlighting this point. We will provide a detailed breakdown of the quantized training cost in the revised manuscript. Specifically, for any large language model, our approach requires only ``γ（Number of tokens generated in parallel） × hidden_size × hidden_size`` trainable parameters. The specific training time is shown in **Appendix I**. For example, the training time for models 8B does not exceed two hours. The concrete results for the LLMs used in our experiments are summarized in the table below:\n\n| Model | Llama3.1-8B | Llama2-7B | Qwen2.5-1.5B | Qwen2.5-7B | Qwen2.5-14B |\n| -------- | -------- | -------- | -------- | -------- | -------- |\n| Param. | 50.3M | 50.3M | 7.1M | 38.5M | 78.6M |\n\n> **Q2:** However, the resource cost of maintaining full KV cache for verification isn’t quantified, which could affect scalability claims on resource-constrained settings—an area for minor clarification.\n\n**A2:** Thank you for your suggestion. The full KV Cache memory overhead can indeed be derived from the model configuration. Taking Llama3.1-8B (GQA) as an example (batch size=1, bfloat16), the **peak** memory usage is calculated as:\n2 × Layer Num × Batch Size × Seq Len × KV Heads × Head Dim × Bytes\n= 2 × 32 × 1 × 102,400 × 8 × 128 × 2 bytes ≈ 13.4 GB.\nThe table below summarizes the **peak** memory requirements for other LLMs in our study when maintaining full KV Cache:\n\n| Model | Llama3.1-8B | Llama2-7B(MHA) | Qwen2.5-1.5B | Qwen2.5-7B | Qwen2.5-14B |\n| -------- | -------- | -------- | -------- | -------- | -------- |\n| Param. | 13.4G | 53.7G | 2.9G | 5.9G | 20.1G |\n\nWe hope the above response can resolve your questions and concerns. Please let us know if there is any further question! Thanks again for your review.", "claims_and_evidence": "The claims are well-supported by evidence. The 3x speedup is convincingly demonstrated through experiments (Tables 3, 4), with detailed comparisons to AR and baselines, and time savings (e.g., 3.5 hours for Qwen2.5-14B) adding clarity. Lossless acceleration is theoretically backed by speculative decoding (Appendix A) and empirically implied by matching AR outputs. The “first for 100K-token lossless acceleration” claim aligns with cited limitations of prior work (e.g., TriForce’s 256-token limit, Table 1), though “minimal training cost” lacks detailed quantification beyond training three linear layers (§3.1), slightly weakening its evidential strength.", "methods_and_evaluation_criteria": "The proposed methods—multi-token generation, dynamic KV updates, and contextual penalties—are sensible for ultra-long sequence generation, directly addressing identified bottlenecks. The evaluation criteria, including speedup (latency ratio), acceptance rate\n$\\alpha$, and Distinct-n for diversity, are appropriate and standard for assessing acceleration and quality. Using PG-19 as a benchmark is reasonable for long-sequence tasks, though its representativeness for all LLM applications could be broader.", "theoretical_claims": "I reviewed the primary theoretical claim of lossless acceleration, supported by the proof in Appendix A, which demonstrates that TOKENSWIFT’s speculative decoding (SD) output distribution $p_{SD} $ equals the target model’s distribution $q_{target} $.", "experimental_designs_or_analyses": "The experimental design is sound, testing TOKENSWIFT across diverse models (e.g., LLaMA3.1-8B, Qwen2.5 series) and lengths (20K-100K tokens) on a single A100 GPU (§4.1), with results averaged over five runs to reduce randomness (Table 3). Ablations on sampling methods (Table 12), temperature (Table 13), and penalty windows (Table 15) are rigorous, validating robustness. However, the resource cost of maintaining full KV cache for verification isn’t quantified, which could affect scalability claims on resource-constrained settings—an area for minor clarification.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "KYne0Fthx1", "reviewer": "Reviewer_7LKx", "summary": "As LLMs become bigger in terms of number of parameters, model inference has become computationally expensive leading need for faster and computationally efficient sequence generation. The authors propose the TOKENSWIFT, a new framework to accelerate autoregressive generation for LLMs. TOKENSWIFT utilizes multi token generation to draft multiple tokens in a single forward pass and dynamically updates the KV cache across iterations to achieve lossless acceleration for autoregressive generation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable suggestions and acknowledgment of our method. We are encouraged by your recognition of ``our thorough ablation studies`` and ``the practical impact of our method, which achieves up to 3× speedup across diverse architectures``. We also appreciate your note on ``the wider community would benefit from our findings``. Below, we will address your concerns:\n\n> **Q1:** Nitpick: The title \"FROM Hours to Minutes\" might be slightly misleading\n\n**A1:** We appreciate this observation. We will remove this phrase from the title in the revised version.\n\nWe hope our answers have resolved your concerns. If you have any other concerns, please feel free to let us know. Thanks again for your review.", "claims_and_evidence": "TOKENSWIFT claims to be the first to accelerate lossless autoregressive generation for LLMs for upto 100k tokens and attain upto 3x speedup across various model architectures. The authors provide empirical evaluation results to substantiate their claims in Table 3 and 4.\n\n\nNitpick: The title *\"FROM Hours to Minutes\"* might be slightly misleading, TOKENSWIFT provides upto 3x speedup and Figure 1 itself showcases sequence generation time coming down from ~5 hours to 1.5 hours.", "methods_and_evaluation_criteria": "TOKENSWIFT compares autoregressive generation performance across different models and attention architectures (MHA and GQA) and compute latency based with varying prefill lengths. TOKENSWIFT is compared against existing SOTA literature such as Medusa and Triforce for check for performance gains.", "theoretical_claims": "Section 3 discusses the TOKENSWIFT framework which includes multi token generation using additional tuned linear layers, token reutilization and dynamic KV cache management which is based on ranking importance scores suggested in equation 2, with parallel verification of the draft tokens.", "experimental_designs_or_analyses": "Yes, the authors compare TOKENSWIFT to existing SOTA literature for various models, attention architectures, varying prefill lengths. Thorough ablation studies are conducted to evaluate the pros and cons of different components of the TOKENSWIFT framework.", "relation_to_broader_scientific_literature": "The work presents novel method for accelerating autoregressive language generation for LLMs. The wider community would benefit from the findings presented to accelerate sequence generation for longer sequences in a lossless manner.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "duYnzYj4zN", "reviewer": "Reviewer_v64u", "summary": "This work proposes a three-pronged approach (TokenSwift) to improving the latency and quality of generating ultra-long sequences: 1) Multi-token prediction similar to Medusa; 2) Using a sparse KV-cache whose elements are selected based on their attention scores (query/key inner product before softmax); 3) token reutilization via n-gram look-ups, somewhat similar to prompt lookup but applied to the generated outputs. The authors show that these techniques significantly improve generation latency compared to selected speculative decoding methods and, when paired with a contextual penalty for repeated outputs, improve the distinct-N metric (unique n-grams / total words) of the output sequences.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your time and insightful feedback, which has helped us improve our manuscript.\n> **Q: Reformulate Claim**\n\n**A:** We appreciate your suggestions to replace \"fail\" with \"benefit\" and will revise accordingly.\n\n1. **Dynamic KV Cache Compression (Challenge II)**\nThe limitation of baseline methods is not merely budget constraints but their **single-compression design** for long inputs. For long outputs, however, the KV Cache grows dynamically with generated tokens. In contrast, our method maintains a fixed-size KV Cache regardless of output length (no hard budget), as we continuously compress the growing cache.\n\n2. **Memory Limits**:\nLike all speculative decoding methods, we preserve a full KV Cache for lossless generation. If this cache exceeds **GPU memory** (not a pre-set budget), generation fails—but this is distinct from baselines’ rigid budget-based failures. Note that our focus is on **draft-phase optimization**.\n\n3. **Example**:\nFor TriForce (budget=4096):\n    * Input=100K, Output=256 → KV Cache=4096+256 (valid).\n    * Input=8192, Output=100K → KV Cache=4096+100K (fails).\n\n    Our method fixes the KV Cache size for any input/output length.\n\n> **Q: Sampling Diversity**\n\n**A:** \nWe sincerely appreciate your insightful comments regarding the diversity-speedup balance. \n\n1. **Trade-off**\n   In **Table 6**, our experiments demonstrate that the proposed penalty mechanism enables effective balancing of these two objectives:\n   - Without penalty: Achieves 3.58× speedup with baseline diversity \n   - With θ=1.2 penalty: Maintains 3.27× speedup (only 0.31x reduction) while significantly improving diversity metrics\n   \n   This evidences that our approach attains competitive acceleration without severely compromising diversity.\n\n2. **Main Results**\n   All experiments in **Tables 3-4** already employ θ>1.0 penalty configuration (**Table 10**). The absence of severe repetition issues in these results further confirms the practical viability of our trade-off strategy.\n\n3. **Self-BLEU**\n    Self-BLEU provides direct measurement:\n     |Metric|Self-BLEU-2|Self-BLEU-3|Self-BLEU-4|Self-BLEU-5|\n     |-|-|-|-|-|\n     |w/o Penalty|0.7899|0.7445|0.7162|0.6966|\n     |w/ Penalty|0.5588|0.4745|0.4115|0.3788|\n\n     Consistent 23.11-31.78% relative reduction across n-grams confirms diversity improvement, aligning with Distinct-N trend(Table 8). BERTScore/MAUVE are inapplicable for our **reference-free open-generation** setting, as they require parallel references.\n\n4. **Implementation**\n   The adjustable penalty coefficient allows practitioners to prioritize either speed or diversity based on application needs, demonstrating our framework's adaptability.\n\n> **Q: 250M vs. 68M** \n\n**A:**\nFor a fair comparison, we used 68M for llama2 and 250M for llama3.1 in the TriForce experiment in Table 3, and the parameter settings of the two draft models are exactly the same. Because the **vocabulary size** of llama3.1 is much larger than that of llama2, the model size becomes larger.Finally, we have open-sourced this model to support future research.\n\n> **Q: Table 1** \n\n**A:** While Table 1 is briefly referenced in **L49–50**, we will explicitly add this context in the revised manuscript to ensure transparency.\n\nWe reproduced Triforce's results on A100-80G and PG-19 using identical hyperparameters. The only difference (as noted in L49-50) is that their original experiments were conducted on llama2(**MHA**), while ours used llama3.1(**GQA**).\n\nThe observed performance gap arises because **MHA typically requires a KV cache several times larger than GQA**, enabling TriForce’s acceleration.\n\n> **Q: Clarify Statement of Baseline**\n\n**A:** Thank you for your question.\n1. **Limitations in Prior Work**:\nThe values 256 and 64 in Table 1 are just examples. We also optimized TriForce and experimented with generating 100K lengths (**Table 3**). It does achieve a 2x speedup on MHA, but not on GQA.\n\n2. **Length Restrictions in Baselines**:\nAs observed in practice, baselines enforce strict limits on generation length: TriForce caps generation at the KV Cache budget size:\n    ```\n    def update_graph_cache(self, kv_cache=None):\n        self.value_cache[:,:,self.max_budget-(kv_cache.seq_len-self.prefill):self.max_budget] = kv_cache.value_cache[:,:, self.prefill:kv_cache.seq_len].clone()\n        self.key_cache[:,:,self.max_budget-(kv_cache.seq_len-self.prefill):self.max_budget] = kv_cache.key_cache[:,:, self.prefill:kv_cache.seq_len].clone()\n    ```\n\n> **Q: Penalty Value** \n\n**A:** During experiments, we observed that while higher θ (e.g., 1.5) increases diversity, it often leads to incoherent outputs or even garbled text in practice. (Table 8) Thus, we adopted θ=1.2 as a empirically stable default, **balancing diversity and quality**.\n\n> **Q: Typos** \n\n**A:** These were typos in our manuscript, and we will correct them in the revised version. To clarify: when θ=1.0, no repetition occurs.\n\nWe hope our answers have resolved your concerns.", "claims_and_evidence": "* Overall, I believe the empirical evidence supports the author's claims that TokenSwift improves output generation latency for long sequences. \n* However, I have concerns regarding some specific claims made otherwise:\n    * TokenSwift doesn’t directly address the growing KV cache problem for long sequences. Although the authors note that the baseline methods “would inevitably encounter failures due to KV cache budget constraints” their proposed method would also fail in such a setting as the verification step requires the *full* KV cache. Therefore, in cases where the “growing size of the KV cache would far exceed the allocated length budget”, TokenSwift will also fail. I believe it would be better to reformulate this claim as a benefit with respect to latency instead of claiming other speculative decoding methods would “fail”. \n    * The authors claim that TokenSwift enhances diversity of the generated output and also significantly reduces latency. While these claims separately appear to be accurate based on the empirical measures provided, I am concerned TokenSwift seems to inherently *benefit* from repeated / duplicated n-grams in long outputs due to the proposed token reutilization scheme. The reported acceptance rate (AR) for TokenSwift without token reutilization falls significantly as noted in Figure 3. I worry that if sampling was improved such that repetitive content generation was not as prominent, TokenSwift’s performance would be greatly diminished and may no longer offer significant latency improvements over TriForce and other speculative decoding methods. As such, the proposed token utilization is at odds with the eventual desire to have more diverse long generated outputs.", "methods_and_evaluation_criteria": "* Overall the methods and evaluation criteria for assessing the quality of the speculative decoding process are standard and make sense.\n* For assessing the output quality, I find distinct-n to be a useful but insufficient metric on its own. Distinct-n only captures lexical but not semantic diversity. Other text diversity metrics that also capture semantic similarities should be considered. For example: self-BLEU [1], BERTScore [2], or MAUVE [3]. Since repeated content is acknowledged by the authors to also be present in TokenSwift outputs, it would improve the work to further quantify this with additional metrics. \n\n[1] Y. Zhu et al., “Texygen: A Benchmarking Platform for Text Generation Models,” Feb. 06, 2018, arXiv: arXiv:1802.01886. doi: 10.48550/arXiv.1802.01886.\n[2] T. Zhang, V. Kishore, F. Wu, K. Q. Weinberger, and Y. Artzi, “BERTScore: Evaluating Text Generation with BERT,” Feb. 24, 2020, arXiv: arXiv:1904.09675. doi: 10.48550/arXiv.1904.09675.\n[3] K. Pillutla et al., “MAUVE: Measuring the Gap Between Neural Text and Human Text using Divergence Frontiers,” Nov. 23, 2021, arXiv: arXiv:2102.01454. doi: 10.48550/arXiv.2102.01454.", "theoretical_claims": "N/A, no novel proofs provided.", "experimental_designs_or_analyses": "The described experimental design and analyses appear to be sound.", "relation_to_broader_scientific_literature": "TokenSwift builds on prior methods from speculative decoding literature work such as Medusa and prompt-lookup decoding. While these individual components are not overly novel in themselves, their combination and integration is. Further, I believe tweaks to these approaches included in this work such as having non-independent multi-token generation heads is unique and a valuable contribution to the literature. Overall speculative decoding for long context prompts has been studied in some detail but as far as I know this is the first work to directly apply these techniques to the setting of long output generation.", "essential_references_not_discussed": "None noted.", "other_strengths_and_weaknesses": "## Strengths: \n* Due to the increasing importance of synthetic data and in particular obtaining reasoning traces, this method is of importance to improve the efficiency of such generations. \n* This is the first work that I am aware of to apply speculative decoding to long-output generation settings.\n* The extensive ablation studies help the reader understand the pros/cons of the proposed method. \n\n## Weaknesses\n* The TriForce comparison requires a custom pretrained draft model for the first tier of drafters. Originally, TriForce used a 68M model for this tier whereas in this work we have a 250M model. The large discrepancy between results may influence the overall conclusions reached. \n* Some details are not made clear. For example, Table 1 is not referenced in the work. Why are the acceleration rates noted here so much worse than the reference methods? Eg., TriForce achieves acceleration over 2x on A100s with a prompt length of 122K and generation length of 256. Without more details regarding the Table 1 results it’s impossible to compare with previously published values. \n* Some unclear choices made in hyperparameter selections for the penalty value.", "other_comments_or_suggestions": "* Table 4 Delta T is the number of minutes saved, not hours. \n* L433: Text in parentheses states that without a penalty theta = 0 which directly contradicts Table 8 caption.", "questions_for_authors": "1. How does the generated outputs with and without penalty compare using other non-lexical based metrics such as self-BLEU, BERTScore, or MAUVE? Does the contextual penalty also improve repeated semantic similarity?  \n2. The authors claim that Triforce and MagicDec are limited to generating 256 or 64 output tokens, respectively (see L040, second column). However, in practice there is no such limit, these are merely the generation settings used by these respective works when benchmarking their methods. Since both of these baselines operate in the typical draft-then-verify framework of speculative decoding, we can simply continue speculating for additional drafting rounds until a desired output length is reached. This is also made clear by the author's use of these baselines for generating sequences greater than the noted limits. Please clarify this statement. \n3. What are the settings used for Table 1? Prompt length, data, etc? \n4. Why was the penalty value selected as 1.2 instead of 1.5 where a much higher diversity is observed?", "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:

Meta-review: The paper introduces TokenSwift, tackling three latency problems in autoregressive decoding  by combining multi-token generation, dynamic KV cache updates, and token reutilization with contextual penalties. The approach is empirically solid, with a 3× speedup validated across models and lengths without sacrificing output quality, and theoretically justified for lossless acceleration. While some concerns were raised about diversity tradeoffs and baseline comparisons, the authors responded thoroughly, and reviewers generally agreed on the method's merit and practical significance. I recommend acceptance.
Decision: Accept (poster)