🤖 machine learning

Faster LLM Inference via Sequential Monte Carlo

This paper introduces Sequential Monte Carlo Speculative Decoding (SMC-SD), a novel inference method that replaces token-level rejection with importance-weighted resampling over draft particles to achieve significant speedups (up to 5.2x over autoregressive decoding) while maintaining high accuracy by leveraging idle compute for vectorized verification.

Original authors: Yahya Emara, Mauricio Barba da Costa, Chi-Chih Chang, Cameron Freer, Tim Vieira, Ryan Cotterell, Mohamed S. Abdelfattah

Published 2026-04-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yahya Emara, Mauricio Barba da Costa, Chi-Chih Chang, Cameron Freer, Tim Vieira, Ryan Cotterell, Mohamed S. Abdelfattah

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

Imagine you are trying to write a long, complex story with a very famous, brilliant, but slow-witted editor (the Target Model). You want the story to be perfect, but the editor takes a long time to read and approve every single word you write.

The Old Way: The "Stop-and-Check" Game

Currently, most AI systems use a method called Speculative Decoding. Here's how it works:

You hire a fast, cheap intern (the Draft Model) to quickly write a few sentences ahead of time.
The intern writes a block of 5 words.
The brilliant editor reads those 5 words.
- If the editor likes the first word, great!
- If the editor likes the first and second word, great!
- But, if the editor dislikes the third word, they stop immediately. They throw away the 3rd, 4th, and 5th words the intern wrote.
- The editor then has to start over, writing the 3rd word themselves.

The Problem: If the intern and the editor disagree often, the editor spends most of their time throwing away the intern's work. It's like a relay race where the runner keeps dropping the baton, forcing the next runner to stop and pick it up. This wastes a lot of time.

The New Way: The "Voting Party" (SMC-SD)

This paper introduces a new method called Sequential Monte Carlo Speculative Decoding (SMC-SD). Instead of relying on just one intern and one "stop-and-check" rule, they use a team of interns and a voting system.

Here is the analogy:

1. The Team of Interns (Particles)

Instead of one intern, you hire 8 interns (called "particles"). They all start with the same story so far.

2. The Drafting Phase

All 8 interns work in parallel. Each one quickly writes the next 4 words of the story.

Intern A writes: "The cat sat on the..."
Intern B writes: "The dog ran to the..."
Intern C writes: "The cat sat on the..."
...and so on.

3. The Scoring Phase (No Throwing Away!)

The brilliant editor (Target Model) looks at all 8 versions of the story at once.

In the old way, if the editor hated the 3rd word of Intern A, they would throw away Intern A's whole block.
In this new way, the editor scores every single word from every intern.
- "Intern A's 3rd word is okay, but not great. Score: 0.5."
- "Intern B's 3rd word is perfect! Score: 1.0."
- "Intern C's 3rd word is terrible. Score: 0.0."

4. The Resampling Phase (The Magic Trick)

This is the most important part. Instead of deleting the "bad" interns, the system rearranges the team.

The interns who wrote good words (high scores) get duplicated. Now you have two copies of Intern B.
The interns who wrote bad words (low scores) get fired (evicted).
The system takes the "fired" slots and fills them with copies of the "winners."

The Result: In the next round, you have 8 interns, but 6 of them are now working on the path that the editor liked best. You never wasted the time of the editor checking a word that turned out to be wrong; you just used the editor's time to figure out which path was best, and then you doubled down on that path.

Why is this faster?

Think of the editor's brain as a highway.

The Old Way: The highway is often empty because the editor keeps stopping to throw away bad drafts. The "traffic" (computation) is low.
The New Way: The highway is always full. The editor is constantly processing 8 different paths at once. Even if some paths are bad, the "traffic" keeps moving because the system instantly swaps the bad cars for good ones without stopping the engine.

The "Free Lunch"

The paper points out a funny thing about modern computer chips (GPUs). They are incredibly fast at math, but they are often waiting for data to arrive from memory (like a chef waiting for ingredients).

The old method didn't use enough math power to keep the chef busy.
The new method (SMC-SD) uses that "waiting time" to do extra math on the 8 interns. It turns "idle time" into "speed."

The Bottom Line

Accuracy: The new method is almost as smart as the old, perfect method (within 3% accuracy).
Speed: It is 2.36 times faster than the best existing fast methods, and 5.2 times faster than the standard slow method.
The Metaphor: Instead of playing "Guess Who?" where you eliminate one person at a time, you are playing a game where you instantly clone the winners and eliminate the losers, keeping the game moving at lightning speed.

This technique allows AI to write stories, solve math problems, and code much faster without losing its intelligence.

1. Problem Statement

Autoregressive generation in Large Language Models (LLMs) is inherently sequential, creating a bottleneck where each token depends on all previous tokens, requiring serial forward passes. Speculative Decoding (SD) attempts to solve this by using a small, cheap "draft" model to propose $K$ tokens, which are then verified by the large "target" model in a single forward pass.

However, standard SD relies on rejection sampling: if the target model rejects the first draft token, the entire draft block is truncated, and the remaining tokens are discarded. This leads to significant throughput degradation when the draft and target models diverge (low acceptance rates). Furthermore, the verification step in SD is often memory-bandwidth bound, leaving significant GPU compute resources idle.

2. Methodology: Sequential Monte Carlo Speculative Decoding (SMC-SD)

The authors propose SMC-SD, a principled approximate inference scheme that replaces token-level rejection with importance-weighted resampling over a population of draft particles.

Core Mechanism

Instead of maintaining a single draft sequence, SMC-SD maintains a population of $N$ candidate sequences (particles). Each round proceeds as follows:

Drafting (Extend): The draft model $q$ extends all $N$ particles in parallel, generating $K$ new tokens for each particle.
Scoring (Reweight): The target model $p$ scores all $N$ sequences (totaling $N \times K$ tokens) in a single batched forward pass and generates a "bonus" token for each.
Resampling: Instead of rejecting a sequence, the algorithm calculates importance weights based on the ratio of target to draft probabilities. If the Effective Sample Size (ESS) drops below a threshold, low-weight particles are pruned, and high-weight particles are duplicated (resampled).
Output: The process repeats until the desired length is reached. The final output is sampled from the terminal particle population based on their normalized weights.

Key Differences from Standard SD

No Truncation: In standard SD, a single rejection truncates the block. In SMC-SD, every particle is extended by exactly $K$ tokens per round; "errors" are handled by lowering the particle's weight, not discarding the sequence.
Vectorization: The verification step becomes a fixed-size, vectorized operation ( $N \times (K+1)$ tokens), eliminating the variable-length rollback logic of standard SD.
Approximation vs. Exactness: SMC-SD trades exact sampling for speed. It provides asymptotic convergence guarantees and non-asymptotic error bounds, whereas standard SD guarantees exactness but suffers stochastic speedups.

3. Key Contributions

A. Theoretical Analysis

Speed-up Modeling: Using the Roofline Model, the authors derive closed-form expressions for the tokens-per-second (TPS) speed-up.
- In the memory-bound regime (typical for LLMs), the speed-up is $S \approx \frac{K+1}{\rho K + 1}$ , where $\rho$ is the draft-to-target parameter ratio. Crucially, adding particles ( $N$ ) is "free" in this regime because the target weights are loaded only once per batch.
- In the compute-bound regime, speed-up degrades linearly with batch size, but the method still outperforms autoregressive decoding.
Error Bounds: The paper establishes non-asymptotic bounds on approximation error. The $L_2$ bias and Mean Squared Error (MSE) decay as $O(1/N)$ , and the $L_1$ bias decays as $O(1/\sqrt{N})$ , governed by the $\chi^2$ -divergence between the draft and target models.

B. Systems Engineering

High-Throughput Engine: The authors built a custom inference engine (forked from SGLang) optimized for SMC-SD.
Pointer-Based Resampling: To avoid the high cost of copying KV-cache data during resampling, the engine exploits prefix sharing. When a particle is duplicated, the engine performs an $O(\ell_{seq})$ page-metadata copy (incrementing reference counts) rather than an $O(\ell_{seq} \times d_{model})$ tensor copy. This reduced KV-cache usage by 72.3% in experiments.
Arithmetic Intensity: By processing $N$ particles in parallel, SMC-SD significantly increases arithmetic intensity, better utilizing modern GPU compute capabilities that are often underutilized by memory-bound autoregressive decoding.

C. Generalization

The framework is not limited to standard decoding. It can sample from unnormalized distributions, enabling:

Power Sampling: Sampling from $p(x)^\alpha$ (tempering over entire sequences rather than per-token).
Constrained Generation: Enforcing hard constraints (syntax, format) without retraining.
Reward-Weighted Decoding: Steering models toward reward functions (RLHF) without fine-tuning.

4. Experimental Results

The authors evaluated SMC-SD on GSM8K, MATH500, AlpacaEval, and DS1000 using Llama and Qwen model families.

Throughput Gains:
- vs. Autoregressive (AR): Up to 5.2× speed-up in multi-GPU settings.
- vs. Optimized Speculative Decoding (SD): 2.36× speed-up over state-of-the-art tree-based SD (SGLang) and 2.5× over standard SD on single-GPU benchmarks.
- Robustness: Unlike standard SD, whose throughput collapses as the draft-target acceptance rate drops (e.g., at higher temperatures), SMC-SD maintains near-constant throughput because it always produces $K+1$ tokens per round.
Accuracy:
- SMC-SD remains within 3% of the target model's accuracy on reasoning, instruction-following, and coding benchmarks.
- On the Pareto frontier (Speed vs. Accuracy), SMC-SD configurations consistently dominate standard SD, offering higher throughput for the same accuracy or higher accuracy for the same throughput.
Power Sampling: In a specific application, power sampling with SMC-SD improved Pass@1 accuracy by 10% on MATH500 compared to the baseline target model.

5. Significance and Future Outlook

Paradigm Shift: SMC-SD shifts the paradigm from "exact rejection" to "approximate resampling," turning the verification step into a fixed-size, vectorized operation that aligns perfectly with modern GPU hardware.
Hardware Co-Design: The method is particularly well-suited for next-generation architectures (e.g., NVIDIA Blackwell) where compute capacity is growing faster than memory bandwidth. SMC-SD leverages this excess compute to turn idle cycles into speed.
Versatility: By decoupling the sampling mechanism from the exactness requirement, SMC-SD opens new avenues for constrained generation and distributional steering without the need for additional training or complex rejection logic.

In summary, SMC-SD offers a theoretically grounded, systems-optimized approach to LLM inference that significantly accelerates generation while maintaining high fidelity, effectively solving the throughput bottlenecks inherent in both autoregressive and standard speculative decoding methods.