Polybasic Speculative Decoding Under a Theoretical Perspective

Given that the paper claims the theoretical foundation for SD as one of their key contributions, the reviewer found the presentation and results in the paper somewhat underwhelming. Improving the presentation of existing results by properly setting up notation, formalizing theoretical statements, and rigorously justifying various assumptions is essential to improve the quality of a future submission. Some of the comments in this direction are as follows:

1. The authors may want to first provide a clear and brief outline of what they want to establish via their theoretical analysis before stating their results.
2. Section 3.1 starts by assuming that accepted token lengths follow a Gaussian distribution. What is the justification for this? Is this done only to make the analysis simpler? Without a rigorous justification, it is not clear if the rest of the analysis provides any realistic insight. Could authors assume this distribution to be a more plausible discrete distribution?
3. The authors state that by empirical analysis they obtain a precise formulation for $\phi_i$. There are no details provided regarding this analysis. If the results heavily rely on this precise formulation, it needs to be further explained and justified.
4. Please formally define acceleration ratio in Section 3.1.
5. Please define what $T_{M_1}$ and $T_{D_2}$ represent in line 218. Similarly, please define what $T_i$ vs. $T'_i$ and $L_i$ vs $L'_i$ are in Theorem 3.2
6. In Line 273, the authors talk about "...unstable acceptance token lengths...", which is not formally defined so far.
7. Please make the main result of Theorem 3.3 formal. In its present form, the theorem makes a qualitative statement that needs to be formalized.

The description of the main algorithm is not clear enough. For instance, Algorithm 1 does not seem to be utilizing $M_1$ anywhere.

The paper has multiple typos. Please consider performing a thorough proofread to fix the typos similar to the following:

1. In the abstract (line 18), ..is then serve --> ...then serve? Also, please change theorem to theorems Or serve to serves.
2. Line 189, the acceptance token length --> the accepted token length?
3. Please consistently use lemma or Lemma throughout the text.
4. Line 423, 'We approach consistently...' --> 'Our approach consistently....'?
5. Section 4.3 title: 'Limitation and discuss' --> 'Limitation and discussion'?
6. Line 483, 'As show in Figure....' --> 'As shown in Figure...'?

The theoretical parts are not sound:

• The concept "ideal forward count" $\phi_i$ is not properly defined. "Optimal number of forward passes required to generate tokens that are likely to be accepted by the previous model Mi−1". Is $\phi_i$ a random variable? What do you mean by "optimal"? Is $\phi_i$ obtained by optimizing some objective? What is "likely to be accepted"? Is this a high probability definition?
• Line 205-209 also comes from a contingent source of evidence: the definition of $\phi_i$ shouldn't be dependent on your specific empirical setting.
• The statment of Lemma 3.1 is not rigorous. The proof is not rigorous as well. In the proof, the authors neglect the randomness of $L_i$ by a extremely vague argument "when the variability of Li is sufficiently low relative to its mean, we can substitute L with its expected value E[L]". Instead, a proper development of lemma 3.1 will involve certain form of concentration inequalty, and the authors should quantify the errors of Talyor expansion and dropping the higher-order terms.
• In Theorem 3.2, the definition of $T_2'$ and $L_2'$ should be clearly stated in the theorem statement.
• Why would we need $\mathbb{E}[L_{D_i}] > \mathbb{E}[L_{D_{i+1}}]$ in the first place? There is no theoretical result supporting this goal.
• Line 275-277 the claim "we found that using speculative sampling can lead to more stable acceptance token length." is weird.

The novelty of the empirical algorithm is limited. Cascaded speculative decoding idea is not new and there are already multiple previous papers, including but not limit to:

• [1]. Cascade Speculative Drafting for Even Faster LLM Inference (https://arxiv.org/pdf/2312.11462)
• [2]. Accelerating LLM Inference with Staged Speculative Decoding (https://arxiv.org/pdf/2308.04623)

The theory developed in the paper can extend to speculative decoding systems with more than 4 models, but the experiments only restrict to 3-model cases.

The theoretical part seems to be disconnected with the empirical part. The results of Theorem 3.2 is not used in guiding the determination of the number of models $n$ and the selection of models $M_1,M_2,\dots, M_n$. E.g., I would expect the authors construct a pool of models and calculate the $T_i$ and $L_i$ as per Theorem 3.2 for each pair of the models. Besides, Theorem 3.3 is a simple characteristic of capped geometry variable and is a bit misleading (we want draft models with high acceptance rate instead of low acceptance length variance.)

Overall writing could be improved. More importantly, many important mathematical statements are not precisely stated. This is a major concern. Many statements are imprecise to the point of hindering understanding of the work. For instance, Lemma 3.1 has only one sentence that states “We can substitute L with its expected value E[L].”. I was left wondering “Substitute into where? What assumptions are made?” There is no objective function written until Lemma 3.1 that would allow me to substitute L with E[L]. I guess that perhaps Lemma 3.1 is meant for $\phi_i$ (L207). This then leads to another trouble which is that the definition of $\phi_i$ is never justified beyond the phrase “Through empirical analysis”. No further detail is given. There are other examples. More specific questions will be given in the Questions section of this form. Significance and in fact correctness of many statements are not easy to verify because of their impreciseness.

See Summary.

If the authors are able to clarify some of the questions and fix some of the writing. I am happy to bump up the score to a 5.