[2605.04263] Parallel Prefix Verification for Speculative Generation

Computer Science > Artificial Intelligence arXiv:2605.04263 (cs) [Submitted on 5 May 2026] Title:Parallel Prefix Verification for Speculative Generation Authors:Yuncheng Yao, Yuxuan Xia, Shengjie Wang, Danyang Zhuo View a PDF of the paper titled Parallel Prefix Verification for Speculative Generation, by Yuncheng Yao and 3 other authors View PDF HTML (experimental) Abstract:We introduce PARSE (PArallel pRefix Speculative Engine), a speculative generation framework that accelerates large language model (LLM) inference by parallelizing prefix verification on a semantic level. Existing speculative decoding methods are fundamentally limited by token-level equivalence: the target model must verify each token, leading to short acceptance lengths and modest speedups. Moving to semantic or segment-level verification can substantially increase acceptance granularity, but prior approaches rely on sequential verification, introducing significant overhead and limiting practical gains. PARSE introduces parallel prefix verification, enabling semantic-level verification without sequential checks. Given a full draft from a draft model, the target model evaluates correctness across multiple prefixes in a single forward pass using a custom attention mask, directly identifying the maximal valid prefix. This eliminates sequential segment verification, and makes verification compute-efficient. PARSE is orthogonal to token-level speculative decoding and can be composed with it for additional ga...