PaperlayerView exact revision on arXiv

Source-linked AI summary

PEARL: Parallel Speculative Decoding with Adaptive Draft Length

Tianyu Liu, Yun Li, Qitan Lv, Kai Liu, Jianchen Zhu, Winston Hu, Xiao Sun

arXiv:2408.11850v3cs.CL

TL;DR

Speculative decoding can accelerate LLM inference, but asynchronous drafting and verification leave the draft and target models waiting on one another, a problem worsened by fixed draft length. PEARL uses pre-verify and post-verify to overlap those phases and adapt draft length. Across text-generation benchmarks, it reports speedups of up to 4.43× over autoregressive decoding and 1.50× over vanilla speculative decoding.

  • Problem

    Speculative decoding’s asynchronous drafting and verification leave one model idle while the other works, and its fixed draft length can worsen mutual waiting.

    Source: §3.1 · p. 4

  • Method

    PEARL pre-verifies the first draft token during drafting and continues drafting during verification, enabling parallel execution and adaptive draft length.

    Source: §1 · p. 2

  • Results

    PEARL reports up to 4.43× speedup over auto-regressive methods and 1.50× over vanilla speculative decoding across text-generation benchmarks.

    Source: §4.2 · p. 7

  • Takeaways & Limitations

    PEARL outperforms existing state-of-the-art methods on various text-generation benchmarks.

    Source: §6 · p. 10

    Scheduling GPU resources to avoid resource competition remains a challenge and may potentially increase power consumption.

    Source: §6 · p. 10

Abstract

from arXiv · show

Speculative decoding (SD), where an extra draft model is employed to provide multiple draft tokens first, and then the original target model verifies these tokens in parallel, has shown great power for LLM inference acceleration. However, existing SD methods suffer from the mutual waiting problem, i.e., the target model gets stuck when the draft model is guessing tokens, and vice versa. This problem is directly incurred by the asynchronous execution of the draft model and the target model and is exacerbated due to the fixed draft length in speculative decoding. To address these challenges, we propose a conceptually simple, flexible, and general framework to boost speculative decoding, namely Parallel spEculative decoding with Adaptive dRaft Length (PEARL). Specifically, PEARL proposes pre-verify to verify the first draft token in advance during the drafting phase, and post-verify to generate more draft tokens during the verification phase. PEARL parallels the drafting phase and the verification phase via applying the two strategies, and achieves adaptive draft length for different scenarios, which effectively alleviates the mutual waiting problem. Experiments on various text generation benchmarks demonstrate the effectiveness of our PEARL, leading to a superior speed up performance up to 4.43$\times$ and 1.50$\times$, compared to auto-regressive decoding and vanilla speculative decoding, respectively. Our code is available at https://github.com/smart-lty/ParallelSpeculativeDecoding.

1 INTRODUCTION

Autoregressive decoding increases LLM inference latency, while speculative decoding can accelerate inference but leaves the draft and target models waiting on one another. PEARL combines pre-verification and post-verification to parallelize their work and adapt draft length, reporting speedups of up to 4.43× over autoregressive decoding and 1.50× over speculative decoding.

1 INTRODUCTION

  • Autoregressive decoding requires K serial model runs to decode K tokens, with latency increasing with output length and model scale.The paper identifies this token-by-token process as a substantial inference-latency obstacle, especially where computational resources are restricted.Source: §1 · p. 1
  • Speculative decoding’s mutual waiting problem leaves the target idle during drafting and the draft model idle during verification.The paper attributes the problem to asynchronous execution and says fixed draft length exacerbates it.Source: §1 · p. 2
  • 4.43× and 1.50× speedups are reported over auto-regressive methods and vanilla speculative decoding, respectively.The introduction reports these maxima across text-generation benchmarks.Source: §1 · p. 2
  • PEARL pre-verifies the first draft token during drafting and post-verifies by letting the draft model continue during verification.The two strategies are intended to parallelize drafting and verification while adapting draft length to the scenario.Source: §1 · p. 2, Figure 1 · p. 2
  • Figure 2 motivates PEARL by showing non-negligible drafting and verification times and iteration-to-iteration changes in optimal draft length.These observations are linked to asynchronous execution and the fixed draft length in speculative decoding.Source: Figure 2 · p. 3

2 BACKGROUND

Speculative decoding drafts multiple tokens with a small draft model, then asks the target model to verify them in parallel. Its window size is fixed, but PEARL’s draft length may vary independently of that window.

2 BACKGROUND

  • Mq and Mp denote the draft and target models, γ controls window size, and c is the target-to-draft single-forward time ratio.The ratio is defined as T(Mp(·))/T(Mq(·)).Source: §2 · p. 3
  • Speculative decoding drafts γ tokens with Mq, then sends the prefix and drafts to Mp for parallel verification.The target model produces logits for the draft positions and one additional position; draft tokens are verified sequentially.Source: §2 · p. 3
  • A rejected draft token is resampled from norm(max(0, pi − qi)); if all drafts are accepted, SD samples an additional token from pγ+1.Each SD step therefore produces between one and γ + 1 tokens.Source: §2 · p. 3
  • In SD, draft length is fixed to the window size, whereas PEARL allows draft length to differ from that hyperparameter.The window size controls drafting behavior; draft length counts tokens produced in one continuous draft-model execution.Source: §2 · p. 3

3 METHODOLOGY

PEARL addresses mutual waiting by overlapping drafting and verification and adjusting how many draft tokens are generated. Its pre-verify and post-verify strategies switch according to verification outcomes.

3.1 MOTIVATED OBSERVATION

  • When drafting and verification both take non-negligible time, asynchronous execution leaves opportunities for mutual waiting; optimal draft length also varies across iterations.A fixed length can produce unnecessary drafts when the optimal length is shorter, or interrupt drafting when more acceptable tokens could be generated.Source: §3.1 · pp. 3–4

3.2 PRE-VERIFY: VERIFY THE FIRST DRAFT TOKEN IN ADVANCE.

  • Pre-verify runs Mp on the available prefix during drafting to verify the first draft token before the verification phase.If that token is rejected, the remaining drafts are dropped and the next drafting phase can use the resampled token; if accepted, the drafts proceed to verification.Source: §3.2 · pp. 4–5

3.3 POST-VERIFY: CONTINUE DRAFTING DURING VERIFICATION.

  • Post-verify assumes the current γ drafts are accepted and lets Mq continue drafting during Mp’s verification phase.If all drafts are accepted, the target’s last logit can verify the next draft token, allowing the next drafting phase to be skipped; rejected extra drafts are dropped.Source: §3.3 · p. 5

3.4 PEARL: PARALLEL SPECULATIVE DECODING WITH ADAPTIVE DRAFT LENGTH

  • The two strategies switch according to verification results, keeping Mq and Mp running in parallel and making draft length adaptive.Pre-verify avoids additional drafting when no “right” tokens are available; post-verify lets drafting continue when more tokens could be accepted.Source: §3.4 · pp. 5–6

4 EXPERIMENTS

Across the evaluated text-generation tasks, PEARL outperforms vanilla speculative decoding and related baselines, while ablations and case studies examine its strategies and draft-length choices. In resource-competition settings, a pipeline-parallel variant retains 89%–99% of original performance.

4.1 EXPERIMENTAL SETUP

  • Evaluation spans code generation, arithmetic reasoning, and multi-round dialogue, using CodeLlama, Deepseek-Coder, Llama 2, and Llama 3.1 against four training-free baselines.Draft models are smaller than 7B, targets are larger than 33B, and the reported metric is walltime speedup.Source: §4.1 · p. 6

4.2 MAIN RESULTS.

  • 4.43× vs vanilla auto-regressive methods and 1.50× vs vanilla speculative decoding; PEARL also reaches 1.36–1.55× vs vanilla SD on multilingual arithmetic and dialogue tasks.On HumanEval, PEARL outperforms vanilla SD, Ouroboros, Lookahead Decoding, and assisted generation across backbone configurations; the arithmetic and dialogue evaluations cover 12 and 8 tasks.Source: Table 1 · p. 6, Table 2 · p. 7, Table 3 · p. 7

4.3 ABLATION STUDIES

  • Removing either strategy degrades PEARL, with removing post-verify having the larger impact; pre-verify matters more at lower acceptance, while post-verify matters more when models align.Pre-verify can save a target-model forward when the first draft token is rejected; the authors describe the strategies as complementary.Source: §4.3 · p. 7, Table 4 · p. 8

4.4.1 SENSITIVE ANALYSIS OF THE WINDOW SIZE γ

  • The rounded integer of c maximizes acceleration across model combinations on HumanEval, while γ=5 maximizes acceleration across HumanEval, GSM8K, and MT-Bench for Llama 2 7B&70B.These findings suggest γ is less burdensome to tune across model configurations and tasks.Source: Table 5 · p. 8, Table 6 · p. 8, §4.4.1 · p. 8

4.4.2 MEAN ACCEPTED TOKENS

  • 39.9 is PEARL's maximum mean accepted tokens; for Deepseek 6.7&33B, PEARL reaches 2.75× speed-up, near that configuration's 3× theoretical cap.The draft model runs approximately three times faster than the target model in this example.Source: §4.4.2 · pp. 8–9, Table 7 · p. 9

4.5 MORE DISCUSSIONS ON PEARL

  • In resource-adequate settings, separate devices let the draft and target models run simultaneously without adding latency to either drafting or verification; the main experiments use this setup.The authors describe these scenarios as having adequate computational resources.Source: §4.5 · p. 9
  • For co-located/resource-competition settings, PEARL splits draft-token generation across target-model devices via pipeline parallelism, retaining 89%–99% of original performance.The split is intended to avoid GPU resource competition when draft and target models share constrained resources.Source: Table 8 · p. 9, §4.5 · p. 9

5 RELATED WORK

Prior work accelerates transformer inference through model compression, efficient architectures, and hardware optimization, approaches described as orthogonal to speculative decoding. Draft-then-verify methods address drafting and verification but leave the parallelism issue unresolved.

5 RELATED WORK

  • Transformer acceleration spans model compression, lightweight architecture design, and hardware optimization, which can be integrated with speculative decoding for further speedup.The cited compression approaches include quantization, distillation, and pruning.Source: §5 · pp. 9–10
  • Draft-then-verify methods remove or refine the draft model, but do not address parallelism; PEARL is presented as orthogonal to these methods.The section leaves integration of PEARL with these methods as future work.Source: §5 · p. 10

6 CONCLUSION AND FUTURE WORK

PEARL combines pre-verify and post-verify to parallelize drafting and verification while adapting draft length. The conclusion reports better performance than existing methods on varied text-generation benchmarks, alongside a GPU resource-scheduling challenge.

6 CONCLUSION AND FUTURE WORK

  • PEARL's parallel acceleration still requires GPU scheduling to avoid resource competition, which may potentially increase power consumption.The paper identifies shared-device resource competition as a deployment concern.Source: §6 · p. 10
  • PEARL outperforms existing state-of-the-art methods on various text-generation benchmarks; future work aims to integrate it with other accelerated inference methods.The paper frames integration as a route to explore more efficient and resource-friendly approaches.Source: §6 · p. 10

A ALGORITHM OF PEARL

  • Pre-verify drafts tokens and verifies the first with the target model; post-verify drafts further while the target verifies prior drafts, switching strategies after acceptance or rejection.The algorithm starts in pre-verify mode; rejection returns it to pre-verify, while acceptance moves it to post-verify.Source: A ALGORITHM OF PEARL · p. 13

B A SIMPLE STEP-BY-STEP PROFILING EXAMPLE

  • In the profiling example, accepting all drafted tokens lets PEARL save draft-model forward runs, while a rejection switches the next strategy back to pre-verify.The example shows post-verify continuing after acceptance and pre-verify resuming after a rejected draft token.Source: B A SIMPLE STEP-BY-STEP PROFILING… · p. 15

C.1 DATASET CONFIGURATIONS

The evaluation covers code generation, arithmetic reasoning, multilingual inference, and multi-round dialogue. It uses representative model families without additional training and specifies task-specific evaluation sizes and generation limits.

C.1 DATASET CONFIGURATIONS

  • Experiments span code generation, arithmetic reasoning, multilingual inference, and multi-round dialogue, with task-specific sample sizes and maximum generation lengths.HumanEval has 164 entries; GSM8K uses 100, and MGSM uses 10 entries for each of its other 10 languages.Source: §C.1 · p. 15

C.2 MODEL CONFIGURATIONS

  • Evaluation uses Llama 2, CodeLlama, and DeepSeek-Coder in bfloat-16, with no additional training; running speed is measured on code-generation tasks.Detailed model configurations are summarized in Table 10.Source: §C.2 · p. 15, Table 10 · p. 16

C.3 EVALUATION DETAILS

Evaluation details specify GPU placements, batch size, and baseline reproduction conditions. The parallel implementation uses Accelerate, with further parallel optimization left for future work.

C.3 EVALUATION DETAILS

  • Experiments use NVIDIA A100-SXM4-80G GPUs and batch size 1, with GPU allocation varying by model size.The 1.3B and 7B models use one A100, 34B models use two, and 70B models use three.Source: §C.3 · p. 16
  • Lookahead Decoding and Ouroboros are reproduced on code-generation tasks with default parameters and the same model configuration and GPU usage as PEARL.Table 11 reports draft- and target-model run counts across HumanEval model configurations.Source: §C.3 · p. 16, Table 11 · p. 16
  • The parallel algorithm is implemented in Accelerate; optimizing it with other parallel techniques is left for future work.The paper identifies this as a potential route to further acceleration.Source: §C.3 · p. 16

D.1 EVALUATION RESULTS OF LLAMA 3.1 ON MT-BENCH AND MGSM

Appendix D reports additional Llama 3.1 evaluations, optimal γ settings for vanilla speculative decoding, and component timing for PEARL.

D.1 EVALUATION RESULTS OF LLAMA 3.1 ON MT-BENCH AND MGSM

  • Llama 3.1 results cover GSM8K, MGSM, and MT-bench, but Ouroboros and Lookahead Decoding results could not be reproduced because transformers had to be above version 4.43.0.Tables 12 and 13 cover the Llama 3.1 multilingual arithmetic and MT-bench evaluations, respectively.Source: §D.1 · p. 16, Table 12 · p. 16, Table 13 · p. 17

D.2 OPTIMAL γ OF SPECULATIVE DECODING

  • Vanilla speculative decoding results use each model pair’s optimal γ because an appropriate γ can outperform the commonly used fixed γ = 5.Table 14 presents the optimal γ values for each model pair.Source: §D.2 · p. 17, Table 14 · p. 17

D.3 TIME CONSUMPTION OF EACH COMPONENT IN ONE PEARL STEP

  • Communication cost is negligible, and draft and target times are very close, indicating PEARL effectively addresses the mutual waiting problem.Table 15 reports component time costs for one PEARL step on HumanEval.Source: Table 15 · p. 17, §D.3 · p. 17

E FORWARD TIMES COMPARISON OF PEARL AND SD METHODS

PEARL uses more draft- and target-model forward passes than traditional speculative decoding, with the additional inference time occurring in another process. The appendix also describes a tensor-parallel deployment approach and its padding technique, but leaves integration with vLLM as future work.

E FORWARD TIMES COMPARISON OF PEARL AND SD METHODS

  • PEARL uses relatively more forward passes for both models than traditional speculative decoding, increasing target-model power consumption, while the additional inference time does not affect multi-user throughput.The method runs draft and target models in parallel.Source: E FORWARD TIMES COMPARISON OF PEARL… · pp. 17–18

F INTEGRATING TP WITH PEARL

  • Tensor parallelism can place the draft model and target model on separate devices; zero-padding dimensions addresses divisibility, with the text describing padding as lossless across MLP, attention, and norm layers.For norm-layer scaling factors, ignoring the added zeros preserves the original results.Source: F INTEGRATING TP WITH PEARL · p. 18
  • Integration of tensor parallelism with PEARL using an existing framework such as vLLM remains future work because implementation is complex.Source: F INTEGRATING TP WITH PEARL · p. 18

G EXPERIMENT RESULTS UNDER LIMITED GPU RESOURCES

PEARL addresses resource competition in GPU-constrained settings by distributing draft computation across GPUs during pipeline-parallel target-model execution. Experiments report retained performance under resource competition, alongside a KV-cache transfer cost estimate.

G EXPERIMENT RESULTS UNDER LIMITED GPU RESOURCES

Loading 2408.11850v3…