Approximate evaluation
CRESCENT: scoring a candidate on only as many rows as it takes to know whether it matters.
The compute the search wastes is structural, not incidental
At cluster scale, the time spent evaluating candidates dwarfs the time spent in selection, mutation and crossover. The bigger the dataset, the more dominant evaluation becomes: tuning the constants of one candidate means computing its loss over the data thousands of times.
Most of those evaluations are wasted. The vast majority of candidates the search produces are bad; the search is supposed to produce many bad candidates so the rare good ones can stand out. Spending a full pass over the data on a candidate that is clearly not competitive is a structural inefficiency, not a tuning issue. CRESCENT treats the question of how many rows a candidate deserves as a decision made while it is being scored.
Four threads of work
Sequential early stopping
- Batches, not stages. A candidate is scored on the data in small batches while a running error is kept. After a statistically sufficient minimum number of rows, the running error is compared with a threshold at every batch boundary. A candidate that is clearly not competitive stops there; one that stays competitive runs on.
- Where it applies. Inside the refinement pipeline, where one candidate is evaluated again and again while it is pruned and its constants are tuned. The score a candidate finally competes with is exact.
- Open questions. Whether a candidate's final score can be estimated too without distorting selection.
How many rows are enough
- A sample-size bound. The minimum number of rows comes from a classical sample-size bound (Cochran), so the estimate carries a known error before the first decision is taken.
- Small and very large data. Sampling pays off outside a middle band of dataset sizes. Inside it, exact evaluation is cheap enough and is used instead.
- Open questions. Stratified sampling when the data has explicit structure; rare rows that carry most of the signal.
Dynamic thresholds
- Static thresholds underweight progress. The population's quality distribution shifts as the run progresses. A threshold that was well calibrated in generation 10 is too lax in generation 100; most candidates pass, nothing is stopped, and the saving collapses.
- Population-aware. The threshold is a percentile of the gene pool's current error distribution, strict while few rows have been seen and more lenient as the sample fills. It moves with the run.
- Cold start. Until the gene pool holds enough candidates to form a distribution, nothing is stopped early.
- Open questions. Smoothing the threshold against its own noise floor without reintroducing the static problem.
Variable-cost evaluation (open)
- Cost is candidate-dependent. A tall, expensive expression takes substantially longer to evaluate than a small one. Treating evaluation cost as constant across the population, as the racing literature usually does, overcounts the cost of small candidates and undercounts the cost of large ones.
- Not yet built. Predicting a candidate's evaluation cost from its structure, and weighing expected savings against expected risk, is a research thread, not a property of the system today.
- Open questions. Interaction with constant optimization, which dominates evaluation cost for many candidates; calibration drift of a cost predictor across datasets.
Two consequences of this design
Related material
The narrative companion to this area is the note Approximate evaluation, as a research problem, which records the idea as it stood before the mechanism was built. CRESCENT is a paper candidate. The mechanism runs by default; the ablation that isolates its contribution is the open step.
Adjacent areas: Constant optimization is where most of the evaluations come from; Search describes the gene pool whose error distribution sets the threshold. The pipeline view is described under Technology § 6 with Figure 3.
Continue reading
Other research areas are listed under Research. Published work lives on Papers; short-form notes on Notes.