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.
Figures & tables
Figure 1: Goal: improve tail optimality gaps while preserving average performance. Distributions of optimality gaps H−OPT and H′−OPT for GPU batch admission ( §2 ), where H and H′ denote the baseline and candidate performance, expressed as costs to minimize. The shaded regions are the worst 5% of each distribution, starting at its 95th-percentile cutoff. H′ reduces the tail optimality gap by 14% while preserving average performance.
Figure 2: Mean objectives hide tail regressions, and percentile objectives control only the tail cutoff; paired CVaR controls both. CDF of paired differences Δ=H′−H on held-out Azure streams, normalized by FCFS average value per stream. Negative values are improvements over FCFS and positive values are regressions; curves further left are better. The horizontal line at 0.95 marks the start of the worst 5% of streams. (a) Mean-based objectives, with or without adversarial inputs, achieve large improvements on most streams but leave a long regression tail. (b) Percentile objectives control only their tail cutoff, not the severity of regressions beyond it. Paired CVaR accounts for the entire tail, achieving better worst-5% performance while retaining substantial average improvements.
Synthesis objective
Mean cost improvement (%) ↑
Regressions (%) ↓
Worst-5% mean (%) ↓
Mean H′
25.7±20.8
6.4±5.8
+7.4±7.9
Mean Δ
29.8±17.3
7.5±5.0
+9.2±6.0
Mean Δ + attacker
39.0±1.7
10.4±1.5
+12.2±2.2
RAISE [ 49 ]
35.5±3.4
7.4±2.8
+8.6±3.1
95th pct. of H′
17.2±10.6
1.6±1.9
−0.6±4.2
95th pct. of Δ
12.3±6.9
0.2±0.2
−4.1±2.3
Table 1: Paired-CVaR balances mean cost improvement and tail robustness. Comparison of synthesis objectives on Azure GPU Batch Admission, evaluated on our target workload distribution of real Azure request streams. Results are mean ± standard deviation over five independent synthesis runs. Mean cost improvement ( E[H−H′] ) and tail differences are normalized by the magnitude of the baseline’s average cost. Δ=H′−H .
Figure 3: Mean-optimized heuristics fail predominantly on short streams. Regression rate against FCFS as a function of stream length. The mean-oriented curves rise sharply on the shortest streams, while the paired-tail objectives have much lower regression rates. Both classes of heuristics improve on nearly all longer streams.
Figure 5: Tailor end-to-end workflow. Given a baseline heuristic, a lower bound, a requested tail level βreq , and a workload distribution, Tailor first checks whether the certification target can be ruled out. If not, an LLM-based coding agent generates candidate heuristics using tail-focused feedback. The final candidate is evaluated on independent instances, and its paired differences with the baseline are used to determine the certification verdict.
Figure 6: Paired-CVaR objective achieves strong mean–tail trade-offs. Normalized mean cost improvement versus empirical paired CVaR at β=0.95 for (a) Azure VM packing and (b) server placement ( k -median). Both metrics are expressed as percentages of the baseline’s average cost magnitude. Markers show means over five independent synthesis runs, with standard-deviation bars. Higher mean improvement and lower paired CVaR indicate better performance.
Figure 7: Tailor achieves mean and tail improvements across six of seven benchmarks. Mean cost improvement versus empirical paired-CVaR on held-out workloads, normalized per problem by ∣E[H]∣ , the baseline’s average cost on the certification set. Markers show mean ± standard deviation over five independent synthesis runs. Labels indicate the number of certified runs out of five ( Tab. 2 ).
Figure 8: Small-scale worst-case feedback does not reliably transfer to large-scale tail robustness. Empirical paired-CVaR on large, held-out workloads after synthesis using distributional paired-CVaR or MetaEase-based small-scale maximum-gap feedback. Values are in each benchmark’s native units; lower is better. Error bars show standard deviations across five independent synthesis runs.
Figure 9: Best observed Tailor -generated heuristics versus human-designed controls. Empirical paired-CVaR relative to the same baseline, normalized by the magnitude of the benchmark-specific empirical floor F0.95<0 ( §B.1 ). Lower is better; −100% reaches the theoretical floor, which need not be attainable.
Figure 10: Coding-agent harnesses converge with stronger models. Tail improvement relative to the best harness for each benchmark and model ( 100% matches the best). Bars average across six benchmarks, with standard errors. The spread among the four coding-agent harnesses decreases from 17% with Sonnet 5.5 to 6% with Opus 5. GPT-4o-mini certifies none of its runs.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Benchmark
U (%)
Certified
Metric k -median
−0.22 to +371.68
3/5
Online VBP2D
0.00 to +93.07
0/5
Online weighted matching
−0.42 to +5.54
2/5
VBP2D
−0.29 to −0.18
5/5
TE MLU
−0.32 to 0.00
4/5
GPU Batch Admission (Azure)
−4.23 to −2.80
5/5
Appendix
Table 2: Certification at β=0.95 . Range of U across five synthesis runs, normalized by the magnitude of the baseline’s mean cost. For sampled distributions, U=UDKW with δ=0.01 ; for Azure VM Packing, U is the exact finite-population CVaR. Negative values indicate certified improvements.
Run
Paired CVaR
True change
H′=OPT
1
−6.3
−1685.4
79.1%
2
−27.0
−2117.3
94.9%
3
−12.7
−1734.4
69.6%
4
−27.4
−2142.8
95.5%
5
−27.7
−2156.9
97.6%
Appendix
Table 3: Small-scale Metric k -Median validation at β=0.95 using Engram (five Opus runs). The baseline tail optimality gap is 2,173.
Problem
Baseline
Human control
GPU Batch Admission
FCFS
Zhou et al. [ 81 ]
Azure VM packing
Tight packing
L2 best-fit [ 66 ]
Server Placement (Metric k -median)
GreedyAdd
2-swap local search [ 8 ]
Online weighted matching
Accept-if-free
Probe-based reservation
VBP2D
First Fit
LP rounding [ 45 ]
Online VBP2D
Online First Fit
Weighted L2 fit [ 66 ]
Appendix
Table 4: Baselines and human-designed comparisons. Makespan is ruled out in preflight.
Benchmark
Workload distribution
Online Weighted Matching
8–80 groups of weighted paths, with uniformly random arrival orders and weights.
VBP2D
16–400 items with randomly generated two-dimensional resource demands and unit-capacity bins.
Online VBP2D
8–80 perfectly packed bins, each split into 2–4 items whose two-dimensional demands sum to one bin’s capacity. The resulting 16–320 items arrive in random order.
TE MLU
Five real network topologies with varying uniformly random traffic patterns, load levels, and link failures.
Makespan
2–26 machines with uniformly randomly generated job processing times, plus constructed difficult instances.
Appendix
Table 5: Workload distributions used for synthetic benchmarks.
Benchmark
Offline optimum
Lower bound LB(I)
LB Time Complexity
Server Placement (Metric k -median)
k median; NP-hard [ 39 , 58 ] ; all center sets, O(nk+1)
LP relaxation of the k -median program; integral, hence exact, on 92% of instances
negated fractional-knapsack bound on captured value, filling in decreasing density order [ 16 ]
O(nlogn)
Online Weighted Matching
max-weight matching; polynomial, O(n∣E∣+n2logn) [ 18 , 20 ] , but one solve per instance
21∑vmaxe∋vwe (negated for minimization): each vertex is matched at most once and each matched edge is counted at both ends; exact on the disjoint gadget grammar
max(⌈∑jpj/m⌉,maxjpj) : average load and longest job
O(n)
Appendix
Table 6: Offline optimum and preflight lower bound per benchmark. Every bound is a relaxation of the offline optimum. n : items, jobs, clients, or vertices; d : demands; C : knapsack capacity; O∗ hides polynomial factors.
Figure 12: Tail improvements extend beyond the level used for synthesis. Mean Δ over the worst X% of streams for each objective (lower is better). The dashed vertical line is X=5% , the fraction optimized by paired CVaR. Its measured advantage persists across the plotted tail fractions, from 20% to 0.5%; these observations are not a guarantee for every tail level.
Figure 13: Performance certification does not imply constraint compliance. Each point shows the certificate and isolated p95 latency of a generated metric k -median candidate.
Systems resource management tasks rely primarily on hand-designed heuristics. However, growing hardware heterogeneity and workload diversity require heuristics specialized to particular deployment instances, making manual design expensive and difficult to scale. In this paper, we explore how to synthesize systems heuristics using LLMs. The main challenge is ensuring that generated heuristics execute safely, integrate correctly with the surrounding system, and still achieve strong performance. We propose Vulcan, a framework that identifies LLM-friendly interfaces that isolate core decision logic from the rest of the implementation. With Vulcan, LLM-generated code is restricted to simple stateless decision functions, while trusted runtime abstractions provide rich derived statistics for meaningful policy exploration without system-integration bugs. To ensure execution safety, LLMs synthesize heuristics in a restricted language, Anvil, that guarantees important properties by construction. We evaluate Vulcan across three well-studied domains and demonstrate up to 4.9× higher savings for spot-VM scheduling, up to 2× lower miss ratios for cache eviction, and up to 14% higher application performance for tiered-memory systems, while ensuring execution safety throughout.
Large language models have recently been used to discover heuristics through iterative program search, offering a promising approach to automated algorithm design. However, candidates selected by average performance may degrade across instance families, random seeds, and problem scales because mean-based objectives can obscure rare but severe failures. We propose CVaR-RMD, a risk-sensitive evolutionary framework that uses an LLM to mutate executable heuristic programs and ranks candidates by empirical conditional value-at-risk over heterogeneous evaluation conditions. Across three combinatorial optimization domains, CVaR-based selection improves upper-tail performance and reduces failure rates while maintaining competitive mean performance. These gains persist on larger unseen instances and independently curated within-domain benchmarks
Ruodai Cui, Li Niu
Qualcomm Technologies, Inc. · The Hong Kong Polytechnic University · Department of Computer Science and Engineering, MoE Key Lab of Artificial Intelligence, Shanghai Jiao Tong University
Automated Heuristic Design (AHD) with Large Language Models (LLMs) has shown remarkable progress in discovering high-quality heuristics. However, existing LLM-based AHD methods optimize heuristics for a fixed training instance set and may fail catastrophically when deployed under real-world distributional shifts. We propose Robust Adversary Instance Search (RAISE), a framework that integrates constrained worst-case instance search within a principled neighborhood of the training distribution into the LLM-based evolutionary search loop. RAISE treats robust AHD as a constrained adversarial instance search problem: the outer loop evolves heuristics via LLM operators, while an LLM-free inner loop efficiently identifies hard instances within an epsilon-ball around the training instance set using a basis distribution parameterization with boundary projection. Comprehensive experiments on Online Bin Packing (OBP), Online Job Shop Scheduling (OJSP), and Online Vehicle Routing (OVRP) across five distribution families demonstrate that existing LLM-based AHD methods degrade by up to 19 times under distribution shift, while RAISE consistently maintains strong performance across all tested distributions and problem scales