Robustness Starts with the Objective: Designing and Certifying Robust LLM-Generated Heuristics
cs.AI, cs.CL, cs.DC, cs.PF
Submitted: 2026-10-31
Updated: 2026-10-31
Code: https://github.com/Azure/AzurePublicDataset
License: http://creativecommons.org/licenses/by/4.0/
The gist: LLMs are increasingly used to design heuristics for computer systems.
Terminology
Abstract
LLMs are increasingly used to design heuristics for computer systems. However, most synthesis frameworks evaluate candidates by their average performance, which can mask severe regressions on specific workloads. Even adding adversarial training inputs doesn't eliminate these regressions, and percentile objectives (e.g., optimizing for the 95th percentile) overlook how severe regressions can be beyond the selected threshold. We present TAILOR, a framework that guides LLM synthesis using the Conditional Value at Risk (CVaR) of the cost difference between each candidate and an existing baseline on the same workload. This paired CVaR measures the average difference over the worst fraction of workloads. We show that a negative paired CVaR guarantees improvements in both average performance and tail optimality gap relative to the unknown optimum, without ever computing that optimum. We find that TAILOR achieves the best mean--tail trade-off among the synthesis objectives we evaluate across three case studies: Azure GPU batch admission, Azure VM packing, and server placement. Tested across seven diverse optimization benchmarks, TAILOR produces heuristics that are certified with 99% confidence to improve both average performance and tail optimality gaps over the baseline in six of them. On these six benchmarks, TAILOR also outperforms known robust, human-designed alternatives in the tail while achieving better or comparable average-performance improvement over the baseline.
Sources
- New Approximability Results for the Robust k-Median Problem
- AdaEvolve: Adaptive LLM Driven Zeroth-Order Optimization
- Barbarians at the Gate: How AI is Upending Systems Research
- Glia: A Human-Inspired AI for Automated Systems Design and Optimization
- AIDE: AI-Driven Exploration in the Space of Code
- Robust Heuristic Algorithm Design with LLMs
- ShinkaEvolve: Towards Open-Ended And Sample-Efficient Program Evolution
- EvoX: Meta-Evolution for Automated Discovery
- AHD Agent: Agentic Reinforcement Learning for Automatic Heuristic Design
- AlphaEvolve: A coding agent for scientific and algorithmic discovery
- AIChilles: Automatically Uncovering Hidden Weaknesses in AI-Evolved Systems
Related papers
- Multi-Objective Structured Pruning of LLMs for Latency and Model Size Optimization
- MAVEN-T: Reinforced Heterogeneous Distillation for Real-Time Multi-Agent Trajectory Prediction
- Model Discovery Agent: LLM-assisted Bayesian experiment design for data-efficient discovery of mechanistic world models
- Embeddings for Preferences, Not Semantics
- Can We Trust Item Response Theory for AI Evaluation?
- Diagnosing Task Insensitivity in Language Agents