Research map / Probabilistic and scientific modeling / Variational and generative sampling
Parallelizing MCMC Across the Sequence Length
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.
Parallelizes MCMC samplers (Gibbs, MALA, HMC) across the chain length by solving the sampling recursion with parallel Newton (DEER/quasi-DEER) methods, plus stochastic and block quasi-DEER variants.
Problem
Standard MCMC is inherently sequential, so its time scales linearly with chain length; prior hardware acceleration has only parallelized across independent chains.
Approach
Cast MCMC transitions as a nonlinear recursion and solve the whole state trajectory as a fixed point with parallel-in-time Newton iterations (DEER), using stochastic Hutchinson diagonal estimates and block quasi-DEER to reduce memory and compute, and early-stopping for approximate samples.
Key results
- Parallel MALA achieved speedups of up to 20-30x over sequential MALA for smaller batch sizes on the German Credit BLR posterior, with MMD comparable to sequential sampling.
- Parallel evaluation of 100K HMC samples on the Rosenbrock distribution converged to the sequential trace in 147 parallel iterations.
- On IMDB LLM-embedding sentiment classification, parallel MALA with a 256 sliding window achieved over 3x faster wall-clock time than sequential MALA.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Parallelize Gibbs sampling across chain length | Gibbs sampling · Eight schools | wall-clock time: approximately $2\times$ faster | Helped |
| Parallelize MALA across chain length | MALA · German Credit Dataset | wall-clock time: up to 20 or 30 times | Helped |
| Parallelize MALA across chain length at batch size 32 | MALA · German Credit Dataset | wall-clock time | Hurt |
| Parallelize MALA across chain length | MALA · German Credit Dataset | MMD | No clear effect |
| Parallelize HMC leapfrog integration | HMC · German Credit Dataset | ESS/s | Mixed |
| Parallelize HMC across the sequence rather than only leapfrog integration | HMC · German Credit Dataset | ESS/s | Helped |
| Estimate the Jacobian diagonal stochastically instead of using automatic differentiation (ablation) | Quasi-DEER for MALA · German Credit Dataset | wall-clock time: over $10\times$ faster | Helped |
| Use block quasi-DEER to retain position-momentum interactions (ablation) | Quasi-DEER for parallel leapfrog · German Credit Dataset | Newton iterations to convergence: $ approx 2\times$ | Helped |
| Stop parallel MALA after 8 Newton iterations (ablation) | Parallel MALA · German Credit Dataset | MMD: nearly an order of magnitude faster runtime | No clear effect |
| Use sliding-window updates with window size 256 (ablation) | Parallel MALA · IMDB embeddings sentiment classification | wall-clock time: over $3\times$ faster | Helped |
| Run parallel MALA with batch size 32 | Parallel MALA · German Credit Dataset | wall-clock time | Hurt |
Surprising findings
- For batch size B=32, parallel MALA was slower than sequential MALA because the GPU was saturated.
- Interpolated parallel MALA (running several smaller parallel batches sequentially) can beat a single larger batch in wall-clock time at equal sample quality.
Limitations
- Convergence of Newton's method varies with step size, target geometry, and hyperparameters; highly multimodal targets may be unstable.
- Parallel MCMC trades extra memory and computation for lower time complexity, which may be unfavorable for high-memory targets.
- Early-stopped sample quality is problem-dependent and the optimal number of early-stopping iterations is not characterized.
Experimental setup
Datasets: German Credit dataset Eight schools IMDB reviews Rosenbrock distribution item-response theory dataset
Benchmarks: German Credit BLR posterior eight schools Gibbs posterior IMDB sentiment BLR
Metrics: wall-clock time number of Newton iterations MMD ESS per second speedup multiplier
Baselines: sequential MALA sequential HMC sequential Gibbs sampling NUTS quasi-DEER with automatic differentiation
Builds on: DEER quasi-DEER DeepPCR parallel associative scan Hutchinson diagonal estimator
Closest papers by meaning
- Pseudo-Extended Markov chain Monte Carlo (NeurIPS 2019 · similarity 0.89)
- Accelerated Parallel Tempering via Neural Transports (ICLR 2026 · similarity 0.89)
- Involutive MCMC: a Unifying Framework (ICML 2020 · similarity 0.89)
- Metropolis Adjusted Microcanonical Hamiltonian Monte Carlo (NeurIPS 2025 · similarity 0.88)
- AutoStep: Locally adaptive involutive MCMC (ICML 2025 · similarity 0.86)
- Multi-Marginal Couplings for Metropolis--Hastings (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.