RFC: adaptive per-request verify windows under load (SPS(B) scheduler, DSpark Phase 3) — design space + CUDA-graph strategy

[n-WN]

TL;DR: Design RFC for adaptive per-request verify windows under load — DSpark Phase 3 (SPS(B) cost-table scheduler + variable-length verify) and, more generally, "dynamic speculation windows" for OpenInfer. Core claims argued below: (1) for our block drafters the right dynamism is the verify window, not the draft loop; (2) dynamic can go into CUDA graphs — as discrete span buckets now, and as packed ragged verify keyed on total-token tiers later (the pattern SGLang shipped for DSpark); (3) almost all adaptive-length papers are HF-harness bs=1 evaluations, so we should only trust engine-integrated evidence and evaluate on Qwen3 with real GPUs under continuous batching. Part of #443. Companion near-term proposal: #717 (DSpark Phase 2 confidence truncation, single-GPU slice, no scheduler).

1. The taxonomy: what is "dynamic" in speculative decoding?

Before surveying anyone's implementation, my own decomposition of where adaptivity can live:

Layer	The decision	Who (in the literature) does it	Cost of the decision
A. Draft-side length	how many tokens to propose this round	SVIP / AdaEDL (entropy stop), SpecDec++ / DISCO (trained heads), DDD	per-token host sync if it controls a sequential draft loop
B. Verify-side dynamics	how many/how hard to check (early-exit target forward, mid-forward pruning, relaxed judges)	ProPD, FASER, Judge/SelfJudge	breaks static shapes mid-forward, or breaks losslessness
C. Verify-window scheduling	per-request verify span, chosen after drafting, before verify	DSpark confidence scheduler, AdaServe	a scheduling decision — host-side scalar(s) per step
D. Serving-level γ control	speculation on/off and budget as a function of load	SmartSpec/TurboSpec, Nightjar, BanditSpec; vLLM's static --speculative-disable-by-batch-size	per-engine-step scalar

For OpenInfer specifically, layer A is mostly a dead end: our DFlash/DSpark drafter emits the whole block's logits in one batched backbone forward, so "stop drafting early" saves no draft compute — the tokens exist whether we verify them or not. The compute that scales with span is the target verify (and the rejected-suffix KV transaction). Layer B is rejected (lossy or shape-breaking). That leaves C + D, which are the same mechanism at two scopes: choose each request's verify span before the verify forward — per-request (C) and load-aware (D). This is exactly DSpark's confidence scheduler + SPS(B) table, and it is why Phase 2 (confidence truncation, companion issue) is the right foundation.

2. Can the dynamic part go into CUDA graphs?

Yes — if the dynamism is a shape choice made outside the graph, with graphs captured per shape tier:

• Option 1 — discrete span buckets (near-term). Capture verify graphs per batch × span bucket as today (verify_graph.rs already buckets); the scheduler picks each request's bucket, low-span requests pad into the smallest fitting bucket. Zero new kernel work; savings bounded by bucket granularity. This is what Phase 2 ships with.
• Option 2 — packed ragged verify, tier-keyed graphs (end state). Front-pack the per-request variable-length verify into one compact cu_seqlens-style buffer, round the total token count up to the nearest captured tier, and capture graphs per tier. When windows trim, the packed total drops to a genuinely smaller graph (fewer attention/MLP rows — not a masked full-width forward). Attention reuses existing varlen kernels; each backend rebuilds its varlen metadata from the packed layout on replay. This is what SGLang shipped for DSpark (blog, [Spec] Add DSpark: confidence-scheduled speculative decoding sgl-project/sglang#30261), with three verify modes: static (full block), compact (scheduled window), cap-accept (verify full, commit up to window — for ceiling observability). Under DP attention ranks share one tier and step down together.
• What does NOT go into graphs: per-token stop decisions inside a sequential draft loop (host sync per step — this is why SGLang's overlapped SpecV2 path is topk=1-only today); mid-forward pruning with mask regeneration (ProPD); input-dependent tree topologies (EAGLE-2-style threshold expansion, OPT-Tree, DySpec). Rule of thumb: dynamic lives in tensor contents and in scheduler-side shape choices; never in per-step host-visible control flow.

Supporting pieces needed either way: an SPS(B) (steps/sec vs. batch) profiler run at engine init; per-request survival products Π c_k (Phase 2 computes them); STS calibration before the survival values feed throughput math; and ceiling observability (cap-accept mode or an estimator) because trimming censors the acceptance ceiling.

3. Prior art — and yes, most of it is HF-eval at bs=1

Work	Layer	Mechanism	Evaluation	Engine-shipped?
SpecDec++ (2405.19715)	A	trained acceptance head	HF, bs=1, 2×A100	no
AdaEDL (2410.18351)	A	entropy bound, training-free	HF, bs=1	no public code found
DISCO (2405.04304)	A	trained FFN classifier	HF, bs=1	no public code found
SVIP (2411.18462)	A	entropy threshold	HF, bs=1, SpecBench	no (SGLang issue #2754 open)
DDD (2409.00142)	A (tree depth)	logprob-sum threshold	HF, bs=1	no
BanditSpec (2505.15141)	A/D	bandit over γ configs	incl. batched throughput reward	no
SmartSpec/TurboSpec (2406.14066)	C/D	goodput model + acceptance EMA	vLLM, continuous batching	fork, not mainline
Nightjar (2512.22420)	D	contextual MAB on batch size	vLLM 0.8.2, prod traces	not mainline
TETRIS (2502.15197)	batch verify budget	entropy-ordered token selection	vLLM @ 64 req (+5–9%)	no
MagicDec (2408.11049)	D	γ grows with batch at long ctx	gpt-fast+FlashInfer, bs 32–256	no
EAGLE-3 (2503.01840)	—	(draft model)	HF bs=1: 6.5×; SGLang bs=64: 1.38×	yes (SGLang/vLLM)
DSpark (2607.05147)	C (+A)	confidence + SPS(B) scheduler	DeepSeek-V4 production; SGLang bs 1→256	yes (SGLang #30261)
Judge (2501.19309), FASER, ProPD	B	lossy / mid-forward	various	no

Two honest datapoints to anchor expectations: (i) HF-harness bs=1 claims of 3–9× collapse to ~1.3–1.5× at serving batch sizes because verify turns compute-bound; (ii) SGLang's DSpark A/B (compact vs no-trim) shows trimming wins primarily at higher batch and more so on lower-acceptance traffic — bs=1 is a tie. So the feature's value is a throughput-regime feature, and our benchmarks must sweep concurrency, not single-stream only.

Also worth reading before committing: vLLM's deliberately static stance (--speculative-disable-by-batch-size, no per-request adaptive length upstream) and the "batching beats speculation" analysis — under saturation, the correct γ can be 0, and our scheduler must be able to choose 0 (fall back to plain decode graphs).

4. Proposal

1. Phase 2 (companion issue, near-term): confidence-head truncation into discrete span buckets, single-GPU friendly, no scheduler. Delivers the survival products + instrumentation this RFC needs.
2. Phase 3a: per-request windows with bucketed spans + an SPS(B) profiler + window policy maximizing Θ = τ · SPS(B) over admitted tokens (paper Alg. 1, simplified: per-request argmax over buckets first, batch-global greedy admission second). Add cap-accept observability mode.
3. Phase 3b: packed ragged verify with tier-keyed graphs (Option 2 above) once profiling shows padding waste dominates; this is real engine surgery on verify_graph.rs and the KV transaction, sized only after 3a data.
4. Load-aware γ (layer D): fold batch size into the window policy, including span=0 (speculation off) at saturation. TurboSpec's no-regression property is the bar.
5. Evaluation: Qwen3-4B (+ one larger Qwen3) on real GPU boxes (5090 dev / H200 cluster), bench_http_serving.py-style sweeps at c1→c256 on mixed-difficulty traffic (gsm8k-like high-accept + chat/poetry-like low-accept in one batch — per-request differentiation is the actual point, cf. SGLang's mixed-traffic figure). Never HF-style bs=1-only numbers.

5. Anti-goals

• No per-token host-sync draft stopping in the hot path.
• No lossy/relaxed verification (Judge-family) — we keep prefix-match-exact acceptance.
• No mid-forward verify pruning (ProPD/FASER-style) under graphs.
• No per-request tree topology dynamism — variable per-request verify lengths are a scheduling problem (tractable); variable tree shapes are a graph problem (avoid; see my tree-draft notes on [Roadmap] Speculative decoding (qwen3 first, shared primitives) #443).

6. Open questions

• STS calibration: needed once survival feeds throughput math — can we calibrate online from observed accepts instead of paper's offline STS?
• SPS(B) table granularity vs. context length (SGLang flags this as their known approximation); do we need (B, ctx) bins?
• Bucket/tier count vs. graph memory and startup capture time (SGLang documents spec-decoding OOM via tree+graph buffers — same tradeoff applies to span tiers).
• Interaction with Qwen3 DFlash can exhaust KV blocks below advertised max_model_len #681 (DFlash KV-block exhaustion under long sequential requests) — variable spans change KV pressure; fix ordering TBD.
• Does the EAGLE proposer-trait discussion ([Roadmap] Speculative decoding (qwen3 first, shared primitives) #443) want the window policy to be proposer-agnostic from day one? (DFlash, DSpark, n-gram PR: feat(qwen3): n-gram speculative decoding #349, EAGLE-3 feat(eagle3): Qwen3 EAGLE-3 drafter forward pass (single-step + chain rollout) #707 all produce spans; the window logic should not care who proposed them.)

[github-actions]

This issue has been inactive for 14 days. It will be closed after another 30 days unless there is new activity.