A new theoretical paper shows that AI-guided genetic algorithms are not a free upgrade over their random ancestors.
Genetic algorithms solve problems by keeping a pool of candidate solutions and repeatedly mutating and recombining them, classically at random. Newer versions swap in a machine learning model that mutates and recombines with the explicit goal of improving the objective at inference time, at the cost of far more computation per step. The paper builds a formal framework, treated as a query-complexity problem in reinforcement-learning terms, to compare these smarter operators against the classic ones. For a task called parity learning, the authors derive an exact formula tying the minimum number of queries to the size of the solution pool and the length of the input, plus a matching bound of roughly n-squared bits of memory; they also show generation, mutation, and recombination can all be simultaneously required to reach a near-optimal answer, and that Gaussian-distributed problems have a phase transition where a positive drift in the operators produces an exponential speedup.
As labs increasingly bolt large language models onto genetic-style search loops, for prompt optimization, drug design, or automated code repair, it is tempting to assume smarter, model-guided operators always beat random tweaking. This paper is a mathematical check on that assumption: a diverse pool of candidate solutions can be provably necessary, not just helpful, and trading diversity for narrower ML-guided search hits real limits no matter how good the mutation model is.
It is theory, not a benchmark leaderboard entry, but it marks where the current wave of AI-plus-genetic-algorithm tools should expect diminishing returns.