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

• URL: http://arxiv.org/abs/2604.04987v1
• Date: Sun, 05 Apr 2026 03:37:30 GMT
• Title: Cactus: Accelerating Auto-Regressive Decoding with Constrained Acceptance Speculative Sampling
• Abstract summary: Speculative sampling (SpS) has been successful in accelerating the decoding throughput of auto-regressive large language models.<n>We propose Cactus (constrained acceptance speculative sampling), a method that guarantees controlled divergence from the verifier distribution.
• Score: 29.45621080100186
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• ResiSpec: Enhancing Multi-Candidate Speculative Sampling via Residual Distribution Shaping [79.1905186547363]
  ResiSpec is a framework that strategically reforms the proposal distribution during verification.<n>It prevents candidate obsolescence and achieves up to 1.92$times$ speedup over state-of-the-art multi-candidate methods.
  arXiv  Detail & Related papers  (2026-08-25T11:25:55Z)
• Revisiting Lossy Verification in Speculative Decoding: Mechanisms, Trade-offs, and Failure Modes [19.68865985432786]
  We present a principled analysis of the distributions induced by lossy verification methods.<n>We show that many seemingly distinct approaches differ only superficially and can be classified into two categories: truncation-based verification and collaborative verification.
  arXiv  Detail & Related papers  (2026-07-29T08:54:27Z)
• Accelerating Speculative Diffusions via Block Verification [77.23389794645801]
  Speculative decoding speeds up LLM inference by using a draft model to generate tokens, with an acceptance-rejection scheme.<n>Existing diffusion adaptations either use inefficient sampling techniques or rely on an alternative scheme.<n>We introduce a novel scheme that efficiently implements the original speculative sampling mechanism for diffusion models.
  arXiv  Detail & Related papers  (2026-06-11T14:54:13Z)
• Pliable rejection sampling [61.01438712621603]
  We present pliable rejection sampling (PRS), a new approach to rejection sampling.<n>PRS builds on rejection sampling and comes with a guarantee on the number of accepted samples.
  arXiv  Detail & Related papers  (2026-04-24T09:21:53Z)
• Locally Confident, Globally Stuck: The Quality-Exploration Dilemma in Diffusion Language Models [52.61023005303122]
  We show that low-confidence remasking improves a proxy for quality while constraining the entropy of the induced sequence distribution.<n>We develop a simple Independent--Hastings sampler that approximately targets this distribution during decoding.
  arXiv  Detail & Related papers  (2026-04-01T02:01:30Z)
• Training-free Dropout Sampling for Semantic Token Acceptance in Speculative Decoding [13.249778063956917]
  Speculative decoding accelerates large language model inference by proposing tokens with a lightweight draft model.<n>This work introduces DropMatch, a novel approach that matches draft tokens to the predictive distribution of the target model.<n> Experiments across multiple benchmarks demonstrate that our approach increases acceptance length while maintaining competitive task performance.
  arXiv  Detail & Related papers  (2026-02-11T04:53:33Z)
• Learnable Chernoff Baselines for Inference-Time Alignment [64.81256817158851]
  We introduce Learnable Chernoff Baselines as a method for efficiently and approximately sampling from exponentially tilted kernels.<n>We establish total-variation guarantees to the ideal aligned model, and demonstrate in both continuous and discrete diffusion settings that LCB sampling closely matches ideal rejection sampling.
  arXiv  Detail & Related papers  (2026-02-08T00:09:40Z)
• Efficient Adaptive Rejection Sampling for Accelerating Speculative Decoding in Large Language Models [2.4065240342323384]
  This paper introduces Efficient Adaptive Rejection Sampling (EARS)<n>EARS dynamically adjusts the acceptance threshold by incorporating the target model's own predictive uncertainty, measured as 1 - max(P_target)<n>It significantly enhances the efficiency of speculative decoding, achieving up to an 18.12% increase in throughput with a negligible 0.84% accuracy drop on the GSM8K benchmark.
  arXiv  Detail & Related papers  (2025-12-15T11:08:56Z)
• Constrained Adaptive Rejection Sampling [27.579645342312674]
  Language Models (LMs) are increasingly used in applications where generated outputs must satisfy strict semantic or syntactic constraints.<n>Existing approaches to constrained generation fall along a spectrum: greedy constrained decoding methods enforce validity during decoding but distort the LM's distribution.<n>We present Constrained Adaptive Rejection Sampling (CARS), an approach that strictly improves the sample-efficiency of RS without distributional distortion.
  arXiv  Detail & Related papers  (2025-10-02T11:17:26Z)
• Towards Optimal Multi-draft Speculative Decoding [102.67837141152232]
  Multi-Draft Speculative Decoding (MDSD) is a recent approach where, when generating each token, a small draft model generates multiple drafts.<n>This paper discusses the dual of the optimal transport problem, providing a way to efficiently compute the optimal acceptance rate.
  arXiv  Detail & Related papers  (2025-02-26T03:22:44Z)
• Conditional Sampling of Variational Autoencoders via Iterated Approximate Ancestral Sampling [7.357511266926065]
  Conditional sampling of variational autoencoders (VAEs) is needed in various applications, such as missing data imputation, but is computationally intractable. A principled choice forally exact conditional sampling is Metropolis-within-Gibbs (MWG)
  arXiv  Detail & Related papers  (2023-08-17T16:08:18Z)
• Preconditioned Score-based Generative Models [45.66744783988319]
  An intuitive acceleration method is to reduce the sampling iterations which however causes severe performance degradation.<n>We propose a novel preconditioned diffusion sampling (PDS) method that leverages matrix preconditioning to alleviate the aforementioned problem.<n>PDS preserves the output distribution of the SGM, with no risk of inducing systematical bias to the original sampling process.
  arXiv  Detail & Related papers  (2023-02-13T16:30:53Z)
• DensePure: Understanding Diffusion Models towards Adversarial Robustness [110.84015494617528]
  We analyze the properties of diffusion models and establish the conditions under which they can enhance certified robustness. We propose a new method DensePure, designed to improve the certified robustness of a pretrained model (i.e. a classifier) We show that this robust region is a union of multiple convex sets, and is potentially much larger than the robust regions identified in previous works.
  arXiv  Detail & Related papers  (2022-11-01T08:18:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.