Dustin: Draft-Augmented Sparse Verification for Efficient Long-Context Generation with Speculative Decoding

As Large Language Models (LLMs) are deployed for increasingly long-context tasks, the memory-bandwidth bottleneck caused by loading the Key-Value (KV) cache becomes the primary inhibitor of inference speed. While speculative decoding (SD) helps, the verification phase—where the target model validates tokens drafted by a smaller model—remains slow due to the massive KV cache size. This paper asks how to efficiently compress the KV cache during the verification phase without incurring the accuracy losses associated with static eviction or the high computational overhead of dynamic selection.

The authors introduce Dustin, a sparse verification framework that identifies and retains only the most critical KV tokens during the verification step. Unlike previous methods that rely solely on historical attention or draft-model lookahead, Dustin uses a hybrid selection policy. It aggregates attention signals from both the target model's history and the draft model's lookahead to identify important tokens. To ensure this selection process does not itself become a performance bottleneck, Dustin employs a sparse estimation scheme using Semantic Retrieval Heads (SRHs)—a small, pre-identified subset of attention heads that capture the most significant semantic dependencies. The optimal configuration for these heads and the budget allocation between historical and lookahead signals are determined via a multi-stage offline search.

Dustin significantly reduces the computational burden of the verification phase. Evaluations on the Qwen2.5-72B model at a 32k sequence length demonstrate a 27.85x speedup in self-attention computation and a 9.17x end-to-end decoding speedup compared to standard speculative decoding. The authors show that the hybrid approach effectively mitigates the "saliency shift" issue—where token importance changes dynamically—by leveraging the complementary strengths of the draft model's foresight and the target model's historical reliability. The framework achieves these gains with negligible impact on generation accuracy.