Runtime Analysis of Cartesian Genetic Programming on MAX: A Proven Exponential Speedup

Created by W.Langdon from gp-bibliography.bib Revision:1.9262

@InProceedings{Dang:2026:NeurIPS,

• author = "Duc-Cuong Dang and Roman Kalkreuth and Andre Opris",
• title = "Runtime Analysis of Cartesian Genetic Programming on {MAX}: A Proven Exponential Speedup",
• booktitle = "Proceedings of the Neural Information Processing Systems",
• year = "2026",
• editor = "Hsuan-Tien Lin and others",
• month = "10 " # dec,
• keywords = "genetic algorithms, genetic programming, Cartesian Genetic Programming, TinyverseGP, theory: Poster",
• URL = "https://neurips.cc/virtual/2026/loc/sydney/poster/155859",
• abstract = "Genetic Programming (GP) is a search paradigm inspired from natural evolution for the automated discovery of expressions, functions, and computer programs. Cartesian GP (CGP) is a flavour of GP that uses a graph-based model to encode candidate programs, as contrasted to the conventional Tree-based GP (TGP). Since its inception two decades ago, CGP has predominantly been analyzed empirically, thus little is known regarding its theoretical performance guarantees. This paper analyzes CGP for the MAX problem, which has been only rigorously studied for TGP with a proven expected runtime superlinear in the optimal program length. We prove that the expected time for the (1+1) CGP employing common mutation operators to evolve an equivalent optimal of the same output is polylogarithmic in n, specifically at most O(log^9 n). This is remarkable, as it shows an exponential speedup by switching to CGP. Our results shed light on the benefit and the compactness of the graph-based representation for programs, and on how CGP can navigate its search and fitness spaces efficiently. This is a first proven performance guarantee for CGP on an established benchmark problem. Experiments complement our theoretical findings.",
• notes = "neurips 2026 1269 Law St, San Diego CA 92109",

}

Genetic Programming entries for Duc-Cuong Dang Roman Tobias Kalkreuth Andre Opris

Citations