# A Structural Correlation Filter Combined with A Multi-task Gaussian Particle
Filter for Visual Tracking

Manna Dai
<EMAIL_ADDRESS>Shuying Cheng
<EMAIL_ADDRESS>Xiangjian He
<EMAIL_ADDRESS>Dadong Wang
<EMAIL_ADDRESS>
###### Abstract

In this paper, we propose a novel structural correlation filter combined with
a multi-task Gaussian particle filter (KCF-GPF) model for robust visual
tracking. We first present an assemble structure where several KCF trackers as
weak experts provide a preliminary decision for a Gaussian particle filter to
make a final decision. The proposed method is designed to exploit and
complement the strength of a KCF and a Gaussian particle filter. Compared with
the existing tracking methods based on correlation filters or particle
filters, the proposed tracker has several advantages. First, it can detect the
tracked target in a large-scale search scope via weak KCF trackers and
evaluate the reliability of weak trackers’decisions for a Gaussian particle
filter to make a strong decision, and hence it can tackle fast motions,
appearance variations, occlusions and re-detections. Second, it can
effectively handle large-scale variations via a Gaussian particle filter.
Third, it can be amenable to fully parallel implementation using importance
sampling without resampling, thereby it is convenient for VLSI implementation
and can lower the computational costs. Extensive experiments on the OTB-2013
dataset containing 50 challenging sequences demonstrate that the proposed
algorithm performs favourably against 16 state-of-the-art trackers.

##  1 Introduction

Visual tracking is one of the most fundamental problems in computer vision due
to its numerous applications such as video surveillance, motion analysis,
vehicle navigation and human computer interactions. Although a great progress
has been seen on developing algorithms [19, 39, 40, 46] and benchmark
evaluations [43] for visual tracking, visual tracking is still a challenging
problem in the situations of heavy illumination changes, pose deformations,
partial and full occlusions, large scale variations, background clutter and
fast motion.

Correlation filters have recently attracted a great attention due to their
rapid speeds of calculation and robust tracking performance [24, 27, 28, 29].
Bolme et al. [6] proposed an adaptive correlation filer, called MOSSE, for
producing ASEF-like filters by fewer training images. Henriques et al. [35]
extended the correlation-filter-based trackers to kernel-based training,
called CSK method, to utilize a circulant structure of one image patch to
conduct dense sampling, and then improved the KCF tracker [19] by using multi-
channel inputs and HOG descriptors. Danelljan et al. [14] developed the DSST
method handling scale changes of a target, and Choi et al. [10] proposed a
spatially attentional weight map to weight various correlation filters. Ma et
al. [30] used a correlation filter as a short-term tracker and an online
random fern classifier for re-detection as a long-term memory system.

Although achieved the appealing results both in precision and success rate,
these correlation-filter-based trackers cannot deal with fast motions and
scale variations well. For example, although two correlation-filter-based
trackers, namely SCT[10] and KCF [19], have achieved state-of-the-art results
and have beaten all other attended trackers in terms of accuracy in the
OTB-2013 dataset [43], they fail to track a target object when partial
occlusions or illumination changes occur.

To deal with the above issues, we propose a novel and an ensemble tracker,
which first builds weak trackers by applying structural correlation filters,
and then integrate all weak trackers into one stronger tracker using a
reliability evaluation and a multi-task Gaussian particle filter. Each weak
tracker is treated as an expert and the weights of all experts are computed
via their confidence maps. Through the reliability evaluation, the weak
trackers provide weak decisions for the Gaussian particle filter to make a
final decision. The tracking result in the current frame is interred by the
weights of the Gaussian particle filter. Particles respectively calculate two
results using HOG and gray-normalization features, and therefore the Gaussian
particle filter conducts a multi-task tracking for making a strong decision.

The contributions in this paper are summarized as follows.

  * •

A novel ensemble algorithm is proposed to combine structural correlation
filters and a Gaussian particle filter into a single stronger tracker.

  * •

A large-scale search scope algorithm using for multiple structural correlation
filters is proposed, considering spatial geometric relations between target
locations in consecutive frames and therefore making the search reliable.

  * •

Extensive experiments in the OTB-2013 benchmark dataset [43] with 50
challenging sequences and 11 various attributes to demonstrate the
outperformance of the proposed method in comparison with 16 state-of-the-art
trackers.

##  2 Related Work

A comprehensive tracking review can be found in [43, 44, 36]. In this section,
we discuss the methods closely related to this work, mainly regarding multi-
task correlation filters, Gaussian particle filters and Average Peak-to-
Correlation Energy (APCE).

###  2.1 Structural Correlation Filters

Qi et al. [34] described the weak correlation filers on CNN features in each
layer and Liu et al. [27] proposed the concept of the structural correlation
filter.

In [34], $\mathbf{\emph{X}}^{k}\in\mathbb{R}^{P\times Q\times D}$ denote the
feature map extracted from the $k$-th convolutional layer with Gaussian
function label $\mathbf{\emph{Y}}\in\mathbb{R}^{P\times Q}$. Let
$\mathbf{\mathcal{X}}^{k}=\mathcal{F}(\mathbf{\emph{X}}^{k})$ and
$\mathbf{\mathcal{Y}}=\mathcal{F}(\mathbf{\emph{Y}})$, where
$\mathcal{F}(\cdot)$ represents the discrete Fourier transformation (DFT). The
objective function of correlation filter method [34] can be extended into its
$k$-th filter modeled as

$\mathbf{\mathcal{W}}^{k}=\mathrm{arg}\min_{\mathbf{\mathcal{W}}}\|\mathbf{\mathcal{Y}}-\mathbf{\mathcal{X}}^{k}\cdot\mathbf{\mathcal{W}}\|^{2}_{F}+\lambda\|\mathbf{\mathcal{W}}\|^{2}_{F},$
(1)

where

$\mathbf{\mathcal{X}}^{k}\cdot\mathbf{\mathcal{W}}=\sum_{d=1}^{D}\mathbf{\mathcal{X}}^{k}_{*,*,d}\bigodot\mathbf{\mathcal{W}}_{*,*,d}.$
(2)

Here, the symbol $\bigodot$ is the element-wise product.

The optimization problem in Eq. 1 has a simple closed form solution, which can
be efficiently computed in the Fourier domain by

$\mathbf{\mathcal{W}}^{k}_{*,*,d}=\frac{\mathbf{\mathcal{Y}}}{\mathbf{\mathcal{X}}^{k}\cdot\mathbf{\mathcal{X}}^{k}+\lambda}\bigodot\mathbf{\mathcal{X}}^{k}_{*,*,d}.$
(3)

Given the testing data $\mathbf{\emph{T}}^{k}$ from the output of the $k$-th
layer, we first transform it to the Fourier domain
$\mathbf{\mathcal{T}}^{k}=\mathcal{F}(\mathbf{\emph{T}}^{k})$, and then the
responses can be computed by

$\mathbf{\emph{S}}^{k}=\mathcal{F}^{-1}(\mathbf{\mathcal{T}}^{k}\cdot\mathbf{\mathcal{W}}^{k}),$
(4)

where $\mathcal{F}^{-1}$ denotes the inverse of DFT.

The $k$-th weak tracker outputs the target position with the largest response

$(x^{k},y^{k})=\mathrm{arg}\max_{x^{\prime},y^{\prime}}\mathbf{\emph{S}}^{k}(x^{\prime},y^{\prime}).$
(5)

###  2.2 Gaussian Particle Filters (GPF)

Kotecha and Djuric [23] introduced the Gaussian Particle Filter (GPF), which
is used for tracking filtering and predictive distributions encountered in
Dynamic State-Space models (DSS) [18]. The DSS model represents the time-
varying dynamics of an unobserved state variable. GPF is based on the particle
filtering and Gaussian filtering concepts. Gaussian filters provide Gaussian
approximations to the filtering and predictive distributions, and they include
Extended Kalman Filter (EKF) [21] and its variations [20, 31, 37, 42]. Unlike
EKF, which assumes that predictive distributions are Gaussian and employs
linearization of the functions in the process and observation equations, GPF
updates the Gaussian approximations using particles. GPF only propagates the
posterior mean and covariance of an unobserved state variable in a DSS model,
and essentially importance sampling makes the procedure simple.

Particle filters [16, 32, 33] use sequential importance sampling (SIS) [26] to
update the posterior distributions. GPF is quite similar to SIS filters by the
fact that importance sampling is used to obtain particles. However, a
phenomenon called sample degeneration occurs wherein only a few particles
representing the distribution have significant weights. A procedure called
resampling [25] has been introduced to mitigate this problem, but it may give
limited results and may be computationally expensive. Since GPF approximates
posterior distributions as Gaussians, unlike the SIS filters, particle
resampling is not required. This results in a reduced complexity of GPF as
compared with SIS with resampling and is a major advantage. Furthermore,
Berzuini et al. [5] reported that particle filters with resampling also had
bias due to resampling, and resampling in SIS filters is a nonparallel
operation. Fortunately, resampling would never occur in GPF simulation
examples, and the particle filters in GPF are amenable to parallel
implementation. Therefore, GPF is more amenable for fully parallel
implementation in very large scale integration (VLSI) than SIS.

Simulation results are presented to demonstrate the versatility and improved
performance of GPF over conventional Gaussian filters and the lower complexity
of GPF than the known particle filters. However, the parallelizibility of GPF
and the absence of resampling makes it convenient for VLSI implementation and,
hence, feasible for practical real-time applications.

###  2.3 Ensemble trackers

Multiple component trackers have been combined with hand-crafted features to
develop ensemble tracking methods [1, 2, 41] for visual tracking. For example,
several ensemble methods [1, 2] using a boosting framework [15] train each
component weak tracker to classify foreground objects and background. In [41],
Wang and Yeung used a conditional particle filter to infer a target’s position
and the reliability of each component tracker. Qi et al. [34] treated tracking
as a decision-theoretic online learning task and the tracked target was
inferred by using the decisions from multiple expert trackers. Similar to
[34], we consider visual tracking as a decision-theoretic online learning task
[9], and use it in the structure of multiple correlation filters combined with
a Gaussian particle filter. That is, in every round, each correlation filter
makes a decision and the final decision is determined by a Gaussian particle
filter.

###  2.4 Average Peak-to-Correlation Energy (APCE)

For correlation filters, the peak value $F_{max}$ denotes the maximum response
score of a response map. To measure the fluctuation degree of a response map
and the reliability degree of a detected object, Wang et al. [40] proposed an
average peak-to-correlation energy (APCE) which is defined as

$APCE=\frac{|F_{max}-F_{min}|^{2}}{\mathrm{mean}\left(\sum\limits_{w,h}(F_{w,h}-F_{min})^{2}\right)}$
(6)

where $F_{max}$, $F_{min}$ and $F_{w,h}$ denote the maximum, minimum and the
$w$-th row and $h$-th column elements of $F(s,y;w)$. APCE indicates the
fluctuated degrees of response maps and the confidence degrees of the tracked
results. For sharper peaks and less noise, in the case that the target fully
appearing in a tracking region, APCE will become greater and the response map
will become smoother except for only one sharp peak. On the other hand, APCE
will be small if an object is occluded or missing.

Figure 1: Flowchart of the proposed algorithm. The proposed algorithm consists
of three components: 1) constructing multiple weak trackers using correlation
filters where each one is trained using HOG features and makes a weak decision
(Section 3.1); 2) evaluating the reliability degree of each weak decision via
maximum response score and APCE measure and the most reliable decision is used
for the next step (Section 3.2); 3) constructing a stronger tracker and making
a final decision via a multi-task Gaussian particle filter which takes the
most reliable decision into account (Section 3.3).

##  3 Proposed Algorithm

In this section, we present the combination of structural correlation filters
with a multi-task Gaussian particle filter for ensemble tracking, namely KCF-
GPF. Different from the KCF method [19, 35] that learns a single correlation
filter in a fixed-size area, KCF-GPF is proposed to construct multiple weak
correlation filters in a more reliable search scope for dealing with fast
motion issues and bound effects in the conventional correlation filters. The
Gaussian particle filter jointly learns particle weights based on different
features to make a stronger tracker by a multi-task method. Furthermore, our
tracker can effectively handle scale variations via the sampling strategy of a
Gaussian particle filter. Overall, the proposed ensemble method will achieves
the following two goals: 1) weak expert trackers are tuned to separate a
foreground object from background and 2) the ensemble as a whole ensures the
temporal coherence of each part of the tracker.

###  3.1 Weak Structural Correlation Filter

A conventional correlation filter has bound effects [13] during a target
tracking and it interferes with the progress of target detection with fast
motions. For this, we extend the conventional search window for a single
tracker to a large-scale search scope for multiple trackers, and exploit
spatial-geometric relations between target locations in consecutive frames to
make the search scope reliable.

The feature map $\mathbf{\emph{X}}^{k}$ in Eq. 1 is extracted from an image
patch which is sampled by a search sliding window (see Figure. 2), where
$d_{t}$ donates the maximum historical-moving-distance of a tracked target in
Eq. 17 at time $t$ and the object location in the previous frame is the center
of the search scope. Besides it, we respectively use $d_{t}^{x}$ and
$d_{t}^{y}$ to represent the horizontal and vertical moving distances at time
$t$.

Figure 2: Illustration of the target tracking using the weak structural
correlation filter in sequence Deer from OTB-2013 dataset [43]. The search
scope is based on the max historical moving distance of the object in
horizontal and vertical directions at time $t$, namely $d_{t}^{x}$ and
$d_{t}^{y}$, and considers the last-frame object location as the center. A
search window slides in the search scope to enclose a sample corresponding to
a weak correlation filter.

Given the initial confidence weights of all weak experts, in the current
round, a further decision is made based on the expert tracker with the
greatest weight. In the visual tracking scenario, it is natural to treat each
KCF tracker as an expert and then predict the target position at time $t$ by

$(x^{*}_{t},y^{*}_{t})=(x^{k}_{t},y^{k}_{t})\cdot[1-\mathrm{sign}(\left|w^{k}_{t}-\max
w^{k}_{t}\right|)],$ (7)

where $w^{k}_{t}$ is the weight of expert $k$ and $\sum_{k=1}^{K}w^{k}_{t}=1$,
$\left|\cdot\right|$ denotes the absolute value and $\mathrm{sign}$ represents
the signum function.

Kernel Selection: We choose the Gaussian kernel in the existing correlation
filter tracker [19].

Feature Representation: Similar to [19], we use HOG features with 31 bins.
However, our tracker is quite generic and any dense feature representation
with arbitrary dimensions can be incorporated.

Compared to the HDT [34] and SCF [27] methods which are similar to the
proposed weak structural correlation filter, we demonstrate differences among
these approaches as follows.

  1. 1.

HDT uses CNN features, while SCF and KCF-GPF are based on HOG features.

  2. 2.

The features of HDT are extracted from one layer to build a weak tracker, and
the part-based correlation filter SCF samples several parts of a target object
to construct features, while KCF-GPF samples via sliding window in a search
scope which is subject to the maximum historic-moving-displacement of the
tracked target over time $t$.

  3. 3.

In HDT, the target position is made based on the weighted decisions of all
experts and SCF solves the optimization problem using the fast first-order
Alternating Direction Method of Multipliers (ADMM) [7], while KCF-GPF exploits
Eq. 7 to infer the ultimate target position.

###  3.2 Reliability Degree of Correlation Filter

The peak value and the fluctuation of the response map can reveal the
confidence degree about the tracking results to some extent. The ideal
response map should have only one sharp peak and be smooth in all other areas
when the detected target is extremely matched to the correct target. The
sharper the correlation peaks are, the better the location accuracy is.
Otherwise, the whole response map will fluctuate intensely, and its pattern is
significantly different from normal response maps. If we continue to use
uncertain samples to update the tracking model, it would be corrupted mostly.

Inspired by [40], we evaluate the stability of the $k$-th expert with two
criteria. The first criterion is the maximum response score $F_{max}$ of the
response map defined as

$F_{max}=\max_{x^{\prime},y^{\prime}}\mathbf{\emph{S}}^{k}(x^{\prime},y^{\prime})$
(8)

where $\mathbf{\emph{S}}^{k}(x^{\prime},y^{\prime})$ is referred to Eq. 4 and
Eq. 5.

The second criterion is called average peak-to-correlation energy (APCE)
measure which is defined in Eq. 6.

###  3.3 Multi-task Gaussian Particle Filter

The proposed multi-task Gaussian particle filter at time $t$ approximates the
posterior mean $\bm{\mu}_{t}$ and covariance $\bm{\Sigma}_{t}$ of the unknown
state variable $\mathbf{x}_{t}$ using Bayesian importance sampling.

We draw samples from the importance function $\pi(\cdot)$ at time $t$ using

$\pi(\mathbf{x}_{t}|\mathbf{y}_{0:t})=\mathcal{N}(\mathbf{x}_{t};\bm{\mu}_{t},\mathbf{\Sigma}_{t}),$
(9)

and denote them as $\\{\mathbf{x}_{t}^{j}\\}^{M}_{j=1}$. Here,
$\mathbf{y}_{0:t}$ is the observations over time $t$, and $\mathcal{N}(\cdot)$
represents a Gaussian function. Note that, in Eq. 9, $\bm{\mu}_{t}$ is equal
to Eq. 7 and $\mathbf{\Sigma}_{1}$ is chosen based on prior information.

The respective weights are computed by

$w_{t}^{j}=\frac{p(\mathbf{y}_{t}|\mathbf{x}_{t}^{j})\mathcal{N}(\mathbf{x}_{t}=\mathbf{x}_{t}^{j};\bm{\mu}_{t},\mathbf{\Sigma}_{t})}{\pi(\mathbf{x}_{t}^{j}|\mathbf{y}_{0:t})},$
(10)

where the distribution $p(\mathbf{y}_{t}|\mathbf{x}_{t}^{j})$ represents the
observation equation $\mathbf{y}_{t}$ conditioned on the unknown state
variable $\mathbf{x}_{t}^{j}$ at time $t$.

Eq. 10 can be rewritten as follows from Eq. 9:

$w_{t}^{j}\propto p(\mathbf{y}_{t}|\mathbf{x}_{t}^{j}).$ (11)

Then, we set
$p(\mathbf{y}_{t}|\mathbf{x}_{t}^{j})=|f_{t}^{*}-f(\mathbf{x}_{t}^{j})|$,
where $\left|\cdot\right|$ denotes the absolute value and $f_{t}$ is the
function of features, where $f_{t}^{*}$ represents the features of the
template at time $t$. Hence, each Gaussian particle weight can be calculated
with

$w_{t}^{j}\propto|f_{t}^{*}-f(\mathbf{x}_{t}^{j})|$ (12)

Normalize the weights as

$\tilde{w}_{t}^{j}=\frac{w_{t}^{j}}{\sum_{j=1}^{M}w_{t}^{j}}.$ (13)

In this paper, we adopt HOG for tackling deformation variations and gray
normalization of raw pixel values from sample images for handling illumination
changes, and the $j$-th features are represented by $f^{j}_{t(hog)}$ and
$f^{j}_{t(norm)}$ at time $t$, respectively . Hence, we get the corresponding
weights $\tilde{w}_{t(hog)}^{j}$ and $\tilde{w}_{t(norm)}^{j}$.

For the multi-task Gaussian particle filter, we jointly define the
similarities of respective samples as

$\bar{w}_{t}^{j}=\theta\cdot\tilde{w}_{t(hog)}^{j}+(1-\theta)\cdot\tilde{w}_{t(norm)}^{j},$
(14)

where learning rate parameter $\theta$ is a constant value in this paper.

The mean and covariance are estimated by

$\displaystyle\bm{\mu}_{t}$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{M}\bar{w}_{t}^{j}\mathbf{x}_{t}^{j},$ (15)
$\displaystyle\bm{\Sigma}_{t}$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{M}\bar{w}_{t}^{j}(\bm{\mu}_{t}-\mathbf{x}_{t}^{j})(\bm{\mu}_{t}-\mathbf{x}_{t}^{j})^{H},$
(16)

where $H$ represents the Hermitian Matrix.

The maximun historical-moving-distance of the tracked target at time $t$ is
defined as

$d_{t}=\max_{i=1}^{t}(\left|\bm{\mu}_{i}-\bm{\mu}_{i-1}\right|).$ (17)

Here, we set $d_{1}=0$, and $\left|\cdot\right|$ denotes the function for
absolution values;

###  3.4 KCF-GPF Tracker

Figure 1 illustrates the flowchart of the proposed algorithm. Based on the
structural correlation filter and a Gaussian particle filter, we propose a
KCF-GPF tracker. The first step generates $K$ weak correlation filters. The
second step is to make weak decisions via the weak structural correlation
filter.s The third step is to evaluate the reliability degrees of weak
decisions. Finally, the optimal decision is made using a multi-task Gaussian
particle filter.

To update the KCF-GPF for visual tracking, we adopt an incremental strategy in
the current frame to update the template in Eq. 12 by

$f_{t}^{*}=\rho\cdot f_{t-1}^{*}+(1-\rho)\cdot f_{t-1}(\bm{\mu}_{t-1}),$ (18)

where learning rate parameter $\rho$ is a constant value in this paper.

An overview of the proposed method is summarized in Algorithm 1.

Input: Frames $\\{\mathbf{I}_{t}\\}_{1}^{T}$;

Output: Target location of each frame $\bm{\mu}_{t}$.

1 for  _Time $t=1:T$ _ do

2

3 if  _$t=1$_ then

4 Initialize the target location $(x^{*}_{1},y^{*}_{1})$;

5 Crop interested image region;

6 Initiate $K$ weak correlation filters using Eq. 3;

7 else

8 Compute each correlation filter’s response using Eq. 4;

9 Find target position predicted by each weak tracker using Eq. 5;

10 Evaluate the reliability degrees $APCE$ and $F_{max}$ via Eq. 6 and Eq. 8;

11 if  _$\max\limits_{k=1}^{K}APCE$ $\mathrm{and}$
$\max\limits_{k=1}^{K}F_{max}$ $\mathrm{satisfy\ the\ condition}$_ then

12 Draw samples from Eq. 9;

13 else

14 Draw samples from Eq. 9 where $\mathbf{\Sigma}_{t}=3$;

15 end if

16 Compute the ultimate position using Eq. 15;

17 Update the template via Eq. 18;

18 end if

19

20 end for

Algorithm 1 KCF-GPF tracking algorithm

##  4 Experiments

###  4.1 Experimental Setups

Implementation Details. The conventional features used for KCF-GPF are
composed of HOG features and gray normalization features. Our tracker is
implemented on MATLAB in a PC with a 2.80 GHz CPU and runs faster than 21 FPS
in Table 2. Our tracker requires few parameter settings, reported in Table 1,
where ‘padding’ (referring to KCF [19]) means the magnification of the image
region samples relative to the target bounding box.

Table 1: Parameters of KCF-GPF Part of Track | parameters | values
---|---|---
KCF | padding | 1.2
Feature bandwidth $\sigma$ | 0.5
Adaptation rate | 0.045
GPF | Sample numbers $N$ | 200
Learning rate $\theta$ (Eq. 14) | 0.65
Learning rate $\rho$ (Eq. 18) | 0.8

Datasets. Our method is evaluated in the OTB-2013 dataset [43] consisting of
50 sequences. The images are annotated with ground truth bounding boxes and 11
various visual attributes include scale variation, out of view, out-of-plane
rotation, low resolution, in-plane rotation, illumination, motion blur,
background clutter, occlusion, deformation, and fast motion.

Evaluation Metrics. We compare the proposed method with the 16 state-of-the-
art tracking methods using evaluation metrics and code provided by the
respective benchmark dataset. For testing on OTB-2013, we employ the one-pass
evaluation (OPE) and use two metrics: precision and success plots. The
precision metric computes the rate of frames whose center location is within
some certain distance from the ground truth location. The success metric
computes the overlap ratio between the tracked and ground truth bounding
boxes. In the legend, we report the area under curve (AUC) of success plot and
precision score at a 20 pixel threshold (PS) corresponding to the one-pass
evaluation for each tracking method.

###  4.2 Comparison with State-of-the-Art

Table 2: Tracking results of all 17 evaluated trackers over all 50 sequences using OPE evaluation in the OTB-2013. The entries in  red denote the best results and the ones in  blue indicate the second best. OPE Trackers |  LMCF[40] |  CFNet[39] |  CFN[11] |  CFN [11] |  CNT[46] |  BIT[8] |  SINT[38] |  SCT[10] |  Staple[3]
---|---|---|---|---|---|---|---|---|---
precision | 0.842 | 0.803 | 0.813 | 0.784 | 0.723 | 0.816 | 0.851 | 0.836 | 0.793
success | 0.800 | 0.775 | 0.675 | 0.630 | 0.656 | 0.745 | 0.791 | 0.730 | 0.754
OPE Trackers |  SiamFC[4] |  SRDCF[13] |  DSST[12] |  MEEM[45] |  KCF[19] |  TLD[22] |  Struck[17] | KCF-GPF(ours) | mean FPS(ours)
precision | 0.809 | 0.838 | 0.740 | 0.840 | 0.740 | 0.608 | 0.656 | 0.857 |  21.3
success | 0.783 | 0.781 | 0.670 | 0.706 | 0.623 | 0.521 | 0.559 | 0.805

We evaluate KCF-GPF in the OTB-2013 dataset [43] and compare it with 16 state-
of-the-art trackers including LMCF [40], CFNet [39], CFN [11], CFN [11], CNT
[46], BIT [8], SINT [38], SCT [10], Staple [3], SiamFC [4], SRDCF [13], DSST
[12], MEEM [45], KCF [19], TLD [22] and Struck [17]. Among them, LMCF, CFN,
CFN , Staple, SRDCF, KCF, DSST, CFNet and SCT are CF based algorithms; SiamFC,
SINT, CFNet, CNT and BIT are convolutional networks based algorithms; MEEM is
developed based on regression and multiple trackers; TLD is based on an
ensemble classifier; and Struck is structured SVM based methods.

The characteristics and tracking results are summarized in Table 2. The mean
FPS here is estimated on all sequences in the OTB-2013 and achieves 21.3 fps
satisfying the requirement of real-time capability. LMCF achieves the second
best performance in terms of the success metric and SINT shows the second best
performance in terms of precision metric. Figure 5 illustrates the precision
and success plots of all trackers under all challenging attributes in the
OTB-2013. KCF-GPF is also superior to other up-to-date trackers with precision
and success evaluation metrics in the OTB-2013 benchmark.

For detailed analyses, we also evaluate KCF-GPF with these state-of-the-art
trackers on various challenging attributes in the OTB-2013 benchmark dataset
and the results are shown in Figure 3 and Figure 4. The results demonstrate
that KCF-GPF is ranked on top three in each attribute and achieves the best
performances in the general success plots. Besides that, the proposed method
outperforms other trackers in terms of deformation and out-of-plane rotation
attributes.

Figure 3: Success plots over all 50 sequences using OPE evaluation in the
OTB-2013 dataset. The evaluated trackers are LMCF, CFNet, CFN, CFN , CNT, BIT,
SINT, SCT and KCF-GPF. All 11 tracking challenges include scale variation, out
of view, out-of-plane rotation, low resolution, in-plane rotation,
illumination, motion blur, background clutter, occlusion, deformation, and
fast motion. The numbers in the legend indicate the average AUC scores for
success plots. Our KCF-GPF method performs favorably against the state-of-the-
art trackers.

Figure 4: Success plots over all 50 sequences using OPE evaluation in the
OTB-2013 dataset. The evaluated trackers are Staple, SiamFC, SRDCF, DSST,
MEEM, KCF, TLD, Struck and KCF-GPF. All 11 tracking challenges include scale
variation, out of view, out-of-plane rotation, low resolution, in-plane
rotation, illumination, motion blur, background clutter, occlusion,
deformation, and fast motion. The numbers in the legend indicate the average
AUC scores for success plots. Our KCF-GPF method performs favorably against
the state-of-the-art trackers.

Figure 5: Precision and success plots over all 50 sequences using OPE
evaluation in the OTB-2013 dataset. The numbers in the legend indicate the
average precision scores for precision plots and the average AUC scores for
success plots. Our KCF-GPF method performs favorably against the state-of-the-
art trackers.

###  4.3 Qualitative Comparison

To demonstrate the effect of the proposed KCF-GPF tracking algorithm, we make
a qualitative comparison with above state-of-the-art trackers in the OTB-2013
benchmark dataset with 11 different attributes. As shown in Figure 6, all
trackers perform well overall, but the existing trackers have the following
drawbacks. The SCT does not perform well under scale variations (Liquor,
Woman, and Dog1). The CFNet cannot handle occlusion (Lemming, Skating1,
Subway, Singer2, Suv, Liquor, Woman and Soccer), deformation(Skating1, Subway,
Singer2, Suv and Woman) ,out-of-plane rotation (Lemming, Skating1, Singer2,
Liquor, Woman and Soccer) and background clutters (Skating1, Subway, Singer2,
Suv, Liquor and Soccer). The KCF drifts when there are illumination variations
(Shaking, Lemming and Woman), scale variations (Shaking, Lemming, Woman and
Dog1), out-of-plane rotations (Shaking, Lemming, Woman and Soccer), and fast
motions (Woman and Soccer). The TLD and Struck methods drift when target
objects undergo illumination changes (Shaking, Skating1, Singer2 and Soccer),
heavy occlusion (Lemming, Subway, Singer2, Suv, Liquor, Woman and Soccer) and
scale variations (Lemming and Dog1). Overall, the proposed KCF-GPF tracker
performs the best against the existing trackers in tracking objects on these
challenging sequences.

Figure 6: Comparisons of the proposed tracker with the state-of-the-art
trackers (SCT [10], CFNet [39], KCF [19], [22] and Struck [17]) in our
evaluation on 10 challenging sequences (from left to right and top to down are
Shaking, Lemming, Skating1, Subway, Singer2, Suv, Liquor, Woman, Soccer, Dog1,
respectively).

##  5 Conclusion

In this paper, we have proposed a novel tracker combining multiple structural
correlation filters with a multi-task gaussian particle filter, namely KCF-
GPF, to construct a strong tracker for ensemble tracking. The proposed method
takes multiple correlation filters as weak expert trackers, and exploits
spatial-geometric relations between target locations in consecutive frames to
provide weak decisions in a reliable search scope. The reliability degrees of
weak decisions are introduced in experiments for the GPF to make a strong
decision. As a result, it not only has the advantages of the existing
correlation filter trackers, such as, computational efficiency and robustness,
but also can deal with scale variations by the sampling strategy of a GPF. The
proposed KCF-GPF tracking algorithm outperforms 16 state-of-the-art methods
over all 50 sequences in the OTB-2013 benchmark in terms of qualitative and
quantitative evaluations.

## References

  * [1] S. Avidan.  Ensemble tracking.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(2):261–271, 2007.
  * [2] Q. Bai, Z. Wu, S. Sclaroff, M. Betke, and C. Monnier.  Randomized ensemble tracking.  In IEEE International Conference on Computer Vision, pages 2040–2047, 2013.
  * [3] L. Bertinetto, J. Valmadre, S. Golodetz, O. Miksik, and P. H. S. Torr.  Staple: Complementary learners for real-time tracking.  38(2):1401–1409, 2015.
  * [4] L. Bertinetto, J. Valmadre, J. F. Henriques, A. Vedaldi, and P. H. S. Torr.  Fully-convolutional siamese networks for object tracking.  pages 850–865, 2016.
  * [5] C. Berzuini, N. G. Best, W. R. Gilks, and C. Larizza.  Dynamic conditional independence models and markov chain monte carlo methods.  Journal of the American Statistical Association, 92(440):1403–1412, 1997.
  * [6] D. S. Bolme, J. R. Beveridge, B. A. Draper, and Y. M. Lui.  Visual object tracking using adaptive correlation filters.  In Computer Vision and Pattern Recognition, pages 2544–2550, 2010\.
  * [7] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  Foundations and Trends in Machine Learning, 3(1):1–122, 2011.
  * [8] B. Cai, X. Xu, X. Xing, K. Jia, J. Miao, and D. Tao.  Bit: Biologically inspired tracker.  IEEE Transactions on Image Processing, 25(3):1327–1339, 2016.
  * [9] K. Chaudhuri, Y. Freund, and D. Hsu.  A parameter-free hedging algorithm.  Computer Science, pages 297–305, 2009.
  * [10] J. Choi, H. J. Chang, J. Jeong, Y. Demiris, and Y. C. Jin.  Visual tracking using attention-modulated disintegration and integration.  In Computer Vision and Pattern Recognition, pages 4321–4330, 2016\.
  * [11] J. Choi, H. J. Chang, S. Yun, T. Fischer, Y. Demiris, and Y. C. Jin.  Attentional correlation filter network for adaptive visual tracking.  In IEEE Conference on Computer Vision and Pattern Recognition, 2017\.
  * [12] M. Danelljan, G. Hager, F. S. Khan, and M. Felsberg.  Accurate scale estimation for robust visual tracking.  In British Machine Vision Conference, pages 65.1–65.11, 2014.
  * [13] M. Danelljan, G. Hager, F. S. Khan, and M. Felsberg.  Learning spatially regularized correlation filters for visual tracking.  In IEEE International Conference on Computer Vision, pages 4310–4318, 2015.
  * [14] M. Danelljan, G. Hager, F. S. Khan, and M. Felsberg.  Discriminative scale space tracking.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 39(8):1561–1575, 2016.
  * [15] Y. Freund and R. E. Schapire.  A desicion-theoretic generalization of on-line learning and an application to boosting.  In European Conference on Computational Learning Theory, pages 23–37, 1995.
  * [16] F. Gustafsson, F. Gunnarsson, N. Bergman, U. Forssell, J. Jansson, R. Karlsson, and P. J. Nordlund.  Particle filters for positioning, navigation, and tracking.  IEEE Transactions on Signal Processing, 50(2):425–437, 2002.
  * [17] S. Hare, A. Saffari, and P. H. S. Torr.  Struck: Structured output tracking with kernels.  In IEEE International Conference on Computer Vision, pages 263–270, 2012.
  * [18] P. J. Harrison and C. F. Stevens.  Bayesian forecasting. discussion.  Journal of the Royal Statistical Society, 38, 1976.
  * [19] J. F. Henriques, C. Rui, P. Martins, and J. Batista.  High-speed tracking with kernelized correlation filters.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(3):583–596, 2015.
  * [20] Jazwinski and AndrewH.  Stochastic processes and filtering theory.  Academic Press,, 1970.
  * [21] S. J. Julier and J. K. Uhlmann.  Unscented filtering and nonlinear estimation.  Proceedings of the IEEE, 92(3):401–422, 2004.
  * [22] Z. Kalal, K. Mikolajczyk, and J. Matas.  Tracking-learning-detection.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(7):1409, 2012.
  * [23] J. H. Kotecha and P. M. Djuric.  Gaussian particle filtering.  IEEE Transactions on Signal Processing, 51(10):2592–2601, 2003\.
  * [24] Y. Li, J. Zhu, and S. C. H. Hoi.  Reliable patch trackers: Robust visual tracking by exploiting reliable patches.  In Computer Vision and Pattern Recognition, pages 353–361, 2015\.
  * [25] J. S. Liu and R. Chen.  Sequential monte carlo methods for dynamic systems.  Journal of the American Statistical Association, 93(443):1032–1044, 1998.
  * [26] J. S. Liu, R. Chen, and T. Logvinenko.  A Theoretical Framework for Sequential Importance Sampling with Resampling.  Springer New York, 2001.
  * [27] S. Liu, T. Zhang, X. Cao, and C. Xu.  Structural correlation filter for robust visual tracking.  In Computer Vision and Pattern Recognition, pages 4312–4320, 2016\.
  * [28] T. Liu, G. Wang, and Q. Yang.  Real-time part-based visual tracking via adaptive correlation filters.  In Computer Vision and Pattern Recognition, pages 4902–4912, 2015\.
  * [29] C. Ma, J. B. Huang, X. Yang, and M. H. Yang.  Hierarchical convolutional features for visual tracking.  In IEEE International Conference on Computer Vision, pages 3074–3082, 2015.
  * [30] C. Ma, X. Yang, C. Zhang, and M. H. Yang.  Long-term correlation tracking.  In IEEE Conference on Computer Vision and Pattern Recognition, pages 5388–5396, 2015.
  * [31] J. Mendel.  Optimal filtering.  IEEE Transactions on Automatic Control, 25(3):615–616, 1980.
  * [32] R. V. D. Merwe, A. Doucet, N. D. Freitas, and E. Wan.  The unscented particle filter.  Advances in Neural Information Processing Systems, 13:584–590, 2001\.
  * [33] K. Nummiaro, E. Koller-Meier, and L. V. Gool.  An adaptive color-based particle filter.  Image and Vision Computing, 21(1):99–110, 2003.
  * [34] Y. Qi, S. Zhang, L. Qin, H. Yao, Q. Huang, J. Lim, and M. H. Yang.  Hedged deep tracking.  In Computer Vision and Pattern Recognition, pages 4303–4311, 2016\.
  * [35] C. Rui, P. Martins, and J. Batista.  Exploiting the circulant structure of tracking-by-detection with kernels.  In European Conference on Computer Vision, pages 702–715, 2012\.
  * [36] A. W. M. Smeulders, D. M. Chu, R. Cucchiara, S. Calderara, A. Dehghan, and M. Shah.  Visual tracking: An experimental survey.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(7):1442–1468, 2014.
  * [37] H. W. Sorenson.  Recursive estimation for nonlinear dynamic systems.  Bayesian Analysis of Time, 1988.
  * [38] R. Tao, E. Gavves, and A. W. M. Smeulders.  Siamese instance search for tracking.  In Computer Vision and Pattern Recognition, pages 1420–1429, 2016\.
  * [39] J. Valmadre, L. Bertinetto, J. F. Henriques, A. Vedaldi, and P. H. S. Torr.  End-to-end representation learning for correlation filter based tracking.  2017\.
  * [40] M. Wang, Y. Liu, and Z. Huang.  Large margin object tracking with circulant feature maps.  2017\.
  * [41] N. Wang and D. Y. Yeung.  Ensemble-based tracking: aggregating crowdsourced structured time series data.  In International Conference on International Conference on Machine Learning, pages II–1107, 2014.
  * [42] G. Welch and G. Bishop.  An introduction to the kalman filter.  University of North Carolina at Chapel Hill, 8(7):127–132, 2010\.
  * [43] Y. Wu, J. Lim, and M. H. Yang.  Online object tracking: A benchmark.  In IEEE Conference on Computer Vision and Pattern Recognition, pages 2411–2418, 2013.
  * [44] A. Yilmaz.  Object tracking: A survey.  Acm Computing Surveys, 38(4):13, 2006.
  * [45] J. Zhang, S. Ma, and S. Sclaroff.  Meem: Robust tracking via multiple experts using entropy minimization.  In European Conference on Computer Vision, pages 188–203, 2014\.
  * [46] K. Zhang, Q. Liu, Y. Wu, and M. H. Yang.  Robust visual tracking via convolutional networks without training.  IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society, 25(4):1779, 2016.


# Online Speculative Decoding

Xiaoxuan Liu 1 Lanxiang Hu2 Peter Bailis3 Ion Stoica1

Zhijie Deng4 Alvin Cheung1 Hao Zhang2∗

1 UC Berkeley 2 UCSD 3 Sisu Data 4 SJTU

{xiaoxuanliu, istoica<EMAIL_ADDRESS>

{lah003<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Corresponding author

###### Abstract

Speculative decoding is a pivotal technique to accelerate the inference of
large language models (LLMs) by employing a smaller draft model to predict the
target model’s outputs. However, its efficacy can be limited due to the low
predictive accuracy of the draft model, particularly when faced with diverse
text inputs and a significant capability gap between the draft and target
models. We introduce online speculative decoding to address this challenge.
The main idea is to continually update (multiple) draft model(s) on observed
user query data using the abundant excess computational power in an LLM
serving cluster. Given that LLM inference is memory-bounded, the surplus
computational power in a typical LLM serving cluster can be repurposed for
online retraining of draft models, thereby making the training cost-neutral.
Since the query distribution of an LLM service is relatively simple,
retraining on query distribution enables the draft model to more accurately
predict the target model’s outputs, particularly on data originating from
query distributions. As the draft model evolves online, it aligns with the
query distribution in real time, mitigating distribution shifts. We develop a
prototype of online speculative decoding based on online knowledge
distillation and evaluate it using both synthetic and real query data on
several popular LLMs. The results show a substantial increase in the token
acceptance rate by 0.1 to 0.65, which translates into 1.22$\times$ to
3.06$\times$ latency reduction. Code is available at
https://github.com/LiuXiaoxuanPKU/OSD.

##  1 Introduction

Large language models (LLMs) such as GPT-4 (OpenAI, 2023), Claude (Bai et al.,
2022), and Llama (Touvron et al., 2023a; b) are rapidly reinventing today’s
applications. Many companies are racing to deploy LLMs in their vertical
domains, such as search, chatbots, and virtual assistants. Since most of these
applications demand low latency, optimizing LLM serving latency is of vital
importance and can directly translate into better quality of service and cost
reduction.

The latency of today’s LLM service is unfortunately very high. This is
primarily because serving a user query requires multiple serial evaluations of
the LLM, each generating only one token of the response. An emerging solution
to reduce the latency is speculative decoding. Speculative decoding employs a
smaller model to speculate multiple output tokens of the target (large) model,
then lets the target LLM verify these speculations in parallel. Then, if the
verification of a token fails, the large model must recompute from that point.
Therefore, the performance of speculative decoding primarily depends on the
speculation accuracy of the small model. In the presence of diverse text
inputs, the accuracy of existing speculative decoding methods is unfortunately
not very high, due to the capability gap between the draft and target model.
Employing a larger, more accurate model however defeats the purpose of
speculative decoding as it potentially increases latency.

To address this challenge, we introduce a novel method, _online speculative
decoding_ , specifically designed for online LLM services. The method
leverages the abundant redundant compute, termed as “spare flops,” available
in a typical LLM serving cluster to continuously retrain (multiple) small
draft models through online learning on query data posted to the LLM service.
Our approach is simple and offers several significant advantages. First, user
queries to a specific LLM service often exhibit a common domain-specific
distribution (Zheng et al., 2023a), reflecting shared usage patterns. While
accurately speculating the larger model’s outputs on _any diverse input_ is
challenging, it is feasible to enhance the draft model’s prediction accuracy,
_only for similar inputs posted to the service_ , characterized by the query
distribution. This can be achieved by finetuning the draft model on user query
distribution or finetuning multiple draft models, each on a cluster of the
query distribution, and selecting the appropriately specialized draft model to
speculate based on the class of inputs they are trained on. As shown in §5.2,
we show that it is possible to train multiple draft models, each for a
different language or topic. Second, the primary bottleneck for transformer-
based LLM inference is the accelerator’s memory bandwidth, as generating each
word requires loading the model weights from HBM to SRAM as well as reading
the KV cache on all previous words. This results in a substantial amount of
unused compute, especially during non-spike traffic hours (Spector & Re, 2023;
Chen et al., 2023; Kwon et al., 2023), in an LLM serving cluster. We
demonstrate that these spare FLOPs can be effectively repurposed for online
retraining of draft models, with inconspicuous retraining cost (§4.2.2).
Third, since tuning is performed online, the draft models continuously evolve
over time based on the observed query data, which ensures high speculation
accuracy even when faced with shifts in query distribution.

Based on these insights, we develop an online speculative decoding framework
to improve the efficiency of online LLM serving. To align the draft model with
the target model on a newly observed user query, we develop a new online
learning algorithm based on Generalized Knowledge Distillation (GKD) (Gu et
al., 2023; Agarwal et al., 2023). The algorithm keeps track of the recent
queries that the draft model has speculated incorrectly, and forces the draft
model to emulate the target model’s outputs on these queries. The algorithm
performs GKD-based gradient update opportunistically only when spare flops are
available, hiding the overhead.

Figure 1: Online speculative decoding overview. For each prompt, the draft
model suggests multiple tokens in a single step. The target model then
verifies these tokens, accepting some and rejecting others. If the student
proposes incorrect tokens, both the draft and target distributions are stored
in a buffer. Once the buffer exceeds a specified threshold, the draft model is
updated by calculating the loss between the draft and target distributions
using various distance metrics.

In summary, this paper makes the following contributions:

  * •

We introduce online speculative decoding to reduce LLM serving latency by
adapting (multiple) draft models on the fly using query data and knowledge
distillation.

  * •

We explore various GKD methods for constructing draft models and identify the
most effective variants, suggesting them as superior alternatives to existing
finetuning methods in offline settings.

  * •

Our method demonstrates a significant improvement in token acceptance rate by
10-65% on diverse datasets, translating to 1.2-3.1$\times$ reduction in
latency theoretically, with a negligible additional cost. It surpasses
existing methods which construct static draft models using fine-tuning or
distillation on offline datasets, and matches the hypothetical accuracy
achieved if all query data were available a priori.

##  2 Related Work

LLMs have become pervasive in today’s AI applications, underscoring the
importance of optimizing LLM inference. Numerous system optimizations have
been developed to optimize the throughput of LLM serving (Yu et al., 2022;
Kwon et al., 2023). This paper particularly concentrates on a significant
strand of research, speculative decoding, aimed at reducing the latency of LLM
inference.

Speculative decoding. Speculative decoding (Leviathan et al., 2023; Chen et
al., 2023) accelerates LLM decoding by employing a (small) draft model to
predict the outputs of the larger target model, which are then verified by the
target model. Typically, the draft model, while having fewer parameters, is
pretrained using the same training data as the target mode, resulting in a
negotiable inference cost but with compromised capability. If the draft model
can correctly predict more than one token per verification step, the memory
I/O for accessing the model weights and KV cache at inference is amortized
across multiple output tokens, thereby reduces latency, especially since LLM
inference is often constrained by GPU HBM bandwidth. The efficacy of
speculative decoding largely hinges on the draft model’s ability to accurately
predict the target model’s outputs. Existing work improves the speculation
accuracy by using multiple collectively boosted (Miao et al., 2023) or staged
(Spector & Re, 2023) draft models, or retraining the target model with
auxiliary prediction heads as a draft model (Cai et al., 2023; Stern et al.,
2018). These methods predominantly assume a static draft model post-
deployment. In contrast, our work introduces a framework that actively adapts
the draft model to the evolving user query distribution on the fly,
irrespective of the draft model’s construction.

Distillation for auto-regressive models. Knowledge distillation (KD) is a
framework to generate smaller models that emulate the performance of larger
models. However, KD in its conventional form has been observed to be less
effective for LLMs. Gu et al. (2023) extend KD to autoregressive LLMs by
decoding from the student model and optimizing the reserve KL divergence
between students and teachers. Further, Agarwal et al. (2023) introduce
generalized knowledge distillation (GKD) to optimize a linear combination of
the forward KL and reverse KL between teacher and student, using a blend of
teacher- and student-sampled data. Drawing inspiration from both works, our
paper applies KD to speculative decoding for LLMs. We empirically determine
the most effective KD variant for maximizing the draft model’s accuracy, and
extend it to dynamically generate draft models for online LLM services.

##  3 Background

We first briefly review speculative decoding (Leviathan et al., 2023), a
critical technique that accelerates inference of a large target LLM
$p(\cdot|{\bm{x}})$ with token proposals from a small draft model
$q_{\bm{\theta}}(\cdot|{\bm{x}})$. ${\bm{x}}$ denotes the concatenation of the
input prompt and already generated tokens. The two distributions are both
auto-regressive. We emphasize the parameters ${\bm{\theta}}$ of the draft
model because we usually need to tailor them according to the target LLM for
more substantial acceleration.

Speculative decoding uses a (small) draft model to propose $k$ tokens
${{\bm{y}}}\triangleq\\{y_{i}\\}_{i=1}^{k}\sim
q_{\bm{\theta}}(\cdot|{\bm{x}})$, and let the target LLM estimate the $k+1$
probabilities,
$\\{p({y}|{\bm{x}},{{\bm{y}}}_{<i})\\}_{i=1}^{k+1}$111${{\bm{y}}}_{<i}$ refers
to $\\{y_{j}\\}_{j=1}^{i-1}$., in parallel. With $i$ rising from $1$ to $k$,
speculative decoding accepts the proposal ${y}_{i}$ if $u\leq
p(y_{i}|{\bm{x}},{{\bm{y}}}_{<i})/q_{\bm{\theta}}({y}_{i}|{\bm{x}},{{\bm{y}}}_{<i})$
where $u\sim U[0,1]$; otherwise exits. Let $a$ denote the number of accepted
tokens, which takes values in $\\{0,\dots,k\\}$. We can sample an additional
token ${y}_{a+1}$ from the following distribution

$p^{\prime}(y)=\begin{cases}p(y|{\bm{x}},{{\bm{y}}}_{<a+1})&\text{if $a=k$}\\\
\mathrm{norm}(\max(0,p(y|{\bm{x}},{{\bm{y}}}_{<a+1})-q_{\bm{\theta}}(y|{\bm{x}},{{\bm{y}}}_{<a+1})))&\text{otherwise}\end{cases}$
(1)

where $\mathrm{norm}(\cdot)$ makes the probabilities over the vocabulary sum
to $1$.

Prior work has shown that the resulting samples
$\tilde{{\bm{y}}}\triangleq\\{{y}_{1},\dots,y_{a+1}\\}$ strictly follow the
distribution of the target LLM $p(\cdot|{\bm{x}})$ (Leviathan et al., 2023).
We concatenate $\tilde{{\bm{y}}}$ to ${\bm{x}}$ and repeat the above process
until meeting ⟨EOS⟩. Each run of the target LLM generates $a+1$ tokens with
$a\geq 0$. This ensures that at least one new token is generated even in the
worst case. The generation process can be significantly accelerated if the
draft LLM better approximates the target one, particularly $a$ is larger for
each target LLM run.

Expected acceptance rate & speedup. The acceptance rate, denoted as $\alpha$,
serves as a measure of how closely the draft model approximates the target
model. It is defined as the expected probability that speculative decoding
will accept a proposal token given the prompt $y_{i}\sim
q_{\bm{\theta}}(y_{i}|{\bm{x}},{{\bm{y}}}_{<i})$. This rate directly
influences the expected length ($\mathbb{E}(|\tilde{{\bm{y}}}|)$) of
$\tilde{{\bm{y}}}$ for each target LLM run and the speedup brought by
speculative decoding.

Assuming that the $k+1$ simultaneous evaluations of the target LLM $p$ take
roughly the same amount of time as generating a single token in parallel, let
$c$ be the time ratio for a single run between $q_{\bm{\theta}}$ and $p$. The
expected generation length of a single target LLM run and the speedup in the
total wall time due to speculative decoding is represented as (Leviathan et
al., 2023):

$\mathbb{E}(|\tilde{{\bm{y}}}|)=\frac{1-\alpha^{k+1}}{1-\alpha},\quad\mathbb{E}(speedup)=\frac{1-\alpha^{k+1}}{(1-\alpha)(kc+1)}.$
(2)

We depict the speedup for varying values of $\alpha$ in Figure 2, which
demonstrates the importance of $\alpha$ in affecting the speedup.

Figure 2: Speculative decoding speedups for varying values of $\alpha$ in
Figure 2. For smaller $\alpha$ values, speculative decoding may even degrade
performance (indicated by a speedup $<1$), particularly when the draft model
is sizeable. Furthermore, the relationship between speedup and $\alpha$ is
superlinear; doubling the acceptance rate can yield a speedup exceeding
2$\times$.

Observation. Interestingly, we can actually enhance $\alpha$ based on a key
observation: the speculative decoding process inherently identifies the
inaccuracies of the small draft LLM and offers correct solutions for these
inaccuracies. This essentially means that we receive valuable insights on the
areas and strategies to refine the draft model at no additional cost. Viewed
through the lens of online learning, we can effortlessly accumulate a set of
input-output pairs, denoted as
$([{\bm{x}},{\bm{y}}_{<a+1}],p(y|{\bm{x}},{{\bm{y}}}_{<a+1}))$, that have yet
to be assimilated by the draft LLM, paving the way for its subsequent
optimization. Given the reduced size of the draft model (for instance, it may
be over $20\times$ smaller than the target model), its tuning is not only
efficient but also viable for real-time online adjustments. Prior work
(Leviathan et al., 2023; Miao et al., 2023) has primarily approached
speculative decoding in an offline manner, meaning the draft model remains
static during online deployment. We next develop online speculative decoding
to bridge this gap.

##  4 Online Speculative Decoding

We propose the online speculative decoding approach to update the draft model
dynamically for more effective suggestions. We frame the learning problem
based on the aforementioned auxiliary information as online knowledge
distillation, where the teacher and student models correspond to the target
and draft LLMs in speculative decoding, respectively. We elaborate on the
details below.

###  4.1 Knowledge Distillation for Speculative Decoding

Knowledge distillation is a general framework to align the predictive
distribution of a small model (i.e., student model) with that of a larger one
(i.e., teacher model). Prior research has utilized knowledge distillation to
compress neural networks, resulting in decreased inference costs and memory
requirements. We posit that knowledge distillation is highly effective for
speculative decoding. In this approach, the draft model acts as the student
and the target model serves as the teacher. During speculative decoding, we
possess complete information on both the proposed and verified probabilities
of each token. This information helps to construct objectives for distilling
the draft model, aligning its output distributions with those of the target
model and thereby improving the token acceptance rate of the draft model. The
distillation loss generally takes the form of:

$\displaystyle\ell({\bm{\theta}})$
$\displaystyle=\frac{1}{n_{B}}\sum_{{\bm{x}}^{(i)}\in\mathcal{B}}\ell({\bm{x}}^{(i)},{\bm{\theta}}),\quad\ell({\bm{x}},{\bm{\theta}})=D({p(\cdot|{\bm{x}})}\|{q_{\bm{\theta}}(\cdot|{\bm{x}})}),$
(3)

where $\mathcal{B}=\\{{\bm{x}}^{(i)}\\}_{i=1}^{n_{B}}$ denotes a batch of
inputs and $D$ denotes some distance measure.

Distance measure. In the case of auto-regressive models, the prediction
distribution is categorical at each token. Often, we can augment the predicted
logits with a tunable temperature $\tau$ for softmax transformation. We then
use the popular forward KL and reverse KL (RKL), as well as their mixture
(i.e., the JSD divergence) to instantiate $D$ (Agarwal et al., 2023; Gu et
al., 2023):

$\displaystyle\ell_{KL}({\bm{x}},{\bm{\theta}})=D_{\mathrm{KL}}({p(\cdot|{\bm{x}})}\|{q_{\bm{\theta}}(\cdot|{\bm{x}})}),$
(4)
$\displaystyle\ell_{RKL}({\bm{x}},{\bm{\theta}})=D_{\mathrm{KL}}({q_{\bm{\theta}}(\cdot|{\bm{x}})}\|{p(\cdot|{\bm{x}})}),$
$\displaystyle\ell_{{JSD}[\beta]}({\bm{x}},{\bm{\theta}})=\beta
D_{\mathrm{KL}}\left({p(\cdot|{\bm{x}})}\big{\|}{p}^{\beta}_{\bm{\theta}}(\cdot|{\bm{x}})\right)+(1-\beta)D_{\mathrm{KL}}\left({q_{\bm{\theta}}(\cdot|{\bm{x}})}\big{\|}{p}^{\beta}_{\bm{\theta}}(\cdot|{\bm{x}})\right),$

where
${p}^{\beta}_{\bm{\theta}}(\cdot|{\bm{x}})\triangleq\beta{p(\cdot|{\bm{x}})}+(1-\beta){q_{\bm{\theta}}(\cdot|{\bm{x}})}$.
These objectives diverge from the conventionally used label-based fine-tuning
objectives in speculative decoding, as highlighted in (Miao et al., 2023;
Leviathan et al., 2023). As shown in Section 5.1, objectives based on the KL
divergence prove to be more effective. This is because distributions convey
richer information than mere labels, thereby enhancing their capability to
guide the student model (Hinton et al., 2015). Additionally, these objectives
enhance convergence rates (He et al., 2022) and bolster calibration. The
reverse KL is highlighted for its mode-seeking behavior, offering unique
advantages (Gu et al., 2023). In our study, and in alignment with previous
research (Agarwal et al., 2023), we empirically determine that the optimal
distance measure can vary depending on the tasks and the relative capacities
of the teacher and student models (see §5.1).

Sampling and gradient estimation. Estimating the above objectives involves the
expectation over $q_{\bm{\theta}}(\cdot|{\bm{x}})$ or $p(\cdot|{\bm{x}})$,
which should be expanded recursively. Once the recursion depth exceeds $1$, we
can not analytically compute $D_{\mathrm{KL}}$ but hinge on Monte Carlo
approximation. When sampling from $q_{\bm{\theta}}(\cdot|{\bm{x}})$, we should
differentiate through the sampling process for unbiased gradient estimation.
However, this leads to policy gradient-style estimators and should rely on
elaborate policies such as reward hacking and single-step regularization to
reduce gradient variance and stabilize training (Gu et al., 2023).

In comparison, a more straightforward approach is to omit the differentiation
through the sampling process (Agarwal et al., 2023), where the sample
${\bm{y}}$ is directly plugged into the objective:

$\ell({\bm{x}},{\bm{\theta}})\approx\sum_{j=1}^{|{\bm{y}}|+1}D({p(y|{\bm{x}},{\bm{y}}_{<j})}\|{q_{\bm{\theta}}(y|{\bm{x}},{\bm{y}}_{<j})}).$
(5)

This way, various distance measures can be readily applied. Besides, the
sampling becomes disentangled from the distance measure. i.e., we sample
${\bm{y}}$ from an arbitrary mixture of ${p}(\cdot|{\bm{x}})$ and
${q}_{\theta}(\cdot|{\bm{x}})$ but use KL, RKL or JSD for estimating the
distribution mis-alignment.

Intuitively, the samples from the teacher model are usually coherent, which
may raise difficulties in fitting the small student model, while samples from
the student model may be less structured or even meaningless. A workaround
strategy is to trade off between them via mixed sampling (Gu et al., 2023),
i.e.,
$y_{j}\sim\beta{p(\cdot|{\bm{x}},{\bm{y}}_{<j})}+(1-\beta)q_{\bm{\theta}}(\cdot|{\bm{x}},{\bm{y}}_{<j})$.

###  4.2 Online Knowledge Distillation

This section expands the application of knowledge distillation for speculative
decoding in online environments. The approach enables improving the
performance of draft model using results from speculative decoding, thus
dynamically adapting to the query distribution and improving token acceptance
rate. We also discuss the trade-off of our approach when integrating LLM
serving systems.

####  4.2.1 Algorithm

Algorithm 1 Online Speculative Decoding.

1: Input: Target LLM $p(\cdot|{\bm{x}})$, draft LLM
$q_{\bm{\theta}}(\cdot|{\bm{x}})$, warmup dataset $\mathcal{D}$, online data
stream $\mathcal{S}$, guess number $k$, temporary buffer $\mathcal{R}$, replay
buffer $\mathcal{Q}$, update interval for the draft model $I$.

2: Pre-train $q_{\bm{\theta}}$ to approximate $p$ with data from $\mathcal{D}$
by minimizing $\ell({\bm{x}},{\bm{\theta}})$ using Equation 5;

3: $i\leftarrow 0$;

4: $\mathcal{Q}\leftarrow[]$;

5: $cur\\_len=|{\bm{x}}|$ // Total sequence length, including prompt length
and tokens generated so far.

6: while True do

7: $\mathcal{R}\leftarrow[]$ // List of ($error\\_index$, target logits at
$error\\_index$) pairs for a single request.

8: ${\bm{x}}\sim\mathcal{S}$, $i\leftarrow i+1$;

9: while ⟨EOS⟩ not in ${\bm{x}}$ do

10: ${{\bm{y}}}=\\{{y}_{1},...,{y}_{k}\\}\sim
q_{\bm{\theta}}(\cdot|{\bm{x}})$;

11: Estimate $\\{p({y}|{\bm{x}},{{\bm{y}}}_{<i})\\}_{i=1}^{k+1}$ in parallel;

12: Determine number of accepted tokens $a$ and sample one more token,
yielding ${\bm{y}}=\\{{y}_{1},\dots,y_{a+1}\\}$;

13: $cur\\_len\leftarrow cur\\_len+a+1$;

14: $error\\_index\leftarrow cur\\_len$;

15: Append $(error\\_index,p(y|{\bm{x}},{{\bm{y}}}_{<a+1}))$ to $\mathcal{R}$;

16: ${\bm{x}}\leftarrow[{\bm{x}},{{\bm{y}}}_{<a+2}]$;

17: end while

18: Append $({\bm{x}},\mathcal{R})$ to $\mathcal{Q}$;

19: if $i\;\mathrm{mod}\;I=0$ then

20: Update $q_{\bm{\theta}}$ on $\mathcal{Q}$ to minimize
$\ell({\bm{x}},{\bm{\theta}})$ analytically;

21: $\mathcal{Q}\leftarrow[]$;

22: end if

23: end while

We depict our online speculative decoding algorithm (OSD) in Algorithm 1. OSD
begins by training the draft model using the warmup dataset (Line 2). The
serving system then continuously handles incoming requests (as described in
Lines 6 to 23). For each request, it uses standard speculative decoding (Lines
10-11) to generate responses until the ⟨EOS⟩ token. Concurrently, OSD tracks
the token index ($error\\_index$) and target logits where the draft model
proposes the wrong tokens (Line 15). Leveraging tracked information, OSD
updates the draft model every $I$ iteration, with $I$ being a dynamically
adjustable parameter. OSD updates the draft model with different loss
functions (Line 20) as described in Section 4.1. The choice of loss function
depends on the specific (draft, target) model pairs and the corresponding
input data.

Discussion. OSD utilizes a replay buffer, $\mathcal{Q}$, to capture all
pertinent information for updating the draft model. Various eviction policies
can be employed to maintain a compact size for $\mathcal{Q}$. For example, one
could opt to retain only the most informative pairs or the most recent
entries. Similarly, users have the option to retain data in $\mathcal{Q}$ even
after utilizing it to update the model multiple times. Determining the optimal
eviction/retention strategy is a subject for future exploration. In the
current study, we refrain from evicting any pairs and release $\mathcal{Q}$
after each model update. Furthermore, $I$ is a dynamic parameter. Depending on
the system load and the rate at which the query distribution changes, users
can adjust $I$ accordingly. For example, we can perform a gradient update
opportunistically only when the service traffic is not on spike (i.e., spare
flops are available). Overall, OSD continuously improves the draft model’s
approximation (indicated by increased token acceptance rate $\alpha$) by
learning from the target model during the serving phase. We next demonstrate
how the enhanced acceptance rate directly contributes to a reduction in
request latency.

####  4.2.2 Latency & Flops Analysis

Latency. As detailed in Appendix A.2, compared with standard speculative
decoding, the expected speedup for online speculative decoding is
$\frac{1+\alpha_{2}+\alpha_{2}^{2}+...+\alpha_{2}^{k}}{1+\alpha_{1}+\alpha_{1}^{2}+...+\alpha_{1}^{k}}$.
Based on the data from our experiment (refer to Table 1), when compared to
standard speculative decoding, we expect a speedup improvement for Vicuna-7B
(LLaMA-160M as the draft model) by factors of $2.42\times$, $1.43\times$,
$1.64\times$, and $1.22\times$. Similarly, for Flan-T5-XL 3B (T5-small 80M as
the draft model), the speedup enhancements are $3.06\times$, $1.76\times$,
$2.72\times$, and $1.55\times$ across the four evaluated datasets.

FLOPs. (1) The FLOPs required to update the draft model are significantly
fewer than those needed for inference on a large model. As elaborated in
Appendix A.3, for the two evaluated model pairs, the FLOPs ratio between the
target model and the draft model is 18.75 for the pair (LLaMA-160M, Vicuna7B),
and 12.6 for the pair (T5-small 80M, Flan-T5-XL 3B). (2) In practical systems,
the FLOPs required for inference are significantly below the machine’s
capacity. The Appendix A.3 provides an analysis of Arena chatbot traces where
the cluster’s computational utilization is under 1 percent. Given the above
two observations, it becomes evident that the FLOPs spent on inference and
updating the draft model are relatively insignificant when juxtaposed with the
FLOPs consumed while operating the target model and the cluster’s total FLOPs.

##  5 Experiments

To assess the efficacy of our method, we initially evaluate its ability to
improve the token acceptance rate ($\alpha$) within an offline context. This
provides us with a theoretical upper bound on the performance improvements
achievable when the query distribution remains constant. Subsequently, we
examine the approach’s impact in an online environment, discovering that the
acceptance rate improves even with a moderate amount of data while maintaining
accuracy levels comparable to those in the offline scenario. Throughout our
experiments, we employ two target models ($M_{p})$: Vicuna-7B (Chiang et al.,
2023) and FLAN-T5-XL (3B) (Chung et al., 2022). Specifically for Vicuna-7B, we
utilize LLaMA-160m (Miao et al., 2023) as the draft model ($M_{q}$). For
FLAN-T5-XL, we use T5-Small (Raffel et al., 2020) as the draft model. We
evaluate performance across four diverse datasets: Text-to-SQL (Spider) (Yu et
al., 2018), graduate school math (Gsm8k) (Cobbe et al., 2021), Python code
generation (Code-search-Python) (Husain et al., 2019), and financial question
answering (Alpaca-finance) (Bharti, 2023). In all experiments, we set the
number of proposed tokens to 5 for speculative decoding. For all online
experiments, we fix the update interval $I$ at 8.

###  5.1 Offline Evaluation

In this section, we assess the efficacy of employing knowledge distillation to
train a small model specifically for speculation in an offline environment. In
such a setting, the speculative $M_{q}$ model has unrestricted access to the
dataset, and the query distribution remains stable. To emulate these offline
conditions, we distill the $M_{q}$ using the training dataset for two epochs
and subsequently evaluate its performance by measuring the average token
acceptance rate ($\alpha$) on the test set. As detailed in Section 4.1, we
evaluated various sampling methods, namely teacher sampling, student sampling,
and mix token-level sampling. Table 1 displays the token acceptance rate of
the draft model for each method, using forward KL as the distance metric on
the test dataset. For comparison, we also provide the acceptance rate for
teacher-generated label fine-tuning and the original model.

For both the Vicuna-7B and FLAN-T5-XL models, the teacher sampling method
outperforms others by achieving the highest acceptance rate. Furthermore,
knowledge distillation has proven its efficacy in enhancing the draft model’s
approximation, resulting in a high token acceptance rate. Intriguingly, we
also find that fine-tuning with teacher-generated labels yields impressive
performance on the Vicuna-7B model. Lastly, we experimented with different
distance measurements like reverse KL and JSD. Nevertheless, these
measurements either paralleled or underperformed when compared to forward KL.
Such empirical findings underscore that the optimal distance measurement or
sampling method varies depending on the task and model, and we leave to future
work to find the best combination.

Table 1: Token acceptance rates ($\alpha$) after two epochs. FT: Finetuning on teacher-generated labels. TF, SF, MixF: Teacher, student, and mix token sampling respectively, all with forward KL.  Model | Task | Original | FT | TF | SF | MixF
---|---|---|---|---|---|---
Vicuna-7B | Spider | 0.28 | 0.74 | 0.76 | 0.62 | 0.70
Gsm8k | 0.58 | 0.74 | 0.75 | 0.67 | 0.73
Code-search-Python | 0.38 | 0.65 | 0.65 | 0.51 | 0.61
Alpaca-finance | 0.57 | 0.68 | 0.67 | 0.63 | 0.65
FLAN T5-XL | Spider | 0.13 | 0.33 | 0.78 | 0.67 | 0.70
Gsm8k | 0.29 | 0.50 | 0.62 | 0.51 | 0.55
Code-search-Python | 0.28 | 0.44 | 0.81 | 0.67 | 0.78
Alpaca-finance | 0.39 | 0.56 | 0.63 | 0.59 | 0.60

###  5.2 Online Evaluation

Online Learning. First, we evaluate the effectiveness of our online algorithm
by addressing two key questions: (1) Does the online algorithm increase the
token acceptance rate? And is this enhancement comparable to the rates
achieved in offline settings, which serve as an upper bound given their full
access to data? (2) How quickly does the online algorithm increase the token
acceptance rate, thereby indicating that the compact model has grasped the
underlying distribution?

In our approach, we replicate the online serving process by iterating through
the datasets, extracting prompts, and streaming generation requests. The
system utilizes speculative decoding for each of these requests. Throughout
this serving phase, we continually refine the speculative models, as detailed
in Algorithm 1. For our baseline, we envision a scenario where the serving
system has the capability to collect data offline in order to distill an
initial draft model. This model is subsequently deployed online to cater to
future requests. This process is simulated by using 10% of the dataset to
distill the draft model, which remains static during online serving. For
evaluation metrics, we calculate token acceptance rates averaged over the most
recent 50 requests. This demonstrates $M_{q}$’s efficacy on the most current
data.

Figure 3: Online acceptance rate ($\alpha$) across different datasets. The
x-axis represents the number of records that OSD has processed. Alpha is
averaged over the most recent 50 records. Figure 4: Distribution Shift: Alpha
is averaged over the most recent 100 records.

As depicted in Figure 2, both for Vicuna-7B and FLAN-T5, in the beginning, OSD
yields a lower token acceptance rate in comparison to the offline distilled
model. Nevertheless, these acceptance rates rise swiftly as the draft model is
exposed to more data. We also annotate the token acceptance rate from the
offline setting to highlight the potential peak performance that the online
serving system could reach. In all instances, the online context can achieve
comparable results. In some scenarios, OSD even surpasses the token acceptance
rate of the offline test alphas. This discrepancy can be attributed to the
fact that offline test alphas are assessed on the entire test dataset, whereas
the online alphas represent the moving average of the latest 50 requests. It’s
plausible that OSD performs optimally on specific data subsets, particularly
if those subsets are more narrowly distributed than the complete dataset.

Distribution Shifts. We evaluate OSD’s ability to adapt to changes in data
distribution. We detail the dataset preparation in Appendix A.5. As
illustrated in Figure 4, OSD’s alpha value dips notably at distribution
boundaries, especially around 2K, 4K, and 6K records. This is anticipated
since the draft model initially struggles when faced with a new distribution.
However, the alpha value rebounds quickly as OSD processes more data,
highlighting its adaptability to shifting query distributions.

We also compared our results to those from a static setting. To ensure the
draft model wasn’t just memorizing data, we chose samples distinct from the
online evaluation data. These samples correspond to 30%, 50%, 70%, and 100% of
each dataset’s online evaluation volume, at 0.6K, 1K, 1.4K, and 2K quantities
respectively. As depicted in Figure 4, upon an initial shift in query
distribution, OSD’s performance aligns with or slightly trails the
distillation with 30% data. However, it quickly catches up, matching or even
surpassing performances seen with 70% to 100% data access. This highlights
OSD’s ability to rival models fully exposed to the query distribution, even
without intimate knowledge of the underlying query dynamics.

Real Workloads. We evaluate OSD on real LMSYS-chat conversations (Appendix
A.6) that span 4 months. First, we categorize conversations based on the
language and we focus on conversations among the top five languages, excluding
English. For every chosen language, we use an independent LLaMA-160M to serve
as our draft model. All draft models share the same Vicuna-7B as the target
model. The token acceptance rate, averaged over the latest 100 requests,
showed in Figure 5, reveals that OSD’s enhances rates by 0.1 to 0.2, even with
under 2K data points. Notably, Japanese was the easiest while Portuguese was
the toughest. We also clustered English conversations by topics using the
fine-tuned distilled Bert model (Luqmani, 2023), focusing on the top five. For
topics with over 5K conversations, we sampled evenly to keep it within 5K.
Figure 5 shows acceptance rates above 0.6 across topics, with Social and
Computer discussions peaking near 0.8.

Figure 5: Chatbot Arena Conversations clustered by language and topic.

Figure 6: Precision and recall of high-frequency tokens. The x-axis shows the
rating of the tokens based on their occurrence in the generated answers. For
instance, token 1 appears most frequently in answers. Precision = # of times
token $i$ is accepted by the target model / # of times token $i$ is proposed
by the draft model. Recall = # of times token $i$ is accepted by the target
model / # of times token $i$ appears in the final answer.

###  5.3 Qualitative Analysis

In this section, we conduct a comprehensive analysis to understand how our
method enhances the token acceptance rate, and which tokens the draft model
acquires across varying query distributions.

High-frequency tokens precision and recall. In our experiment using the Spider
dataset, Vicuna-7M is the target model and LLaMA-160M the draft. We identify
the top 100 tokens most frequently generated by the target model, which
account for 72.2% of all appearances, following a power-law distribution.
Figure 6 shows a marked improvement in both accuracy and recall of these
tokens after distillation on the test dataset in an offline evaluation.

Table 2: Top 15 tokens with the most recall/precision improvement across datasets. We ignore _ before tokens, which represents space in the LLaMA tokenizer. Dataset |  Spider |  Gsm8k |  Alpaca-Finance |  Code-Python
---|---|---|---|---
Tokens with the greatest precision increase |  AV, SELECT, first, ⟨EOS⟩, template, SUM, G, COUNT, \n, city, WHERE, ’;, (, IST, id |  ⟨EOS⟩, >>, +, To, <<, this, =, %, know, are, We, calculate, be, The, have |  1, Here, (, :, provide, depends, However, goals, amount, 3, there, The, \n, personal, will |  ”’, (, Here, python, ’, how, doc, snippet, import, based, {, Python, This, :, you
Tokens with the greatest recall increase |  SELECT, *, FROM, (, IST, *), \n, COUNT, G, first, WHERE, ⟨EOS⟩, IN, ;, MAX, ’; |  start, >>, <<, +, find, how, we, =, fore, To, so, \, ⟨EOS⟩, then, let |  general, 1, several, This, depends, Here, provide, However, goals, over, (, If, amount, it, can |  Here, This, snippet, ”’, ’, how, python, (, takes, Python, you, doc, an, import, def

Tokens learned across different datasets In our study, we analyze the top 10
tokens with the most pronounced accuracy and recall improvements across
various datasets, focusing on the 100 most frequent tokens to understand the
draft model’s learning trends. As detailed in Table 2, the improved tokens
align well with the underlying data distribution. For example, in the Spider
dataset, which frequently generates SQL statements, tokens like SELECT and
WHERE have notably higher acceptance rates post-distillation. Similarly, in
the Graduate Math dataset (Gsm8k), tokens such as <<, >>, =, and + stand out.
These patterns highlight the draft model’s ability to adapt and predict tokens
consistent with the data distribution.

##  6 Conclusion

Speculative decoding’s efficiently hinges on the draft model’s approximation
to the target model. We introduce an online speculative method that
continuously enhances the draft model based on varying data distributions.
Experiments on both synthetic and real data demonstrate that online
speculative decoding swiftly adapts to new data distributions, significantly
enhancing token acceptance.

## References

  * Agarwal et al. (2023) Rishabh Agarwal, Nino Vieillard, Piotr Stanczyk, Sabela Ramos, Matthieu Geist, and Olivier Bachem.  Gkd: Generalized knowledge distillation for auto-regressive sequence models.  _arXiv preprint arXiv:2306.13649_ , 2023.
  * Bai et al. (2022) Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  _arXiv preprint arXiv:2204.05862_ , 2022.
  * Bharti (2023) Gaurang Bharti.  gbharti/finance-alpaca, 2023.  URL https://huggingface.co/datasets/gbharti/finance-alpaca.  Accessed: 2023-09-17.
  * Cai et al. (2023) Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, and Tri Dao.  Medusa: Simple framework for accelerating llm generation with multiple decoding heads.  https://github.com/FasterDecoding/Medusa, 2023.
  * Chen et al. (2023) Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper.  Accelerating large language model decoding with speculative sampling.  _arXiv preprint arXiv:2302.01318_ , 2023.
  * Chiang et al. (2023) Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, Ion Stoica, and Eric P. Xing.  Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality, March 2023.  URL https://lmsys.org/blog/2023-03-30-vicuna/.
  * Chung et al. (2022) Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al.  Scaling instruction-finetuned language models.  _arXiv preprint arXiv:2210.11416_ , 2022.
  * Cobbe et al. (2021) Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman.  Training verifiers to solve math word problems.  _arXiv preprint arXiv:2110.14168_ , 2021.
  * Gu et al. (2023) Yuxian Gu, Li Dong, Furu Wei, and Minlie Huang.  Knowledge distillation of large language models.  _arXiv preprint arXiv:2306.08543_ , 2023.
  * He et al. (2022) Ruifei He, Shuyang Sun, Jihan Yang, Song Bai, and Xiaojuan Qi.  Knowledge distillation as efficient pre-training: Faster convergence, higher data-efficiency, and better transferability.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 9161–9171, 2022.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  _arXiv preprint arXiv:1503.02531_ , 2015.
  * Husain et al. (2019) Hamel Husain, Ho-Hsiang Wu, Tiferet Gazit, Miltiadis Allamanis, and Marc Brockschmidt.  CodeSearchNet challenge: Evaluating the state of semantic code search.  _arXiv preprint arXiv:1909.09436_ , 2019.
  * Kaplan et al. (2020) Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.  Scaling laws for neural language models.  _arXiv preprint arXiv:2001.08361_ , 2020.
  * Kwon et al. (2023) Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E Gonzalez, Hao Zhang, and Ion Stoica.  Efficient memory management for large language model serving with pagedattention.  _arXiv preprint arXiv:2309.06180_ , 2023.
  * Leviathan et al. (2023) Yaniv Leviathan, Matan Kalman, and Yossi Matias.  Fast inference from transformers via speculative decoding.  In _International Conference on Machine Learning_ , pp. 19274–19286. PMLR, 2023.
  * Luqmani (2023) Ali Mazhar Luqmani.  distilled bert topic, 2023.  URL https://huggingface.co/alimazhar-110/website_classification.  Accessed: 2023-10-07.
  * Miao et al. (2023) Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Rae Ying Yee Wong, Zhuoming Chen, Daiyaan Arfeen, Reyna Abhyankar, and Zhihao Jia.  Specinfer: Accelerating generative llm serving with speculative inference and token tree verification, 2023.
  * OpenAI (2023) R OpenAI.  Gpt-4 technical report.  _arXiv_ , pp. 2303–08774, 2023.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer, 2020.
  * Spector & Re (2023) Benjamin Spector and Chris Re.  Accelerating llm inference with staged speculative decoding.  _arXiv preprint arXiv:2308.04623_ , 2023.
  * Stern et al. (2018) Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit.  Blockwise parallel decoding for deep autoregressive models.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Touvron et al. (2023a) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023a.
  * Touvron et al. (2023b) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ , 2023b.
  * Yu et al. (2022) Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun.  Orca: A distributed serving system for $\\{$Transformer-Based$\\}$ generative models.  In _16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22)_ , pp. 521–538, 2022.
  * Yu et al. (2018) Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, et al.  Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-sql task.  _arXiv preprint arXiv:1809.08887_ , 2018.
  * Zheng et al. (2023a) Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Tianle Li, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zhuohan Li, Zi Lin, Eric Xing, et al.  Lmsys-chat-1m: A large-scale real-world llm conversation dataset.  _arXiv preprint arXiv:2309.11998_ , 2023a.
  * Zheng et al. (2023b) Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Tianle Li, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zhuohan Li, Zi Lin, Eric. P Xing, Joseph E. Gonzalez, Ion Stoica, and Hao Zhang.  Lmsys-chat-1m: A large-scale real-world llm conversation dataset, 2023b.

##  Appendix A Appendix

###  A.1 Speedup of Speculative Decoding

As proved in Leviathan et al. (2023), compared with standard decoding, the
expected improvement factor for offline speculative decoding is
$\frac{1-\alpha^{k+1}}{(1-\alpha)(ck+1)}$. Let the time taken for a single run
of $M_{p}$ be $T$. Define $c$, the cost coefficient, as the ratio of the time
taken for a single run of $M_{q}$ to that of $M_{p}$. Each execution of lines
7 to 8 takes $Tck+T$ and, on average, yields $\frac{1-\alpha^{k+1}}{1-\alpha}$
tokens. As a result, the average time to produce one token using speculative
decoding is given by $\frac{(ck+1)(1-\alpha)}{1-\alpha^{k+1}}T$. In contrast,
the time to produce a single token using standard decoding is $T$. Hence, the
wallclock time reduction of offline speculative decoding can be described as
$\frac{1-\alpha^{k+1}}{(1-\alpha)(ck+1)}$.

###  A.2 Latency Analysis

Suppose OSD can improve the token acceptance rate from $\alpha_{1}$ to
$\alpha_{2}$ and $T$ is the generation time for standard decoding. Based on
Equation 2, this improvement leads to a decrease in the average generation
time for each token, transitioning from
$\frac{(ck+1)(1-\alpha_{1})}{1-\alpha_{1}^{k+1}}T$ to
$\frac{(ck+1)(1-\alpha_{2})}{1-\alpha_{2}^{k+1}}T$. Consequently, this results
in a speedup factor of
$\frac{1-\alpha_{2}^{k+1}}{1-\alpha_{1}^{k+1}}\frac{1-\alpha_{1}}{1-\alpha_{2}}=\frac{1+\alpha_{2}+\alpha_{2}^{2}+...+\alpha_{2}^{k}}{1+\alpha_{1}+\alpha_{1}^{2}+...+\alpha_{1}^{k}}$
compared to standard speculative decoding.

In the aforementioned analysis, we omitted the additional latency due to
updating the smaller model for the following reasons: (1) As illustrated
subsequently, the additional computational cost (FLOPs) from the update
remains marginal when juxtaposed with the computational demands of running the
larger model. (2) Updates are periodic, during times of moderate request
loads, the latency for serving individual requests remains largely unaffected.
Additionally, given that the update operation for the smaller model is
considerably less resource-intensive than inference, the associated latency
might be seamlessly masked, rendering it virtually imperceptible. Lastly, the
processes of updating and inference can even be executed concurrently on
separate devices.

###  A.3 Flops Analysis

_The FLOPs required to update the draft model are significantly fewer than
those needed for inference on a large model._ Denote $L$ as the average length
of the generated sequence. For each verification, the draft model suggests $k$
tokens. The expected length for a single run of the target LLM, denoted as
$a$, can be calculated using Equation 2. Therefore, OSD undergoes the
verification process $\frac{L}{a}$ times, with each time verifying $k+1$
tokens. We use $F_{qfwd}$ to represent the arithmetic operations required by a
singular forward run of the draft model for each token, and $F_{pfwd}$ stands
for the FLOPs needed for a single forward run of the target model per token.
Therefore, the computational demand (in FLOPs) for the draft and teacher
models to handle one request can be expressed as:
$\text{FLOPs}(draft)=\frac{L}{a}\times k\times
F_{qfwd},\text{FLOPs}(target)=\frac{L}{a}\times(k+1)\times F_{pfwd}.$ Let’s
consider the FLOPs required to update the student model per token as
$F_{qbwd}$. The cumulative FLOPs necessary to process $I$ requests is given
by:

$\frac{LI}{a}\times\left[k\times F_{qfwd}+(k+1)\times F_{pfwd}\right]+I\times
L\times F_{qbwd}.$

Based on the findings of Kaplan et al. (2020), training is approximately three
times costlier than inference. This translates to roughly 6 FLOPs per
parameter for training on a single token and 2 FLOPs per parameter for
inferring on one token. Thus, we can simplify the total FLOPs expression to:

$\frac{LI}{a}\left[(k+3a)\times F_{qfwd}+(k+1)\times F_{pfwd}\right].$ (6)

The proportion of FLOPs needed to run the target model to that of the draft
model is given by:

$\frac{(k+1)\times F_{pfwd}}{(k+3a)\times F_{qfwd}}.$

For the two model pairs evaluated, assuming an average of 5 proposed tokens
per run: (1) (LLaMA-160M, Vicuna7B) with an average acceptance rate of 0.71,
the ratio is approximately $\frac{(5+1)\times 7B}{(5+3\times 3)\times
160M}=18.75$. (2) (T5-small 80M, Flan-T5-XL 3B), with an average acceptance
rate of 0.76, the ratio is roughly $\frac{(5+1)\times 3B}{(5+3\times
4.3)\times 80M}=12.6$.

_In practical systems, the FLOPs required for inference are significantly
below the machine’s capacity._ Consider the LMSYS-Chat-1M Zheng et al.
(2023b). It comprises traces spanning 125 days with 1000,000 requests,
averaging less than 2,000 tokens per request (including both prompts and
responses). When serving a 30B model with 8 A100 GPUs, the FLOPs consumed per
second can be estimated as (Still, we estimate 2 FLOPs per token per
parameter):

$\frac{2000\times 1000,000}{125\times 24\times 3600}\times 30\times
10^{9}\times 2=5.5\times 10^{9}\text{ FLOPs or 5.5 GFLOPs}$

On the other hand, 8 A100 GPUs offer a combined capacity of $8\times 312\text{
TFLOPs}$, and the computational utilization is notably low. While Arena (the
platform that generates LMSYS-Chat-1M) may not be the most efficient and might
lack substantial traffic, it’s the only publicly accessible LLM service trace.
Even after amplifying the load multiple times, based on the above
calculations, the computation efficiency remains limited.

###  A.4 Data Mix

Moreover, there is a question of whether the draft model, once adapted to the
new distribution, might lose its prior knowledge. To probe this, we conducted
an experiment mixing 2k prompts each from the Gsm8k and Alpaca-finance
datasets. During online serving, for the initial 2k requests, we only update
the model based on data from the Gsm8k dataset. For the subsequent half of the
requests, we restrict updates solely to data from the Alpaca-finance dataset.
We then provide the average token acceptance rates for all requests, segmented
by their data source (Gsm8k versus Alpaca-finance). As depicted in Figure 7,
the token acceptance rate for Gsm8k increases as the draft model is exposed to
more data. Conversely, the acceptance rate ($\alpha$) for the Alpaca-finance
dataset remains consistent. This is anticipated since we only update the draft
model using Gsm8k data. In the latter half of the dataset, the token
acceptance rate for the Alpaca-finance dataset also shows an uptrend.
Intriguingly, the rate for Gsm8k remains consistent, suggesting that the draft
model retains its learned knowledge without showing signs of forgetting.

Figure 7: Mix of distributions.

###  A.5 Data Preparation for Distribution Shift Analysi

To emulate this shift in distribution, we select 2k prompts from each dataset
under evaluation. T he data from the four datasets are amalgamated by direct
concatenation, such that the records from $i\times 2k$ to $(i+1)\times 2k$
belong solely to dataset $i$.

###  A.6 Arena Dataset

For expedited experimental evaluation, we randomly sample a subset with 10K
records from LMSYS-Chat-1M Zheng et al. (2023b), a comprehensive real-world
LLM conversation dataset. This dataset encompasses interactions with 25 models
spanning from April to August 2023 and features conversations in over 150
languages. For all experiments, we only pick conversations for Vicuna models.