Multi-Draft Speculative Sampling: Canonical Architectures and Theoretical Limits

• URL: http://arxiv.org/abs/2410.18234v1
• Date: Wed, 23 Oct 2024 19:28:34 GMT
• Title: Multi-Draft Speculative Sampling: Canonical Architectures and Theoretical Limits
• Authors: Ashish Khisti, M. Reza Ebrahimi, Hassan Dbouk, Arash Behboodi, Roland Memisevic, Christos Louizos,
• Abstract summary: We consider multi-draft speculative sampling, where the proposal sequences are sampled independently from different draft models. We show that the optimal scheme can be decomposed into a two-step solution.
• Score: 26.220189807865548
• License:
• Abstract: We consider multi-draft speculative sampling, where the proposal sequences are sampled independently from different draft models. At each step, a token-level draft selection scheme takes a list of valid tokens as input and produces an output token whose distribution matches that of the target model. Previous works have demonstrated that the optimal scheme (which maximizes the probability of accepting one of the input tokens) can be cast as a solution to a linear program. In this work we show that the optimal scheme can be decomposed into a two-step solution: in the first step an importance sampling (IS) type scheme is used to select one intermediate token; in the second step (single-draft) speculative sampling is applied to generate the output token. For the case of two identical draft models we further 1) establish a necessary and sufficient condition on the distributions of the target and draft models for the acceptance probability to equal one and 2) provide an explicit expression for the optimal acceptance probability. Our theoretical analysis also motives a new class of token-level selection scheme based on weighted importance sampling. Our experimental results demonstrate consistent improvements in the achievable block efficiency and token rates over baseline schemes in a number of scenarios.

Related papers

• Inferring from Logits: Exploring Best Practices for Decoding-Free Generative Candidate Selection [37.54564513506548]
  Generative Language Models rely on autoregressive decoding to produce the output sequence token by token. We introduce an evaluation of a comprehensive collection of decoding-free candidate selection approaches on a comprehensive set of tasks.
  arXiv  Detail & Related papers  (2025-01-28T23:21:28Z)
• Dynamic-Width Speculative Beam Decoding for Efficient LLM Inference [35.730941605490194]
  Large language models (LLMs) have shown outstanding performance across numerous real-world tasks. Speculative decoding has emerged as a promising solution, leveraging a smaller auxiliary model to draft future tokens. This paper explores the novel integration of speculative decoding with beam sampling.
  arXiv  Detail & Related papers  (2024-09-25T02:20:42Z)
• An incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting [53.36437745983783]
  We first construct a max-margin optimization-based model to model potentially non-monotonic preferences. We devise information amount measurement methods and question selection strategies to pinpoint the most informative alternative in each iteration. Two incremental preference elicitation-based algorithms are developed to learn potentially non-monotonic preferences.
  arXiv  Detail & Related papers  (2024-09-04T14:36:20Z)
• Graph-Structured Speculative Decoding [52.94367724136063]
  Speculative decoding has emerged as a promising technique to accelerate the inference of Large Language Models. We introduce an innovative approach utilizing a directed acyclic graph (DAG) to manage the drafted hypotheses. We observe a remarkable speedup of 1.73$times$ to 1.96$times$, significantly surpassing standard speculative decoding.
  arXiv  Detail & Related papers  (2024-07-23T06:21:24Z)
• Diffusion Forcing: Next-token Prediction Meets Full-Sequence Diffusion [61.03681839276652]
  Diffusion Forcing is a new training paradigm where a diffusion model is trained to denoise a set of tokens with independent per-token noise levels. We apply Diffusion Forcing to sequence generative modeling by training a causal next-token prediction model to generate one or several future tokens.
  arXiv  Detail & Related papers  (2024-07-01T15:43:25Z)
• Multi-Candidate Speculative Decoding [82.05519287513444]
  Large language models have shown impressive capabilities across a variety of NLP tasks, yet their generating text autoregressively is time-consuming. One way to speed them up is speculative decoding, which generates candidate segments from a fast draft model that is then verified in parallel by the target model. This paper proposes sampling multiple candidates from a draft model and then organising them in batches for verification. We design algorithms for efficient multi-candidate verification while maintaining the distribution of the target model.
  arXiv  Detail & Related papers  (2024-01-12T17:15:23Z)
• Domain Generalization via Rationale Invariance [70.32415695574555]
  This paper offers a new perspective to ease the challenge of domain generalization, which involves maintaining robust results even in unseen environments. We propose treating the element-wise contributions to the final results as the rationale for making a decision and representing the rationale for each sample as a matrix. Our experiments demonstrate that the proposed approach achieves competitive results across various datasets, despite its simplicity.
  arXiv  Detail & Related papers  (2023-08-22T03:31:40Z)
• Optimizing model-agnostic Random Subspace ensembles [5.680512932725364]
  We present a model-agnostic ensemble approach for supervised learning. The proposed approach alternates between learning an ensemble of models using a parametric version of the Random Subspace approach. We show the good performance of the proposed approach, both in terms of prediction and feature ranking, on simulated and real-world datasets.
  arXiv  Detail & Related papers  (2021-09-07T13:58:23Z)
• Online Active Model Selection for Pre-trained Classifiers [72.84853880948894]
  We design an online selective sampling approach that actively selects informative examples to label and outputs the best model with high probability at any round. Our algorithm can be used for online prediction tasks for both adversarial and streams.
  arXiv  Detail & Related papers  (2020-10-19T19:53:15Z)

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.