# EcoSearch: A Constant-Delay Best-First Search Algorithm for Program Synthesis

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 26 references that are in the map.
- First posted on arXiv 23 Dec 2024.

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

- [On the Measure of Intelligence](https://mlsanity.com/paper/1911.01547/) (2019)
- [Addressing the Abstraction and Reasoning Corpus via Procedural Example Generation](https://mlsanity.com/paper/2404.07353/) (2024)
- [Guiding Enumerative Program Synthesis with Large Language Models](https://mlsanity.com/paper/2403.03997/) (2024)

## Abstract (arXiv)

Many approaches to program synthesis perform a combinatorial search within a large space of programs to find one that satisfies a given specification. To tame the search space blowup, previous works introduced probabilistic and neural approaches to guide this combinatorial search by inducing heuristic cost functions. Best-first search algorithms ensure to search in the exact order induced by the cost function, significantly reducing the portion of the program space to be explored. We present a new best-first search algorithm called EcoSearch, which is the first constant-delay algorithm for pre-generation cost function: the amount of compute required between outputting two programs is constant, and in particular does not increase over time. This key property yields important speedups: we observe that EcoSearch outperforms its predecessors on two classic domains.