Paper

{
  "raw_xml": "<entry>\n    <id>http://arxiv.org/abs/2602.16961v1</id>\n    <title>Greedy Multi-Path Block Verification for Faster Decoding in Speculative Sampling</title>\n    <updated>2026-02-18T23:55:01Z</updated>\n    <link href='https://arxiv.org/abs/2602.16961v1' rel='alternate' type='text/html'/>\n    <link href='https://arxiv.org/pdf/2602.16961v1' rel='related' title='pdf' type='application/pdf'/>\n    <summary>The goal of $L$-step speculative decoding is to accelerate autoregressive decoding of a target model by using a cheaper draft model to generate a candidate path of $L$ tokens. Based on a verification algorithm involving target and draft model probabilities, a prefix of the candidate sequence is accepted, and an additional correction token is sampled from a residual distribution to ensure that the final output adheres to the target distribution. While standard speculative decoding uses a verification algorithm which is independent at each token on the path, a recent extension called block verification uses a joint condition involving all sampled on-path probabilities. Block verification (BV) was shown to be optimal over all verification algorithms which use only on-path probabilities, improving on standard speculative decoding. In this work, we first show that block verification is optimal even over verification algorithms that use off-path probabilities, by constructing an information-agnostic linear program (LP). Further, we can extend our LP to the setting where the draft model samples multiple candidate paths, and use it to construct a natural class of multi-path block verification generalizations. While computing the optimal algorithm in this class is not tractable, by considering a stricter class of greedy algorithms, we can formulate an efficient method called greedy multi-path block verification (GBV). Empirically, GBV can improve block efficiency by over 30% and reduce decoding walltimes by over 15% relative to BV. On Llama-3 70B, GBV can improve the end-to-end decoding throughput over SOTA multi-path verification methods by more than 15%.</summary>\n    <category scheme='http://arxiv.org/schemas/atom' term='cs.IT'/>\n    <category scheme='http://arxiv.org/schemas/atom' term='cs.LG'/>\n    <published>2026-02-18T23:55:01Z</published>\n    <arxiv:primary_category term='cs.IT'/>\n    <author>\n      <name>Rahul Thomas</name>\n    </author>\n    <author>\n      <name>Arka Pal</name>\n    </author>\n  </entry>"
}