Parallelizing Evaluation in Black Box Optimization

15 concepts20 papers1 proposal

In black-box optimization, we treat a target function as an unknown landscape. To find its global optimum, an algorithm iteratively samples a candidate solution, evaluates its quality (or "fitness"), and uses that feedback to determine where to sample next. This loop is inherently sequential: step $t+1$ depends directly on the outcome of step $t$.

Historically, this sequential dependency was acceptable because evaluating a candidate solution was computationally cheap. Today, however, the evaluation step is frequently the most expensive part of the entire process. Whether it involves training a deep neural network to evaluate a hyperparameter configuration, running a fluid dynamics simulation to calibrate an aero-engine, or generating high-fidelity images from diffusion noise seeds, a single evaluation can take minutes, hours, or even days.

When evaluations are performed one after another, the total wall-clock time scales linearly with the number of iterations. This creates a severe sequential evaluation bottleneck. While modern computing infrastructure has evolved toward massive parallelism—via multi-core GPUs, distributed cloud clusters, and high-performance computing nodes—traditional optimization algorithms remain trapped in a "batch size of one" paradigm, leaving powerful hardware resources largely idle.

To scale optimization to high-dimensional, real-world problems, researchers across machine learning and operational research are redesigning algorithms to break this sequential dependency, shifting from serial execution to concurrent, asynchronous, and distributed evaluation frameworks.


The Ubiquity of the Sequential Bottleneck

The tension between sequential optimization logic and parallel hardware limits throughput across several distinct domains:

Hyperparameter and Pipeline Optimization

In automated machine learning (AutoML), tuning hyperparameters or searching over complex data pipelines requires training models to completion to obtain a performance metric. As Ilija Ilievski et al. point out in their work on deterministic surrogate models, Efficient Hyperparameter Optimization for Deep Learning Algorithms Using Deterministic RBF Surrogates, frameworks that evaluate configurations sequentially fail to utilize distributed computing environments, leading to prohibitive wall-clock times.

This limitation extends to Bayesian optimization frameworks. In FLASH: Fast Bayesian Optimization for Data Analytic Pipelines, Yuyu Zhang et al. note that evaluating pipeline configurations serially severely restricts scalability in modern cloud environments. Even when integrating advanced planning mechanisms, such as the energy-based reinforcement learning framework proposed by RUIYAO MIAO et al. in Optimizing the Unknown: Black Box Bayesian Optimization with Energy-Based Model and Reinforcement Learning, the underlying execution remains constrained by sequential sampling, presenting a major hurdle for massive tuning tasks.

Even modern sequence-to-sequence approaches face this barrier. For instance, the text-based Transformer framework developed by Yutian Chen et al., Towards Learning Universal Hyperparameter Optimizers with Transformers, is fundamentally designed around sequential trial evaluation; transitioning these models to suggest asynchronous or synchronous parallel trials remains an open challenge.

Evolutionary Algorithms and Neuroevolution

Population-based methods, such as Evolutionary Algorithms (EAs), seem naturally parallel because they maintain a collection of candidate solutions simultaneously. However, traditional implementations often evaluate the fitness of the population sequentially or enforce strict synchronization barriers at the end of each generation.

In the context of evolving neural network topologies for complex control tasks, Karan Kumar Budhraja et al. demonstrate in Neuroevolution-Based Inverse Reinforcement Learning that sequential evaluation of independent genomes in large state spaces creates a critical scalability bottleneck. Similarly, when using Large Language Models as evolutionary operators to discover code solutions, Jinzhu Mao et al. observe in Identify Critical Nodes in Complex Network with Large Language Models that a lack of parallelization in the evaluation phase slows down discovery.

Whether calibrating physical systems—as explored by Jialin Liu et al. in fSDE: efficient evolutionary optimisation for many-objective aero-engine calibration—or searching for optimal initial noise seeds in generative models, as shown by Yuan He in Dual-Seed Evolutionary Algorithm for Noise Optimization in Diffusion Models, operating serially fails to exploit concurrent hardware units, driving up latency.


Strategies for Concurrent Evaluation

To unlock the power of parallel hardware, optimization frameworks must be structurally altered to generate, evaluate, and ingest multiple candidate points concurrently. Researchers utilize three primary mechanisms to achieve this:

1. Batch and Asynchronous Sampling

Instead of waiting for a single evaluation to finish before computing the next candidate, algorithms can propose a batch of points simultaneously. In Bayesian optimization, this means designing acquisition functions that identify multiple diverse, high-performing regions at once, rather than focusing myopically on a single peak.

However, synchronous batching introduces the "straggler problem": if one evaluation takes longer than the others, the entire algorithm stalls. To prevent this, frameworks are transitioning to asynchronous execution. In an asynchronous framework, as soon as a single worker node finishes evaluating a candidate and returns its score, the central optimizer immediately ingests that data, updates its internal model, and deploys a new candidate to the idle worker, keeping hardware utilization near 100%.

2. Problem Decomposition and Sub-populations

For high-dimensional optimization problems, a powerful strategy is to break the search space down into smaller, semi-independent components. In A cooperative coevolution PSO technique for complex bilevel programming problems and application to watershed water trading decision making problems, Tao Zhang demonstrates how cooperative coevolutionary particle swarm optimization can decompose a massive problem into interacting "species" or sub-populations. By evolving these sub-populations within parallelized execution environments, the system bypasses the sequential bottleneck that typically occurs as dimensionality increases.

Sequential Loop (Bottleneck):
[Propose Candidate] ──> [Slow Evaluation] ──> [Update Model] ──> [Propose Next]

Parallel/Asynchronous Framework:
                       ┌──> [Worker 1: Evaluation] ──┐
[Central Optimizer] ───┼──> [Worker 2: Evaluation] ──┼──> [Asynchronous Ingestion & Update]
                       └──> [Worker 3: Evaluation] ──┘

3. Hardware-Native Redesign

Maximizing throughput often requires moving away from CPU-bound sequential logic entirely and redesigning algorithms to run natively on parallel architectures like GPUs or cloud-native clusters. For example, in signal processing, Bai Yan et al. demonstrate in Multiobjective Bilevel Evolutionary Approach for Off-Grid Direction-of-Arrival Estimation that leveraging GPU architectures to evaluate candidate solutions simultaneously provides the throughput necessary for high-dimensional decoding.

Similarly, early work on image processing by Megumi Takezawa et al., A GA and SA-Based Fractal Image Coding, highlighted that sequential block processing limits real-time execution, a problem that can be overcome by distributing evolutionary searches across modern hardware.


Scaling to Hyperscale Data

The need to eliminate sequential bottlenecks is not unique to black-box optimization; it is a fundamental requirement for scaling any data-intensive computational model.

In classical machine learning, training algorithms have faced identical constraints. For instance, Olvi L. Mangasarian et al. addressed this in Active Support Vector Machine Classification by reformulating linear SVM training into a positive-definite dual form, shifting complexity away from the number of data points to allow parallelized architectures to handle massive datasets.

As model parameters scale into the millions, Dimitri Kanevsky et al. emphasize in Introduction to the Special Section on Large-Scale Optimization for Audio, Speech, and Language Processing that conventional sequential optimization algorithms inevitably fail, requiring a fundamental shift toward parallelized architectures and efficient gradient computation methods.

Ultimately, as optimization tasks move into hyperscale cloud environments—such as the virtual machine consolidation problems studied by Huiqun Yu et al. in Multi-Objective Biogeography-Based Method to Optimize Virtual Machine Consolidation—sequential processes become completely unviable. As summarized by Jinjun Chen in Guest editorial: Special issue on data intensive cloud computing, the future of efficient large-scale computation depends on redesigning classical operational research and optimization models to function natively within parallelized, cloud-native frameworks. By breaking the sequential evaluation bottleneck, these systems can finally match the scale of modern data and hardware.

Key Foundational Work

Active Support Vector Machine Classification (2000) — contributed 1 concept elements to this direction.
A GA and SA-Based Fractal Image Coding (2003) — 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_sequential_evaluation_bottleneck_98d34dbf,
  title = {sequential evaluation bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-evaluation-bottleneck/rdr_98d34dbfea684637ae3076edd2a12e30},
  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_sequential_evaluation_bottleneck_98d34dbf_v1,
  title = {sequential evaluation bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-evaluation-bottleneck/rdr_98d34dbfea684637ae3076edd2a12e30/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