"LHS in LHS": A new expansion strategy for Latin hypercube sampling in simulation design

Matteo Boschini, Davide Gerosa, Alessandro Crespi, Matteo FalconeSoftwareX 2025 · DOI · DBLP

Abstract

Latin Hypercube Sampling (LHS) is a cornerstone of computer experiment design, ensuring efficient parameter space coverage. However, standard LHS is inherently static, requiring the sample size $N$ to be fixed a priori. We present "LHS in LHS," a flexible expansion strategy that allows for adding $M$ new samples to an existing $N$-sample design while preserving space-filling and projection properties. By regridding the space and nesting a new LHS within the resulting voids, this method maintains high sampling quality without discarding previous simulations.

Introduction

In computationally intensive fields such as astrophysics and climate modeling, the cost of individual simulations necessitates highly efficient sampling strategies. Latin Hypercube Sampling (LHS) addresses this by ensuring that for $N$ samples in $P$ dimensions, each dimension is divided into $N$ equal-probability bins, with exactly one sample per bin. This structure prevents sample clustering and ensures uniform marginal distributions.

A significant limitation of standard LHS is its lack of flexibility; if initial results suggest more samples are needed, adding them randomly or through naive methods destroys the LHS property. Existing expansion techniques are often computationally expensive or restricted to specific increments (e.g., doubling the sample size). The "LHS in LHS" approach provides a model-free, computationally efficient way to expand an existing set by any number of samples $M$.

Methodology: The "LHS in LHS" Algorithm

The proposed expansion strategy operates through three primary stages: regridding, void extraction, and nested sampling.

  1. Regridding: The $P$-dimensional parameter space is re-divided into $N+M$ bins per dimension. In this new grid, the original $N$ points may occupy some bins while leaving others empty. This process can create "overlaps" (bins with multiple points) or "voids" (empty bins).
  2. Void Extraction: The algorithm identifies empty intervals across all dimensions. It selects a subset of $M$ empty intervals to be populated by new samples.
  3. Nested LHS: Instead of simple random placement, a new LHS is performed specifically within the subgrid defined by the $M$ identified voids. This "LHS in LHS" nesting is critical for preserving global projection properties in the expanded set.
The three-step expansion process: (a) regridding the original space, (b) extracting voids, and (c) performing a nested LHS within those voids.

To quantify the quality of the expanded design, the authors define the LHS degree ($\mathcal{D}$). This metric ranges from 0 to 1, where 1 indicates a perfect LHS where every marginalized bin contains exactly one sample.

Results and Discussion

The algorithm was evaluated using synthetic datasets with varying initial sizes ($N=10, 100, 1000$) and dimensions ($P=2, 4, 8$).

The $M=kN$ Phenomenon

A key finding is the existence of "perfect" expansions ($\mathcal{D}=1$) whenever the number of added samples $M$ is an integer multiple of the original size $N$. In these scenarios, the new grid lines align perfectly with the original grid, eliminating bin overlaps.

LHS degree $\mathcal{D}$ as a function of added samples $M$ for different initial sizes $N$. Note the periodic "spikes" where $\mathcal{D}=1$ at $M=kN$.

Dimensionality and Batching

The LHS degree $\mathcal{D}$ appears largely independent of the number of dimensions $P$, depending primarily on the ratio $M/N$. Furthermore, "batch" expansion (adding $M$ points at once) significantly outperforms "unitary" expansion (adding points one by one). Sequential unitary additions rapidly degrade the LHS property, whereas batching maintains a higher $\mathcal{D}$.

Computational Efficiency

The implementation, available in the expandLHS Python package, utilizes Numba for just-in-time compilation. This results in high performance; for instance, expanding a 50-point 2D set takes less than $4 \times 10^{-4}$ seconds. Optimization using discrepancy metrics can further enhance the space-filling quality of the final set by selecting the best candidate from multiple valid expansions.

Conclusion

"LHS in LHS" offers a robust and efficient solution for the sequential expansion of computer experiments. By leveraging regridding and nested sampling, it allows researchers to grow their datasets adaptively. Future work will focus on extending this methodology to constrained parameter spaces, non-uniform boundaries, and weighted sampling scenarios.

Summary updated

BibTeX
@article{boschini2025lhs,
  author = {Matteo Boschini and Davide Gerosa and Alessandro Crespi and Matteo Falcone},
  title = {{"LHS in LHS": A new expansion strategy for Latin hypercube sampling in simulation design}},
  journal = {SoftwareX},
  year = {2025},
  doi = {10.1016/j.softx.2025.102294},
}
Figure