title: Multi-Draft Speculative Sampling: Canonical Architectures and
    Theoretical Limits
summary: 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.
paper_authors._id: 671b167d45299f98b47daf84
paper_authors.name: Ashish Khisti
paper_authors._id: 671b167d45299f98b47daf85
paper_authors.name: M. Reza Ebrahimi
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-10-25T09:29:01.320Z
paper_authors._id: 648a1075e8bee5332919e0ab
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/648a1075e8bee5332919e0ab/KDzi904zGPuy_PL3gbUYE.jpeg
paper_authors.fullname: M.Reza Ebrahimi
paper_authors.type: user
paper_authors.user: mamaj92
paper_authors._id: 671b167d45299f98b47daf86
paper_authors.name: Hassan Dbouk
paper_authors._id: 671b167d45299f98b47daf87
paper_authors.name: Arash Behboodi
paper_authors._id: 671b167d45299f98b47daf88
paper_authors.name: Roland Memisevic
paper_authors._id: 671b167d45299f98b47daf89
paper_authors.name: Christos Louizos
paper_title: Multi-Draft Speculative Sampling: Canonical Architectures and
    Theoretical Limits
paper_summary: 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.
paper_ai_summary: A two-step solution for token-level speculative sampling improves efficiency and token rates by decomposing optimal selection into importance sampling and single-draft sampling.
paper_ai_keywords: multi-draft speculative sampling token-level draft selection linear program importance sampling block efficiency token rates weighted importance sampling