ForeSpark: A New Joint Budget Scheduling Approach for Parallel Speculative Decoding

Title

ForeSpark: A New Joint Budget Scheduling Approach for Parallel Speculative Decoding

Meta Description

ForeSpark proposes a Work-Conserving Speculation (WCS) design that jointly schedules draft and verification budgets for parallel speculative decoding, achieving up to 1.77x throughput improvement over DSpark on vLLM while tolerating higher loads.

Article Content

Speculative Decoding is an important technique for accelerating Large Language Model (LLM) inference, and Parallel Drafter is particularly well-suited for high-load LLM serving scenarios because it can generate an entire block of draft tokens in a single forward pass. However, existing systems often only control the number of verification tokens when optimizing throughput, while the draft stage still generates full blocks at a fixed size, leading to significant wasted computation. A recent paper titled "ForeSpark: Joint Draft and Verification Budget Scheduling for Parallel Speculative Decoding" proposes a Work-Conserving Speculation (WCS) design that jointly allocates draft and verification budgets, significantly improving throughput while keeping the output distribution unchanged.

The Bottleneck of Parallel Speculative Decoding: Draft Waste and Budget Coupling

Parallel drafters generate an entire block of draft tokens at once, avoiding the serial overhead of autoregressive drafting, but this also introduces a new problem: the draft length is determined before a single forward pass and cannot be dynamically adjusted based on context like autoregressive drafting. The paper's authors observe that in high-load serving scenarios, the draft stage can consume up to 40% of step time, and most of these draft tokens are ultimately discarded because they are not verified. This means valuable compute is spent generating useless candidate tokens.

Although existing systems reduce the compute squeeze from rejected drafts by optimizing goodput (accepted tokens per second), they only control the number of verification tokens, and each request still generates a full draft block. More complicated still, draft length and verification length are coupled within a batch—they must be jointly chosen for each request while ensuring the decision's computational overhead is low enough. Length control strategies for autoregressive drafters cannot be directly transferred because parallel drafters lock in length before a single propagation.

Speculative decoding works as follows: a smaller draft model quickly generates several candidate tokens, which are then passed to the target large model for parallel verification, accepting the prefix that matches the target model's distribution. Parallel drafters (such as Medusa and Lookahead Decoding) differ from token-by-token autoregressive drafters in that they output candidate tokens at multiple positions simultaneously in a single forward pass, so the draft length must be statically determined before inference. This "one-shot block" characteristic sacrifices length flexibility: when the context is simple and the acceptance rate is low, many tokens in the full draft block are rejected and discarded, causing compute to idle. Understanding this is the premise for grasping the "draft waste" problem discussed in the paper—the waste does not stem from the draft model being inaccurate, but from the disconnect between length decisions and batch scheduling.

goodput (effective throughput) refers to the number of tokens actually accepted by the target model per unit time, rather than the total number of tokens generated during the draft stage. In speculative decoding serving scenarios, if only raw throughput is pursued, the system may generate many drafts that are ultimately rejected, crowding out compute that could have been used to verify other requests and leading to lower end-to-end effective output. Therefore, existing systems often use goodput as the optimization objective, suppressing waste from rejections by limiting the number of tokens verified per step. But as the original text points out, optimizing only the verification side without controlling the draft side has a ceiling on goodput improvement—this is exactly the motivation for ForeSpark's introduction of joint budgets.

ForeSpark's Core Design: Three Components for Work Conservation

To resolve the above contradiction, the paper proposes the Work-Conserving Speculation (WCS) design and implements a prototype system called ForeSpark. The core idea of WCS is to jointly allocate each request's draft budget and verification budget, so that computational resources are spent only on tokens that are "worth it." ForeSpark achieves this goal through three key components:

1. Context-Aware Pre-Draft Estimator

This component leverages contextual features of the target model to predict the acceptance probability for each candidate draft length. Unlike simple heuristics that rely on historical statistics, it extracts information from the target model's internal representations to provide a basis for subsequent joint scheduling. This enables the system to roughly determine which lengths are more likely to be accepted before draft generation, thereby avoiding blind generation of full blocks.

Acceptance probability is a core quantity in speculative decoding: for a draft token (x), its probability of being accepted by the target model is typically (\min(1, p_{\text{target}}(x)/p_{\text{draft}}(x))), ensuring that the final output distribution is exactly identical to the target model's. This rejection sampling mechanism explains why speculative decoding "does not change the output distribution." What the pre-draft estimator needs to do is predict the cumulative acceptance rate under different draft lengths based on contextual features such as the target model's hidden states before drafts are generated, thereby moving length decisions from "after-the-fact statistics" to "before-the-fact estimation." The more accurate the prediction, the better the scheduler can allocate draft budgets within a batch to requests with high acceptance rates.

2. Lightweight Joint Draft-Verification Scheduler

The scheduler selects draft length and verification length for each request through global ranking. Because draft and verification lengths are coupled within a batch, optimizing either dimension alone may lead to global suboptimality. The global ranking mechanism achieves batch-level joint optimization while ensuring that decision computation is cheap. The paper emphasizes that the scheduler can complete decisions quickly at each step and will not become a new overhead bottleneck.

3. Post-Draft Budget Allocation

After drafts are generated, the system allocates verification budget to the most promising tokens. This means that even if some tokens in the draft block have low acceptance probabilities, verification resources are prioritized for the candidates most likely to be accepted, further improving effective throughput.

Measured Performance: Significant Throughput Gains and Higher Load Tolerance

ForeSpark is implemented on vLLM and compared with the current state-of-the-art DSpark system. At a matched per-request generation rate, ForeSpark's throughput is up to 1.77x higher than DSpark and up to 2.49x higher than autoregressive decoding, without changing the output distribution—a property that is crucial for generation quality.

Beyond throughput gains, ForeSpark demonstrates stronger load tolerance under latency service level objectives (SLOs), sustaining request rates up to 1.51x those of DSpark. This means that under the same latency constraints, ForeSpark can serve more concurrent requests, which has direct value for real-world deployed LLM serving systems.

Implications for LLM Serving Systems

ForeSpark's work reveals a key insight about speculative decoding in serving scenarios: drafting and verification are not two independent stages, but a resource allocation problem that requires joint optimization. Traditional methods treat drafting as a fixed cost and optimize only the verification side, whereas ForeSpark reduces waste at the source by dynamically adjusting draft length.

This "work-conserving" idea—ensuring that each step of computation produces as many accepted tokens as possible—may inspire more inference optimization research for serving systems. As LLM deployments scale up, such fine-grained budget scheduling techniques will become increasingly important. The paper's implementation on vLLM also shows that the approach is feasible to integrate with existing serving frameworks, providing a reference for subsequent engineering deployment.

For developers and researchers focused on LLM inference acceleration, ForeSpark offers a new perspective: against the backdrop of the growing popularity of parallel drafters, re-examining resource allocation strategies in the draft stage may unlock considerable performance dividends.

One-line Summary

ForeSpark jointly schedules draft and verification budgets to reduce draft waste in parallel speculative decoding, improving throughput by up to 1.77x.

Paragraph Summary

This article introduces the paper "ForeSpark: Joint Draft and Verification Budget Scheduling for Parallel Speculative Decoding." The article points out that although parallel drafters can generate an entire block of draft tokens in a single forward pass, the draft length is statically locked, and under high load the draft stage can consume up to 40% of step time, with many tokens discarded because they are not verified. Existing systems only control the number of verification tokens and do not address waste on the draft side, and draft and verification lengths are coupled within a batch. ForeSpark proposes Work-Conserving Speculation (WCS), which jointly allocates budgets through three components: a context-aware pre-draft estimator, a lightweight joint draft-verification scheduler, and post-draft budget allocation. Measurements on vLLM show that throughput is up to 1.77x higher than DSpark and up to 2.49x higher than autoregressive decoding, without changing the output distribution; under latency SLOs, the sustainable request rate reaches 1.51x that of DSpark.