Parallel Candidate Evaluation for Sequential Sampling

15 concepts10 papers1 proposal

Markov Chain Monte Carlo (MCMC) and related particle-sampling frameworks are the gold standard for exploring complex, high-dimensional probability landscapes. However, they suffer from a fundamental computational bottleneck: they are inherently sequential. To compute the next state of a Markov chain ($X_{t+1}$), one must typically know its current state ($X_t$). In an era dominated by modern hardware accelerators like GPUs and multi-core CPUs—which favor massive parallel workloads over single-threaded clock speed—this sequential dependency leaves substantial computational power unutilized.

To overcome this limitation, a powerful paradigm has emerged: parallel candidate evaluation. The core insight is that while the final accepted path of a sampler must remain sequential to preserve its statistical properties, the exploration of the surrounding state space can be performed concurrently. By evaluating multiple candidate steps, future branches, or entire trajectory segments at the same time, researchers can trade abundant parallel compute for scarce wall-clock time without sacrificing mathematical exactness.

Widening the Search: Multi-Proposal Neighborhood Exploration

The most direct way to parallelize a sequential sampler is to look broadly at the immediate neighborhood of the current state. Instead of generating a single proposal and deciding whether to accept it, a sampler can evaluate a large batch of candidate moves simultaneously across multiple processing cores.

Sequential MCMC:  [Current State] ---> [Single Proposal] (Accept/Reject)

Multi-Proposal:                        /---> [Proposal 1] ---\
                  [Current State] ----+----> [Proposal 2] ----+---> (Select Weighted Winner)
                                       \---> [Proposal 3] ---/

This approach is exemplified by the Multiple-try Metropolis (MTM) framework. As demonstrated by Hyunwoong Chang et al. in Rapidly Mixing Multiple-try Metropolis Algorithms for Model Selection Problems, generating a set of candidate moves in parallel and selecting a transition based on a locally balanced weight function allows the chain to explore larger neighborhoods aggressively. Although evaluating multiple proposals increases the raw computational cost per step, the independent nature of these calculations means they can be distributed across processors, resulting in a theoretical mixing rate that can be $N$ times faster than standard Metropolis-Hastings.

This strategy is highly effective across diverse domains:

  • Discrete Spaces & Combinatorial Optimization: In high-dimensional discrete spaces, sequential single-variable updates suffer from severe latency bottlenecks. To circumvent this, Haoran Sun et al. developed a high-throughput discrete sampling method in Revisiting Sampling for Combinatorial Optimization that proposes updates to multiple dimensions of a state simultaneously, leveraging hardware accelerators to perform parallel neighborhood exploration.
  • Structure and Tree Search: When sampling complex structural models like decision trees, Efthyvoulos Drousiotis and Paul G. Spirakis showed in Single MCMC chain parallelisation on decision trees that calculating acceptance probabilities for several potential tree modifications concurrently accelerates state-space exploration up to 18x while strictly maintaining the underlying model's predictive performance and uncertainty measures.
  • Multi-Agent Pathfinding: In robotics and logistics, Keisuke Okumura demonstrated in Engineering LaCAM*: Towards Real-Time, Large-Scale, and Near-Optimal Multi-Agent Pathfinding that parallel Monte-Carlo sampling can evaluate multiple potential successor states simultaneously to identify optimal transitions for thousands of agents in real time.

Deepening the Search: Speculative Execution and Prefetching

Instead of just looking wider, parallel compute can also be used to look deeper into the future. This technique, known as speculative execution or predictive prefetching, treats the future steps of an MCMC chain as a branching decision tree.

When a chain is at state $X_t$, it will either accept a proposal and move to $X_{t+1}$, or reject it and remain at $X_t$. While one processor core evaluates the acceptance criteria for $X_{t+1}$, idle background processors can speculatively pre-compute the subsequent proposals for both potential outcomes.

                           /---> [Evaluate Step t+2 given Step t+1 Accepted]
                          /
[Evaluate Step t+1] -----+
                          \
                           \---> [Evaluate Step t+2 given Step t+1 Rejected]

In Accelerating MCMC via Parallel Predictive Prefetching, Elaine Angelino et al. formalized this framework. By utilizing fast approximations and predictive scheduling to guess which paths are most likely to be taken, the system schedules speculative evaluations on available cores. Once the true outcome of step $X_t$ is finalized, the system selects the pre-computed branch corresponding to the actual outcome and discards the unchosen path.

As surveyed by Elaine Angelino et al. in Patterns of Scalable Bayesian Inference, this speculative strategy yields parallel speedups that scale logarithmically with the number of processors. It effectively compresses wall-clock time by utilizing idle hardware to guess the chain's trajectory in advance, all while preserving the exact mathematical trajectory of the original sequential algorithm.

Trajectory Parallelism and Population Dynamics

Beyond multi-proposal steps and speculative branching, parallel evaluation can be applied to entire continuous trajectories or populations of interacting samplers.

For continuous distributions governed by differential equations, such as Langevin dynamics, sampling traditionally requires sequential discretization steps. However, Nima Anari and Thuy-Duong Vuong proved in Fast parallel sampling under isoperimetry that this process can be parallelized using Picard iterations. Instead of evaluating gradients sequentially step-by-step, their algorithm queries the gradient of the target distribution at multiple points along an entire proposed trajectory segment simultaneously. This allows the system to update an entire temporal window in a single computational round, achieving polylogarithmic parallel depth.

On a macro level, population-based MCMC methods run multiple chains concurrently to navigate complex, multimodal landscapes. As highlighted by Ronald J. Janssen and Pasi Jylänki in the context of fMRI data parcellation, running multiple chains in parallel accelerates convergence and prevents samplers from becoming trapped in local optima.

To maximize the efficiency of these populations, Jakub M. Tomczak demonstrated in Approximate Bayesian Computation for Discrete Spaces how population-based chains can share evolutionary information to navigate discrete spaces. Similarly, Achille Thin et al. introduced the NEO framework in NEO: Non Equilibrium Sampling on the Orbits of a Deterministic Transform, which uses iterated sampling-importance resampling to allow multiple parallel walkers to interact. By combining local trajectory information with global resampling steps, the walkers collectively transition toward high-density regions, combining the benefits of wide exploration with coordinated convergence.

Why It Works: The Intuition

To understand why parallel candidate evaluation works so effectively without violating the mathematical rules of probability theory, consider an analogy of a scout exploring a dense, foggy mountain range at night.

A traditional sequential sampler is a single explorer. They can only take one step at a time. They stand at their current position, feel out a potential next step with their foot, evaluate the slope, and decide whether to step forward or stay put. If evaluating the slope takes 10 seconds, every single step costs 10 seconds of wall-clock time.

Parallel candidate evaluation transforms this single explorer into a coordinated team equipped with radios:

  1. The Wide Approach (Multi-Proposal): The lead explorer stands still but sends out ten scouts in a circle around them simultaneously. All ten scouts evaluate their respective slopes at the same time. They radio back their findings, and the leader chooses the best path based on a mathematically rigorous lottery. The team covers a massive amount of ground in the same 10 seconds it would take a single explorer to check one spot.
  2. The Deep Approach (Speculative Prefetching): The leader is currently deciding whether to step onto a rock to the north. While they are thinking, they send one scout further north of that rock, and another scout to the east of their current position. If the leader decides to step onto the rock, the northern scout has already evaluated the next move. The time spent waiting is converted into forward progress.
  3. The Trajectory Approach (Picard Iterations): The team guesses a plausible path along a ridge for the next hundred meters. Scouts position themselves along the entire guessed path simultaneously and measure the terrain gradients all at once. They then collectively adjust the entire path segment in a single round of communication.

Crucially, in all three scenarios, the final path recorded in the logbook adheres strictly to the laws of the target distribution. Because the parallel processing power is spent solely on evaluating possibilities—while the final filtering step maintains the exact acceptance criteria required by probability theory—the statistical integrity of the distribution is preserved. We effectively trade abundant, concurrent compute to bypass the tyranny of sequential time.

Key Foundational Work

Patterns of Scalable Bayesian Inference (2016) — contributed 2 concept elements to this direction.
Accelerating MCMC via Parallel Predictive Prefetching (2014) — contributed 2 concept elements to this direction.
Let’s Not Waste Time: Using Temporal Information in Clustered Activity Estimation with Spatial Adjacency Restrictions (CAESAR) for Parcellating FMRI Data (2016) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_parallel_candidate_evaluation_1a70406f,
  title = {parallel candidate evaluation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parallel-candidate-evaluation/rdr_1a70406fb48741e4afb3eeb277adf258},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_parallel_candidate_evaluation_1a70406f_v1,
  title = {parallel candidate evaluation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parallel-candidate-evaluation/rdr_1a70406fb48741e4afb3eeb277adf258/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake