Speculative Decoding with CTC-based Draft Model for LLM Inference Acceleration
Authors: Zhuofan Wen
Shangtong Gui
Yang Feng
Venue: NeurIPS 2024 poster (2024)
Keywords: Pretrained language model
Speculative decoding
CTC decoding algorithm
Primary area: natural_language_processing
TL;DR: We propose a flexible speculation decoding framework with CTC-based draft model for context information retrieving when drafting and adaptive candidate sequence generation.

Abstract: Inference acceleration of large language models (LLMs) has been put forward in many application scenarios and speculative decoding has shown its advantage in addressing inference acceleration. Speculative decoding usually introduces a draft model to assist the base LLM where the draft model produces drafts and the base LLM verifies the draft for acceptance or rejection. In this framework, the final inference speed is decided by the decoding speed of the draft model and the acceptance rate of the draft provided by the draft model. Currently the widely used draft models usually generate draft tokens for the next several positions in a non-autoregressive way without considering the correlations between draft tokens. Therefore, it has a high decoding speed but an unsatisfactory acceptance rate. In this paper, we focus on how to improve the performance of the draft model and aim to accelerate inference via a high acceptance rate. To this end, we propose a CTC-based draft model which strengthens the correlations between draft tokens during the draft phase, thereby generating higher-quality draft candidate sequences. Experiment results show that compared to strong baselines, the proposed method can achieve a higher acceptance rate and hence a faster inference speed.

Speculative Decoding with CTC-based Draft Model for LLM Inference Acceleration
Zhuofan Wen' ,Shangtoog Gui ,Yagg Feng Fengl.3.44 ,3,4+
Key Laboratory of Intelligent Information Processing,
Institute of Computing Technology. Chinese Academy of Sciences State Key Lab of Processors,
Institute of Computing Technology. Chinese Academy of Sciences Key Laboratory of Al Safety, Chinese Academy Sciences UUniversity of Chinese Academy of Sciences, Beijing. China (wenzhuofan242 guishangtong21s hug.gi/fnnaaeeouugggggggoggggggo fengyang) @ict. ac. on
Abstract
Inference acceleration of large language models (LLMs) has been put forward in many application scenarios and speculative decoding has shown its advantage in addressing inference acceleration. Speculative decoding usually introduces a draft model to assist the base LLM where the draft model produces drafts and the base LLM verifies the draft for acceptance or rejection. final inference speed is decided by the decoding speed of the draft model and the acceptance rate of the draft provided by the draft model. Currently the widely used draft models usually generate draft tokens for the next several positions in a non-autoregressive way without considering the correlations between draft tokens. Therefore, it has a high decoding speed but unsatisfactory acceptance rate. In this paper, we focus on how to improve the performance of the draft model and aim to accelerate inference via high acceptance rate. To this end, propose CTC-based draft model which strengthens the correlations between draft tokens during the draft phase, thereby generating higher-quality draft candidate sequences. Experiment results show that compared to strong baselines, the proposed method can achieve higher acceptance rate and hence faster inference speed.
this framework, the
Introduction
Large Language Models (LLMs) have been applied to wide range of text generation tasks such as machine translation and question answering due to their remarkable performancel [1] 21 6 [T]. In many applications, LLMs is required to produce long generation give explanations its answer or perform chain of thought (CoT). Moreover, in some practical scenarios, I.LMs have to resort to other applications fulfill task under the frame of AI agents where LLMs usually generate long outputs to communicate with other applications. All of these have high demand for the inference speed of LLMs. However, bringing on the severe inference delay problem, which obstacles the real applications of LLMs.
LLMs employ token-by-token autoregressive generation paradigm,
To mitigate the inference latency of LLMs, speculative decoding is proposed and proves be more efficient decoding strategy compared with autoregressive generation [2] 4 Besides the base LLM, speculative decoding usually introduces drafter model in the working flow that the draft model generates candidates for the next several tokens and the base LLM verifies the candidate and decides to accept reject some criterion. Once accept, then the winner candidate will be used as the output, otherwise, the base L.LM will decode and generate the output. In this process, the draft
Corresponding author: Yang Feng
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

model usually has few parameters and hence produces generations at a faster speed. Meanwhile, the LLM can verify draft tokens parallelly and takes less time than generating the next several tokens by itself. As only the candidate is accepted at a high rate, the decoding speed can be improved. It can be derived that the final inference speed is related to the decoding speed of the draft model and the acceptance rate of the candidate selected out by the draft model. Nevertheless, there is trade-off for the draft model between its decoding speed and its performance related to acceptance rate.
Following the principle of speculative decoding, many works focus on optimizing the draft model 17 in which the methods based on non -on-atorrerresivve (NAR) generation have shown promising results. The NAR speculative decoding methods draft the next several tokens parallelly by predicting them independently based on the representation of the original LLM. Although these methods drafts at a high speed, they ignore the dependence between the next several tokens and sacrifice the performance as the cost. As a consequence, the speed of speculative decoding can be affected via the acceptance rate.
to accelerate inference T5 19
Based on these observations, we make efforts from the perspective of model performance by intro- ducing dependency relationships during draft generation, aiming at achieving a higher acceptance rate. At this end, we propose draft model based on Connectionist Temporal Classification(CTT algorithm [9] which generates drafts in a non-autoregressive way with additional blank and repetitive tokens participating in. As during training the CTC-based draft model will count all the possible candidates sequentially that can generate the given ground truth when calculating the probability of the ground truth, the candidates with better dependency relationships will achieve higher probabilities. As result, at inference the best candidate selected out by the CTC-based draft model will be more sequentially reasonable and hence can accepted at a higher rate, ultimately leading to faster inference. For the rest of this paper, we refer to CTC-drafter as CTC-based draft model for short. Experiments on MT-bench show that the proposed method able to draft sequences at a higher acceptance rate compared to strong baselines, thus achieving remarkable inference speedup.
Our contributions are as follows:
We introduce the CTC-based draft model to speculative decoding framework, to the best of our knowledge, which is the first to apply the CTC algorithm within the speculative decoding domain. This approach can not only generate drafts in non-autoregressive way but also introduce correlations between draft tokens through probability allocation.
Through experiments conducted on MT-bench and GSM8K using various LLMs as base models, we have demonstrated superior speedup ability of the CTC-based draft model compared to other speculative decoding improvement methods. These results prove the rationality and effectiveness of our method.
2 Background
Recent advancements have emerged from the innovative approach of Blockwise Decoding(12) 17). which introduced the seaft-then-veriige paradigm, leading to the development of Speculative Decoding [2] and Speculative Sampling(4) []. These methodologies offer promising avenues for enhancing the speed of Large Language Models (LLMs).
Speculative Decoding predicts multiple future tokens and verifies their accuracy within a single decoding step. Using greedy sampling as illustration: at step I, given initial prompt X and previously produced tokens у<r = yı, 1--1, a speculative sequence of length n. Be.....''e ke is generated by the draft model with respective probabilities p/...., P/.,......... The target LLM then computes the accurate probabilities Pt, ...: Pt+n in one pass during verification. Each token yf is evaluated in sequence, with its acceptance probability given by min(1, (iinn,,'///e p///p.). Upon rejection of token 1/.- subsequent tokens are disregarded, and the rejected token is re-sampled using the adjusted distribution P()) norm (max((, P(yslyes, X) P' (' (oll,,,, X))).
The effectiveness of Speculative Decoding significantly depends on designing an intelligent draft model for precise token prediction and devising an optimal strategy for token sequence verification (24. Consequently, current research efforts concentrate on these aspects to further exploit the potential of Speculative Decoding for speed acceleration.

---

2.1 Design of Draft Model
Many researchers have pursued the strategy of designing draft model that operates independently of
the base model [3
19 5 [33, such as employing non-autoregressive transformer for simultaneous token drafting 23 To ensure compatibility with the base model, works like [2] opt for draft models
with fewer parameters from the same model series.
However, independent draft models necessitate training or fine-tuning, posing flexibility issues when transitioning between hase models. Alternatively, some approaches rely on modifying the base model itself for token drafting through moderate adjustments 25| 26 I0]. For instance, [3] introduces an additional module comprised of linear layers atop the target LLM for drafting tokens independently for different positions. In contrast, [25] incorporates bypass within the LLM, allowing for earlier exits during the model's layer-by-laye computation.
2.2 Optimization of Verification
The strategy for compiling drafted tokens into candidate sequences and the criteria for sequence selection are vital during the verification stage. Initially, forming a single candidate sequence from the most probable tokens across positions the prevalent approach[16 [8]. To incorporate broader range of draft sequences, SpecInfer([4] organizes draft tokens into a tree structure, with paths from the root leaf nodes representing different candidate sequences. Regarding selection criteria, early methods only accepted sequences matching the target model's greedy decoding output [23]. Later, introduced Nucleus Sampling as more effective yet complex acceptance criterion.
2.3 Connectionist Temporal Classification
Connectionist Temporal Classification (CTC) is tailored for sequence prediction tasks, especially ap- plicable in speech and handwriting recognition[]] CTC expands the output space, V, by introducing a blank token c denoting "output nothing', creating an augmented space y" It defines function ((B) that maps any sample E Y to a subset of y", containing all valid alignments. Conversely, 8 processes aligmments from ) back to y by merging adjacent, repeated tokens and removing blanks, resulting in the target sentence.
The sequence-level CTC loss function offers superior context modeling capabilities compared to token-level alternatives and effectively manages variable-length outputs without necessitating alignment during training. The training objective leverages dynamic programming aggregate over all potential alignments a E y
log p(y) llog Σ p(a)
aEdy For inference, the model generates alignment a, from which repeated tokens and blanks are removed to yield the final output y = 3 (a).
CTC-drafter Model
In this section, we describe our implementation of the proposed model. CTC-drafter improves the acceptance rate of draft tokens while keeps extra investment of draft time in a reasonable duration, consequently achieving superior inference speedup. We first give an illustration of CTC-drafter's model structure, analyzing the functions of involved modules. Subsequently, we clarify CTC-drafter's training strategies and inference procedure.
3.1 Model Structure
Our CTC-drafter model structure are displayed in Figure I The training strategy is the upper part and the inference process is on the bottom part. The base model on the left side are the LLM desired to accelerate, which generally is composed of embedding layer, multiple attention transformer layers and a output LM head that maps the hidden states to probability in vocabulary dimension.
For the draft procedure, we insert an attention draft module which take the hidden states outputted from base model as input and predict the probability distributions of draft tokens. Here hidden states

---

Training
Base model prodiction
Base Model
Pox
Pox
Pox
Pos
Pos
Combinations
wi wi wi wl
22
m7
93
93
Calculation
L.M Head
M4
LM Heed
Transformer Layers xN
Attention Draf Medule
Optimize
Embedding
Raw Training Data Inpot
Inference
Base Model
Pos
my
L. Head
Top1
Top
Top
Top
Top
1.M Head
CTC Transform Module
Transformrr Layers XN
Hädden States
Attention Drafl Module
Current Step Generatione
Update
Embedding
Generation History: User: what your name! Assistant: hello.
Figure 1: Illustration of CTC-drafter model training and inference strategy.
represents the compressed feature sequence after multiple transformer layers. Inspired by 13, the inner construction Attention Draft Module is similar the base model, with one single transformer layer conducting prediction in parallel.
For the verify procedure, raw candidate sequences are acquired by combining draft tokens in different places. Different from Medusa 3 which cuts off a part of combinations prearranged, all the raw sequences keep the same length, containing possible draft tokens in each place. CTC Transform Module is designed to process all raw sequences. The module first removes consecutive duplicate tokens and blank character, namely & in Figure [ Then the attention map that is used in base model verification calculation is modified. Positions in the attention map that corresponds to tokens been removed CTC transform will masked.
3.2 Training
The basic training strategy of CTC-drafter displayed in Figure T We fixed the parameters of base model and trained the transformer layer in Attention Draft Module on ShareGPT dataset, which

---

is subset of Vicuna's training data. All input sequences are padded to the same max length, which is a predefined hyper parameter. Instead of conventional token-level cross entropy function that separately calculate the loss of each position, we use sequence-level CTC loss as the training objective. Note the input sequence as X and its corresponding label as Y, The dataset contains set of (X, Y) pair. The parameters of the trained draft model is noted as 0. Our training objective is optimizing 0 to maximize the probability of labels across the dataset:
f argmax
Σ P(Y
(2)
(XY)ED
Conventionally, the training labels can be acquired by simply shifting the input. To train CTC-drafter, we follow the knowledge distillation method to calculate Ydistall as labels Y in equation by inputting base model the origin data (28]. for the consideration that draft model can better match base model trained on distilled dataset. First, base model outputs the probability distribution Paistin (Y|X) in equation 3 and equation 4 trouugh multiple transformer layers and LM head, then we get distilled label
sentence Ydiststl by greedy decoding in equation
Fdistall = BaseModel(X)
(3)
Paistau (YIX) Softmax(LmMead| (Faistitt)
(4)
Ydistill =
argmax(Pdiettee (Y (X))
(5)
Y
Given labels, we use sequence-level CTC loss to model equation 2 Assume the set Ax,y contains all possible raw sequences A that be converted to Y after removing reduplicate tokens and blank
characters. Sum up all prohabilities of sequence in the set to get P(Y|X,0) (). Considering the time complexity, impractical enumerate all sequence. In Figure [ we briefly show the dynamic programming of traversing all routes to calculate training labels probability P( [X, 0) in equation The detailed algorithm discussed in 9
P(Y|X,0)
E P(A[X,0)
(6)
AEA(X.))
Further, the probability each sequence P(A token a; in the sequence with the independent assumption:
(0 0) equals to the product of probability of each
P(A 0) II p(ar(X,0)
A (01, 022 03 0t,
an)
(8)
The probability distribution of each token in the sentence is predicted by the transformer layer we added in draft module based on the hidden states outputted from base model as in equation 3
F DraftMoouleePPiian
P Xx 0) = Softmax (oftmax((mHeed(())) (')
(10)
P(Y X, 0) actually contains group of probability distribution of different places in the sentence. Locate the corresponding position P, P,(Y|X,0) 0) to calculate p(a,lXX00 0) in equation 7
MarlX, 0) P:(Y a,)X,0)
(11)
3.3 Inference
To clarify the inference speedup mechanism of CTC-drafter, we further explain this procedure in one specific decoding step with the decoding history "Usr: what is your name? Assistant: hello," as base model input. The input will first be passed through base model producing the hidden states and greedy sampling base token "my". Attention Draft Module takes the hidden states from last transformer layer as input, outputting probability distributions of different positions after base token after LM Head projection.
For every position, the top tokens are selected in descending order of probability, where predefined. In this instance, Attention Draft Module suggests that "name" is the best candidate token
5

---

Table 1: performance of average speedup ratio on MT-bennch.y represents the average speedup ratio for all evaluation questions relative Vanilla method, calculated by equation 13 represents the average number of accepted tokens per decoding step for all evaluation questions, calculated by equation 12
Vicuna-7B
Vicuna-13B
Vicuna-33IB
Speculation Method
B
Y
Y
B
MT-bench
Vanilla
1.00x
1.00
1.00x
1.00
1.00x
1.00
Medusa
2.13x
2.58
1.97x
2.60
1.93x
2.55
Hydra
2.36x
3.04
2.17x
3.06
2.15x
2.95
CTC-drafter
2.78x
3.56
2.52x
3.51
2.20x
3.53
GSM8K
Vanilla
1,00x
1.00
1.00x
1.00
1.00x
1.00
Medusa
2.33x
2.78
2.21x
2.68
2.10x
2.46
CTC-drafter 2.43x
3.53
2.66x
3.53
2.16x
3.40
right next to "My" while it is possible that blank character appears after "my" and the first draft token. Attempting cover more reasonable candidate sequences, tokens in each place with different probability are combined in token tree structure and a group of the most valuable combinations are reserved as the raw candidate sequences. The raw candidate sequences is refined in CTC Transform Module, removing repetitive tokens and blank character and modifying the attention map.
All candidates are verified parallelly in base model, the longest sequence that satisfies the criterion will be selected as current decoding step's output, which in this case is "my name is". The decoding history is updated according to the output. In one single decoding step, compared with autoregressive decoding which will only produces token "My", CTC-drafter enables multiple tokens to be outputted. thus reducing overall base model calculation steps and achieving speedup.
4 Experiments
4.1 Implementation Settings
We choose open-source Vicuna large language model [ with different parameter sizes as base model to conduct experiments. Vicuna models is fine-tuned on ShareGPT dataset based on LLaMA model, which are noted below as Vicuna-7b, Vicuna-13h and Vicuna-33b according different parameter sizes. We also conduct training on LLaMA-2-Clis base models, detailed in the Appendix.
We fix Vicuna model's parameters and train the transformer layer inside draft module ShareGPT dataset. The learning rate set to x 10 10-5 To avoid gradient explosion, we adopt gradient clipping, setting the clipping threshold to 0.5. We set the max length of training data 2048. All training tasks were executed on four 24GB NVIDIA GeForce RTX 3090 devices, taking around two days. To fully utilize graphics memory and accelerate training, load models with FP16 precision for quantization. For comparison, we also implemented Medusa 3 on Vicuna models, following suggested experiment settings and retrain the same ShareGPT dataset.
Trained models are evaluated on MT-bench and GSMSK datasets to assess the acceleration per- formance in various scenarios. MT-Bench is carefully curated benchmark that includes 80 high- quality, multi-turn questions covering 8 primary categories user prompts such as writing, roleplay and extraction[27] GSM8K contains 8.5K high quality linguistically diverse grade school math problems 7]]. Unlike some other datasets that offer base model questions with definitive answers such multiple-chois questions, the two selected evaluation datasets contain open-ended questions, requiring base model to output long sequence answers in multiple decoding steps.
For every question, we record the total number of tokens in its corresponding answer as N, the total inference time T and the base model decoding steps M. We calculate the average number of tokens accepted per decoding step and the inference speedup compared to vanilla base model without

---

Table 2: Performance of average speedup ratio on MT-bench for different model structures, repre- sents the average speedup ratio for all evaluation questions relative to Vanilla method, calculated by equation 13P S represents the average number of accepted tokens per decoding step for all evaluation questions, calculated by equation T2
CTC Verify
Medusa verify
Speculation method
Linear layer + Cross Entropy Loss
1.71x
2.38
2.13x
2.58
Transformer layer CTC Loss
2.78x
3.56
2.25x
3.02
speculative decoding:
N Accepted tokens
(12)
M
Tvanilla
T vanilll/ /N Nvanilla
speedup
(13)
Tspec
T Tspec/ /N
The average number of accepted tokens reflects models' ability to speculate candidate tokens. However, takes extra inference time to draft tokens. Thus, the speedup metries can be viewed as trade-off between speculation quality and extra time consumed.
4.2 Results and analysis
The performance of different speculation methods MT-bench and GSM8K showed in Table [ The speedup ratio of Medusa is evaluated following recommended setting in its corresponding technical report. The results of Hydra 2 on Vicuna models acquired from its corresponding paper. We also measures the performance of fully auto-regressive decoding with no speculation method as baseline to calculate speedup ratio of other three methods, noted Vanilla in Table
MT-bench. The results show that our proposed CTC-drafter achieves better draft quality on MT- bench compared other works, with more than three tokens been accepted per decoding steps. Higher predicting accuracy enables CTC-drafter to achieve speedup ratio of more than 2x, outperforming Medusa and Hydra all types of base model. Besides, the speedup performance of all speculation method is influenced as base model size increases. Possible explanation is that we can not significantly expand the size of draft module considering extra time consumed, when base model size increase, larger ability gap between base model and draft module makes it more difficult for draft module to imitate base model's prediction behavior. Therefore, the average number of accept tokens B of CTC-drafter decreases from 3.56 to 3.53, influencing the speedup performance.
GSM8K. Compared with MT-bench, questions in GSM8K mainly focus math category. As is shown on the bottom of Table []] our proposed CTC-drafter keep a superior speedup performance over Medusa for all base models. Besides, the speedup performance suffers to some extent for CTC-drafter in Vicuna-7B base model, compared with the performance
MT-bench. The main
reason is that we completely rely the comprehensive ability of origin base model to offer answers without fine-tuning on GSM8K training dataset. Fortunately, when the base model size increases to 13B, CTC-drafter maintains prediction accuracy, achieving 2.66x speedup. However, bridging the capability gap for Vicuna-33B is challenging, leading to a decline in performance.
4.3 Ablation experiments
In this part, list the results of ablation experiments and further analyze the working paradigm of CTC-drafter. First, we explore how each part of the model structure influences the acceleration performance in Table 2 Then we illustrate how the prediction ability varies across different categories
of test questions in Figure 2 Besides, to better visualize the trade-off between extra time consumption and prediction accuracy, the time consumption of each calculation procedure during inference is measured in F
Model structure. To better utilize the context information, CTC loss is used the training objective as discussed in Section 3.2, which optimizes the draft module under sequence-level supervision. Besides, we replace the linear layers of Medusa head with more complex transformer layer suit
7

---

So -brl 1i0230
3.5
preroga Nurber Accepted Takens Decod ng
331
3.0
2.5
235
2.0
1.5
1.0-
0.5
0.0
Poleplay
Wrkting
Reasoning
Math
Coding Question Categories
Extraction
Stem
Humanities
Overall
Figure 2: Average number of tokens accepted per decoding step in different question categories on MT-bench, with Vicuna-7B base model. The performance on Vicuna- 13B and Vicuna-33B is consistent with this result. The blue color represents CTC-drafter method, orange color represents Medusa method and green color represents baseline. All evaluation experiments are conducted on the same device.
CTC loss and better imitate the base model. For inference, the original token verification strategy is modified to include extra operations such as CTC transform and attention map modification.
To explore the speedup contribution of each part of modification as discussed above, we replace the draft module and verify module with the corresponding ones in Medusa and conduct experiments on the modified speculation methods. The results showed in Table with Vicuna-7B base model. this table, linear layer represents drafting tokens based on linear layers with cross-entropy Loss function training objective, which is adopted by Medusa. Transformer layer represents drafting tokens based on transformer layers with CTC loss as training objective, which is adopted by CTC-drafter. Medusa verify refers to vanilla token tree verification described in [14] CTC verify includes extra operations compared with Medusa verify including CTC transform of candidate sequences and attention map modification mentioned before.
Replacing linear layer with transformer layer and using CTC loss to design training loss function increase the average number of accepted tokens from 2.58 to 3.02. It is clear that with these two efforts combined, draft module guided to conduct attention across the whole input sentence instead of simply learning offsets of the last hidden states. However, blank characters and repeated tokens exist the candidate sequences spoil draft quality and speedup for models without CTC transform, decreases from 3.56 to 3.02 and 7 from 2.78x to 2.25x.
Question categories. We further explore how speedup performance varies on different question categories, showing in Figure 2 Both CTC-drafter and Medusa achieved the best prediction accuracy on coding category, which can be attributed the highly logical nature of the problems within this category. Among all categories, the acceptance rate of roleplay questions is slightly low for CTC-drafter, which may be due to the deficiency of questions of this category in our training datasets.
Time consumption. Compared with Medusa, it is unavoidable that our methods' draft strategy requires more complex calculations. We display each stage's time consumption throughout the whole inference decoding process in Figure 3 First, we replace the original medusa head with transformer layer to better fit the base model, which cause the time of draft model increases from 3.71% to 14.93%. Besides, for the need to dynamically process candidate sequences in each decoding round, CTC transform accounts for extra 5.36% of the overall decoding time consumption. Considering that the base model's calculation still account for the main part, it is acceptable that we increase the draft ability and thus reducing base model's 's decoding rounds, which balances the extra time consumption and achieve better speedup on the whole.

---

Figure 3: The percentage time consumed for different processes based on CTC CCTC-drafter(left) and (rdusa(right) speculation strategies. The "others" part mainly contains matrix operations involved in token tree verification.
Related Work
Medusa. After Speculative decoding 23 and Speculative sampling 12], many improvement works has been proposed to optimize the draft model and verification strategy. Among these, Medusa explores novel and efficient acceleration framework [3]. Instead using an independent model with fewer parameters the draft model, several Medusa Heads are added top of the last transformer layer of base model. The i-th Medusa Head is responsible for predicting the i-th token after the base model decoding token in each step. For each Medusa Head, top k tokens with highest probability are selected and combined in tree structure to form candidate sequences. Using tree mask method in validated in parallel during the next decoding step. Two strategies
[14, the multiple sequences are used for the training of Medusa Head: Medusa-1 fix the parameters of base model, optimize only the Medusa Head on small dataset, Medusa-2 adopt end-to-end training, fine-tuning base model and Medusa Head together on larger datasets. Although Medusa-2 can achieve remarkable inference speedup, the need of large training data and time consumption limits its generality across different base model. In this paper, we only implement and demonstrate Medusa-1 considering fairness.
Hydra. Modified from Medusa Head, Hydra designs Hydra Head, sequentially dependent, drop-in replacement for standard draft h2a A Hydra Head conduct prediction not only based on base model hidden states but also the decoding output of other Hydra Heads, which significantly improves speculation accuracy. Besides, some other tricks are adopted for further inference speedup including adding noise and knowledge distillation.
Conclusion and Future work
Speculation decoding and corresponding improvement works mostly draft candidate tokens without considering context information and generate fixed-length candidate sequences for verification, which not only influences the draft quality, bur also lacks generality across different large language models. In this paper, we propose novel framework named CTC-drafter based on CTC algorithm. Specifically, we use CTC loss as the training objective to model the context connection instead of cross entropy. We reconstruct the structure of draft model, using transformer layer to better fit base models. Besides, with CTC transform, we achieve adaptive candidate sequence generation which makes it convenient to transfer the framework across different base models. Nevertheless, our current work is subject to certain limitations that requires careful consideration. More training tricks can be explored to further enhance the prediction ability of draft module. Besides, it is still doubtful that whether the current draft model structure is optimal. What's more, different types large pretrained language model need to be adopted in proposed framework evaluate the acceleration performance of CTC-based draft model.
For the future work, we attempt to identify techniques to reduce the extra time consumed caused by more complex draft operations introduced. Other verification criteria such as Nuclear Sampling 4 can be integrated into our framework. What's more, some other methods such Conditional Random CCRF, (20) and Directed Acyclic Graph(DAG, (8) can be explored to model the context information when drafting tokens, remain these ideas for future work.

---

References
[1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, lige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidr, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 2023.
[2] Zachary Ankner, Rishab Parthasarathy, Aniruddha Nrusimha, Christopher Rinard, Jonathan Ragan-Kelley, and William Brandon. Hydra: Sequentaaly-depeedeem draft heads for medusa decoding, arXiv preprint arXiv:2402.0555 2024.
[3] Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, and Tri Dao. Medusa: Simple framework for accelerating Ilm generation with multiple decoding heads, 2023.
[4] Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint 230..01330000.111.. 2023.
[5] Ziyi Chen, Xiaocong Yang. Jiacheng Lin, Chenkai Sun, Jie Huang, and Kevin Chen- Chuan Chang. Cascade speculative drafting for even faster Ilm inference. arXiv preprint arXiv:2312.11462, 2023.
[6] Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E Gonzalez, et Vicuna: An open-source chatbot impressing gpt-4 with 90%* * chatgpt quality. See https://vicua. Imsys. org (accessed 14 April 2023), 2(3);6, 2023.
[7] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 14168, 2021.
[8] Jean C Digitale, Jeffrey N Martin, and Medellena Maria Glymour. Tutorial on directed acyelic graphs. Journal of Clinical Epidemiology, 142:264-266 2022.
[9] Alex Graves, Santiago Fernández, Faustino Gomez, and Jürgen Schmidhuber. Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks. In Proceedings of the 23rd international conference on Machine learning, pages 369-376, 2006.
[10] Coleman Hooper, Sehoon Kim. Hiva Mohammadzadeh, Hasan Gene, Kurt Keutzer, Amir Gholami, and Sophia Shao. Speed: Speculative pipelined execution for efficient decoding. arXiv preprint arXiv:2310. /2072, 2023.
[11] Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.06825, 2023.
[12] Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pages 19274-19286. PMLR, 2023.
[13] Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. Eagle: Speculative sampling requires rethinking feature uncertainty. arXiv preprint 2xxXi:2401.15077 2024.
[14] Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Rae Ying Yee Wong, Zhuoming Chen, Daiyaan Arfeen, Reyna Abhyankar, and Zhihao Jia. Specinfer: Accelerating generative IIm serving with speculative inference and token tree verification. arXiv preprint arXiv:2305.09781, 1(2):4, 2023.
[15] Benjamin Spector and Chris Re. Accelerating Ilm inference with staged speculative decoding. arXiv preprint arXiv:2308. 0066234,, 2023.
[16] Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit, Insertion transformer: Flexible sequence generation via insertion operations. International Conference on Machine Learning, pages 5976-5985. PMLR, 2019.
10

---

[17] Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit. Blockwise parallel decoding for deep autoregressive models. Advances in Neural Information Processing Systems, 31, 2018.
[18] Xin Sun, Tao Ge, Furu Wei, and Houfeng Wang. Instantaneous grammatical error correction with shallow aggressive decoding. arXiv preprini urXiv:2106.049770 2021.
[19] Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix Yu. Spectr: Fast speculative decoding via optimal transport. Advances in Neural Information Processing Systems, 36, 2024.
[20] Charles Sutton, Andrew McCallum, al. An introduction to conditional random fields. Foundations and Trends@ in Machine Learning, 4(4):267-373, 2012.
[21] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et Llama: Open and efficient foundation language models. arXiv preprint arXiv:23002. 13371, 2023.
[22] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXii:2307.099000 2023.
[23] Heming Xia, Tao Ge. Peiyi Wang, Si-Qing Chen, Furu Wei, and Zhifang Sui. Speculative decoding: Exploiting speculative execution for accelerating seq2seq generation. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 3909-3925, 2023.
[24] Heming Xia, Zhe Yang, Qingxiu Dong, Peiyi Wang, Yongqi Li, Tao Ge, Tianyu Liu, Wenjie Li, and Zhifang Sui. Unlocking efficiency in large language model inference: A comprehensive survey of speculative decoding. arXiv preprint arXiv:2401.0785. 2024.
[25] Seongjun Yang, Gibbeum Lee, Jaewoong Cho, Dimitris Papailiopoulos, and Kangwook Lee. Predictive pipelined decoding: A compute-lateney trade-off for exact Ilm decoding. arXiv preprint arXiv:2307.05908 2023.
[26] Jun Zhang, Jue Wang, Huan Li, Lidan Shou, Ke Chen, Gang Chen, and Sharad Mehrotra. Draft & verify: Lossless large language model acceleration via self-speculative decoding. arXiv preprint arXiv:2309.0816 2023.
[27] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, al. Judging llm-as-a-judge with mt-bench and chatbot arena. Advances in Neural Information Processing Systems, 36, 2024.
[28] Yongchao Zhou, Kaifeng Lyu, Ankit Singh Rawat, Aditya Krishna Menon, Afshin Ros- tamizadeh, Sanjiv Kumar, Jran-oras Kagy, and Rishabh Agarwal. Distillspec: Improving speculative decoding via knowledge distillation. arXiv preprint arXiv:2310.0846 2023.

---

Speedup Across Defferen Mode
2.5
2122
2.23
2.42
Monr Ta
Mounk 4
Mode
wo Ta
age
The Average hur Accepted Thkkns per Decoding Steps Acroos Diferent Midel Types and Staes
4.-
1:4
Wob 10
Figure 4: The bar charts of speedup ratio relative to vanilla method ((tpp) and average number of tokens accepted per decoding step (bottomm) across different model types and sizes with CTC-drafter. The blue bar represents performance on MT-bench and the orange bar represents GSM8K. All evaluation experiments are conducted on the same devices.
A Appendix
To evaluate the generality of our method across different base models, add supplementary experiments on LLaMA-2-Chal base models(22), We select LLaMA-2-CHE 7b and 13b as base models and evaluate CTC-drafter's performance MT-bench and GSM8K. For clear comparison, the evaluation results of various base models, including Vicuna, are documented in Figure
CTC-drafter maintains ideal performance when transferring from Vicuna models to LLaMA-2-Chat models, only slight decline when compared the evaluation results on Vicuna-7b and LLaMA-2-chatt 7b. Besides, it should be noted that increasing the size of the LLaMA-2- compromise draft quality, while enhancing speedup performance. This trend diverges from Vieuna base models, potentially due to distinct inference paradigms inherent in both models.
model to 13b does not
12

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In Section 3(CTC-drafter) we illustrate our contributions for novel acceleration framework design. In Section 4(Experiments) experimental results showed support our contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
In Section we discuss the limitations of our work and leave these for future work.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: In Section 3.2, we declare the training objective with full set of assumptions and complete (and correct) proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Section 4. (Implementation Settings) we provide the main settings and steps train the models and conduct evaluation.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification:
We provide the code in Supplementary Material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ praips.cc/publiccguuieeee CoodeSumeeieeeeee ssi iessonPolll mollicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section 4. (Implementation Settings) we provide the main settings and steps train the models and conduct evaluation.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: ments.
section 4(Experiments), we discuss the statistical significance of the experi-
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Section 4. 4lmmmmmemnnttaio Settings), we discuss the devices we use and time consumption.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The research conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
In Section 1(Introduction) we discuss potential societal impacts of our work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: All pretrained language models and datasets use is open-source without high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All models and datasets we use are cited and credited properly.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemoodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
18

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
19


Reviews:
[{"review_id": "HcHYnH9sEY", "reviewer": "Reviewer_EXv7", "summary": "The paper proposes a novel framework, CTC-drafter, to accelerate speculative decoding in large language models (LLMs). The authors introduce the use of Connectionist Temporal Classification (CTC) as a training objective, replacing the traditional cross-entropy loss. This method aims to improve context modeling and generate adaptive candidate sequences, which purportedly enhances the speed and accuracy of the speculative decoding process. The paper demonstrates the effectiveness of CTC-drafter through experiments on various benchmarks and compares its performance with existing methods such as Medusa and Hydra.", "questions": "1. Can the authors provide more details on the hyperparameter settings and training configurations used in the experiments?\n\n2. How does the performance of CTC-drafter vary with different model architectures and dataset sizes?\n\n3. Can the authors elaborate on the computational overhead introduced by the CTC loss and how it compares to the benefits in inference speed?", "limitations": "The authors have discussed several limitations, including the need for more training tricks to enhance the draft module and the uncertainty regarding the optimality of the current draft model structure.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Originality: Introducing CTC as a training objective for speculative decoding is a novel approach.\n\n- Quality: The theoretical framework is well-developed, with clear definitions and derivations.\n\n- Clarity: The paper is generally well-written and logically structured, making it accessible to a broad audience.", "weaknesses": "- Experimental Validation: The experiments do not fully validate the claims. There is a need for more extensive testing across different datasets and model architectures to ensure the generality and robustness of the proposed method.\n\n- Comparative Analysis: While comparisons are made with Medusa and Hydra, the analysis lacks depth. More detailed insights into why \n\n- CTC-drafter performs better or worse in specific scenarios would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the insightful comments and constructive suggestions.\n\n$\\textbf{R1. More details on the hyperparameter settings and training configurations used in the experiments (Q1). }$ \n\nThe main training configurations are listed in Section 4.1 including learning rate, gradient clipping threshold and the max length of training data, which is relatively crucial to the reproduction of experiment results. In this part we clarify other hyperparameters involved in the training of CTC-drafter. The total training number of epoch is set to 20. Uniform noise is added to enhance the robustness of CTC-drafter. AdamW optimizer is selected with $\\beta_{1} = 0.9$ and  $\\beta_{2} = 0.95$. For the settings of CTC loss, we choose the token <unk> in the vocabulary to represent blank token $\\epsilon$ of CTC algorithm.We will add these details in the next version.\n\n$\\textbf{R2. How does the performance of CTC-drafter vary with different model architectures and dataset sizes?(Q2) }$ \n\nRegarding your concern about the different model structures, we would appreciate more clarification. Are you referring to the base model that requires acceleration, or the draft model used for speculation? To cover all bases, we provide an explanation for both aspects. \n\nFor base model, we evaluate the performance in Vicuna-7b, Vicuna-13b and Vicuna-33b in Table 1. The architecture of base model is the same as Medusa and Hydra for fair comparison. CTC-drafter outperforms other draft models in base models of all sizes. We also added evaluation experiments on MT-bench with LLaMA2-Chat as base models to ensure the generality and robustness. The results are displayed as follow. CTC-drafter keeps a desirable speedup performance when transferring to LLaMA2-Chat-7b. The results on LLaMA2-Chat-13b and LLaMA2-Chat-70b will be included in our next version.\n\n| Base models | Speedup $\\beta$ | Token acceptance rate $\\gamma$ |\n|:------------------|:--------------------:|:-------------------:|\n| Vicuna-7b      | 2.99×                          | 3.73                                  |\n| Vicuna-13b     | 2.52×         | 3.70                         |\n| Vicuna-33b     | 2.20×         | 3.53                         |\n| LLaMA2-Chat-7b    | 2.33×         | 3.24                         |\n\nFor draft model, we modify the components to construct different structures and conduct evaluation in ablation experiment. The results are demonstrated in Table 2. It shows that with CTC loss and CTC blank-collapse, draft module is guided to conduct attention across the whole input sentence instead of simply learning offsets of the last hidden states. For fair comparison, the training dataset we choose is still ShareGPT, which contains 68000 dialogues and is also used in Medusa and Hydra. However, we introduce a new evaluation dataset GSM8K beside MT-bench to further elaborate the validity of CTC-drafter. The results on different evaluation datasets are recorded in Table 1. CTC-drafter achieves desirable speedup performance on both datasets, showing its generality.\n\n$\\textbf{R3. Comprehensive and in-depth comparative analysis with Medusa and Hydra (W2). }$ \n\nBased on the observation that currently the widely used draft models usually generate draft tokens for the next several positions in a non-autoregressive way without considering the correlations between draft tokens, we introduce CTC modeling strategy into draft model to strengthen the correlations between draft tokens during the draft phase, thereby generating higher-quality draft candidate sequences. Main experiment results on MT-bench and GSM8K (Table 1) reflect the performance improvement compared with Medusa and Hydra. Higher draft accuracy contributes to better speedup while the speedup performance of all speculation method is influenced by the larger ability gap as base model size increases. \n\nTo further evaluate performance in specific scenarios, we further explore how speedup varies on different question categories, showing in Figure 2. CTC-drafter is relatively difficult to deal with Roleplay question, which may be due to the deficiency of questions of this category in our training datasets. \n\nCompared with Medusa and Hydra, it is unavoidable that our methods’ draft strategy requires more complex calculations. We display each stage’s time consumed throughout the whole inference decoding process in Figure 3. Although extra time added in one single decoding step, the overall decoding steps are decreased for better draft quality. It is acceptable to increase the draft ability and thus reducing base model’s decoding rounds, which balances the extra time consumption and achieve better speedup on the whole.\n\nAbove is the comprehensive analysis based on the experiments for our work. If you have any suggestions for additional aspects that could be included, we would be most grateful to hear them and would be delighted to incorporate them in the next version.\n\n$\\textbf{R4. The computational overhead introduced by CTC loss and how it compares to the benefits in inference speed? (Q3). }$ \n\nWe would like to clarify that the time-consuming CTC loss calculation is conducted only during training, while not at inference. When inference, extra computational overhead related to CTC includes first removing consecutive duplicate tokens and blank character ϵ and then modifying attention map used in base model verification. The detailed computational overhead at inference is elaborated in Figure 3. The computational overhead introduced by CTC discussed above is noted as CTC transform in the Figuren3. Compared with Medusa, \nthe drafting of our method takes more time while it provides a better draft and leads to a higher acceptance rate by base model. Considering that the calculation of base model still accounts for the main overhead, our method achieves better speedup on the whole.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dlpctj4aEM", "reviewer": "Reviewer_6n7r", "summary": "The authors study the setup of speculative decoding where multiple tokens are being generated at parallel. \nIn this setup the authors use the idea of connectionist temporal classification to train a draft model which generates multiple tokens in parallel.", "questions": "See weakness section", "limitations": "The authors have listed some weaknesses however it is not clear the cases where the idea will fail. \n\nSpecifically how dependent is data drift between training the draft model and inference.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The method shows significant improvement in token acceptance rates. \n\n- The speedups reported are quite impressive.", "weaknesses": "- The speedups are unclear, it is calculated using the token acceptance rate rather than on a real system\n\n- Details are not clear about at what layers the authors are taking the intermediate representation \n\n- The details of training overhead are unclear\n\n- It will be great if authors can compare to - Draft & Verify: Lossless Large Language Model Acceleration via Self-Speculative Decoding", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the insightful comments and constructive suggestions.\n\n$\\textbf{R1. Evaluate the speedup on a real system(W1). }$ \n\nWe measured the speedup not only using the token acceptance rate(denoted as $\\gamma$), but also the inference speedup which is conducted on a real system(denoted as $\\beta$). In Section 4.1, we clarify the calculation of these two items in equation(12) and equation(13). For inference speedup $\\beta$, we first record the average decoding time for each token of base model without speculation method ${\\bar{T}}_{vanilla}$. Then measure the average time of models with different speculation methods \n\n${\\bar{T}}_{spec}$. The speedup is gained by dividing these two average values. All evaluations are conducted on the same device, which reflects performance of a real system. The speedup performance of different draft methods on MT-bench and GSM8K is displayed in Table 1. CTC-drafter shows superior speedup performance on a real system compared with Medusa and Hydra. \n\n$\\textbf{R2. At what layers the intermediate representation are taken? (W2) }$ \n\nAll the intermediate representation are taking from the last transformer layer of base model which covers the complete hidden states. The intermediate representation is then transferred as the input of draft module to generate candidate sequences.\n\n$\\textbf{R3. Details about the training overhead(for W3 and Q3). }$ \n\nSimilar to Figure 3 which displays the inference overhead, we give each stage’s time consumed throughout the whole training process as follow. Besides the conventional forward and back propagation which accounts for the main overhead, the calculation of CTC loss and label process are two additional steps that consume extra training time. \n| Forward Propagation | Label Process| CTC loss calculation| Back Propagation | Others |\n|:------------------|:--------------------:|:--------------------:|:--------------------:|:--------------------:|\n| 26.50%   |    6.01%      |    12.72%      |    54.06%      |    0.71%      |\n\nWe follow the dynamic programming calculation of CTC loss to aggregate over all potential alignments that ultimately form the label sequence after CTC blank-collapse. To enable parallel label supervision, complete label sequences are sliced to short pieces and then be used in the calculation of CTC loss. These two extra stages are necessary when using CTC loss as training objective, causing additional training overhead.\n\nBesides, we list some main experimental environment settings in Section 4.1. In detail, for training task in Vicuna-7b, forward propagation and gradient upgrade were conducted on each device, following data parallelism. For Vicuna-13b, every two devices support one training process. For Vicuna-33b, all four devices are utilized together to conduct training following model parallelism. For base models of these three sizes, we uniformly set the max number of training epoch to 20. In practice, the models approach convergence after approximately 8 epochs. It takes around two days to train draft module for Vicuna-7b and Vicuna-13b. The training time consumed increase for Vicuna-33b, which is around four days.\n\n\n$\\textbf{R4. Comparison with Draft and Verify (W4). }$ \n\nDraft & Verify: Lossless Large Language Model Acceleration via Self-Speculative Decoding presents an impressive plug-and-play and cost-effective solution for inference acceleration with Skipped Layer and Draft-Exiting mechanism. It focuses on base model itself to draft tokens without additional draft module, which is distinct from our work. \nWe have conducted evaluation experiments with llama-2-chat-13B as the base model and compared the speedup performance with Draft & Verify. The results are displayed as follow, with the temperature is set to 0. Due to time limitation, the results of evaluations on base models of other types like llama-2-13B will be included in our next version. \n\n| Draft method | Speedup $\\beta$ |\n|:------------------|:--------------------:|\n| CTC-drafter   |    2.334×      |\n| Draft /& Verify       |    1.409×      | \n\nSince CTC-drafter introduces extra draft module compared with Draft & Verify, higher speedup performance can be viewed. However, it is a novel idea that considering skipped-layers for CTC-drafter. We will further explore possible improvement when introducing these mechanisms in our future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lc48OogF4K", "reviewer": "Reviewer_NRvU", "summary": "The paper proposes a novel architecture and training technique for LLM speculative decoding, aiming to improve the reliability and acceptance rate of generation candidates. Unlike Medusa, the proposed method replaces the draft module with a Transformer and utilizes CTC-based loss instead of CE loss. For CTC training, pseudo-labels generated from the base model, rather than ground-truth tokens, are used. During inference, the draft head generates probability candidates, and the CTC beam search process produces the final candidates for evaluation. Experimental results show that the CTC-drafter achieves higher speedup due to an increased acceptance rate and a greater number of accepted tokens.", "questions": "* How many beams are used for CTC decoding? Is the number of beams (or candidates) the same as in Medusa, ensuring a fair comparison?\n* The architecture of the Attention Draft Model is somewhat difficult to understand. Does it take a single hidden embedding vector as input? Is this vector expanded (duplicated? or repeated?) to create an input sequence for the Transformer-based draft model? What is the input of the Transformer-based draft model, and are positional encodings inserted at the beginning?\n* The explanation of the CTC-related part could be improved. For example, it would be helpful to mention that different candidates can be expanded to multiple \"alignments\" before the CTC blank-collapse.", "limitations": "The paper adequately addresses the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Combining CTC loss with sequence prediction in text-only LLMs is an interesting approach that could inspire further research.\n* The results suggest that CTC-drafter is promising in terms of inference acceleration without significant overhead.", "weaknesses": "* CTC is known to suffer from the conditional independence problem, i.e., each token's prediction does not depend on other tokens. Given this, it is unclear how CTC can address the low acceptance rate. The Hydra paper emphasized the importance of token-level sequential dependency, but CTC loss does not seem to support this due to its conditional independence. This is a critical point for the paper’s motivation, so a thorough justification of CTC loss is necessary.\n* Is the CTC output decoding during inference the same as the well-known CTC prefix beam search? If so, it should be clarified that this is known as prefix search decoding.\n* There is no ablation study on (Transformer Layer + CE loss) or (Linear layer + CTC loss). It is unclear which changes contribute more to performance improvements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the insightful comments and constructive suggestions.\n\n$\\textbf{R1.Ablation study of draft model structure. (W3)}$ \n\nThank you for the constructive suggestions. We add ablation experiments with modified draft model structure (Transformer Layer + CE loss) and (Linear layer + CTC loss) to evaluate which part contribute more to performance improvements.\n| Draft model structure | Speedup $\\beta$ | Token acceptance rate $\\gamma$ |\n|:------------------|:--------------------:|:-------------------:|\n| Linear layer + Cross Entropy Loss + CTC Verify      | 1.71×                          | 2.38                                  |\n| Linear layer + Cross Entropy Loss + Medusa Verify     | 1.94×         | 2.53                         |\n| Transformer layer + CTC Loss + CTC Verify     | 2.99×         | 3.73                         |\n| Transformer layer + CTC Loss + Medusa Verify    | 2.25×         | 3.02                         |\n| Linear layer + CTC Loss + CTC Verify   | 1.52×         | 2.07                         |\n| Transformer layer + Cross Entropy Loss + Medusa Verify        | 1.98×         |  2.77                        |\n\nTwo observations are listed as follow:\n1. Based on the results of evaluation on (Linear layer + Cross Entropy Loss + Medusa Verify) and (Linear layer + CTC Loss + Medusa Verify): CTC loss could not match well with linear layer and obvious performance decrease happens. \n2. Based on the results of evaluation on (Linear layer + Cross Entropy Loss + Medusa Verify) and (Transformer layer + Cross Entropy Loss + Medusa Verify): replacing linear layer with transformer layer could contribute to more precise draft prediction while more complex calculation of transformer layer obstructing the overall speedup.\n\n$\\textbf{R2. Discussions about the conditional independence problem of CTC (W1 and Q3).}$ \n\nAlthough the draft model with CTC loss conducts prediction independently in a non-autoregressive manner at each time step, that is also known as the conditional independence, during training it employs dynamic programming to count all the possible generated candidate sequences which can derive ground truth and then adjust the probability distribution to make these possible candidates distributed the greatest probability. In this way, the generated candidate that can derive ground truth most likely, which can also be thought to have the most reasonable sequence dependency, will be selected out by the draft model and meanwhile will be accepted by the base model at a higher rate.\n\n\nThe motivation that we combine CTC algorithm into speculation prediction for text-only LLMs is based on the observation that Medusa actually adopt a fully non-autoregressive decoding strategy to generate candidates: Each Medusa head independently generates tokens of the same position without depending on tokens from other medusa heads. During training, it only uses cross-entropy loss as the training objective which only performs word-level matching and cannot introduce sequence-level dependency, hence the quality of the draft is affected. In contrast, CTC-loss introduces sequence-level dependency via adjusting probability distribution, so it provides a better solution to the conditional independence problem existing in Medusa.\n\n\n$\\textbf{R3. Detailed explanation of decoding method (W2 and Q1).}$  \n\nFor the the decoding of CTC-drafter, we first generate original sequences based on the Token-tree used in Medusa, then conduct CTC blank-collapse on the generated original sequences to acquire candidate sequences of different lengths. Here CTC-drafter and Medusa keep the same number of 42 candidate beams, ensuring a fair comparison. This decoding method can better fit the scenarios of speculation decoding.\n\n\nWe've tried prefix beam search to generate candidate sequences at first. However, this decoding method is time-consuming, reducing the inference speedup dramatically. What's more, the sequences generated from prefix beam search lack diversity, which leads to relatively low acceptance rate. \n\n$\\textbf{R4.Explanation of architecture of the Attention Draft Model (Q2).}$ \n\nThe internal structure of the Attention Draft Module is similar with that of the base model, using a single transformer layer that takes the hidden states from the last transformer layer of the base model as input and performs prediction in parallel. \n\nCurrently, we do not consider expanding the vector. Original sequences are generated based on a token-tree, which is the same as Medusa, and then candidate sequences of varying lengths are obtained after CTC blank-collapse. \n\nThe rotary positional encodings are inserted at the beginning of the draft module, following the base model’s configuration.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper applies the Connectionist Temporal Classification (CTC) approach to draft model training and inference in speculative decoding. By incorporating CTC, the draft model considers all possible candidate sequences that could generate the target during training, leading to better candidate generation during inference and a higher acceptance rate. The proposed method demonstrates significant speedup compared to previous approaches across several benchmarks. All reviewers agreed that this paper is above the acceptance threshold.
Decision: Accept (poster)