Cactus: Accelerating Auto-Regressive Decoding with Constrained Acceptance Speculative Sampling
| Authors | Yongchang Hao & Lili Mou |
| Year | 2026 |
| HF Upvotes | 0 |
| arXiv | 2604.04987 |
| Download | |
| HF Page | View on Hugging Face |
Abstract
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.
Engineering Breakdown
Plain English
This paper addresses a key bottleneck in speculative sampling (SpS), a technique that accelerates language model inference by using smaller draft models to generate token candidates that are verified by a larger model. Current SpS methods strictly match the verifier's token distribution, which is overly rigid—in practice, slight variations like temperature sampling or top-k filtering would be equally valid. The authors formalize speculative sampling as a constrained optimization problem and propose a solution that accepts more tokens through principled methods while preserving output quality, moving beyond entropy-based heuristics that distort the verifier distribution.
Core Technical Contribution
The key novelty is reframing speculative sampling through constrained optimization rather than treating it as a strict distribution-matching problem. This formalization reveals that the verifier's exact distribution is not necessary—only that the final output distribution respects certain constraints. The authors develop a principled alternative to typical acceptance sampling (TAS) that maintains verifier distribution integrity while accepting more draft tokens than baseline SpS. This optimization lens opens a new design space for balancing acceptance rate (throughput) against output quality (fidelity).
How It Works
The algorithm operates in three stages: (1) A draft model generates candidate tokens with its own distribution; (2) The verifier model scores these candidates and computes its preferred distribution; (3) Instead of strict binary acceptance (standard SpS), the optimization framework determines an acceptance probability for each token that maximizes throughput while constraining the output distribution to stay within acceptable deviation from the verifier. The constraint can be formulated as a divergence bound (e.g., KL divergence threshold) between the final sampling distribution and the verifier distribution. By varying the constraint tightness, the system trades off acceptance rate against distribution fidelity—tighter constraints mean fewer accepted tokens but higher quality, while looser constraints accelerate throughput at some quality cost. The optimization is solved efficiently without requiring expensive resampling or rejection loops.
Production Impact
For production LLM serving, this directly translates to higher token generation throughput without sacrificing output quality—critical for latency-sensitive applications like real-time chat or code generation. If deployed in a speculative decoding pipeline, you'd replace binary accept/reject logic with a learned or analytically computed acceptance probability that respects distribution constraints. This is particularly valuable for smaller model serving where draft-verifier pairs are more accessible (e.g., 7B draft + 70B verifier) and where current SpS rejection rates limit speedup. The trade-off is modest computational overhead in computing acceptance probabilities and managing constraint parameters, but this is negligible compared to the verifier's forward pass. Integration into existing systems like vLLM or TensorRT-LLM would be straightforward—the changes are in the sampling kernel between draft and verifier stages.
Limitations and When Not to Use This
The paper's formalization assumes the verifier distribution accurately represents desired output—but in practice, verifiers can encode harmful biases or outdated information that you might intentionally want to deviate from. The constraint-based approach requires choosing appropriate divergence thresholds (e.g., KL divergence tolerance), which becomes another hyperparameter to tune and may not generalize across different domains or model pairs. The paper doesn't address dynamic constraint adjustment based on observed output quality or user feedback in deployed systems. Additionally, the approach assumes draft and verifier models are fixed; it doesn't handle continual fine-tuning or model updates well, and the optimal constraints likely differ per task, requiring per-deployment tuning.
Research Context
This work builds on a line of research in efficient LLM inference starting with speculative decoding (Leviathan et al., Chen et al.) and typical acceptance sampling variants. It advances beyond heuristic-based acceptance methods by providing a principled, optimization-grounded framework applicable to any draft-verifier pair. The paper connects to broader work on distribution matching in sampling and constrained generation, touching on themes in RLHF and KL-constrained decoding. This opens research directions in adaptive constraint scheduling, multi-constraint optimization (quality + latency + energy), and theoretical analysis of the throughput-quality frontier.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::