TAILOR targets the risky tail of AI-generated computer-system heuristics

Why averages can hide risky replacements

Computer systems use heuristics—practical decision rules—to schedule jobs, pack virtual machines and allocate resources when exact optimization is too expensive or future requests are unknown. Large language models can generate these rules, but choosing candidates by average performance can conceal serious regressions.

In their preprint, Karimi and colleagues illustrate the problem with GPU batch admission using Azure inference traces. A policy must accept or reject incoming requests without knowing when the stream will end. Rejecting low-value requests can reserve capacity for better arrivals, but on short streams that capacity may remain unused.

The authors report that heuristics optimized for the mean candidate–baseline difference underperformed a first-come, first-served baseline on 7.5% of held-out streams. Their average regression across the worst 5% of paired outcomes was 9.2%, normalized by the baseline’s average admitted value. Adding adversarial training inputs did not eliminate regressions in the tested configurations.

Score the whole tail, relative to a baseline

The proposed framework, TAILOR, evaluates the candidate and baseline on the same workload. It subtracts baseline cost from candidate cost, so negative differences indicate improvement. Maximization tasks are converted into cost-minimization form by negating rewards.

TAILOR then minimizes conditional value at risk, or CVaR, of these paired differences. At the paper’s chosen level of 0.95, this means averaging the worst 5% of differences.

This differs from optimizing a percentile. A percentile identifies a cutoff but does not describe how severe outcomes become beyond it. CVaR incorporates the entire selected tail. Comparing paired differences also avoids treating every expensive workload as a heuristic failure: some workloads are inherently difficult.

For GPU admission, the authors report a 12.3% average cost improvement with TAILOR, regressions on fewer than 0.01% of streams, and a worst-5% average difference of −6.0%. These results trade some average improvement for stronger tail performance than mean optimization. The reported percentages use the baseline’s average value as their normalization, not each stream’s individual value.

What the certificate establishes

The theoretical result concerns an optimality gap: the difference between a heuristic’s cost and the best possible cost for that workload. Computing that optimum repeatedly would be impractical for many synthesis tasks.

The authors show that a negative population CVaR of paired differences is sufficient to reduce the CVaR of optimality gaps, without computing the optimum. It also implies better average performance, because the worst-tail average difference cannot be smaller than the overall average difference.

This is an aggregate guarantee, not a promise that every workload improves. The workloads with the worst paired differences also need not be those with the largest optimality gaps.

For sampled distributions, TAILOR fixes the selected candidate and evaluates it on independent workloads unavailable during synthesis or selection. A confidence bound accounts for sampling uncertainty and requires a valid upper bound on possible regression. A negative upper bound supports certification at 99% confidence per candidate; otherwise, the result is inconclusive. For Azure VM packing, the authors instead evaluate the entire declared finite population and calculate its CVaR exactly.

Results and limits

Across seven synthesis benchmarks, the authors report certification in 24 of 35 independent runs, with at least one certified run on six benchmarks. All five runs succeeded on GPU admission, Azure VM packing and offline two-dimensional vector bin packing. None succeeded on online two-dimensional vector bin packing.

In the other two main case studies, TAILOR also improved average performance more than mean optimization: the reported average gains were 14% larger for Azure VM packing and 66% larger for server placement. The best observed TAILOR heuristics outperformed the selected human-designed controls on paired-tail performance across six benchmarks.

A preflight check can rule out some unattainable certificate targets when the baseline already achieves a valid optimality lower bound sufficiently often. Passing that check does not establish that a certifiable replacement exists, and failing certification does not prove improvement impossible.

The guarantees remain distribution-specific: changed workloads require re-certification. Regression bounds are currently derived manually and can be conservative. Finally, solution-quality certification does not certify execution speed. Many generated server-placement heuristics exceeded latency allowances on unseen workloads despite training-time filtering. The preprint therefore supports a narrower conclusion than universal robustness: changing the search objective can improve measured tail behavior, while independent certification defines where that claim is justified.