[RFC] Speculative Decoding for rlt

[bjf-frz]

1. Motivation

Native RLT decoding executes all recurrent loops before producing each token. At low request concurrency, the small token batch can leave GPU capacity underused.

This proposal uses shallow loops to draft tokens, reuses their hidden states and KV, and batches the remaining deep loops for verification. The initial configuration is fixed d=2, D=4, with last_exited KV semantics. K is selected through measurement. The goal is faster decoding while preserving the full-depth target's generation semantics.

LoopSpec-style pipelining across token positions is a future direction.

2. Algorithm

At the start of a round, the last committed token A has not been forwarded. KV contains the prefix before A.

1. Autoregressively generate K candidates using loops 1–2, retaining shallow hidden states and KV.
2. Run loops 1–2 on the final candidate as well, producing states for K+1 input positions.
3. Reuse these states and batch loops 3–4, producing K verification distributions and one bonus distribution.
4. Accept candidates in order. At the first rejection, emit a correction and discard the suffix. If all candidates are accepted, emit a bonus token.
5. Commit output and truncate KV. The correction/bonus token becomes the next round's input, not yet forwarded.

Example with K=2:

flowchart TD
    A["A: loops 1–2 → propose B"] --> B["B: loops 1–2 → propose C"]
    B --> C["C: complete loops 1–2"]
    C --> V["Reuse shallow states and KV<br/>Batch loops 3–4 for all three positions"]
    V --> H["A row verifies B; B row verifies C<br/>C row provides the bonus distribution"]
    H --> R1["Reject B: commit Z<br/>Keep KV through A"]
    H --> R2["Accept B, reject C: commit B, Z<br/>Keep KV through B"]
    H --> OK["Accept both: commit B, C, E<br/>Keep KV through C"]

Loading

Reuse condition: with fixed depth and last_exited, each loop reads historical KV at the same depth. Deeper computation does not modify shallow states. Computing the candidate chain's shallow loops first and then batching its deep loops preserves the dependencies, provided positions, normalization, and causal masks match. Shallow KV must not be copied into uncomputed deeper loops.

Verification: greedy compares each candidate with the target argmax and corrects the first mismatch with that argmax. For sampling, let q be the actual proposal distribution and p the target distribution:

Acceptance probability: min(1, p(y) / q(y))
On rejection:           z ~ normalize(max(p - q, 0))
If all accepted:        e ~ p_bonus

Both p and q include their actual temperature/top-k/top-p processing. This rule preserves the target distribution, not identical text under the same seed. Numerical differences between batched and serial BF16 computation require separate validation.

State boundary: retain KV only for the accepted prefix and the round's initial input. The correction/bonus token has no KV yet. Truncate every layer and depth. Apply EOS when committing output, and shorten K to respect output, context, and resource limits.

3. Scheduling and Execution

3.1 Synchronous

3.2 Asynchronous — Proposed

4. Modules

Module	Responsibility
Scheduling	Select requests and effective K; reserve verification rows and KV; manage prefill fairness and in-flight rounds
Draft / Target	Generate candidates with shallow loops; retain states and reuse them for batched deep-loop execution
Verification and correction	Greedy checks, sampling rejection, correction and bonus generation; return valid output and accepted length
State commit	Apply EOS/length limits, commit output, truncate KV, and establish the next input
Asynchronous execution	Manage round tickets, events, and buffers; preserve result ordering and resource lifetimes

5. Accuracy and Performance Evaluation

5.1 Matched Baselines

Use the same Ouro checkpoint, fixed D=4, last_exited, prefill policy, sampling parameters, and inputs. GPU evaluation uses BF16 + FA4 with fixed hardware/software configuration.

Compare native synchronous vs speculative synchronous, and native asynchronous fixed-depth vs speculative asynchronous separately. Comparing across execution modes measures combined gains, not the contribution of speculation alone.

5.2 Accuracy

Fixed inputs: validate reuse. Compare native serial full-depth execution with the reuse verifier on the same token chain, including positions that will eventually be rejected. Record maximum absolute and RMS errors for loop-2 hidden states, KV at each depth, and final logits, plus the argmax mismatch rate. Use a small FP32 reference to diagnose dependency/indexing errors and real Ouro BF16 to assess numerical behavior.

Free generation: validate output. Run native greedy and speculative greedy with K=1/2/4/8 on the same real prompts. Report exact sequence agreement, the first divergent position, and the native top-1/top-2 logit margin there. Replay a divergent prefix with fixed inputs to distinguish numerical differences from KV/rollback errors. Do not compare logits on different prefixes after divergence.

Sampling: validate distributions. Use analytically tractable small-vocabulary p/q distributions to verify acceptance plus residual correction. Across multiple seeds, report empirical deviations from p and sampling uncertainty. Then cover actual temperature/top-k/top-p settings. Same-seed text equality is not a sampling correctness criterion.

Task evaluations such as GSM8K may additionally compare native and speculative scores using the same dataset and evaluator, with uncertainty reported. Similar task scores do not establish losslessness. Agree on BF16 tolerances and acceptable greedy divergence before acceptance testing.

5.3 Performance

Metric	Method
Sweep	d=2, D=4; K=1/2/4/8; concurrency 1 and 8 up to near saturation; short/long contexts and outputs
Decode throughput	Complete matched prefill for all requests before timing; generate equal numbers of new tokens; divide committed tokens by elapsed time
Decode time	Match concurrency and generated work; speedup = T_native / T_spec
Serving latency	Under matched arrival workloads, measure end-to-end latency, TTFT, streaming chunk intervals and tokens per chunk; report p50/p95
Cost analysis	Record accepted length per round, verification rows, draft/target/verification/commit times, and peak memory; profile bandwidth and MFU separately

Match output length and EOS policy in fixed-work tests; evaluate natural termination separately in serving tests. Include draft, the final shallow fill, target execution, verification, sampling, synchronization, and rollback. Synchronize the GPU at timing boundaries, warm up, repeat at least five times, and report median and variability. Use an exclusive GPU, interleave baseline and speculative trials, and keep profiling outside timed runs.

Prioritize effective throughput and latency when interpreting MFU. Computation on rejected candidates increases executed FLOPs without necessarily improving useful performance. Report results by concurrency, length, and K rather than only the best speedup.

6. Open Questions

• Keep synchronous rounds atomic, or allow other work between phases?
• Start asynchronous execution with one in-flight round per request, a CPU commit barrier, and one GPU stream?
• What sampling scope, default-K policy, and BF16 agreement criteria should the first release adopt?

7. Feature Tracking

⬜ Unclaimed · 🚧 In progress · ✅ Complete · 🔬 Exploratory

Claim whole features. 🔬 items first require feasibility and benefit assessment. ✅ refers to the existing local prototype scope, not merged status or validation across all workloads.

Feature	Scope	Owner	Status
Synchronous self-speculative decoding	Fixed loops, compute reuse, greedy/sampling rejection, KV rollback, and output integration	@bjf-frz	🚧
Asynchronous self-speculative decoding	Device-resident candidate chain, round submission/collection, stream dependencies, and resource management	@liuyao0322	🚧
Accuracy and performance evaluation	Extend preliminary BF16 comparisons and K sweeps to real workloads, serving latency, and MFU	@Levius-Fubuki	🚧
🔬 Adaptive speculation	Select K / draft depth based on load and acceptance	@Dmaner	🚧
🔬 Loop-level pipelining	Batch shallow work for subsequent tokens with deep work for current tokens	@YuDeng0102	🚧
🔬 Device-side execution loop	Perform acceptance, stopping, and KV updates on GPU to reduce CPU barriers	@IDEA-V	🚧
🔬 CUDA Graph support	Capture speculative execution and manage variable shapes	@0z5a	🚧
🔬 Scheduling and distributed compatibility	Intra-round scheduling, preemption/resume, KV migration, and PD integration	@0z5a	🚧
🔬 Proposal improvements	Improve shallow proposals, add a second proposal, or explore candidate trees	@prettygirlisnotme	🚧

Versioned RFC document

[liuyao0322]

I’d like to take ownership of asynchronous self-speculative decoding. could you please assign it to me ?

[Levius-Fubuki]

Hi @bjf-frz, I'd like to take ownership of the Accuracy and performance evaluation feature in this RFC.

My related contributions include merged Triton attention work with numerical and performance validation (vllm#55629) and merged fixes for benchmark clients counting failed streams as successful (vllm-omni#8000, #8015).

I'll start with the synchronous implementation in #44 and extend the same evaluation contracts to the asynchronous implementation with @liuyao0322 when it is ready:

• Pin implementation/baseline SHAs, checkpoint, environment and workloads; agree on BF16 acceptance criteria before running acceptance tests.
• Validate reuse on fixed token chains (shallow states, per-depth KV and logits), greedy divergence with prefix replay, and sampling distributions with small-vocabulary references. Cover rejection/rollback and EOS/length boundaries through the production path.
• Extend existing tests/benchmarks with matched native-vs-speculative runs: K=1/2/4/8, concurrency and length sweeps, committed-token throughput, serving latency/chunk sizes, acceptance length and peak memory. Profile phase costs and MFU separately from timing; retain raw repeated measurements and report regressions as well as gains.

My first deliverable will be a gap analysis against #44's existing coverage and a reproducible evaluation matrix. GPU/backend availability will be recorded explicitly, with unrun cases left pending. Please record me as the owner of this feature if this scope fits; I'll coordinate with the implementation owners to avoid duplicating their tests.

[bjf-frz]

I’d like to take ownership of asynchronous self-speculative decoding. could you please assign it to me ?

Of course, thanks for volunteering! RFC list has been updated.

[bjf-frz]

Hi @bjf-frz, I'd like to take ownership of the Accuracy and performance evaluation feature in this RFC.

My related contributions include merged Triton attention work with numerical and performance validation (vllm#55629) and merged fixes for benchmark clients counting failed streams as successful (vllm-omni#8000, #8015).

I'll start with the synchronous implementation in #44 and extend the same evaluation contracts to the asynchronous implementation with @liuyao0322 when it is ready:

• Pin implementation/baseline SHAs, checkpoint, environment and workloads; agree on BF16 acceptance criteria before running acceptance tests.
• Validate reuse on fixed token chains (shallow states, per-depth KV and logits), greedy divergence with prefix replay, and sampling distributions with small-vocabulary references. Cover rejection/rollback and EOS/length boundaries through the production path.
• Extend existing tests/benchmarks with matched native-vs-speculative runs: K=1/2/4/8, concurrency and length sweeps, committed-token throughput, serving latency/chunk sizes, acceptance length and peak memory. Profile phase costs and MFU separately from timing; retain raw repeated measurements and report regressions as well as gains.

My first deliverable will be a gap analysis against #44's existing coverage and a reproducible evaluation matrix. GPU/backend availability will be recorded explicitly, with unrun cases left pending. Please record me as the owner of this feature if this scope fits; I'll coordinate with the implementation owners to avoid duplicating their tests.

Thx for your volunteering! RFC list has been updated. Feel free to share your test plan, btw, no need to prioritize testing the Triton backend for now. You can test directly with FA4.

[Dmaner]

@bjf-frz I’d like to take Adaptive speculation .could you please assign it to me ?

[YuDeng0102]

hi @bjf-frz I’d like to take Loop-level pipelining .could you please assign it to me ?

[bjf-frz]

@bjf-frz I’d like to take Adaptive speculation .could you please assign it to me ?

Of course yes, thx for your volunteering! Feel free to share your implementation plan, we could discuss how to achieve Adaptive speculation a better way.

[bjf-frz]

hi @bjf-frz I’d like to take Loop-level pipelining .could you please assign it to me ?

Of course yes, RFC list has been updated.

[0z5a]

I’d like to take ownership of coda graph support and scheduling and distributed compatibility, please assign them to me if they are still available.

[Dmaner]

@bjf-frz I’d like to take Adaptive speculation .could you please assign it to me ?

Of course yes, thx for your volunteering! Feel free to share your implementation plan, we could discuss how to achieve Adaptive speculation a better way.

​thx, I'll draft an implementation plan asap for feedback

[bjf-frz]

I’d like to take ownership of coda graph support and scheduling and distributed compatibility, please assign them to me if they are still available.
Thx for your volunteering! Cuda graph has been proved to be a valid method to improve performance in previous work. Happy to see what will happen on your job.

[0z5a]

I’d like to take ownership of coda graph support and scheduling and distributed compatibility, please assign them to me if they are still available.
Thx for your volunteering! Cuda graph has been proved to be a valid method to improve performance in previous work. Happy to see what will happen on your job.

ok i see

[Levius-Fubuki]

Thanks! I’ll focus on BF16 + FA4, review #44’s existing coverage, and share a concise test plan.