Generation Meets Verification: Accelerating Large Language Model Inference with Smart Parallel Auto-Correct Decoding (2024)

Abstract: This research aims to accelerate the inference speed of large language models (LLMs) with billions of parameters. We propose Smart Parallel Auto-Correct dEcoding (SPACE), an approach designed for achieving lossless acceleration of LLMs. By integrating semi-autoregressive inference and speculative decoding capabilities, SPACE uniquely enables autoregressive LLMs to parallelize token generation and verification. This is realized through a specialized semi-autoregressive supervised fine-tuning process that equips existing LLMs with the ability to simultaneously predict multiple tokens. Additionally, an auto-correct decoding algorithm facilitates the simultaneous generation and verification of token sequences within a single model invocation. Through extensive experiments on a range of LLMs, SPACE has demonstrated inference speedup ranging from 2.7x-4.0x on HumanEval-X while maintaining output quality.

## introduction the majority of large language models (llms), including prominent examples like chatgpt @xcite and llama @xcite , are autoregressive (ar) in nature. during the inference stage, these ar models generate tokens one by one in a sequential manner. this sequential approach limits parallelism, leading to underutilization of modern parallel computing resources such as gpus. consequently, the inference stage becomes memory-bound and the inference latency increases noticeably, particularly with advanced llms boasting billions of parameters. a straightforward method to mitigate the latency is to adapt the model to predict multiple future tokens in parallel. such models are commonly referred to as semi-autoregressive (sar) models @xcite . nonetheless, the vast majority of llms are inherently ar and, hence, unable to perform inference in a sar manner. in addition, sar models commonly experience a deterioration in the output quality due to their parallel decoding nature @xcite . furthermore, it is worth mentioning that pretraining any llm from scratch is computationally expensive. another effective way to speed up ar sampling is speculative decoding @xcite @xcite . speculative decoding typically adheres to the 'draft-then-verify' paradigm, wherein multiple candidate tokens are initially generated by fast-to-infer smaller models, and are subsequently validated in parallel by the larger llm. this validation process, based on rejection sampling, ensures that the final output is consistent with the llm's distribution, thereby achieving lossless speedup. nonetheless, speculative decoding is contingent on the availability of smaller models, which must utilize the same tokenizer as the larger model to function properly. integrating sar inference with speculative decoding presents a promising approach to accelerate language model inference. by adapting a model to autonomously generate and validate a sequence of future tokens, we establish an efficient and selfreliant process that greatly enhances the speed of inference. this union yields substantial practical benefits: it eliminates the requirement for smaller auxiliary models, thereby simplifying the overall implementation and reducing memory overhead during inference. furthermore, by shifting the emphasis away from precise prediction of multiple tokens towards speculative generation followed by verification, the difficulty of the sar training phase can be significantly reduced. in this paper, we propose smart parallel auto-correct decoding (space), a approach that allows llms to generate multiple tokens speculatively while simultaneously verifying them. space harmonizes a sar model with a draft-then-verify inference algorithm to optimize inference speed while maintaining high model quality. we demonin ar inference, token generation proceeds in a sequential manner, with only one token output per decoding step. in space inference, the input token sequence (i.e., "llms are") is augmented with k + 1 groups of mask tokens and k candidate tokens (i.e., "auto" and "model"). the candidate tokens undergo verification to obtain accepted tokens (i.e., "auto" and "regressive"), and k new candidate tokens (i.e., "model" and "<@xmath0. an illustration of the generation and verification process can be found in figure 2 . space allows for a variable number of tokens to be generated in each step, with the quantity ranging from a minimum of 1 to a maximum of k + 1. our key contributions are summarized as follows: ## related work speculative decoding speculative decoding @xcite accelerates llm inference by using a smaller draft model to predict larger target model outputs, with subsequent verification by the target model. the efficacy of the method is contingent on the accuracy of the draft model's predictions. to enhance accuracy, researchers have adopted various strategies such as employing ensembles of boosted draft models @xcite , staged draft models (spector and ré, 2023), retraining the target model with addition of auxiliary prediction heads @xcite , introducing advanced coordination policies @xcite and refining the decoding algorithm @xcite . however, speculative decoding hinges on the accessibility of suitable smaller models, which can be difficult to obtain and often requiring extra training and careful tuning @xcite . space circumvents this challenge by fine-tuning the target model to prognosticate future token sequences in parallel, eliminating the dependency on extra small model. recent advancements like lookahead decoding @xcite and self-speculative @xcite have refined the draft-then-verify process, forgoing the need for extra models or intricate training steps. although simpler, these methods tend to provide less acceleration than space. contrarily, medusa @xcite and pass @xcite leverage fine-tuning of a single llm to perform both token generation and validation. pass, through fine-tuning lookahead token embeddings, allows llms to predict multiple tokens ahead, but with a limited speedup of about 30% as their verification and drafting phases occur sequentially. medusa adds multiple decoding heads to the llm and introduces a tree-based decoding algorithm for faster inference, but it struggles with larger batch sizes owing to the increased computational demands of tree-structured attention. semi-autoregressive decoding sar departs from the ar approach by decoding multiple tokens in parallel, thereby significantly enhancing inference efficiency. particularly in machine translation, sar has achieved a fivefold speed increase while preserving 88% of the model quality @xcite . for sar decoding, it is a common trick to employ mask tokens as placeholders in input. this approach, originating from the mask-predict paradigm introduced by ghazvininejad et al. in machine translation, has since become a widely recognized decoding strategy @xcite . inspired by this paradigm, space adopts k mask tokens to predict k future tokens. xia et al. accelerate inference of an ar model by creating draft tokens with a sar model and then refined by the ar model. unlike their method which necessitates a secondary sar model for draft generation, space eliminates this requirement, merging generation and verification phases for enhanced efficiency. ## conclusion in this paper, we introduce space, an innovative approach to accelerate inference of llms. space is distinguished by 1) its ability to transform an ar llm into a sar llm utilizing sar-sft, which is easy to implement as it only requires minor modifications to the dataloader in sft setup; 2) its unique auto-correct decoding algorithm that enables the same model for both token generation and verification. experimental results on various llms show space can achieve 2.7x-4.0x speedup on humaneval-x while still preserving model quality.