PaperlayerView exact revision on arXiv

Source-linked AI summary

Cactus: Accelerating Auto-Regressive Decoding with Constrained Acceptance Speculative Sampling

Yongchang Hao, Lili Mou

arXiv:2604.04987v1cs.LGcs.AImath.OCstat.ML

TL;DR

Speculative sampling preserves the verifier distribution but can reject acceptable tokens, while typical acceptance sampling raises acceptance at the risk of distributional distortion. Cactus frames decoding as constrained optimization, achieving higher throughput while preserving generation quality and diversity across benchmarks.

  • Problem

    Speculative sampling strictly matches the verifier distribution, whereas typical acceptance sampling increases acceptance by risking verifier-distribution distortion and semantic drift.

  • Method

    Cactus reformulates speculative sampling as constrained optimization, imposing a hard divergence constraint while enabling higher acceptance rates.

  • Results

    Across benchmarks, Cactus consistently improves throughput over lossless SpS while preserving generation quality and diversity.

  • Takeaways & Limitations

    Cactus offers a theoretically grounded, training-free, lightweight approach for practical real-time speculative inference.

  • Takeaways & Limitations

    Because Cactus solves a token-dependent distribution, the overall effective distribution can have divergence different from the specified δ.

Abstract

from arXiv · show

Speculative sampling (SpS) has been successful in accelerating the decoding throughput of auto-regressive large language models by leveraging smaller draft models. SpS strictly enforces the generated distribution to match that of the verifier LLM. This is unnecessarily restrictive as slight variations of the verifier's distribution, such as sampling with top-$k$ or temperature, would also be acceptable. Typical acceptance sampling (TAS) alleviates this issue by accepting more tokens using entropy-based heuristics. However, this approach distorts the verifier distribution, potentially degrading output quality when the verifier encodes critical information. In this work, we formalize the speculative sampling algorithm through the lens of constrained optimization. Based on this formulation, we propose Cactus (constrained acceptance speculative sampling), a method that guarantees controlled divergence from the verifier distribution and increasing acceptance rates. Empirical results across a wide range of benchmarks confirm the effectiveness of our approach.

1 INTRODUCTION

Speculative sampling accelerates autoregressive LLM decoding but can reject acceptable lower-probability tokens because it strictly preserves the verifier distribution. Cactus formulates acceptance as constrained optimization, enforcing bounded divergence while increasing acceptance and throughput without sacrificing verifier quality or diversity.

  • Motivation: Speculative sampling reduces decoding costs by using a smaller draft model to propose tokens, addressing memory-bound forward-pass bottlenecks in large LLMs.Generating each token requires a memory-bound forward pass through hundreds of billions of parameters.
  • Motivation: Strict distributional equivalence in SpS rejects correct but lower-probability tokens, although real-world applications generally do not require exact adherence to the original distribution.Typical acceptance sampling instead uses entropy-driven heuristics to accept proposals.
  • Cactus: Cactus reformulates speculative sampling as constrained optimization, explicitly trading off acceptance rate against divergence from the verifier distribution.Its hard divergence constraint provides the basis for controlled distributional deviation.
  • Results: Cactus consistently improves generation throughput over lossless SpS while preserving the verifier model’s generation quality and diversity.The preservation is attributed to Cactus’s explicit divergence constraint across experiments on a wide range of benchmarks and multiple state-of-the-art LLMs.

2 APPROACH

Cactus formulates draft-and-verify speculative sampling as constrained optimization, selecting a verifier-near target distribution to increase acceptance while controlling divergence. Its KL-based approximation boosts the candidate token probability with low overhead and preserves the divergence constraint in a specified regime.

  • Generalized formulation: The generalized formulation shows draft-and-verify sampling can exactly produce any target distribution with an optimal acceptance rate.This foundation lets Cactus choose a target distribution h dynamically rather than fixing it to the verifier distribution q.
  • Constrained optimization: Cactus optimizes h to maximize acceptance subject to an f-divergence constraint measuring its distance from verifier distribution q.The hyper-parameter δ controls closeness to q, after which the corresponding acceptance and recovery functions follow from the optimal-design observation.
  • Constrained optimization: Theorem 2 increases the drafted token’s acceptance probability to at least its verifier probability while proportionally scaling down other token probabilities.The resulting trade-off characterizes how closeness to q controls the acceptance rate induced by the acceptance function.
  • Divergence control: Although h depends on the sampled token, Theorem 3 guarantees the overall algorithm’s divergence from q is bounded by a continuous non-decreasing function Γ(δ).For any desired finite overall divergence δalg, a suitable δ can ensure Df(halg∥q) ≤ Γ(δ) ≤ δalg.
  • Cactus algorithm: Cactus uses KL divergence and a second-order Taylor approximation, increasing the candidate token’s probability by a bonus determined by q(n|x<t) and δ.When the exact solution γ∗ is not greater than 0.5, the approximation always satisfies the divergence constraint; unlike TAS, it reads only the candidate probability and minimally changes entropy.

3 EXPERIMENTS

Across benchmarks and model settings, Cactus increases accepted-token lengths while preserving or improving verifier-level accuracy. Experiments show that its constrained acceptance framework balances decoding efficiency with distributional fidelity more reliably than SpS, TAS, and interpolation.

  • Evaluation: Evaluation uses strict-match accuracy and average acceptance length, with rejected tokens reported to capture generation efficiency beyond acceptance rate.Accuracy is regex-extracted and averaged over samples; AL_m counts accepted tokens among m drafted tokens, while rejection counts reflect acceptance and total generation length.
  • Baseline comparison: TAS raises acceptance and lowers rejection relative to SpS but can substantially degrade accuracy through distributional shifts.On GSM8K with m = 20, TAS increases AL_m from 5.44 to 7.23 and reduces rejection by 35%; on GPQA, accuracy falls to 38.89 versus SpS at 42.93.
  • Cactus results: Cactus achieves the highest acceptance rates while maintaining or improving accuracy across benchmarks, including GSM8K and GPQA.At δ = 0.75, Cactus scores 86.66 on GSM8K and 45.46 on GPQA with m = 20; at δ = 1.0, GSM8K reaches AL_m 7.61 with score 86.43.
  • Efficiency and robustness: Cactus outperforms interpolation at similar acceptance rates and achieves nearly 1.9× speedup over the verifier alone in the 0.6B+14B setting.At approximately 90% acceptance, Cactus scores above 86 on GSM8K versus interpolation below 72; Cactus 1.0 reaches the speedup with m = 10 while maintaining the highest GPQA score.
  • Generalization: Cactus generalizes across architectures and larger models, delivering the longest acceptance lengths while surpassing TAS and SpS on IFEval and GPQA.It achieves comparable GSM8K performance and remains competitive across DeepSeek R1, Gemma, and LLaMA settings.

4 RELATED WORK

Cactus is situated within draft-and-verify acceleration, alongside vanilla speculative sampling and typical acceptance sampling. Related work also includes multi-drafter or multi-verifier extensions, low-complexity attention, and methods that reduce Transformer overhead without architectural approximation.

  • The draft-and-verify scheme: Cactus belongs to the draft-and-verify decoding family, whose foundation is designing acceptance-rate and recovery-probability functions.This line includes vanilla speculative sampling and typical acceptance sampling.
  • The draft-and-verify scheme: SpecInfer uses tree-based draft generation, while TreeBoN integrates speculative sampling into best-of-N tree-search decoding.Exploration of more integrated multi-drafter or multi-verifier Cactus remains future work.
  • Low-complexity attention for Transformers: Low-complexity attention variants address quadratic generation-time growth caused by each token attending to all previous tokens.These methods modify the Transformer architecture itself.
  • Minimizing overheads of Transformers: Flash Attention reduces Transformer overhead using tiling to avoid memory-bound operations, while memory-efficient attention reorders computation for constant memory usage.These approaches accelerate decoding without approximating the Transformer architecture.

5 CONCLUSION

The paper presents a constrained optimization framework and Cactus, a training-free speculative sampling method that raises acceptance rates while controlling divergence from the verifier model.

  • Cactus increases acceptance rates while maintaining provably controlled divergence from the large verifier model.It is introduced as a training-free speculative sampling method.
  • The framework analyzes and improves speculative sampling methods through constrained optimization.
  • Cactus uses basic element-wise operations, making it practical and lightweight for real-time inference.

ETHICS STATEMENT · A TECHNICAL PROOFS

The authors certify adherence to the ICLR Code of Ethics and report that the research raises none of the listed human-subject, dataset, harm, conflict, fairness, privacy, legal, or integrity concerns.

  • ETHICS STATEMENT: The authors certify adherence to the ICLR Code of Ethics.They state that the research involves no human subjects, dataset-release practices, potentially harmful content, conflicts of interest or sponsorship, discrimination, privacy or security issues, legal-compliance concerns, or research-integrity issues.

A.1 PROOF OF OBSERVATION 1

The proof shows that Algorithm 1 exactly reproduces any target distribution h when its acceptance rate and recover distribution are defined appropriately. It also establishes that the resulting acceptance rate is optimal, subject to the recover distribution remaining valid.

  • Exact target matching: Algorithm 1 produces the target distribution h exactly when the acceptance rate ϕ and recover distribution g are defined as specified.The proof decomposes the output distribution into accepted draft tokens and rejected tokens resampled from g.
  • Optimal acceptance: The acceptance rate ϕ is optimal for achieving the highest acceptance rate while keeping the recover distribution valid.The admissibility condition is h(i|x) − p(i|x)ϕ(i|x) ≥ 0 for every token, yielding the stated minimum-based optimal rate.
  • Exact target matching: Exact matching follows by equating the algorithm’s resulting token distribution with h and solving for the recover distribution g.The recover expression is self-normalizing, so validity requires each g(i|x) to be non-negative.

A.2 PROOF OF THEOREM 2

Theorem 2 characterizes the optimal constrained distribution by maximizing the target-token mass while allocating the remaining mass optimally and enforcing the divergence constraint. The proof uses Lemma 7’s unique minimizer and clamps the resulting target mass to a valid probability interval.

  • Proof of Theorem 2: Lemma 7 establishes that the proportional allocation is the unique minimizer for the remaining probability mass under the stated constraints.The uniqueness follows from Jensen’s inequality, with equality only when the relevant ratios are constant.
  • Proof of Theorem 2: The objective is maximized by making the target-token mass h_n as large as possible, because min{·, 1} reaches its maximum when h_n ≥ p(n).The proof therefore reduces the optimization to maximizing h_n under the constraints.
  • Proof of Theorem 2: The resulting γ* is clamped into [q(n), 1] because an unconstrained solution may exceed 1 when δ is too large to attain.This truncation ensures a proper probability value.
  • Proof of Theorem 2: For a candidate target mass γ = h_n, Lemma 7 gives the optimal allocation of the remaining mass 1−γ across i ≠ n.The allocation preserves the required total mass 1−γ.
  • Proof of Theorem 2: At optimality, the divergence constraint D_f ≤ δ is tight, so γ* is determined by the resulting equality constraint.Increasing γ further would violate the divergence bound.

A.3 PROOF OF THEOREM 3

Theorem 3 characterizes the overall algorithm’s distribution through the Theorem 2 solution functions and establishes a divergence-control function Γ. Its proof verifies that Γ is non-decreasing, continuous, and zero at zero divergence budget.

  • Theorem 3 expresses the overall algorithm distribution using the functions ϕ_n and g_n associated with the sampled token n.
  • For each drafted index n, the proof permits any target h_n satisfying D_f(h_n∥q) ≤ δ and derives the corresponding conditional output.
  • The algorithm’s one-step output is compared with the all-acceptance distribution p, yielding an upper bound of D_f(p∥q).
  • Basic properties of Γ: Γ is non-decreasing because increasing the budget enlarges the feasible set, and continuous because compactness and continuity apply on the finite alphabet.

A.4 PROOF OF PROPOSITION 4 · A.5 PROOF OF THEOREM 5

The A.4 proof shows that TAS’s acceptance function follows from a cross-entropy-constrained optimization whose optimal distribution is two-point. The A.5 result gives Cactus’s solution under KL divergence and clips its value to remain a valid probability.

  • A.4 PROOF OF PROPOSITION 4: TAS implicitly solves objective (3) with cross-entropy replacing the f-divergence.This establishes the optimization interpretation underlying Proposition 4.
  • A.4 PROOF OF PROPOSITION 4: The optimal solution concentrates probability mass on two outcomes.For fixed h_n = γ, the remaining mass is allocated to m = arg max_i q(i).
  • A.4 PROOF OF PROPOSITION 4: The resulting lower bound q(n) ≥ exp(−H(q)) exp(−δ) is the acceptance rate used in TAS.The bound follows after substituting the optimal two-point distribution into the cross-entropy constraint.
  • A.4 PROOF OF PROPOSITION 4: The theory establishes TAS acceptance-function soundness but does not reproduce the exact TAS algorithm.The exact algorithm requires adding H(h) = 0 and an ϵ threshold to the cross-entropy limit.
  • A.4 PROOF OF PROPOSITION 4: The technical lemma shows the extremal allocation sets h(m) = 1 − γ and h(i) = 0 for all i ≠ n, m.Here m = arg max_i q(i), because log 1/q(i) is minimized at m.
  • A.5 PROOF OF THEOREM 5: Under KL divergence, Corollary 5 gives Cactus’s solution to Equation (14).This is the stated solution characterization for Theorem 5.
  • A.5 PROOF OF THEOREM 5: Cactus clips the resulting value to [q(n|x<t), 1] so it remains a valid probability.The clipping is an implementation step applied to the derived value.

A.6 PROOF OF COROLLARY 6

The proof establishes that when the exact solution γ* ≤ 0.5, the approximation satisfies the divergence constraint. It also shows that the approximation never overestimates γ when the verifier lacks confidence in the sampled token.

  • When the exact solution γ* is not greater than 0.5, the approximation always satisfies the divergence constraint.
  • Φ is strictly increasing on [q, 1], so Φ(γ) = δ has a unique root γ⋆ ∈ (q, 1].
  • Taylor’s theorem with the Lagrange remainder bounds the approximation used to derive the quadratic-approximate root.
  • The approximation never overestimates γ when the verifier model is not confident about the current sampled token.

B ADDITIONAL EXPERIMENTS … E THE USE OF LARGE LANGUAGE MODELS

Across additional experiments, Cactus improves decoding speed and acceptance while preserving quality better than competing approaches and scaling with stronger drafters. Case-study, impact, future-work, and disclosure sections further describe divergence control, efficiency benefits, limitations, and the paper’s use of language models.

  • B ADDITIONAL EXPERIMENTS: Mentored decoding has the smallest acceptance-rate gain while increasing per-step generation time, making GSM8K wall time 20% longer than naive SpS and severely degrading IFEval performance.Mentored decoding also uses numerical optimization, which significantly slows decoding.
  • B ADDITIONAL EXPERIMENTS: SpecCas significantly improves acceptance and decoding speed, but its generation quality is lower than other methods; Cactus at δ = 10 achieves similar GSM8K and GPQA wall-time acceleration with higher quality.The authors attribute the difference partly to SpecCas lacking explicit divergence control.
  • B ADDITIONAL EXPERIMENTS: 1.88× overall speedup (+88% gain over autoregressive decoding) was achieved without hyper-parameter tuning or additional training, with Cactus outperforming SpS across domains.The evaluation used δ = 1 and measured speed with the HuggingFace Transformers framework.
  • B ADDITIONAL EXPERIMENTS: Increasing the drafter size to 4B raises mean accepted length to 7.76 and reduces rejection rates by 76% while maintaining high task accuracy.The experiment used a Qwen 3 14B verifier and same-family drafters on GSM8K.
  • C CASE STUDY: When δ is large, reasoning becomes poor and lengthy, producing an incorrect GSM8K result from a low-quality chain-of-thought; divergence control therefore helps maintain qualitative measures.The case study varied δ for the Qwen 3 0.6B + 14B model pair.
  • D BROADER IMPACT AND FUTURE DIRECTIONS: By improving inference efficiency without sacrificing output quality, Cactus reduces computational costs and energy consumption and can support broader access and lower-cost applications.The paper identifies education, healthcare, and low-resource settings as potential application areas.
  • D BROADER IMPACT AND FUTURE DIRECTIONS: The authors cap evaluation at 32B parameters and leave larger-scale optimization, footprint reduction, and related system extensions for future work.Potential directions include quantization, weight sharing, cache reuse, selective offloading, and early-exit heuristics; they also report Cactus exceeding verifier accuracy by 2 standard deviations on IFEval and GPQA.
  • E THE USE OF LARGE LANGUAGE MODELS: The authors use ChatGPT for minimal grammar revision, ChatGPT and DeepSeek R1 to triple-check technical proofs, and ChatGPT to initially generate plotting code that they subsequently revise.They state that the grammar-editing procedure is an exception to the paper’s general practice.
Loading 2604.04987v1…