  Transformer-based Large language models (LLMs) have demonstrated their power
in various tasks, but their inference incurs significant time and energy costs.
To accelerate LLM inference, speculative decoding uses a smaller model to
propose one sequence of tokens, which are subsequently validated in batch by
the target large model. Compared with autoregressive decoding, speculative
decoding generates the same number of tokens with fewer runs of the large
model, hence accelerating the overall inference by $1$-$2\times$. However,
greedy decoding is not the optimal decoding algorithm in terms of output
perplexity, which is a direct measurement of the effectiveness of a decoding
algorithm. An algorithm that has better output perplexity and even better
efficiency than speculative decoding can be more useful in practice. To achieve
this seemingly contradictory goal, we first introduce multi-token joint greedy
decoding (MJGD), which greedily generates multiple tokens at each step based on
their joint perplexity. We show that it leads to better perplexity for the
whole output. But the computation cost of MJGD is infeasible in practice. So we
further propose multi-token joint speculative decoding (MJSD), which
approximates and accelerates the MJGD from two aspects: it approximates the
joint distribution of the large model with that of a small model, and uses a
verification step to guarantee the accuracy of approximation; then it uses beam
decoding to accelerate the sequence generation from the joint distribution.
Compared with vanilla speculative decoding, MJSD has two advantages: (1) it is
an approximation of MJGD, thus achieving better output perplexity; (2)
verification with joint likelihood allows it to accept the longest prefix
sub-sequence of the draft tokens with valid perplexity, leading to better
efficiency...
