Speculative decoding emerges as a pivotal technique for enhancing the
inference speed of Large Language Models (LLMs). Despite recent research aiming
to improve prediction efficiency, multi-sample speculative decoding has been
overlooked due to varying numbers of accepted tokens within a batch in the
verification phase. Vanilla method adds padding tokens in order to ensure that
the number of new tokens remains consistent across samples. However, this
increases the computational and memory access overhead, thereby reducing the
speedup ratio. We propose a novel method that can resolve the issue of
inconsistent tokens accepted by different samples without necessitating an
increase in memory or computing overhead. Furthermore, our proposed method can
handle the situation where the prediction tokens of different samples are
inconsistent without the need to add padding tokens. Sufficient experiments
demonstrate the efficacy of our method. Our code is available at
this https URL

通过提出一种新方法，解决多样本推断速度提高中可变数量的 token 导致效率下降的问题，无需增加计算和内存开销，并且可以处理不一致的样本预测 token 的情况。

EMS-SD：高效的多样本猜测解码用于加速大型语言模型

EMS-SD: Efficient Multi-sample Speculative Decoding for Accelerating  Large Language Models

We consider statistical as well as algorithmic aspects of solving large-scale
least-squares (LS) problems using randomized sketching algorithms. For a LS
problem with input data $(X, Y) \in \mathbb{R}^{n \times p} \times
\mathbb{R}^n$, sketching algorithms use a sketching matrix, $S\in\mathbb{R}^{r
\times n}$ with $r \ll n$. Then, rather than solving the LS problem using the
full data $(X,Y)$, sketching algorithms solve the LS problem using only the
sketched data $(SX, SY)$. Prior work has typically adopted an algorithmic
perspective, in that it has made no statistical assumptions on the input $X$
and $Y$, and instead it has been assumed that the data $(X,Y)$ are fixed and
worst-case (WC). Prior results show that, when using sketching matrices such as
random projections and leverage-score sampling algorithms, with $p < r \ll n$,
the WC error is the same as solving the original problem, up to a small
constant. From a statistical perspective, we typically consider the
mean-squared error performance of randomized sketching algorithms, when data
$(X, Y)$ are generated according to a statistical model $Y = X \beta +
\epsilon$, where $\epsilon$ is a noise process. We provide a rigorous
comparison of both perspectives leading to insights on how they differ. To do
this, we first develop a framework for assessing algorithmic and statistical
aspects of randomized sketching methods. We then consider the statistical
prediction efficiency (PE) and the statistical residual efficiency (RE) of the
sketched LS estimator; and we use our framework to provide upper bounds for
several types of random projection and random sampling sketching algorithms.
Among other results, we show that the RE can be upper bounded when $p < r \ll
n$ while the PE typically requires the sample size $r$ to be substantially
larger. Lower bounds developed in subsequent results show that our upper bounds
on PE can not be improved.

对大规模最小二乘问题的解决方法采用随机草图算法的统计和算法方面进行了考虑，提出了算法和统计两种框架并比较其性能，并且证明了在使用随机投影和随机抽样算法的情况下，当样本数为 $r$，且 $p<r<n$ 时，算法误差与原始问题的误差相同。