paged-speculative-engine

Why this project

Each of the three techniques is well covered alone. Almost nothing covers the fact that they do not compose for free: continuous batching assumes every request advances one token per step, and speculative decoding breaks that assumption the moment one request accepts all its draft tokens while another rejects them all.

The composition problem, precisely

• The forward pass is always uniform-width across the batch. Drafting is k sequential width-1 calls and verification is one width-k call.
• The heterogeneity is between calls, not within one. After verification each request truncates its own KV-cache back to its accepted length.
• That is where paging earns its cost. Truncation is just freeing a request's trailing blocks to the pool, touching nothing that belongs to any other request.

Correctness, proven four ways

• Exact match against plain greedy decoding at temperature 0, for single requests and for requests forced through small batches.
• A Hypothesis property test over the scheduler: 300 generated examples with random prompts, batch sizes, draft lengths and block sizes, each required to match running alone.
• A Hypothesis property test over the cache allocator: 150 examples of random allocate, free and append sequences that must never corrupt the free-list.
• A chi-squared goodness-of-fit test at temperature above zero, over 4,000 trials, with a measured p-value of 0.64 against the target model's exact distribution.

The benchmark, read honestly

On CPU with tiny models, even the best case (a draft model identical to the target) runs at 0.62x of plain batching, and an untrained draft runs at 0.14x. Speculative decoding wins on real GPUs because decode is memory-bandwidth bound; that regime does not exist here. The repo reports the negative result as it is.

Stack

Python · PyTorch · Hypothesis · SciPy · Pytest

Honest notes