AI Discovers Algorithm That Beats NSDI'24 Best Paper (adrs-ucb.notion.site)

Researchers used OpenEvolve, an automated algorithm discovery system, to evolve cloud-scheduling policies that outperform the NSDI’24 “Uniform Progress” state-of-the-art for meeting deadline-constrained jobs while minimizing cost. Starting from a greedy baseline and running ~400 iterations (≈5 hours, <$20 compute using an ensemble of Gemini 2.5 Pro and GPT‑4o), the evolved single-region policy delivered on average 7% (up to 16.7%) cost savings while preserving deadline guarantees; extending to multi-region scheduling produced average 27% and up to 48% savings versus a round‑robin Uniform Progress baseline. Evaluations used the original paper’s traces spanning deadlines, cold-start delays (20 minutes), regions and GPU types for an apples‑to‑apples comparison. Technically, evolution discovered interpretable mechanisms beyond the fixed progress‑line rule: window‑based pattern recognition of recent spot stability, adaptive decision thresholds, and selective waiting that avoids short‑lived spots whose cold‑start overhead negates benefit. In the multi‑region setting it learned region caching, urgency detection, and a two‑stage urgency system to balance opportunistic exploration of cheap spots against migration costs and deadline pressure. The work shows ADRS can cheaply generate novel, generalizable scheduling algorithms (if trained on diverse traces) and highlights that weaker start policies can let evolution escape local minima to find better strategies.