Extractive Speculative Decoding: Lempel-Ziv Limits and How to Approach Them

Copying candidate continuations from previously observed text provides a lightweight, model-agnostic approach to speculative decoding, which we call extractive speculation. Its performance, however, is fundamentally limited by what is available to copy. We show that this limitation has a precise connection to Lempel–Ziv compression and derive a tight, sequence-dependent upper bound on the acceptance length of any extractive speculator. We compute the resulting LZ bound exactly on standard benchmarks and show that it falls below existing generative speculators. Hence, under standard benchmark settings, no extractive method can close the gap to generative speculation. We further show that substantially enlarging the available copy corpus raises this bound and can make extractive speculation effective. However, existing methods remain well below the LZ bound even in these settings. We therefore introduce a representation-space retrieval method that uses the target model's hidden states and adapts its similarity metric online using supervision derived from our theory. Our method consistently improves over existing extractive approaches and narrows the gap to the LZ bound, while substantial headroom remains.