💬 NLP

MineDraft: A Framework for Batch Parallel Speculative Decoding

This paper introduces MineDraft, a novel batch parallel speculative decoding framework that significantly improves LLM inference throughput and latency by overlapping drafting and verification stages, and demonstrates its practical viability through a vLLM plugin implementation.

Original authors: Zhenwei Tang, Arun Verma, Zijian Zhou, Zhaoxuan Wu, Alok Prakash, Daniela Rus, Bryan Kian Hsiang Low

Published 2026-03-20

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zhenwei Tang, Arun Verma, Zijian Zhou, Zhaoxuan Wu, Alok Prakash, Daniela Rus, Bryan Kian Hsiang Low

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Drafting" Bottleneck

Imagine you are a famous chef (the Target Model, a huge AI) trying to write a complex story. You are very slow because you think deeply about every single word before writing it down.

To speed things up, you hire a fast, energetic sous-chef (the Draft Model, a smaller AI). The sous-chef quickly guesses the next 5 words of the story and writes them on a sticky note. You then look at the sticky note. If you agree with the guesses, you write them down instantly. If you disagree, you throw the note away and write the correct word yourself.

The Catch: In the old way of doing this (Standard Speculative Decoding), the process is strictly sequential:

The Sous-chef writes the notes (Drafting).
The Chef stops, looks at the notes, and decides (Verification).
The Sous-chef waits while the Chef thinks.
The Sous-chef writes the next set of notes.

The Sous-chef is fast, but they spend a lot of time standing around waiting for the Chef to finish checking their work. This "waiting time" is wasted energy.

The Solution: MINEDRAFT (The "Minecraft" Approach)

The authors of this paper realized: Why make the Sous-chef wait?

They created MINEDRAFT, a system that runs two "lines" of work at the same time. Think of it like a video game engine (specifically Minecraft, which inspired the name).

In Minecraft, when you walk forward, the game loads the next chunk of the world while you are still walking through the current chunk. You don't stop walking to wait for the world to load; it happens in the background.

MINEDRAFT does the same thing for AI:

Two Batches: Instead of one line of requests, MINEDRAFT splits the work into two groups: Batch A and Batch B.
The Overlap:
- While the Chef is busy checking the notes for Batch A...
- The Sous-chef is simultaneously writing the notes for Batch B.
The Swap: As soon as the Chef finishes checking Batch A, they immediately start checking the notes the Sous-chef just finished writing for Batch B. Meanwhile, the Sous-chef starts writing notes for Batch A again.

The Result: The Sous-chef never has to stand still. The "waiting time" is completely hidden because the Chef is always busy checking one batch while the Sous-chef is busy drafting the other.

Why This Matters (The Benefits)

The paper proves that this "two-batch" trick is a game-changer:

Speed Boost: Because the Sous-chef is never idle, the whole system gets much faster. The paper shows it can make the AI 75% faster (throughput) and cut the waiting time (latency) by nearly 40%.
No Magic Training: Unlike some other methods that require retraining the AI models, MINEDRAFT works with existing models. It's like adding a new conveyor belt to a factory without rebuilding the machines.
Real-World Ready: The team built this as a plugin for vLLM, a popular tool used by companies to run AI. This means it's not just a theory; it's ready to be used in production systems today.

The Trade-off (The Cost)

Is there a downside? Yes, but it's a small one.
To run this "two-batch" system, you need one extra graphics card (GPU).

Standard way: 1 GPU for the Chef, 1 GPU for the Sous-chef (but they take turns).
MINEDRAFT way: 1 GPU for the Chef, 1 GPU for the Sous-chef (working at the same time).

The paper argues that buying one extra GPU is a small price to pay to get a 75% speed boost. It's like hiring a second assistant to double your productivity.

Summary Analogy

Standard AI: A single-lane road where a fast car (Sous-chef) has to stop at a toll booth (Chef) every few seconds. The fast car sits idle while the toll booth processes the slow car.
MINEDRAFT: A two-lane highway. While the toll booth is processing cars in Lane 1, the fast cars are speeding through Lane 2. As soon as Lane 1 clears, the fast cars from Lane 2 move in, and the toll booth immediately starts processing the next batch. No one ever stops.

In short: MINEDRAFT makes AI faster by ensuring the "guessing" part and the "checking" part happen at the exact same time, using a clever two-batch system inspired by how video games load the world around you.

1. Problem Statement

Speculative Decoding (SD) is a standard technique for accelerating Large Language Model (LLM) inference. It uses a smaller, faster "draft" model to propose a sequence of tokens, which are then verified in parallel by a larger "target" model. While effective, standard SD suffers from a fundamental bottleneck: sequential execution. The drafting and verification stages occur one after another, meaning the drafting latency sits directly on the critical path of inference.

Existing attempts to parallelize SD face significant trade-offs:

Resource Intensity: Some methods require massive additional GPU memory or dedicated training stages.
Single-Request Limitation: Many parallel approaches work only for single requests and fail to scale efficiently to batched inference (multi-request scenarios).
Dependency Issues: Since verification inherently depends on draft outputs, breaking this dependency without incurring high overhead is difficult.

The core problem MINEDRAFT addresses is how to hide drafting latency in a batched inference setting without requiring excessive hardware resources or sacrificing the flexibility of existing drafting strategies.

2. Methodology: MINEDRAFT Framework

MINEDRAFT introduces a Batch Parallel Speculative Decoding (PSD) framework. Instead of processing requests sequentially, it maintains two distinct batches of requests to enable overlapping execution.

Core Mechanism: Batch Alternation

The framework operates on a simple principle: While the target model verifies the draft tokens of Batch A, the draft model generates tokens for Batch B.

Two Batches: The system maintains Batch 0 and Batch 1.
Alternating Roles: At any given step, one batch is the "Target Batch" (undergoing verification) and the other is the "Draft Batch" (undergoing drafting).
Synchronization: At the end of each step, the roles swap. The batch that was just verified becomes the new draft batch, and the batch that was just drafted becomes the new target batch.

System Architecture

The implementation, integrated as a plugin for vLLM, consists of four key components:

Batch Manager: Manages request lifecycles, assigning requests to Batch 0 or Batch 1 to maintain load balance. It handles edge cases like request termination or preemption to prevent workload imbalance.
Scheduler: A modified vLLM scheduler that handles KV block allocation. Crucially, it avoids allocating KV blocks for requests in the "Draft Batch" during the drafting phase (since they are not yet verified), preventing memory fragmentation and unnecessary allocation overhead.
Drafter: Runs on a dedicated GPU separate from the target model. It generates draft tokens for the current draft batch and communicates them directly to the verifier via GPU-to-GPU communication.
Verifier: Runs on the main GPU cluster (with tensor parallelism). It verifies the draft tokens from the previous step's draft batch.

Theoretical Efficiency

The authors provide a theoretical analysis showing that PSD is significantly more efficient than standard SD.

Latency Reduction: Under mild assumptions about the draft model's quality (modeled by a Pareto frontier), MINEDRAFT achieves at least a 37% reduction in end-to-end latency.
Ideal Case: In an idealized scenario where drafting time is perfectly hidden within verification time, the theoretical upper bound for latency reduction is 50%.

3. Key Contributions

Theoretical Analysis: Proves that parallelizing drafting and verification across batches yields substantial latency gains (minimum 37% improvement) compared to sequential SD.
Novel Framework (MINEDRAFT): Proposes a practical architecture that uses two batches to overlap drafting and verification. It requires only one additional GPU (for the draft model) compared to standard SD, making it resource-efficient.
Orthogonality: MINEDRAFT is agnostic to the specific drafting strategy. It can be combined with existing state-of-the-art methods like EAGLE, PEARL, and TETRIS to further boost performance.
Production Readiness: Implemented as a vLLM plugin, supporting continuous batching, PagedAttention, and standard production workflows.

4. Experimental Results

The authors evaluated MINEDRAFT across various model configurations (Qwen3, Llama-3, Vicuna) and datasets (ShareGPT, Arena, Spec-Bench).

Throughput Gains:
- MINEDRAFT achieved up to 75% higher throughput compared to standard SD.
- It outperformed the best existing baseline methods (like PEARL and standalone EAGLE) by an average of 38.62% to 65.02%.
Latency Reduction:
- End-to-end latency was reduced by up to 39% compared to standard SD.
- Compared to the best baseline, latency reductions reached up to 31.13%.
Memory Efficiency:
- In scenarios with large draft models (e.g., Qwen3-8B), standard SD often fails due to VRAM contention (both models on the same GPU). MINEDRAFT's separation of draft and target models onto different GPUs eliminates this bottleneck, allowing larger models to be used effectively.
Scalability:
- Performance scales well with batch size ( $m$ ).
- The framework remains effective even when integrated with adaptive drafting strategies (like TETRIS), overcoming limitations where excessive drafting usually degrades performance.

5. Significance and Impact

Bridging the Gap: MINEDRAFT successfully bridges the gap between theoretical parallelism and practical, production-ready LLM serving. It demonstrates that significant speedups are possible without the massive hardware overheads of previous parallel approaches.
Resource Optimization: By utilizing a single extra GPU to hide latency, it offers a high return on investment for inference clusters.
Ecosystem Integration: As a vLLM plugin, it lowers the barrier to entry for researchers and engineers to adopt parallel speculative decoding, encouraging further optimization in the LLM serving ecosystem.
Future Directions: The paper highlights that while the current design requires an extra GPU, future work could explore weight-padding techniques to potentially eliminate this hardware requirement, further democratizing the technology.

In summary, MINEDRAFT represents a paradigm shift in speculative decoding, moving from sequential processing to batch-level parallelism, effectively hiding drafting latency and significantly accelerating LLM inference in production environments.