The process of generating a large language model naturally has its own regression characteristics, namely that the model predicts and generates subsequent content by token in the context. As the model grows in size, the expense of one-step forward computation also increases, causing higher logical delays from regression decoding. Speculative decoding (SD) has become an important technological route for accelerated big language model reasoning by introducing a more light draft model.
However, existing methods are typically optimized along two routes: one by generating multiple draft sequences to expand the candidate space, the other by verifying longer token blocks via block verification. The former increases the chances of finding an acceptable candidate block, and the latter increases the upper limit of how long a block can be accepted, but the latter is designed separately over the long term.
The team proposed SpecTr-GBV, which integrates multi-draft and greedy block verification (GBV) into the same deductive decoding framework. It wrote multiple draft token blocks and verification of target token blocks as optimal transmission problems, while maintaining the consistency of the output distribution and pursuing longer acceptance lengths.
SpecTr(NeurIPS2023) illustrates the verification mechanism of SpecTr-GBV in this paper. SpecTr adopts a location-by-site verification strategy, accepting one token at each location and retaining the corresponding draft sequences; in contrast, SpecTr-GBV performs joint verification as a sub-block unit and searches for and retains the longest acceptable subblocks in multiple draft sequences.
SpecTr-GBV: Multi-Draft Block Verification Accelerating Speculative Decoding
It was written by Yijun Lin, Jinhao Sheng, Qingyue Cai, Feng Zhou.
Center for Applied Statistics and School of Statistics, Renmin University of China; School of Intelligent Medicine, China Medical University
Subjects of the study: big language model reasoning acceleration, deductive decoding, multi-draft verification, block verification, optimal transmission
OpenReview links to the following:
Why redesigned the decoding hypothesis for the verification of the decoding link?
The basic idea of standard deductive decoding is for a small model to form an L-length draft, in which the target model first calculates the real-condition distribution of the corresponding position, and then, through rejection sampling, decides whether the draft token can be accepted.
This mechanism, while avoiding token-by-token calling of the target model, also leads to a direct bottleneck: a speculative iteration can ultimately retain the number of tokens, limited to the degree to which the draft sequence matches the target distribution. It is difficult to continue to function as long as one of the previous sequences fails and the subsequent potentially correct tokens fail. In order to further enhance the degree to which the draft sequence matches the target distribution, the verification method can be extended from token-by-token matching to multi-block matching, thus making better use of the candidate information in the draft sequence.
There are already routes: more drafts, or smarter verification
The first route is multi-draft. The method, represented by SpecTr, will generate a series of independent draft articles K from the draft model. At each location, it uses the best transfer structure coupling between the draft distribution and the target distribution to find acceptable candidates from the K candidate token. As K grows, the probability of at least one candidate being accepted will increase.
The second route is block verification. GBV is no longer a token-by-token independent judgment, but is verified as a whole in the single-draft setting, and proves to be able to meet the optimal expectation of accepting token numbers in a single iteration.
The problem is: multi-draft solutions, not enough block verification solutions, can't accept longer blocks at once. How do we bring them together?
At the core of SpecTr-GBV: Optimal Transmission Problems while addressing multiple draft puzzles and block verification puzzles
SpecTr-GBV is derived from Article K i.i.d. draft sequences, each with a length of L. In contrast to SpecTr, which verifies by position, it considers the different prefixes of each draft as a candidate sub-block, and defines the acceptance length by finishing the sequence around the column to match the target sequence.
For a given multi-draft sequence with a target sequence, the paper defines acceptance length as: if there is at least one draft whose length is completely consistent with the length of the forepart of i and the forepart of i of the target, it can be accepted to position i; ultimately take the maximum i. Thus, the verification goal is no longer to individually maximize the acceptance probability of a particular position, but to directly maximize the expected acceptance length of the entire block.
Intuitively speaking, the SpecTr-GBV study found that in several draft papers, which one would go down as long as possible according to the target distribution.
Step 1: Build multi-draft block and target block coupling
The paper will write validation as an optimal transport optimization: seeking the largest coupling that allows the expected acceptance length, on the premise of keeping the draft marginal and the target marginal unchanged.