title: Towards Optimal Multi-draft Speculative Decoding
summary: Large Language Models (LLMs) have become an indispensable part of natural
  language processing tasks. However, autoregressive sampling has become an
  efficiency bottleneck. Multi-Draft Speculative Decoding (MDSD) is a recent
  approach where, when generating each token, a small draft model generates
  multiple drafts, and the target LLM verifies them in parallel, ensuring that
  the final output conforms to the target model distribution. The two main design
  choices in MDSD are the draft sampling method and the verification algorithm.
  For a fixed draft sampling method, the optimal acceptance rate is a solution to
  an optimal transport problem, but the complexity of this problem makes it
  difficult to solve for the optimal acceptance rate and measure the gap between
  existing verification algorithms and the theoretical upper bound. This paper
  discusses the dual of the optimal transport problem, providing a way to
  efficiently compute the optimal acceptance rate. For the first time, we measure
  the theoretical upper bound of MDSD efficiency for vocabulary sizes in the
  thousands and quantify the gap between existing verification algorithms and
  this bound. We also compare different draft sampling methods based on their
  optimal acceptance rates. Our results show that the draft sampling method
  strongly influences the optimal acceptance rate, with sampling without
  replacement outperforming sampling with replacement. Additionally, existing
  verification algorithms do not reach the theoretical upper bound for both
  without replacement and with replacement sampling. Our findings suggest that
  carefully designed draft sampling methods can potentially improve the optimal
  acceptance rate and enable the development of verification algorithms that
  closely match the theoretical upper bound.
paper_authors._id: 67c0b4d0cda310c08781e820
paper_authors.name: Zhengmian Hu
paper_authors._id: 67c0b4d0cda310c08781e821
paper_authors.name: Tong Zheng
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2025-02-27T22:08:55.900Z
paper_authors._id: 6623ea65b642e29cdf90a1b4
paper_authors.avatarUrl: /avatars/e32e90574c1162b2be87ed78604e3e4d.svg
paper_authors.fullname: TongZheng
paper_authors.type: user
paper_authors.user: TongZheng1999
paper_authors._id: 67c0b4d0cda310c08781e822
paper_authors.name: Vignesh Viswanathan
paper_authors._id: 67c0b4d0cda310c08781e823
paper_authors.name: Ziyi Chen
paper_authors._id: 67c0b4d0cda310c08781e824
paper_authors.name: Ryan A. Rossi
paper_authors._id: 67c0b4d0cda310c08781e825
paper_authors.name: Yihan Wu
paper_authors._id: 67c0b4d0cda310c08781e826
paper_authors.name: Dinesh Manocha
paper_authors._id: 67c0b4d0cda310c08781e827
paper_authors.name: Heng Huang
paper_title: Towards Optimal Multi-draft Speculative Decoding
paper_summary: Large Language Models (LLMs) have become an indispensable part of natural
  language processing tasks. However, autoregressive sampling has become an
  efficiency bottleneck. Multi-Draft Speculative Decoding (MDSD) is a recent
  approach where, when generating each token, a small draft model generates
  multiple drafts, and the target LLM verifies them in parallel, ensuring that
  the final output conforms to the target model distribution. The two main design
  choices in MDSD are the draft sampling method and the verification algorithm.
  For a fixed draft sampling method, the optimal acceptance rate is a solution to
  an optimal transport problem, but the complexity of this problem makes it
  difficult to solve for the optimal acceptance rate and measure the gap between
  existing verification algorithms and the theoretical upper bound. This paper
  discusses the dual of the optimal transport problem, providing a way to
  efficiently compute the optimal acceptance rate. For the first time, we measure
  the theoretical upper bound of MDSD efficiency for vocabulary sizes in the
  thousands and quantify the gap between existing verification algorithms and
  this bound. We also compare different draft sampling methods based on their
  optimal acceptance rates. Our results show that the draft sampling method
  strongly influences the optimal acceptance rate, with sampling without
  replacement outperforming sampling with replacement. Additionally, existing
  verification algorithms do not reach the theoretical upper bound for both
  without replacement and with replacement sampling. Our findings suggest that
  carefully designed draft sampling methods can potentially improve the optimal
  acceptance rate and enable the development of verification algorithms that
  closely match the theoretical upper bound.
paper_ai_summary: MDSD improves LLM efficiency by generating drafts with a small model and verifying them with a target model, optimizing the acceptance rate to minimize the gap between existing and theoretical upper bounds.
paper_ai_keywords: autoregressive sampling Multi-Draft Speculative Decoding draft model target LLM draft sampling method verification algorithm optimal transport problem optimal acceptance rate theoretical upper bound sampling without replacement sampling with replacement