Filtering Search Proposals with Cheap Surrogates

25 concepts22 papers1 proposal

Optimization and sampling algorithms often face a fundamental tension between exploration and evaluation cost. To find global optima or map complex posterior distributions, an algorithm must generate and test thousands of candidate solutions. However, when evaluating a single candidate requires a high-fidelity simulation—such as a partial differential equation (PDE) solver, a deep neural network training loop, or a live user interaction—the computational budget quickly vanishes.

The core intuition behind candidate pre-screening (or surrogate-based proposal filtering) is to decouple the generation of search steps from the cost of validating them. Instead of evaluating every generated candidate directly with an expensive ground-truth model, the algorithm over-generates a large pool of candidates, passes them through a cheap computational filter (a surrogate model), and only sends the most promising candidates to the high-fidelity evaluator.

By acting as a gatekeeper, the surrogate ensures that the expensive evaluation budget is strictly reserved for high-potential regions of the search space.


In traditional evolutionary algorithms, generating an offspring and evaluating its fitness are tightly coupled operations. If a mutation leads to a poor solution, the computational cost of discovering that failure is identical to the cost of discovering a breakthrough.

Candidate pre-screening breaks this coupling by introducing an "imagination" or "pre-selection" phase. The algorithm generates multiple trial vectors for every parent but uses a fast approximation model to rank them before any real-world fitness function is called.

[ Parent Solution ] 
       │
       ▼  (Over-generation)
[ Candidate Pool (e.g., 100 Mutations) ]
       │
       ▼  (Cheap Surrogate Filter)
[ Top Ranked Candidate Only ]
       │
       ▼  (High-Fidelity Evaluation)
[ True Fitness Score ]

This mechanism allows the search process to aggressively explore wider neighborhoods at minimal cost. Lars Gräning et al. demonstrated in Efficient evolutionary optimization using individual-based evolution control and neural networks: A comparative study that this pre-selection strategy provides significantly higher stability and lower variance in complex landscapes with many local optima. Testing thousands of mutations inside a neural network surrogate allows the algorithm to filter out unpromising search directions early.

Various architectures can serve as this initial filter:


Preserving Exactness via Delayed Acceptance in MCMC

While optimization algorithms can tolerate occasional inaccuracies from a surrogate model, Markov Chain Monte Carlo (MCMC) sampling requires strict mathematical guarantees to converge to the true posterior distribution. If we replace the exact likelihood model entirely with a surrogate, the resulting sampler becomes biased.

Delayed acceptance solves this by using the surrogate as an early-stage filter within the MCMC acceptance step.

  1. Stage 1 (The Surrogate Filter): A proposal is generated. The sampler evaluates its likelihood using a cheap surrogate (e.g., a Gaussian Process). If the surrogate predicts a low acceptance probability, the proposal is immediately rejected. No expensive simulation occurs.
  2. Stage 2 (The High-Fidelity Validation): If the proposal passes the surrogate's gate, it is subjected to the exact, high-fidelity model. The final acceptance probability is adjusted to account for the surrogate's filtering, mathematically preserving the exactness of the target posterior.

The authors of Quantifying the Uncertainty in Model Parameters Using Gaussian Process-Based Markov Chain Monte Carlo: An Application to Cardiac Electrophysiological Models (Jwala Dhamala et al.) demonstrated that this pre-screening mechanism cuts computational costs by over half without introducing any approximation trade-offs or bias.

This framework has proven highly effective for complex physical simulations. For instance, L. Mihaela Păun et al. developed an "$n$-steps ahead" delayed acceptance algorithm using Gaussian Process emulators in MCMC with delayed acceptance using a surrogate model with an application to cardiovascular fluid dynamics to bypass expensive cardiovascular fluid dynamics PDEs. Similarly, Alan Lazarus et al. utilized a fast gradient-matching surrogate in Multiphase MCMC Sampling for Parameter Inference in Nonlinear Ordinary Differential Equations to filter out low-probability proposals before running numerical integrations. This multi-level filtering concept can also be structured as a hybrid chain; Juntao Yang et al. proposed a two-level MCMC framework in A hybrid two-level MCMC framework to accelerate posterior mean estimation with deep learning surrogates for bayesian inverse problems where a fast base chain explores broadly via a deep learning surrogate, followed by a shorter correction chain using the high-fidelity model.

A Critical Caveat: Gradient-Driven Samplers

The efficiency gains of delayed acceptance depend heavily on the underlying sampler's baseline behavior. Dirk Husmeier et al. identified an important limitation in Emulation-accelerated Hamiltonian Monte Carlo algorithms for parameter estimation and uncertainty quantification in differential equation models: for gradient-driven samplers like Hamiltonian Monte Carlo (HMC) or the No-U-Turn Sampler (NUTS), proposals already maintain a very high acceptance rate. Because the sampler rarely generates bad proposals, the surrogate filter rarely finds anything to reject, offering little to no computational advantage over evaluating the full model directly.


Alternative Surrogates: Classifiers, History, and Deterministic Proxies

A surrogate model does not always need to be a complex regression model attempting to mimic exact continuous values. Depending on the problem framing, filters can take simpler, highly robust forms.

1. Classification Filters

Instead of predicting exact objective values, a surrogate can simply act as a binary classifier. In Preselection via Classification: A Case Study on Evolutionary Multiobjective Optimization, Aimin Zhou et al. showed that a simple classifier trained to predict whether a candidate will be "dominated" or "unpromising" is sufficient. Discarding candidates labeled as unpromising speeds up convergence without the overhead of training exact regression models.

2. Historical Data Filters

Surrogates can be constructed entirely from past search trajectories or interaction data, removing the need to train an active model on the fly:

3. Deterministic Proxies

When optimizing stochastic systems, evaluating a candidate requires expensive Monte Carlo simulations to account for uncertainty. J. Christopher Beck et al. showed in Proactive Algorithms for Scheduling with Probabilistic Durations that a fast, simplified deterministic solver can act as an effective filter. Candidates are evaluated deterministically first; only those that perform well under fixed conditions are subjected to high-fidelity probabilistic simulation.


Simplifying Model-Based Guidance

In fields like Hyperparameter Optimization (HPO), incorporating model-based guidance traditionally requires optimizing complex acquisition functions (such as Expected Improvement) over a continuous space, which can be computationally intensive and fragile.

Candidate filtering offers a simpler, more robust alternative. In Automated Benchmark-Driven Design and Explanation of Hyperparameter Optimizers, Julia Moosbauer et al. demonstrated that instead of mathematically optimizing an acquisition function, one can simply sample a large batch of random configurations, rank them using a surrogate model, and select the top performers for actual evaluation.

By acting as a filter rather than a direct generator, the surrogate provides strong model-based guidance while maintaining the underlying robustness, simplicity, and parallelizability of random, bandit-style search algorithms.

Key Foundational Work

Efficient evolutionary optimization using individual-based evolution control and neural networks: A comparative study (2005) — contributed 2 concept elements to this direction.
Saving MGG: Reducing Fitness Evaluations for Real-coded GA/MGG. (2006) — contributed 1 concept elements to this direction.
Preconditioning Markov Chain Monte Carlo Simulations Using Coarse-Scale Models (2006) — 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_surrogate_based_proposal_filtering_08a01b38,
  title = {surrogate-based proposal filtering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/surrogate-based-proposal-filtering/rdr_08a01b38353a47ee9de36c6b1841003c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_surrogate_based_proposal_filtering_08a01b38_v1,
  title = {surrogate-based proposal filtering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/surrogate-based-proposal-filtering/rdr_08a01b38353a47ee9de36c6b1841003c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake