acceptodds
Under review as a conference paper at ICLR 2027

Draft-and-Verify: Speculative Entropy Decoding for Autoregressive Learned Compression

Abstract

Autoregressive (AR) entropy models have been central to modern neural lossless compression, but their sequential decoding introduces substantial latency, often orders of magnitude higher than commercial codecs. We present SpecED, a speculative entropy decoder that reduces the number of sequential entropy-model calls while preserving bit-exact reconstruction from the bitstream. Unlike standard entropy decoding, which invokes the full AR model sequentially for each latent symbol, SpecED uses a lightweight draft model to predict the distributions of several future symbols, the arithmetic decoder recovers candidate symbols from the bitstream under these drafts, and one batched call of the base model verifies them. This draft-and-verify framework combines multi-head lookahead drafting, speculative state branching, and budgeted speculation-tree search to reduce sequential latency while balancing speculation depth, branch diversity, and verification cost. Theoretically, we establish a Rényi-divergence-based bound showing that the probability of consecutive speculation success decays exponentially in the number of drafted symbols, at a rate set by the Chernoff information between draft and base models, and derive a tractable KL-based approximation for practical draft-model design. On lossless codecs for text (LLMZip), point clouds (OctAttention), and particle-physics data (BOA Constrictor), SpecED yields ideal entropy-model speedups of -, and up to measured end-to-end wall-clock speedup on LLMZip ( on enwik8). The algorithm is extended to lossy neural codecs with AR entropy models, where we obtain - theoretical speedups in Encodec, with gains shrinking as the per-symbol entropy grows, as predicted by our theoretical bound.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
learned compression, arithmetic coding, speculative decoding, autoregressive models

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_8eTUOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a speculative entropy decoding (SpecED) framework for accelerating autoregressive entropy models in neural compression. Instead of computing the full entropy model sequentially for every symbol, SpecED uses lightweight draft models to predict future distributions. It then performs speculative arithmetic decoding and verifies the results with batched evaluations of the original entropy model. Multi-head lookahead drafting, speculative state branching and budgeted tree search mechanisms are introduced for efficient parallel speculation. The paper further provides a Rényi-divergence-based bound on speculation success and evaluates the method across lossless and lossy compression tasks.

Critical strengths
  1. The paper addresses an interesting and practical problem in autogressive neural compression, where high decoding latency is caused by sequential entropy-model evaluations. SpecED reduces such a sequential bottleneck while preserving bit-exact reconstruction and leaving the original bitstream and base entropy model unchanged.
  2. The proposed method is broadly evaluated across different benchmarks with various modalities and codecs to show notable speedups.
Critical weaknesses
  1. Table 1 compares two ALB schedules against an exhaustive oracle, but does not include single-path speculation or SLB for BOA Constrictor and OctAttention. Although related comparisons appear in the audio experiments, their benefits should also be demonstrated on these main benchmarks.
  2. Report measured latency for each baseline. Expected acceptance counts alone cannot show whether additional branching is worthwhile, because exploring and verifying more candidates introduces overhead.

Overall the experimental results are not sufficiently strong to make a case that the proposed branching and multi-draft architecture directly translates into improved latency.

Questions for authors
  1. Please address the weaknesses sections above.
  2. Could the authors provide a theoretical characterization or at least clarify how the current theoretical success bound should be interpreted for the actual multi-head, multi-branch budgeted tree search algorithm? Table 1 suggests that these mechanisms have a substantial effect on performance.
3 comments

We thank the reviewer for the constructive feedback. We updated to include the single-path speculation results (Table 1) and clarify why existing experiments show additional branching is worthwhile. We also provide a brief characterization on how Theorem 1 extends to multi-head, multi-branch designs.

Detailed responses follow.

W1. Results on single-path speculation

We have updated to include the following results of the single-path speculation in the revised paper under the same hardware and seeds (Table R3.1).

Table R3.1 E[K]\mathbb{E}[K] of single-path speculation and ALB (2,2,1,1)(2,2,1,1) in revised Table 1 (physics data, point cloud).

Base modelSearchK=1K=1K=2K=2K=3K=3K=4K=4
BOA Constrictor (physics)SLB (1) (single-path)0.470±0.0010.470_{\pm 0.001}0.769±0.0030.769_{\pm 0.003}0.980±0.0030.980_{\pm 0.003}1.161±0.0031.161_{\pm 0.003}
BOA Constrictor (physics)ALB (2,2,1,1)(2,2,1,1)0.517±0.0050.517_{\pm 0.005}0.849±0.0120.849_{\pm 0.012}1.083±0.0171.083_{\pm 0.017}1.287±0.0221.287_{\pm 0.022}
OctAttention (point cloud)SLB (1) (single-path)0.269±0.0040.269_{\pm 0.004}0.366±0.0070.366_{\pm 0.007}0.411±0.0090.411_{\pm 0.009}0.432±0.0100.432_{\pm 0.010}
OctAttention (point cloud)ALB (2,2,1,1)(2,2,1,1)0.363±0.0050.363_{\pm 0.005}0.499±0.0100.499_{\pm 0.010}0.554±0.0120.554_{\pm 0.012}0.582±0.0140.582_{\pm 0.014}

As shown in Table R3.1, a trend consistent with original Table 1 of the manuscript can be observed, where accepted draft tokens increase with the leaf budgets, further supporting our conclusions.

W2. How reported results support value of additional branching

W2.1 Baseline latency

We would like to clarify that measured baseline latency (BOA Constrictor, OctAttention and LLMZip, Encodec) has already been reported in Figure 6, 7 and Table 8. To make it clearer, we also report the detailed datapoints of Figure 6 in Table R3.2:

Table R3.2 Measured latency for decoding 10410^4 symbols of SpecED and baselines (physics data, point cloud).

DepthBOA Constrictor (s)OctAttention (s)
baseline1.242 (1.00×)15.191 (1.00×)
10.805 (1.54×)9.914 (1.53×)
20.750 (1.66×)9.293 (1.63×)
30.743 (1.67×)8.883 (1.71×)
40.671 (1.85×)8.630 (1.76×)

W2.2 Effect of additional branching

We would like to clarify that we can already deduct that additional branching is worthwhile from existing experiment results, by realizing the physical significance of average acceptance E[K]\mathbb{E}[K] and compare with measured latency speedup.

We note that 1+E[K]1+\mathbb{E}[K] is an inherent upper bound of the latency speedup. For example, in Fig. 6(b), ALB (6,6,4,2)(6,6,4,2) strategy achieves an end-to-end latency speedup of 1.8×1.8 \times, which is already surpassing the upper bound 1+E[K]1+\mathbb{E}[K] of single-path speculation and ALB (2,2,1,1)(2,2,1,1), which are 1.43×1.43\times and 1.58×1.58\times respectively, as shown in Table 1. This shows that the proposed branching architecture directly translates into improved latency.

We specify this property for clarity in Section 5.1.

Q1 See the responses to W1, W2.

Q2. Theorem 1's extension to multi-head, multi-branch design

Theorem 1 covers multi-head drafting by letting QQ to be the joint distribution induced by the KK heads. It can extend to tree search. The search, including SLB/ALB pruning, is a deterministic function of the codepoint and retains at most BnB_n leaves at depth nn. Let Q~n(z)=1/Bn∑l∣Al(z)∣\tilde{Q}_ n(z) = 1/B_ n\sum_ {l} |A_ l(z)|, where Al(z)A_ l(z) is the set of codepoints for which leaf ll decodes block zz. A union bound over leaves, followed by the argument of Theorem 1, gives Pn(success)≤inf⁡λ∈(0,1)exp⁡(−λ[D1−λ(P∥Q~n)−log⁡Bn])\mathbb{P}_ n(\text{success}) \le \inf_ {\lambda \in (0,1)} \exp\big(-\lambda[D_{1-\lambda}(P \| \tilde{Q}_n) - \log B_n]\big), which reduces to Theorem 1 when Bn=1B_n = 1. The leaf budget therefore offsets log⁡Bn\log B_n nats of draft–base divergence. The bound holds for any pruning rule with at most BnB_n leaves.

We record this extension in Remark 2, Section 4. While there exists tighter bound for data-dependent pruning rule, the derivation would be non-trivial. Exact characterization is also open in standard speculative decoding, and closed-form optimal acceptance is known only for restricted cases such as two identical drafts at the token level (Khisti et al. "Multi-draft speculative sampling: Canonical decomposition and theoretical limits." ICLR 2025). Multi-step and tree-based analyses rely on simplifying assumptions, such as i.i.d. acceptance decisions across positions (Leviathan et al., 2023), or a candidate's acceptance probability depending only on its child position under an already accepted parent (Chen et al. "Sequoia: Scalable and robust speculative decoding." NeurIPS 2024).

We thank the reviewer again for the constructive feedback, allowing us to improve the completeness of the paper. We welcome further questions to enhance the contribution of our paper.

Thank you for the detailed response and the additional experimental results.

The inclusion of the single-path speculation baseline and the measured latency comparisons addresses my main experimental concerns. In particular, Table 8 demonstrates that increasing the branching budget yields meaningful improvements in end-to-end latency for both BOA Constrictor and OctAttention. I agree that these results provide stronger evidence for the practical benefits of the proposed approach.

We thank the reviewer for the recognition of our work. The valuable suggestions improve the completeness of our paper.

Reviewer_jiZtOpenReview ↗
Rating
4(+2)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The work proposes a method to parallelize entropy decoding in codecs with an autoregressive entropy model, a highly sequential process. It employs a multi-head lookahead candidate generation for multiple consecutive steps that, if successfully verified, prevents the base entropy model from inferring the probability distributions.

Since candidates grow exponentially as the speculation horizon grows, the authors propose two techniques: static leaf budgeting and annealed leaf budgeting. These methods prune the number of candidates generated.

The work derives success bounds that decay exponentially with candidate-true distribution divergence. Even as divergence tends to zero, the sucess probability decays with the number of symbols.

Results show substantial speedups in both arithmetic decoding and end-to-end wall-time. Confirming the theoretical results, it is shown that as the rate increases, the speedup gains diminish.

Critical strengths
  • The impact of this work is strong since entropy coding is the bottleneck in many learned compression models, preventing this research from making it into applications.
  • Exhaustive evaluation covering different modalities and both lossless and lossy codecs.
  • Substantial speedups.
Critical weaknesses
  • The paper is poorly written. It lacks clarity. It is terse, repetitive and as result it is confusing and hard to parse. Overly compounded nouns are further overloaded with superfluous adjectives every time they are referenced. This makes the average reader easily lose track of the message being conveyed. There is some jargon that I am not familiar with even though my current research is closely related to this work. The jargon is not cited so it seems to be made up and lacking definition. Even though explanations are verbose, many details about the proposed method are missing. Lastly, some citations are missing years.
  • There is no explanation on how verification is done besides the very cryptic “symbol-level consistency constraints”. This is a key aspect of the algorithm. Based on Figure 2, it seems to trigger the base entropy model, which should recant any speedups due to parallelization. I do not understand then how there can be any speedups.
  • Ft(xtˉ)F_t(\bar{x_t}) seems poorly defined. What is aa in this equation?
  • Compared against Equation 1, why is Equation 2 swapping tt with ii . Seems inconsistent.
  • The introduction says “exact entropy decoding requires symbol-level consistency rather than exact distribution matching” and the authors mentioned this is something the current method takes advantage of. Then, the related work says “The distribution mismatch can induce state drift or error accumulation even when early symbols are correct”. Remark 2 confirms this again. These two statements are contradictory.
  • Theorem 1: a ”n-symbol block” is not properly defined.
  • Remark 2 seems to come out of nowhere and not related to Theorem 1 or Corollary 1.
  • Where is Remark 1?
  • Line 420 mentions “we observe that speedups vary greatly with (entropy of) the data, similar to in speculative decoding, as suggested by Theorem 1”. This seems incorrect. The entropy of the data is not involved in Theorem 1. Rényi divergence notably factors out the entropies of the probability distributions considered.
  • The construction of Figure 6 is not well explained. How is entropy factored in?
  • No trade-offs of the proposed method are mentioned. Certainly there has to be a memory overhead in the inference process. How much is it?
Questions for authors

If the Authors can show me that I am misunderstanding the work, or that explanations do exist and are clearly presented, I could increase my score. Unfortunately, some weaknesses could be addressed in a rebuttal but some cannot.

4 comments

We would like to express our deep appreciation for the detailed assessment. We clarify the verification part of the algorithm, a few definitions, the links between the statements that the reviewer concerned and the construction of Figure 6. We also amended one wrong statement and included the measured memory overhead of SpecED, in the appendix. Lastly, we revised some inconsistencies in the paper. For clarity, we refer the 1111 points that the reviewer concerns in critical weaknesses as W1−W11W1-W11.

Detailed responses follow.

W2. Verification of draft tokens

The verification is carried out by directly comparing the decoded draft tokens x^i+k\hat{x}_ {i+k} and the decoded reference tokens x~i+k\tilde{x}_ {i+k}, as we described in the paragraph under (5), in Section 3.3. Once x^i+k\hat{x}_ {i+k} is rejected, all successing draft tokens at depth >k>k, i.e. {x^i+k+c:c>0}\{\hat{x}_ {i+k+c}: c>0\} are rejected, as the corresponding decoded reference tokens {x~i+k+c:c>0}\{\tilde{x}_{i+k+c}: c>0\} are not guaranteed to be correct, due to the wrong context at depth kk.

We also note that the computation of reference tokens x~i+k\tilde{x}_ {i+k}, as described in (5), does not require autoregressive calls of the base entropy model, since x^<i+k\hat{x}_ {<i+k} is available before the call. This allows an O(1)O(1) instead of O(K)O(K) latency to compute reference distributions for KK tokens. Moreover, many models such as transformers support natively verification of multiple tokens through single forward, taking input sequence x1:nx_ {1:n} and outputting distribution of x2:n+1x_ {2:n+1}. kk forwards of base entropy model are skipped upon acceptance of first kk draft tokens and speedups are hence gained.

We have added descriptions in line 254-257 to convey this message more clearly.

W3. Definition of Ft(xt−)F_t(x^-_t)

Ft(xt−)F_ t(x^-_ t) is the sum over all possible admissible values aa in the domain of each element of sequence x1:Tx_{1:T} that is less than xtx_t. We note that we did not include the domain of aa, making it seemingly like a real number. We have made changes in Section 3.1 to reflect this.

W5. Statements on distribution mismatch

The feasibility of SpecED comes from the fact that we require only the decoded tokens to be exact, while the distributions used to decode them can be slightly mismatched. This can be seen more clearly in the newly added Figure 3. It is hence possible to decode correct tokens with mismatched proposal distributions from light-weight draft models. Difficulties then arise due to state drift, which we propose state branching to mitigate. Therefore, the two statements are not contradictory.

W6. Definition of nn-symbol block

A n-symbol block means a block of n consecutive symbols, considering block coding in conventional data compression. We have changed the wording to ‘the nn consecutive tokens xi+1:i+nx_{i+1:i+n}’ to represent this concept more clearly.

W7. Deduction of Remark 1 (previously Remark 2)

Remark 1 does not rely on Theorem 1 and is explanatory. We have moved it before Theorem 1 to avoid confusion. Furthermore, we added a new illustrative diagram (Figure 3) to show how error can accumulate, as mentioned in Remark 1.

W9. Mis-specified relation between Theorem 1 and statement in line 467 (previously 420)

We agree with the reviewer. The observation of the trend is largely empirical, which is similar to in speculative decoding. We have removed the indiscreet link to Theorem 1 and added related references from the field of speculative decoding.

W10. Construction of Figure 7 (previously Figure 6)

In Figure 7, there exists time overlap between execution of base entropy model and arithmetic decoding of draft models. Specifically, we allow draft models to run concurrently with base model in every forward, which is possible since draft models shares the same contexts, as shown in (4). Because the draft models are light-weight, they can finish execution before the base entropy model, and the autoregressive arithmetic decoding of draft tokens overlaps with the execution of the base entropy model. We have updated Appendix B.1.3 to state this more clearly.

This time overlap is not dedicated to LLMZip. However in for BOA Constrictor and OctAttention, the latency of arithmetic decoding is already very minimal, as shown in Figure 6. Hence we only show the overlap for LLMZip for an illustration purpose.

W11. Memory overhead of SpecED

We measured the peak GPU memory usage as a metric of the memory overhead in the inference process, on the same hardware and with the same settings as in Appendix B, showing that there is an 5%−44%5\%-44\% memory overhead for LLMZip, BOA Constrictor and OctAttention, as we show in Table R2.1, Table R2.2.

Table R2.1 Peak GPU memory of LLMZip decoding at speculation depth K=1,3,5,7K=1,3,5,7, measured by nvidia-smi.

MethodPeak GPUOverhead
baseline13.23 GiB--
SpecED, K=1K=113.88 GiB+664 MiB (4.9%)
SpecED, K=3K=313.88 GiB+666 MiB (4.9%)
SpecED, K=5K=513.88 GiB+668 MiB (4.9%)
SpecED, K=7K=713.90 GiB+688 MiB (5.1%)

Table R2.2 Peak GPU memory of BOA Constrictor and OctAttention at speculation depth K=1,2,3,4K=1,2,3,4, measured by torch.cuda.max_memory_allocated.

DepthBOA Constrictor Peak GPU (MiB)BOA Constrictor Overhead (MiB)OctAttention Peak (MiB)OctAttention Overhead (MiB)
baseline25.70--92.28--
SpecED, K=1K=136.89+11.20116.95+24.67
SpecED, K=2K=236.91+11.22116.95+24.67
SpecED, K=3K=336.93+11.24116.95+24.67
SpecED, K=4K=436.95+11.26117.36+25.08

As we see in Table R2.1, SpecED adds 664664--688688 MiB to the 13.2313.23 GiB peak of sequential decoding for K=1,…,7K = 1, \dots, 7, about 5%5\% of the baseline. The relatively small overhead is due to the size of LLaMA-7B, whose weights alone occupy 12.812.8 GiB. The relative overhead is larger for smaller base entropy models (Table R2.2), which takes up to 1.44×1.44\times the memory of one base forward pass for BOA Constrictor (25.70→36.9525.70 \rightarrow 36.95 MiB) and 1.27×1.27\times for OctAttention (92.28→117.3692.28 \rightarrow 117.36 MiB), at depth 44.

We included the results and further detailed discussions in Appendix E.

W1, 4, 8. Inconsistencies

We note that since SpecED is fundamentally different from speculative decoding, due to management of states and exact verification, we face new processes and concepts, which may not correspond to existing descriptive phrases. We also borrowed certain phrases such as 'n-symbol block' from information theory and classical data compression (Shannon, Claude E. "Coding theorems for a discrete source with a fidelity criterion," (IRE) Nat. Conv. Rec., vol. 7, 1959.)

However, after we went over the paper again, we find there are a few wordings that restricts readability, for example 'lookahead' and 'speculation', which are used interchangeably but express the same meaning, or 'symbol-level consistency'. We have now thoroughly revised the wordings to improve the readability for the audience (line 14, 87, 98, 212, 215 etc.).

We also revised the missing years in the bibliography, inconsistent notation in (2) and the inconsistent numbering of Remark 1.

We thank the reviewer again for the effort on the detailed review, which allows us to improve the paper. We are open to further discussions if additional clarity is needed.

Thank you for your response. I appreciate the effort put in addressing my concerns. I think most of them have been addressed satisfactorily.

  • The key for my understanding of W2W_2 is that the base entropy model is still called for each symbol, but it is using the drafts to compute a reference, which are obviously (it is the entire point of the paper) not computed autoregressively for the horizon KK . The verification needs to happen autoregressively but since the computational bottleneck is the entropy model and not the arithmetic codec, we can still achieve effective parallelization (Footnote 1 is critical here).
  • I appreciate the additional results in Appendix E. I see it referenced in the main document. Now the reader is more aware of the tradeoffs being made.
  • Regarding Figure 7, could you please reference the Appendix B for readers who want clarification?
  • I think W5W_5 has been addressed very well by the inclusion of Figure 3.
  • Some terms that I highlighted as repetitive/confusing seem to have been addressed even though I did not point them out in my review.

I think this paper is a clear accept to me now. I have expressed before the impact this work can have on learned coding. My concerns were about presentation and a misunderstanding regarding soundness but they have been addressed.

We deeply appreciate the detailed suggestions and the recognition of the impact of the work. We have put the reference Appendix B.1.3 in the caption of Figure 7 for the readers.

Reviewer_EtcqOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

SpecED accelerates autoregressive entropy decoding through lookahead drafting, candidate arithmetic-state branching, and budgeted verification, while preserving exact recovery of encoded symbols. The paper provides a Rényi-divergence success bound and a local KL approximation. Experiments cover five codecs: reported end-to-end speedups are about 1.9× on BOA Constrictor, 1.8× on OctAttention, and 1.78× on average for LLMZip at depth 7. Gains decrease at higher evaluated audio/video bitrates.

Critical strengths
  1. The method addresses a real difference from LLM speculation: correct speculative symbols can still leave the arithmetic decoder in the wrong state. State-aware verification makes speculation possible without replacing the base probability model in the frozen-base setting.

  2. The experiments show actual latency reductions across Mamba-, Transformer-, and LLM-based codecs. This is stronger evidence of practical value than acceptance rates alone. Figure 8’s state-oracle comparison also helps explain why speculative trajectories fail.

Critical weaknesses
  1. Figure 5 reports end-to-end gains with multi-state ALB, but the incremental benefit of branching and annealing over simpler speculation is not isolated. LLMZip uses a single autoregressive draft, Encodec’s latency table retains only one state per depth, and VCT has no end-to-end timing. The timing protocol also needs clarification: Appendix B.2.1 reports the maximum branch decoding time, while Table 3 describes verification on KK devices. Without matched-resource ablations and a clear accounting of concurrency and overhead, it is difficult to assess whether the central branching mechanism justifies its added cost.

  2. The connection between the theory and the empirical predictions is not sufficiently established. Theorem 1 omits the conditional uniform-codepoint assumption used in its proof, whose relation to the implemented finite-precision coders is unclear. Its interval-length relaxation is valid under that model, but does not capture interval displacement, and the bound concerns one draft trajectory rather than budgeted tree search. Corollary 1 assumes memoryless distributions and small per-step KL divergence; it does not derive the fitted αn\alpha\sqrt n correction in Section 5.3. The empirical fit should be distinguished more clearly from a guaranteed bound.

Questions for authors
  1. Implementation clarification: How are candidates ordered, pruned, and batched in SLB/ALB? Please specify the implemented training losses and how they encourage diversity among candidate heads at the same lookahead depth. Does Appendix B.1.1’s statement that search continues only after a draft/base symbol match describe verification or speculative expansion? How does this relate to Section 4’s statement that expansion uses no verification signals?

  2. Timing and attribution: Are the reported latencies directly measured elapsed times with synchronization and all speculative work included? Please clarify the maximum-branch-time accounting in Appendix B.2.1 and the physical resources denoted by “KK devices” in Table 3. Under matched hardware resources, can you provide a representative comparison of a single-draft trajectory, SLB with different leaf budgets including B=1B=1, and ALB, holding the lookahead depth fixed?

  3. Theory clarification: How does the uniform-codepoint model relate to the implemented arithmetic coders, and how informative is the length-based bound when interval displacement accumulates? Is the fitted αn\alpha\sqrt n correction in Section 5.3 intended solely as an empirical predictor, or does it retain an upper-bound guarantee under additional assumptions?

6 comments

We thank the reviewer for the detailed assessment. We clarify the questions on implementation details and how implementations align with theoretical assumptions. We also updated for the suggested additional results on single-draft trajectory (Table 1).

Detailed responses follow.

Q1. Implementation clarification

1.1 Implementation of SLB/ALB

In our implementation, candidates are pruned by taking the first MkM_k successfully decoded (since failure of arithmetic decoding can happen in some baselines) candidates in their natural order (without reordering or sorting), where MkM_k is constant in SLB and specified explicitly in ALB. All selected candidates in the same speculation depth are processed in a single batch. We have updated Section 5.1 to show this more clearly.

This is a naive approach and there certainly exists better approach with proper ordering, which would enable further acceleration. As we mentioned in conclusion, we left the design of such selection strategies as future work.

1.2 Implementation of training loss

As described in Table 3-6, we employ best of model cross-entropy + a tuned Lagrange multiplier of average KL divergence between draft models and base model, in all baselines except LLMZip, where we did not train due to the scale of the backbones. The diversity between candidate heads is hence not explicitly encouraged. Further improvements on model-specific designs are possible, while we only provide the basic framework here.

We revised the wordings used in Table 3-6to show this more consistently.

1.3 Relation between Appendix B.1.1's and Section 4's statement

B.1.1’ statement that search continues only after a draft/base symbol match describes verification. This does not contradict with Section 4’s statement that expansion uses no verification signals, since speculative expansion finishes before verification, outputting a set of draft tokens. Those tokens are then verified during the verification, where all draft tokens beyond a timestep with no draft/base match are discarded. We have revised Section 4's statement to avoid this confusion.

Q2/W1. Timing and attribution

2.1 Implementation of timing

Due to hardware constraints, we trained and evaluated SpecED on single GPU. During inference, KK decoding executions are performed and timed on this single device. We consider the maximum of those KK executions to be the wall time for KK parallel executions. This protocol has been widely employed in the research field of speculative decoding, such as in Timor et al. "Distributed speculative inference (DSI): Speculation parallelism for provably faster lossless language model inference." ICLR 2025. While we omitted the latency of communications between GPUs under this protocol, such latency is of little concern, since the transmission of the tokens and states is negligible comparing to neural network computations.

We have included this in Appendix B to make it more explicit.

2.2 Additional results on single-draft trajectory

We have updated to include the following results of the single-draft trajectory in the revised paper under the same hardware and seeds (Table R1.1).

Table R1.1 E[K]\mathbb{E}[K] of single-draft trajectory and ALB (2,2,1,1)(2,2,1,1) in revised Table 1 (physics data, point cloud).

Base modelSearchK=1K=1K=2K=2K=3K=3K=4K=4
BOA Constrictor (physics)SLB (1) single draft0.470±0.0010.470_{\pm 0.001}0.769±0.0030.769_{\pm 0.003}0.980±0.0030.980_{\pm 0.003}1.161±0.0031.161_{\pm 0.003}
BOA Constrictor (physics)ALB (2,2,1,1)(2,2,1,1)0.517±0.0050.517_{\pm 0.005}0.849±0.0120.849_{\pm 0.012}1.083±0.0171.083_{\pm 0.017}1.287±0.0221.287_{\pm 0.022}
OctAttention (point cloud)SLB (1) single draft0.269±0.0040.269_{\pm 0.004}0.366±0.0070.366_{\pm 0.007}0.411±0.0090.411_{\pm 0.009}0.432±0.0100.432_{\pm 0.010}
OctAttention (point cloud)ALB (2,2,1,1)(2,2,1,1)0.363±0.0050.363_{\pm 0.005}0.499±0.0100.499_{\pm 0.010}0.554±0.0120.554_{\pm 0.012}0.582±0.0140.582_{\pm 0.014}

As shown in Table R1.1, a trend consistent with original Table 1 can be observed, where accepted draft tokens increase with the leaf budgets, further supporting our conclusions. We thank the reviewer for this suggested improvement of completeness.

Q3/W2. Theory clarification

3.1 Relation between uniform-codepoint model and implemented arithmetic coders

The assumption of the uniform codepoints is equivalent to assume that the compressed data actually follow the model PP. In the implementation, this depends on the quality of the pretrained entropy model of the baseline. Where the compression rate of the baseline is near-optimal (such as LLMZip, achieving rate near entropy), this assumption is effectively satisfied.

The reviewer also mentions the possible error induced by the finite-interval coders implemented, caused by the rounding of the integer coder. We note that rounding moves each boundary by at most 2−bM2^{-b} M of the current interval width per step, where MM is the alphabet size and bb is the coder precision. In our baselines, this shift contributes to {0.0015%0.0015\%, 0.39%0.39\%, 0.38%0.38\%, 0.012%0.012\%} of total interval for {BOA Constrictor, OctAttention, LLMZip, Encodec}, therefore the impact is minimal.

3.2 Significance of fitted correction in Section 5.3

The additional simplified assumption of memoryless PP and QQ in Corollary 1 is not practical in modern learned compression schemes. Hence, the expression in Section 5.3 is not a guaranteed upper bound, but an empirical surrogate. It is also applied in such a way in Fig. 8(a), by fitting the correction on only the first bitrate and predicting performance for the others. We have revised the wordings in Section 5.3 to distinguish this more clearly from a guaranteed bound.

We thank the reviewer again for the detailed assessment, allowing us to improve the clarity of the paper. We welcome further questions to enhance the contribution of our paper.

Thank you for the additional experiments and clarification. Further question about 2.2, I can see that ALB(6,6,4,2) accepts more symbols than SLB(1), but I can't tell whether it actually decodes the same data faster from Figure 6 (which only compares ALB with original decoder). Could you also report the time of ALB and SLB(1)?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.