Speculative Decoding with CTC-based Draft Model for LLM Inference Acceleration

Authors: zhuofan  wen
shangtong  gui
yang  feng
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:13:27

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.

Main paper: 
 introduction: 
 Large Language Models (LLMs) have been applied to a wide range of text generation tasks such as machine translation and question answering due to their remarkable performance [1, 21, 6, 11] . In many applications, LLMs is required to produce a long generation to give explanations to its answer or perform chain of thought (CoT). Moreover, in some practical scenarios, LLMs have to resort to other applications to fulfill a task under the frame of AI agents where LLMs usually generate long outputs to communicate with other applications. All of these have a high demand for the inference speed of LLMs. However, most LLMs employ a token-by-token autoregressive generation paradigm, bringing on the severe inference delay problem, which obstacles the real applications of LLMs.To mitigate the inference latency of LLMs, speculative decoding is proposed and proves to be a more efficient decoding strategy compared with autoregressive generation [12, 4] . Besides the base LLM, speculative decoding usually introduces a 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 or reject at some criterion. Once accept, then the winner candidate will be used as the output, otherwise, the base LLM will decode and generate the output. In this process, the draft 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 a 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 to accelerate inference [15, 19, 5, 17] in which the methods based on non-autoregressive (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.Based on these observations, we make efforts from the perspective of model performance by introducing dependency relationships during draft generation, aiming at achieving a higher acceptance rate. At this end, we propose a draft model based on Connectionist Temporal Classification(CTC) 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 a result, at inference the best candidate selected out by the CTC-based draft model will be more sequentially reasonable and hence can be 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 is able to draft sequences at a higher acceptance rate compared to strong baselines, thus achieving remarkable inference speedup.Our contributions are as follows:1. 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 a non-autoregressive way but also introduce correlations between draft tokens through probability allocation.2. 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. 
background: 
 Recent advancements have emerged from the innovative approach of Blockwise Decoding [17] , which introduced the draft-then-verify paradigm, leading to the development of Speculative Decoding [12] 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 an illustration: at step t, given an initial prompt X and previously produced tokens y <t = y 1 , ..., y t-1 , a speculative sequence of length n, y ′ t , ..., y ′ t+n , is generated by the draft model with respective probabilities p ′ t , ..., p ′ t+n . The target LLM then computes the accurate probabilities p t , ..., p t+n in one pass during verification. Each token y ′ i is evaluated in sequence, with its acceptance probability given by min(1, p ′ t /p t ). Upon rejection of a token y ′ i , subsequent tokens are disregarded, and the rejected token is re-sampled using the adjusted distribution P (y i ) = norm(max(0, P (y i |y <i , X) -P ′ (y i |y <i , 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.Many researchers have pursued the strategy of designing a draft model that operates independently of the base model [15, 19, 5, 13] , such as employing a non-autoregressive transformer for simultaneous token drafting [23] . To ensure compatibility with the base model, works like [12] 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 base models. Alternatively, some approaches rely on modifying the base model itself for token drafting through moderate adjustments [3, 25, 26, 10] . 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 a bypass within the LLM, allowing for earlier exits during the model's layer-by-layer computation.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 was the prevalent approach [16, 18] . To incorporate a broader range of draft sequences, SpecInfer [14] organizes draft tokens into a tree structure, with paths from the root to leaf nodes representing different candidate sequences. Regarding selection criteria, early methods only accepted sequences matching the target model's greedy decoding output [23] . Later, [4] introduced Nucleus Sampling as a more effective yet complex acceptance criterion.Connectionist Temporal Classification (CTC) is tailored for sequence prediction tasks, especially applicable in speech and handwriting recognition [9] . CTC expands the output space, Y, by introducing a blank token ϵ denoting 'output nothing', creating an augmented space Y * . It defines a function β(y) that maps any sample y ∈ Y to a subset of Y * , containing all valid alignments. Conversely, β -1 processes alignments from Y * back to Y by merging adjacent, repeated tokens and removing blanks, resulting in the target sentence. For inference, the model generates alignment a, from which repeated tokens and blanks are removed to yield the final output y = β -1 (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.Our CTC-drafter model structure are displayed in Figure 1 . The training strategy is on the upper part and the inference process is on the bottom part. The base model on the left side are the LLM we desired to accelerate, which generally is composed of an 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 represents the compressed feature sequence after multiple transformer layers. Inspired by [13] , the inner construction of Attention Draft Module is similar to 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 as prearranged, all the raw sequences keep the same length, containing possible draft tokens in each place. A CTC Transform Module is designed to process all raw sequences. The module first removes consecutive duplicate tokens and blank character, namely ε in Figure 1 . 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 in CTC transform will be masked.The basic training strategy of CTC-drafter is displayed in Figure 1 . We fixed the parameters of base model and trained the transformer layer in Attention Draft Module on ShareGPT dataset, which is a subset of Vicuna's [6] 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 D contains a set of (X, Y ) pair. The parameters of the trained draft model is noted as θ. Our training objective is optimizing θ to maximize the probability of labels across the dataset:EQUATIONConventionally, the training labels can be acquired by simply shifting the input. To train CTC-drafter, we follow the knowledge distillation method to calculate Y distill as labels Y in equation 2 by inputting base model the origin data [28] , for the consideration that draft model can better match base model if trained on distilled dataset. First, base model outputs the probability distribution P distill (Y |X) in equation 3 and equation 4 trough multiple transformer layers and LM head, then we get distilled label sentence Y distill by greedy decoding in equation 5:EQUATIONEQUATIONGiven labels, we use sequence-level CTC loss to model equation 2. Assume the set A X,Y contains all possible raw sequences A that can be converted to Y after removing reduplicate tokens and blank characters. Sum up all probabilities of sequence in the set to get P (Y |X, θ). Considering the time complexity, it is impractical to enumerate all sequence. In Figure 1 , we briefly show the dynamic programming of traversing all routes to calculate training labels probability P (Y |X, θ) in equation 6.The detailed algorithm is discussed in [9] .EQUATIONFurther, the probability of each sequence P (A|X, θ) equals to the product of probability of each token a i in the sequence with the independent assumption:EQUATIONA = (a 1 , a 2 , a 3 , . . . , a t , a t+1 , . . . , a n ) (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: EQUATIONEQUATIONEQUATIONTo 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 k tokens are selected in descending order of probability, where k is predefined. In this instance, Attention Draft Module suggests that "name" is the best candidate token Table 1 : performance of average speedup ratio on MT-bench.γ represents the average speedup ratio for all evaluation questions relative to 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-33B γ β γ β γ βVanilla [6] 1.00× 1.00 1.00× 1.00 1.00× 1.00 Medusa [3] 2.13× 2.58 1.97× 2.60 1.93× 2.55 Hydra [2] 2.36× 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.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: In Section 3.2, we declare the training objective with full set of assumptions and a 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a 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. 
implementation settings: 
 We choose open-source Vicuna large language model [6] 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-13b and Vicuna-33b according to different parameter sizes. We also conduct training on LLaMA-2-Chat base models, detailed in the Appendix.We fix Vicuna model's parameters and train the transformer layer inside draft module on ShareGPT dataset. The learning rate is set to 3 × 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 to 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, we load models with FP16 precision for quantization.For comparison, we also implemented Medusa [3] on Vicuna models, following suggested experiment settings and retrain on the same ShareGPT dataset.Trained models are evaluated on MT-bench and GSM8K datasets to assess the acceleration performance in various scenarios. MT-Bench is a carefully curated benchmark that includes 80 highquality, multi-turn questions covering 8 primary categories of 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 as multiple-choice 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 EQUATION)The average number of accepted tokens reflects models' ability to speculate candidate tokens. However, it takes extra inference time to draft tokens. Thus, the speedup metrics can be viewed as a trade-off between speculation quality and extra time consumed.The performance of different speculation methods on MT-bench and GSM8K are showed in Table 1 . The speedup ratio of Medusa is evaluated following recommended setting in its corresponding technical report. The results of Hydra [2] on Vicuna models are 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 as Vanilla in Table 1 .MT-bench. The results show that our proposed CTC-drafter achieves better draft quality on MTbench 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 2×, outperforming Medusa and Hydra on 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 β of CTC-drafter decreases from 3.56 to 3.53, influencing the speedup performance.GSM8K. Compared with MT-bench, questions in GSM8K mainly focus on math category. As is shown on the bottom of Table 1 , 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 in MT-bench. The main reason is that we completely rely on 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.66× speedup. However, bridging the capability gap for Vicuna-33B is challenging, leading to a decline in performance.In this part, we 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 Figure 3 .Model structure. To better utilize the context information, CTC loss is used as 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 to suit CTC loss and better imitate the base model. For inference, the original token tree 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 are showed in Table 2 , with Vicuna-7B as base model. In this table, linear layer represents drafting tokens based on linear layers with cross-entropy Loss function as 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 as 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 is 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 in the candidate sequences spoil draft quality and speedup for models without CTC transform, β decreases from 3.56 to 3.02 and γ from 2.78× to 2.25×.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 to 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.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, the 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 decoding rounds, which balances the extra time consumption and achieve better speedup on the whole. 5 Related WorkMedusa. 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 a novel and efficient acceleration framework [3] . Instead of using an independent model with fewer parameters as the draft model, several Medusa Heads are added on 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 Hydra. Modified from Medusa Head, Hydra designs Hydra Head, a sequentially dependent, drop-in replacement for standard draft heads [2] . 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.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: In Section 4.1(Implementation Settings) we provide the main settings and steps to 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 a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is 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 to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions 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) If the contribution is primarily a 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 be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case 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 to have some path to reproducing or verifying the results. 
open access to data and code: 
 Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We provide the code in Supplementary Material. Guidelines:• The answer NA means that paper does not include experiments requiring code. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 a 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 of large pretrained language model need to be adopted in our proposed framework to 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 as Conditional Random Field(CRF, [20] ) and Directed Acyclic Graph(DAG, [8] ) can be explored to model the context information when drafting tokens, we remain these ideas for future work.  
broader impacts: 
 Question: Does the paper discuss both potential positive societal 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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 a 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 or 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: All pretrained language models and datasets we use is open-source without a high risk for misuse.Guidelines:• The answer NA means that the paper poses no 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?Answer: [Yes] Justification: All models and datasets we use are cited and credited properly.Guidelines:• The answer NA means that the paper does not 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 a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • 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 is not available online, the authors are encouraged to reach out to the asset's creators. 
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/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
crowdsourcing 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 as 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 in the supplemental material is fine, but if the main contribution 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. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?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. • Depending on 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. 
 
 Appendix: To evaluate the generality of our method across different base models, we add supplementary experiments on LLaMA-2-Chat base models [22] . We select LLaMA-2-Chat 7b and 13b as base models and evaluate CTC-drafter's performance on MT-bench and GSM8K. For a clear comparison, the evaluation results of various base models, including Vicuna, are documented in Figure 4 .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-chat-7b. Besides, it should be noted that increasing the size of the LLaMA-2-Chat model to 13b does not compromise draft quality, while enhancing speedup performance. This trend diverges from Vicuna base models, potentially due to distinct inference paradigms inherent in both models.NeurIPS Paper Checklist Justification: In Section 6 we discuss the limitations of our work and leave these for future work.Guidelines:• The answer NA means that the paper has no 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 a 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 of 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- Comparative Analysis: While comparisons are made with Medusa and Hydra, the analysis lacks depth. More detailed insights into why 

- CTC-drafter performs better or worse in specific scenarios would be beneficial.
questions: questions: 1. Can the authors provide more details on the hyperparameter settings and training configurations used in the experiments?

2. How does the performance of CTC-drafter vary with different model architectures and dataset sizes?

3. Can the authors elaborate on the computational overhead introduced by the CTC loss and how it compares to the benefits in inference speed?
limitations: 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.
paper_summary: paper_summary: The authors study the setup of speculative decoding where multiple tokens are being generated at parallel. 
In this setup the authors use the idea of connectionist temporal classification to train a draft model which generates multiple tokens in parallel.
strength_weakness: strength_weakness: - The speedups are unclear, it is calculated using the token acceptance rate rather than on a real system

- Details are not clear about at what layers the authors are taking the intermediate representation 

- The details of training overhead are unclear

- It will be great if authors can compare to - Draft & Verify: Lossless Large Language Model Acceleration via Self-Speculative Decoding
questions: questions: See weakness section
limitations: limitations: The authors have listed some weaknesses however it is not clear the cases where the idea will fail. 

Specifically how dependent is data drift between training the draft model and inference.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.
* 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.
* 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.
questions: 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?
* 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?
* 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: limitations: The paper adequately addresses the limitations.

Comments: title: Thank you
Thank your for response
Supplementary Explanations by Authors
Thank you for the further discussion
Supplementary Explanations by Authors
Thank you for the response
comment: Many thanks for your time and valuable suggestions to help improve our paper. We will follow your suggestions to include necessary clarifications in the revised version.
Many thanks for your time and valuable suggestions to help improve our paper. We will follow your suggestions to include necessary clarifications and experiments in the revised version.
Thank you for further clarification.

These detailed explanations make more sense than the information included in the original manuscript. In fact, this is quite "new" information to me (ex: 4 previous tokens, 2x copying, etc.) and possibly to other reviewers.

I increased the soundness score from 2 to 3, and the overall score from 5 to 6.

By the way, I wonder if that information was given in the original version. We might have asked different questions about architectural details. I note this to let the meta reviewer decide.
Appreciate the author response. 

Thank you for providing clarifications. 

I will bump up the score to 6.
Dear Reviewers,

We are writing to kindly request your feedback.

As the author-reviewer discussion phase is nearing its end, we are eagerly awaiting your response to address any questions or concerns you may have.

We apologize for any inconvenience and appreciate your time and efforts.
Dear Reviewers,

We are writing to kindly request your feedback.

As the author-reviewer discussion phase is nearing its end, we are eagerly awaiting your response to address any questions or concerns you may have.

We apologize for any inconvenience and appreciate your time and efforts.
Dear Reviewers,

We are writing to kindly request your feedback.

As the author-reviewer discussion phase is nearing its end, we are eagerly awaiting your response to address any questions or concerns you may have.

We apologize for any inconvenience and appreciate your time and efforts.
Thanks for your valuable suggestions. We reorganized the description of our method, hoping it can help understand our method better. 

Overall, the architecture of our method can be decomposed into three parts: the base model, the drafter which includes the Attention Draft module and LM head, and the CTC-related module which is used to calculate CTC-loss for training and performs CTC-style decoding at inference. The main structures of the three parts are as follows.
- The base model in our method is based on the autoregressive generation framework like Llama which only uses Transformer decoder as the main structure. 
- For the drafter, the Attention Draft module employs one Transformer layer as its structure including masked multi-head self-attention sublayer and Feed Forward sublayer. Compared to Medusa which employs FFN as the structure of each Medusa head without interacting between Medusa heads, our method can introduce sequence correlations between the preceding generated words and next several words to generate, besides the CTC-related module.
- The CTC-related module involves non-autoregressive generation of the next N tokens (N  is a hyperparameter, which is set to 4 for current CTC-drafter) where blank character and repetitive tokens are introduced into the raw generated sequence which will be processed by CTC Transform module to produce the final draft for the current decoding timestep.

Our method works in a different way during training and inference. During training, the base model will generate the whole sequence in an autoregressive manner which is used as the ground truth to distill the drafter. To generate the draft for the drafter, at each timestep, the Attention Draft module accepts as the input the 4  representations of the current position (assuming position i) and its preceding positions (i-3, i-2, i-1)  generated by the last Transformer layer of the base model, and upsamples the input representations by 2 times  via copying the input representations. Then through the Transformer layer of the Attention Draft module, the output representations are fed to LM head. LM head will generate 8 raw draft tokens in a non-autoregressive way and the final draft tokens will be produced by CTC Transform module. The CTC-loss is used to count the probabilities of all the draft sequences that can be transformed into the ground truth sequence via dynamic programming and the sum of all these sequences is maximized as the training loss. In this way, the probability distribution is drawn towards the draft sequences that can derive ground truth sequence being allocated bigger probability. This means the candidate draft sequence with more reasonable sequence correlations will be selected as the winner at a greater likelihood.  

At inference, the base model does not generate the whole sequence in advance. Instead, at each timestep, it is used to generate the representations fed to the Attention Draft module and verify the generated draft tokens according to the probability by performing teacher forcing decoding to generate the draft tokens. If the probability to generate the draft tokens is greater than the set threshold, the base model will accept the draft tokens and uses them as the following generated tokens. Then the base model continues to encode these generated draft tokens in an autoregressive way. If the probability is smaller than the threshold, the base model will reject the draft tokens and generate the next token on its own and meanwhile encode the generated token in an autoregressive way, too.  Then the latest generated 4 representations by the last Transformer layer of the base model are used as the input of the Attention Draft module for the next timestep and the decoding goes to the next timestep. Here the Attention Draft module works in the same way as in training to generate input representations for LM head. Here LM head still generates N tokens for the next N positions in a non-autoregressive way with each position reserving top k tokens (k is a hyperparameter, which is set to 10 for current CTC-drafter), then the token sequence of the N positions with the highest probability will be selected as the raw draft via the token tree structure used in Medusa. The final draft generated via CTC transform will be fed to the base model to verify and the base model will decide to use the draft tokens as the next several output tokens or to generate the next token by itself where the former decision can generate several tokens at once and hence improves the decoding speed.
Many thanks for the further valuable suggestions. We will definitely include the discussion of CTC independence and beam search in the revised version. We would like to give reorganized description about our method to help understand the Attention Draft module’s architecture. 

Overall, the architecture of our method can be decomposed into three parts: the base model, the drafter which includes the Attention Draft module and LM head, and the CTC-related module which is used to calculate CTC-loss for training and performs CTC-style decoding at inference. The main structures of the three parts are as follows.
- The base model in our method is based on the autoregressive generation framework like Llama which only uses Transformer decoder as the main structure. 
- For the drafter, the Attention Draft module employs one Transformer layer as its structure including masked multi-head self-attention sublayer and Feed Forward sublayer. Compared to Medusa which employs FFN as the structure of each Medusa head without interacting between Medusa heads, our method can introduce sequence correlations between the preceding generated words and next several words to generate, besides the CTC-related module.
- The CTC-related module involves non-autoregressive generation of the next N tokens (N  is a hyperparameter, which is set to 4 for current CTC-drafter) where blank character and repetitive tokens are introduced into the raw generated sequence which will be processed by CTC Transform module to produce the final draft for the current decoding timestep.

Our method works in a different way during training and inference. During training, the base model will generate the whole sequence in an autoregressive manner which is used as the ground truth to distill the drafter. To generate the draft for the drafter, at each timestep, the Attention Draft module accepts as the input the 4  representations of the current position (assuming position i) and its preceding positions (i-3, i-2, i-1)  generated by the last Transformer layer of the base model, and upsamples the input representations by 2 times  via copying the input representations. Then through the Transformer layer of the Attention Draft module, the output representations are fed to LM head. LM head will generate 8 raw draft tokens in a non-autoregressive way and the final draft tokens will be produced by CTC Transform module. The CTC-loss is used to count the probabilities of all the draft sequences that can be transformed into the ground truth sequence via dynamic programming and the sum of all these sequences is maximized as the training loss. In this way, the probability distribution is drawn towards the draft sequences that can derive ground truth sequence being allocated bigger probability. This means the candidate draft sequence with more reasonable sequence correlations will be selected as the winner at a greater likelihood.  

At inference, the base model does not generate the whole sequence in advance. Instead, at each timestep, it is used to generate the representations fed to the Attention Draft module and verify the generated draft tokens according to the probability by performing teacher forcing decoding to generate the draft tokens. If the probability to generate the draft tokens is greater than the set threshold, the base model will accept the draft tokens and uses them as the following generated tokens. Then the base model continues to encode these generated draft tokens in an autoregressive way. If the probability is smaller than the threshold, the base model will reject the draft tokens and generate the next token on its own and meanwhile encode the generated token in an autoregressive way, too.  Then the latest generated 4 representations by the last Transformer layer of the base model are used as the input of the Attention Draft module for the next timestep and the decoding goes to the next timestep. Here the Attention Draft module works in the same way as in training to generate input representations for LM head. Here LM head still generates N tokens for the next N positions in a non-autoregressive way with each position reserving top k tokens (k is a hyperparameter, which is set to 10 for current CTC-drafter), then the token sequence of the N positions with the highest probability will be selected as the raw draft via the token tree structure used in Medusa. The final draft generated via CTC transform will be fed to the base model to verify and the base model will decide to use the draft tokens as the next several output tokens or to generate the next token by itself where the former decision can generate several tokens at once and hence improves the decoding speed.
Thanks for your valuable suggestions. We reorganized the description of our method, hoping it can help understand our method better. 

Overall, the architecture of our method can be decomposed into three parts: the base model, the drafter which includes the Attention Draft module and LM head, and the CTC-related module which is used to calculate CTC-loss for training and performs CTC-style decoding at inference. The main structures of the three parts are as follows.
- The base model in our method is based on the autoregressive generation framework like Llama which only uses Transformer decoder as the main structure. 
- For the drafter, the Attention Draft module employs one Transformer layer as its structure including masked multi-head self-attention sublayer and Feed Forward sublayer. Compared to Medusa which employs FFN as the structure of each Medusa head without interacting between Medusa heads, our method can introduce sequence correlations between the preceding generated words and next several words to generate, besides the CTC-related module.
- The CTC-related module involves non-autoregressive generation of the next N tokens (N  is a hyperparameter, which is set to 4 for current CTC-drafter) where blank character and repetitive tokens are introduced into the raw generated sequence which will be processed by CTC Transform module to produce the final draft for the current decoding timestep.

Our method works in a different way during training and inference. During training, the base model will generate the whole sequence in an autoregressive manner which is used as the ground truth to distill the drafter. To generate the draft for the drafter, at each timestep, the Attention Draft module accepts as the input the 4  representations of the current position (assuming position i) and its preceding positions (i-3, i-2, i-1)  generated by the last Transformer layer of the base model, and upsamples the input representations by 2 times  via copying the input representations. Then through the Transformer layer of the Attention Draft module, the output representations are fed to LM head. LM head will generate 8 raw draft tokens in a non-autoregressive way and the final draft tokens will be produced by CTC Transform module. The CTC-loss is used to count the probabilities of all the draft sequences that can be transformed into the ground truth sequence via dynamic programming and the sum of all these sequences is maximized as the training loss. In this way, the probability distribution is drawn towards the draft sequences that can derive ground truth sequence being allocated bigger probability. This means the candidate draft sequence with more reasonable sequence correlations will be selected as the winner at a greater likelihood.  

At inference, the base model does not generate the whole sequence in advance. Instead, at each timestep, it is used to generate the representations fed to the Attention Draft module and verify the generated draft tokens according to the probability by performing teacher forcing decoding to generate the draft tokens. If the probability to generate the draft tokens is greater than the set threshold, the base model will accept the draft tokens and uses them as the following generated tokens. Then the base model continues to encode these generated draft tokens in an autoregressive way. If the probability is smaller than the threshold, the base model will reject the draft tokens and generate the next token on its own and meanwhile encode the generated token in an autoregressive way, too.  Then the latest generated 4 representations by the last Transformer layer of the base model are used as the input of the Attention Draft module for the next timestep and the decoding goes to the next timestep. Here the Attention Draft module works in the same way as in training to generate input representations for LM head. Here LM head still generates N tokens for the next N positions in a non-autoregressive way with each position reserving top k tokens (k is a hyperparameter, which is set to 10 for current CTC-drafter), then the token sequence of the N positions with the highest probability will be selected as the raw draft via the token tree structure used in Medusa. The final draft generated via CTC transform will be fed to the base model to verify and the base model will decide to use the draft tokens as the next several output tokens or to generate the next token by itself where the former decision can generate several tokens at once and hence improves the decoding speed.
Given that the experiments are indeed extensive, I will increase my score from 4 to 5.
Thank you for the response and additional experiments.

I hope the discussion about CTC independence and beam search method to be included in the revised version.

Regarding the Attention Draft Model's architecture, my confusion is this: Medusa uses different heads for each position (i+1, i+2, ...). When you are saying that the Transformer is used for Attention Draft, is it mean that each Medusa head is a Transformer or all heads are integrated into a single Transformer?

* If Former (per-position): Query is only a single timestep input. Do you need a Transformer for this non-sequential input?
* If Latter (unified): Is Attention Draft Module Auto-regressive? How can it generate all tokens at once?