BagDraft: Next-Bag-of-Tokens Drafting for Lossless Speculative Decoding

The speedup of speculative decoding is fundamentally bounded by draft token throughput, yet existing drafters either incur $K$ sequential passes (EAGLE), dilute model capacity across $K$ disjoint heads (Medusa), or tie capacity to rigid per-slot block predictions (DFlash). We propose BagDraft, which reformulates speculative drafting as a next-bag-of-tokens prediction task. Crucially, the informational debt of discarding sequence order requires no parametric recovery in speculative decoding, as exact target verification guarantees lossless generation. Operating via a single forward pass with a shared logit vector, BagDraft directly models future $K$-token sets under a multi-hot cross-entropy objective, using discrete anchor blocks to ensure strict input isomorphism between training and inference. At inference, we mitigate the $K!$ permutation explosion by formalizing path probabilities via Plackett–Luce sampling without replacement; its proven prefix-monotonicity property mathematically justifies expectation-based pruning to construct compact permutation trees, verified by the target model in a single forward pass. Across 7 benchmarks on Qwen3-4B/8B, BagDraft achieves an average acceptance length of $3.976$ and a $3.168\times$ wall-clock speedup on 4B ($+12.1\%$ over DFlash, $+61.0\%$ over EAGLE-3), proving that speculative drafters can surpass state-of-the-art efficiency without dedicated per-position heads or autoregressive rollout, relying solely on an offset-decayed shared distribution.