# Problem-solving benefits of down-sampled lexicase selection

arXiv: https://arxiv.org/abs/2106.06085 · HTML: https://mlsanity.com/paper/2106.06085/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 54 references that are in the map.
- First posted on arXiv 10 Jun 2021.

## Builds on (most cited first, 7 of 7)

- [Illuminating search spaces by mapping elites](https://mlsanity.com/paper/1504.04909/) (2015)
- [An Alternative View: When Does SGD Escape Local Minima?](https://mlsanity.com/paper/1802.06175/) (2018)
- [Quality and Diversity Optimization: A Unifying Modular Framework](https://mlsanity.com/paper/1708.09251/) (2017)
- [Using Centroidal Voronoi Tessellations to Scale Up the Multi-dimensional Archive of Phenotypic Elites Algorithm](https://mlsanity.com/paper/1610.05729/) (2016)
- [Autonomous skill discovery with Quality-Diversity and Unsupervised Descriptors](https://mlsanity.com/paper/1905.11874/) (2019)
- [Where are we now? A large benchmark study of recent symbolic regression methods](https://mlsanity.com/paper/1804.09331/) (2018)
- [Lexicase selection in Learning Classifier Systems](https://mlsanity.com/paper/1907.04736/) (2019)

## Built on by (most cited first, 8 of 8)

- [Fully Autonomous Programming with Large Language Models](https://mlsanity.com/paper/2304.10423/) (2023)
- [Choose Your Programming Copilot: A Comparison of the Program Synthesis Performance of GitHub Copilot and Genetic Programming](https://mlsanity.com/paper/2111.07875/) (2021)
- [Probabilistic Lexicase Selection](https://mlsanity.com/paper/2305.11681/) (2023)
- [Particularity](https://mlsanity.com/paper/2306.06812/) (2023)
- [DALex: Lexicase-like Selection via Diverse Aggregation](https://mlsanity.com/paper/2401.12424/) (2024)
- [Fully Autonomous Programming using Iterative Multi-Agent Debugging with Large Language Models](https://mlsanity.com/paper/2503.07693/) (2025)
- [HOTGP -- Higher-Order Typed Genetic Programming](https://mlsanity.com/paper/2304.03200/) (2023)
- [Generational Computation Reduction in Informal Counterexample-Driven Genetic Programming](https://mlsanity.com/paper/2408.12604/) (2024)

## Abstract (arXiv)

In genetic programming, an evolutionary method for producing computer programs that solve specified computational problems, parent selection is ordinarily based on aggregate measures of performance across an entire training set. Lexicase selection, by contrast, selects on the basis of performance on random sequences of training cases; this has been shown to enhance problem-solving power in many circumstances. Lexicase selection can also be seen as better reflecting biological evolution, by modeling sequences of challenges that organisms face over their lifetimes. Recent work has demonstrated that the advantages of lexicase selection can be amplified by down-sampling, meaning that only a random subsample of the training cases is used each generation. This can be seen as modeling the fact that individual organisms encounter only subsets of the possible environments, and that environments change over time. Here we provide the most extensive benchmarking of down-sampled lexicase selection to date, showing that its benefits hold up to increased scrutiny. The reasons that down-sampling helps, however, are not yet fully understood. Hypotheses include that down-sampling allows for more generations to be processed with the same budget of program evaluations; that the variation of training data across generations acts as a changing environment, encouraging adaptation; or that it reduces overfitting, leading to more general solutions. We systematically evaluate these hypotheses, finding evidence against all three, and instead draw the conclusion that down-sampled lexicase selection's main benefit stems from the fact that it allows the evolutionary process to examine more individuals within the same computational budget, even though each individual is examined less completely.