acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Speculative Decoding, Lempel-Ziv Compression, Large Language Models

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_tjowOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper first investigates the theoretical limits of extractive speculative decoding, and establish a connection between extractive speculation and non-overlapping Lempel–Ziv (LZ) parsing, deriving a tight, sequence-dependent upper bound on the achievable acceptance length. Experiments on SpeedBench and SWE-bench show that this bound can fall below the acceptance length of generative speculative decoding methods under standard settings, while expanding the available copy corpus substantially raises the bound. To narrow the gap between practical extractive methods and this theoretical limit, the authors further propose LatentSpec, which retrieves candidate continuations using the target model's hidden-state representations and adapts the retrieval similarity metric online. Experiments across multiple LLMs demonstrate improvements in acceptance length over N-gram and suffix-based retrieval methods, although a substantial gap to the theoretical bound remains.

Critical strengths
  1. The connection between extractive speculative decoding and non-overlapping Lempel–Ziv parsing is elegant, yielding a tight and computable upper bound on acceptance length. This provides a useful theoretical foundation for understanding the fundamental limitations of extractive speculation. The LZ bound also helps identify scenarios where extractive speculation may be inherently less competitive than generative approaches, even with perfect retrieval. The analysis of different context sizes and copy corpora also provides useful guidance for future research and deployment.

  2. LatentSpec leverages the target LLM's existing hidden representations without requiring retraining or architectural modifications. Its online metric adaptation admits a closed-form solution, making the approach conceptually simple and potentially practical. The empirical validation in this paper is also extensive enough. The authors evaluate the theoretical bound and proposed method across multiple LLMs, benchmarks, and corpus configurations. LatentSpec consistently improves the overall acceptance length over conventional extractive baselines, although the gains are relatively modest.

Critical weaknesses
  1. The comparison or discussion with closely related work seems insufficient. The core idea of LatentSpec, i.e., retrieving draft continuations using the target LLM's hidden-state representations, has already been explored in prior works such as DReSD ( DReSD: Dense Retrieval for Speculative Decoding, ACL 2025) and PLD+ (PLD+: Accelerating LLM inference by leveraging Language Model Artifacts, NAACL 2025). However, these closely related methods are neither adequately discussed nor included as baselines. With these previous work, the main methodological novelty appears to lie in the online LCP-supervised metric learning, making it difficult to establish a substantial algorithmic contribution without comparisons to these existing approaches.

  2. Also, the connection between the theoretical analysis and the proposed method appears to be somewhat weak. Although the LZ bound is elegant and potentially valuable, LatentSpec does not directly optimize the derived bound or the global LZ parsing objective. Instead, its supervision relies on pairwise future-token prefix matching, which can be motivated independently of LZ theory. Moreover, the improvements over existing extractive baselines are modest (e.g., acceptance length of 1.50 vs. 1.45 on SpeedBench), with negligible end-to-end throughput gains. These limitations weaken the practical significance of the proposed method and its connection to the main theoretical contribution.

Questions for authors
  1. Could the authors clarify the key technical differences between LatentSpec and existing hidden-state-based retrieval methods, particularly DReSD and PLD+ ?

  2. Beyond using future-token longest common prefix (LCP) lengths as supervision, how does the LZ theoretical analysis specifically inform the design of LatentSpec? Is there a stronger connection between the proposed metric-learning objective and the derived LZ bound?

  3. Given the relatively modest acceptance-length improvements and the negligible or even negative end-to-end throughput gains reported in Appendix E, could the authors clarify under what practical settings LatentSpec is expected to provide meaningful inference acceleration?

2 comments

Reply to Q1

Could the authors clarify the key technical differences between LatentSpec and existing hidden-state-based retrieval methods, particularly DReSD and PLD+ ?

We will add a discussion of both works to the related work section. Like LatentSpec, both retrieve drafts using the target model’s hidden states, and LatentSpec with M = I is close in spirit to PLD+ (h). Our contributions beyond these works are twofold. (1) The LZ bound. PLD+ and DReSD are themselves extractive, so our bound and negative result apply to them as well. Neither work characterizes the ceiling of extractive speculation or when it can be competitive and we are the first to provide a rigorous analysis. (2) LZ-supervised online adaptation. Both prior methods rely on a fixed similarity (cosine). We use the LZ parsing as supervision to adapt the retrieval metric online in closed form.

Reply to Q2

Beyond using future-token longest common prefix (LCP) lengths as supervision, how does the LZ theoretical analysis specifically inform the design of LatentSpec? Is there a stronger connection between the proposed metric-learning objective and the derived LZ bound?

The main connection is that the LZ analysis provides the per-step optimal retrieval decision. The metric-learning objective is a teacher-forced, per-step supervision from this LZ oracle:it learns the oracle’s choice at every position.

Reply to Q3

Given the relatively modest acceptance-length improvements and the negligible or even negative end-to-end throughput gains reported in Appendix E, could the authors clarify under what practical settings LatentSpec is expected to provide meaningful inference acceleration?

At this stage, our main contribution is the LZ bound and the analysis it enables. LatentSpec serves as a proof of concept showing that better retrieval can narrow the gap to the bound, rather than as a fully optimized system. We acknowledge that its end-to-end gains are currently modest.

Thank you for the detailed response. I appreciate the clarifications regarding the differences between LatentSpec and prior work, as well as the intended role of LatentSpec as a proof of concept for the LZ-bound analysis.

However, my main concerns remain. First, without direct comparisons with DReSD and PLD+, the incremental benefit of the proposed metric adaptation remains unclear. Second, while the connection between LZ analysis and per-step retrieval supervision is better explained, the specific metric-learning objective still appears largely independent of the theoretical framework. Finally, the authors acknowledge that the practical throughput improvements are modest.

I continue to appreciate the theoretical contribution of the LZ bound, but the rebuttal does not sufficiently address my concerns to change my overall assessment. Therefore, I will maintain my original rating.

Reviewer_8VJbOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper establishes a tight upper bound on the achievable acceptance length of extractive speculative decoding by leveraging non-overlapping Lempel–Ziv parsing. Building on this theoretical analysis, the authors propose LatentSpec, which retrieves candidate continuations using the target model's hidden states and adaptively learns a similarity metric from LZ-derived supervision. Experiments on SpeedBench and SWE-bench demonstrate that expanding the available copy corpus substantially increases the theoretical upper bound, while LatentSpec consistently improves acceptance length over existing extractive baselines.

Critical strengths
  • Insightful empirical findings. The analysis reveals that enlarging the copy corpus increases the theoretical performance ceiling but may degrade practical retrieval performance, highlighting an important bottleneck in extractive speculation.
  • Effective theory-guided method design. LatentSpec leverages LZ-derived supervision to adapt hidden-state similarity without training an auxiliary draft model, offering a lightweight and model-compatible retrieval approach.
Critical weaknesses
  • Marginal practical improvements. On SpeedBench, LatentSpec achieves only a modest improvement in average acceptance length over Suffix Decoding (1.45 to 1.50) under the prompt-only setting, with even smaller throughput gains.
  • Insufficient theoretical justification for the learned similarity metric. The proposed reconstruction objective approximates pairwise continuation-match lengths without establishing a theoretical connection to retrieval rankings or acceptance length.
Questions for authors
  1. What motivates the use of squared-error reconstruction of continuation-match lengths rather than directly optimizing retrieval rankings or expected acceptance length? Could the authors provide comparisons with alternative metric-learning objectives?
  2. Can the authors demonstrate meaningful end-to-end throughput improvements over Suffix Decoding under matched deployment conditions?
  3. How does LatentSpec scale to substantially larger external corpora?
2 comments

Reply to Q1

What motivates the use of squared-error reconstruction of continuation-match lengths rather than directly optimizing retrieval rankings or expected acceptance length? Could the authors provide comparisons with alternative metric-learning objectives?

We chose squared error because it admits a closed-form solution, with additive statistics G and A. This enables cheap online updates without gradient-based offline training. Ranking- or acceptance-based objectives align more directly with retrieval but lack this property.

Reply to Q2

Can the authors demonstrate meaningful end-to-end throughput improvements over Suffix Decoding under matched deployment conditions?

Thank you for the question. Appendix E provides a systematic throughput evaluation under matched deployment conditions: all drafters share the same vLLM fork across both SpeedBench (Fig. 7) and SWE-bench. LatentSpec achieves throughput comparable to Suffix Decoding, with small gains of up to ~3% (Fig. 8). We acknowledge that the end-to-end improvement over Suffix is modest. As discussed above, our main focus at this stage is acceptance length, which upper-bounds the achievable speedup.

Reply to Q3

How does LatentSpec scale to substantially larger external corpora?

While larger corpora raise the LZ bound, our results show they also make retrieval harder: adding the codebase lowers the realized acceptance length, whereas adding task-relevant history consistently helps. We therefore see moderate-sized, relevant sources, such as interaction history in agentic workloads, as the practical setting for LatentSpec. In this regime its memory cost is modest, significantly smaller than kv cache as reference.

Reviewer_8VJbOpenReview ↗

Response for the Rebuttal

Thank you for the detailed clarifications. The rationale behind the closed-form objective justifies the design choice on efficiency grounds, and the matched-deployment evaluation addresses my concerns about the experimental setup. That said, the connection between the reconstruction objective and downstream retrieval performance remains weak, and the reported throughput speedups are modest. Similarly, the corpus scalability discussion would benefit from quantitative evidence.

Overall, while the rebuttal resolves several minor issues, it does not fundamentally change my view of the method's novelty or practical impact. I will therefore maintain my original score of 2.

Reviewer_ATGoOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper tries to argue that extractive speculative decoding (SD) has an upper-bound. Relates it to LZ complexity of the string being generated. It showcases that even in the upper bound, MTP is better SD algorithm. And then showcase that learning the retrieval supervision from LZ bound intuition helps improve the extractive SD. The authors showcases the results with 2 benchmarks, different context length buckets, different categories and with different amount of corpora used for extractive drafting. The paper is very clear and easy to follow.

Critical strengths
  1. Arguing about extractive SD from upper-bound perspective. It helps understand how extractive drafting can be limited.
  2. The author also showcases how one can learn a better retrieval by trying to mimic the oracle. It simplifies the goal of extractive SD to find a match to find the longest substring at any given generation step from context (or additional corpora), and suggests how hidden-state information can be useful in this search
Critical weaknesses
  1. The authors argue that the gap between the upper bound and the existing algorithms is due to the gap in retrieval. However, there should be an effect of how long is the match. Typical ngram, suffix-tree drafting would have a limit of number of drafting steps (K=8 in the paper) while the bound can have certain long sequence of acceptance (beyond 8). Typically verification is done at fixed lookahead (easy to CUDA graph) and hence upper bound should have been based on min(8, longest match). This can be trivially be computed using brute force greedy post generation.

  2. The method and the upper bound makes sense for greedy drafting. But typically, SD is used with a sampling target that uses stochastic drafts with rejection sampling. Extractive drafting methods can use prior target logits for effective sampling

Questions for authors
  1. What was the temperature sampling used for the inference in the results of the paper? Is ngram/sufix decoding used with stochastic sampling for the drafts?
2 comments

Reply to W1

The authors argue that the gap between the upper bound and the existing algorithms is due to the gap in retrieval. However, there should be an effect of how long is the match. Typical ngram, suffix-tree drafting would have a limit of number of drafting steps (K=8 in the paper) while the bound can have certain long sequence of acceptance (beyond 8). Typically verification is done at fixed lookahead (easy to CUDA graph) and hence upper bound should have been based on min(8, longest match). This can be trivially be computed using brute force greedy post generation.

Thank you for raising this point. We did not state this clearly in the paper, and we will add it in the revision. We already took the limit of the number of tokens to draft into account. When computing the LZ bound, we limit each step to at most K=8 draft tokens, the same limit used in our experiments. We will clarify this in the revised version of the paper. So all LZ bounds in the paper can be fairly compared with fixed-lookahead verification. Without this limit, the bound can be much higher in some cases, up to about 13 tokens per step. The limit does not break Theorem 1: picking the longest allowed match at each step is still optimal.

Reply to W2

The method and the upper bound makes sense for greedy drafting. But typically, SD is used with a sampling target that uses stochastic drafts with rejection sampling. Extractive drafting methods can use prior target logits for effective sampling

Thank you for this point. Our bound should also works for random drafting with a greedy target, because LZ factorization is the optimal strategy(dtermnistic) and any randomness will only perform worse. So our bound applies.

The case of a sampling target that uses stochastic drafters (or greedy drafter, as in dflash or dspark) is indeed not supported in the current framework. This is a limitation and we will try to extend to this setting in the future work.

Reply to Q1

What was the temperature sampling used for the inference in the results of the paper? Is ngram/sufix decoding used with stochastic sampling for the drafts?

All results in the paper (Ngram, Suffix, LatentSpec) use greedy decoding with temperature 0 for the target model as well we the drafter model.

Thanks for the the reply. Authors agree with some of the points, and provide clarification for the others. I will maintain my rating.

Reviewer_jqu4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies extractive speculative decoding, in which draft continuations are copied from previously observed text. Experiments on SpeedBench and SWE-bench examine how this bound changes as the available copy corpus expands from the current request to additional history and external text. The paper also introduces LatentSpec, which retrieves continuations using target-model hidden states and adapts its similarity metric using continuation-match lengths as supervision. The results distinguish limitations caused by insufficient reusable text from those caused by imperfect retrieval, while showing that practical methods remain substantially below the oracle bound.

Critical strengths
  1. A useful framework for understanding the limits of extractive speculation. The connection to non-overlapping LZ parsing provides a sequence-dependent oracle bound that is independent of a particular retrieval heuristic. This helps distinguish a lack of reusable text from unsuccessful retrieval, making the analysis useful for deciding whether to expand the copy corpus or improve the retrieval algorithm. I consider this the paper's strongest contribution.

  2. A coherent link between analysis and method design. The paper uses continuation-match lengths not only to characterize the oracle but also to supervise hidden-state similarity for retrieval. The evaluation across different corpus configurations provides useful evidence about both the potential and the difficulty of exploiting additional history. Implementing the practical methods within a common vLLM framework also makes the comparison more relevant to inference systems.

Critical weaknesses
  1. Incomplete generation settings and limited long-output evaluation. Please report the temperature, thinking-mode configuration, and maximum generation length. SpeedBench outputs average only 726 tokens (Table 4). Add experiments with a generation budget of at least 8K tokens on tasks that elicit long outputs, and report actual output lengths. Long input contexts alone do not establish performance on long generated continuations.

  2. Unclear practical latency gains. Appendix E reports throughput, but online adaptation can reduce it despite improving acceptance length. Please compare end-to-end latency and time per output token against Ngram, Suffix, and autoregressive decoding under matched settings. Although target hidden states are reused, caching, retrieval, metric application, and online updates add overhead that may offset the acceptance gains.

  3. Unclear construction and cost of external-corpus indexes. For codebases or Wikipedia not previously processed by the target, hidden states require additional computation. Please clarify how these representations are computed and chunked, report preprocessing and storage costs, and state whether these costs enter the performance evaluation. Also confirm whether LatentSpec, Suffix, and the LZ oracle access the same underlying text corpus.

Questions for authors

See Weaknesses.

1 comment

Reply to W1

Incomplete generation settings and limited long-output evaluation. Please report the temperature, thinking-mode configuration, and maximum generation length. SpeedBench outputs average only 726 tokens (Table 4). Add experiments with a generation budget of at least 8K tokens on tasks that elicit long outputs, and report actual output lengths. Long input contexts alone do not establish performance on long generated continuations.

Thank you for this helpful comment. We now report the generation settings : temperature = 0 (greedy decoding), thinking mode disabled, and maximum generation length = 2048 tokens. We agree that long input contexts do not establish performance on long outputs. Because of time and compute constraints, we could not add ≥8K-token generation experiments in this revision. We have noted this limitation will address it in future work.

Reply to W2

Unclear practical latency gains. Appendix E reports throughput, but online adaptation can reduce it despite improving acceptance length. Please compare end-to-end latency and time per output token against Ngram, Suffix, and autoregressive decoding under matched settings. Although target hidden states are reused, caching, retrieval, metric application, and online updates add overhead that may offset the acceptance gains.

We thank the reviewer. Our main contribution is the LZ bound, which characterizes the best acceptance length (AL) any extractive drafter can reach; AL is therefore our primary topic of study. We present a negative result on existing methods and try to get closer to the LZ bound as much as possible. Hence, we only report AL. We agree that this is not necessarily converting into speed-up due to the overhead. We will modify the text and directly mention this as a critical weakness.

Reply to W3

Unclear construction and cost of external-corpus indexes. For codebases or Wikipedia not previously processed by the target, hidden states require additional computation. Please clarify how these representations are computed and chunked, report preprocessing and storage costs, and state whether these costs enter the performance evaluation. Also confirm whether LatentSpec, Suffix, and the LZ oracle access the same underlying text corpus.

We agree on the lack of clarity. The large external corpora (codebases and Wikipedia) are not proposed as a practical deployment setting. They are simply part of the empirical study of LZ-bound. We study what is missing to get LZ-bound closer to the learning-based ones, without an LZ-bound competitive with learning-based methods, such engineering studies have no meaning as they will always fail when compared with the learning-based ones. More importantly, the conclusive results suggest that scaling of the copy source raises the bound, yet existing extractive drafters, including ours, fail to benefit, and their acceptance length even decreases when the codebase is added (Fig. 4; Table 2). This is largely a negative result and study of the overhead would not add much.

To answer the question on the cost: All methods and the LZ oracle access the same underlying text corpus. For LatentSpec, hidden states for the external corpus are computed once by a prefill pass of the target model and then cached and reused across requests.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.