Research map / Learning theory and algorithms / Optimal transport

UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding

NeurIPS 2026 · Learning theory and algorithms › Optimal transport · approach: Neural optimal transport · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes UniVer, a lossless tree-based speculative decoding verifier that frames multi-step, multi-draft verification as a conditional optimal transport problem, improving acceptance length 4.2%-8.5% over recursive rejection sampling without replacement.

Problem

Verification in tree-structured speculative decoding handles horizontal (multi-draft) and vertical (multi-step) dimensions in isolation, leaving their joint optimization poorly addressed.

Approach

Abstracts vertical dependencies as prefix acceptance probabilities that scale the target distribution at each node, so each layer's draft selection becomes a conditional OT problem solved in parallel top-down, followed by a post-order decision traversal; it builds on Greedy multi-draft OT and generalizes it to trees while remaining lossless.

Key results

• On Vicuna-7B-v1.3 (binary tree depth 5, temp 1.0), UniVer reaches avg acceptance length 3.29 vs 3.06 for vanilla RRSw (+7.5%) and 3.21 for Greedy.
• On Llama3.1-8B-Instruct, UniVer improves acceptance length by 8.5% over RRSw (2.95 vs 2.72).
• Gains shrink at low temperature: at temperature 0.3 all OT and RRSw variants are near-identical (~3.39 on binary depth-5 tree).

Surprising findings

• At temperature 0 and near it, UniVer gives no gain over other verification methods, since differences only appear at temperature above zero.

Limitations

• No extra gain at or near temperature 0.
• Relies on a specific mixed sampling strategy (Top-(m-1) plus one residual sample) to derive the OT-based verification.
• Gains vary with tree topology, smaller on EAGLE tree (4.2%).

Experimental setup

Datasets: Spec-Bench

Benchmarks: Spec-Bench

Metrics: acceptance length tokens per second

Baselines: RRSw Traversal Verification Greedy method

Builds on: Greedy multi-draft OT RRSw Traversal Verification Block Verification EAGLE

Closest papers by meaning

• TreeGraft: Adaptive Multi-Drafter Grafting for Tree-Based Speculative Decoding (NeurIPS 2026 · similarity 0.93)
• Traversal Verification for Speculative Tree Decoding (NeurIPS 2025 · similarity 0.92)
• Towards Optimal Multi-draft Speculative Decoding (ICLR 2025 · similarity 0.92)
• BASTION: Budget-Aware Speculative Decoding with Tree-structured Block Diffusion Drafting (NeurIPS 2026 · similarity 0.91)
• Bridging Draft Policy Misalignment: Group Tree Optimization for Speculative Decoding (ICLR 2026 · similarity 0.91)
• PEARL: Parallel Speculative Decoding with Adaptive Draft Length (ICLR 2025 · similarity 0.90)