betaFeedback

WorksComputer Science

Robustness Starts with the Objective: Designing and Certifying Robust LLM-Generated Heuristics

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.

Introduction

Computer systems rely on heuristics to allocate resources, pack workloads, schedule jobs, and route traffic [73, 57, 25, 29]. These heuristics aim to minimize cost or maximize utility when computing an exact optimal solution (OPT) is computationally intractable or requires knowledge of future inputs. Designing effective heuristics requires substantial human expertise to exploit problem structure while maintaining reliable performance across diverse workload regimes.

LLMs have opened new opportunities to automate heuristic design. Recent frameworks use different search harnesses, including evolutionary search, orchestrated agents, and iterative refinement, to generate candidate programs, evaluate them on test inputs, and use the resulting scores to guide the search [46, 36, 38, 28, 72, 65].

Despite differences in search architecture, most LLM-based heuristic design frameworks optimize for average performance and give limited attention to robustness. FunSearch [72] and EoH [48] score candidates by their mean performance on a fixed training set, while EoH-S [50] evolves a portfolio of heuristics over a predefined set of diverse instances. Even recent methods that target robustness do not directly optimize tail or worst-case performance during search. RAISE [49] adds adversarially discovered hard instances to its evaluation set, but still ranks candidates by their mean score over that set, arguing that scoring based on the worst lets single outlier instances dominate and destabilize the search [49]. But in production, good average performance can hide severe regressions on specific workloads. For example, MetaOpt [64] identified a traffic pattern on which a production heuristic in Microsoft’s WAN served 40% less demand than the optimal solution.

In this paper, we seek to automate the design of robust heuristic improvement: improving tail performance without sacrificing average performance. Let I∼DI \sim\mathcal{D} denote a workload drawn from a target distribution D\mathcal{D}, HH an existing baseline heuristic, and H′H' a replacement generated by an LLM. We write H(I)H(I) and H′(I)H'(I) for their performance on the same workload, expressed as costs to minimize (maximization problems are handled by negating rewards). For example, in GPU Batch Admission (§2), requests arrive sequentially and compete for limited batch capacity. Here, II is a stream of requests, HH could be first-come, first-served (FCFS), and H′H' a candidate LLM-generated policy. Their performance, H(I)H(I) and H′(I)H'(I), is the negative of the total value admitted on that stream. OPT(I)(I) denotes the best possible cost had all future requests been known in advance. The optimality gap, H(I)−OPT(I)H(I) - \mathrm{OPT}(I), measures how much value the baseline leaves on the table. A heuristic may perform well on average while suffering large optimality gaps on a fraction of workloads. Our goal is to find a replacement H′H' via LLMs that reduces the tail of these optimality gaps while preserving or improving average performance over DD (Figure 1).

Distributions of baseline and candidate optimality gaps, showing the worst-5% regions and cutoffs

Figure 1. Goal: improve tail optimality gaps while preserving average performance. Distributions of optimality gaps H−OPTH - \mathrm{OPT} and H′−OPTH' - \mathrm{OPT} for GPU batch admission (§ 2), where HH and H′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′H' reduces the tail optimality gap by 14% while preserving average performance.

To control tail regressions, we would ideally optimize the tail of the candidate’s optimality gaps directly (Figure 1). However, the challenge is that computing OPT across large-scale workloads is impractical. Existing tools such as MetaOpt [64] and MetaEase [37] identify worst-case failures relative to OPT, but require formal models or expensive OPT evaluations, taking minutes to hours even on small instances (§C.1). Other tools have similar problems [5, 2, 7, 4, 74, 35, 23]. This makes them impractical for iterative LLM synthesis, which must evaluate thousands of candidate heuristics. A simpler alternative, optimizing the tail of H′H' directly (e.g., its 95th-percentile cost), is also insufficient (§ 2). A high cost may reflect an inherently difficult workload rather than poor heuristic performance, as even an optimal solution may incur a high cost. We therefore need a scalable objective that measures tail performance relative to the baseline without computing OPT.

The second challenge is the tension between average performance and tail robustness, which arises in many problems [82]. In GPU Batch Admission, optimizing average performance leads LLMs to discover heuristics that achieve large average improvements while incurring severe regressions on some workloads. We need an objective that accounts for how often regressions occur and how severe, without sacrificing average performance.

Our approach: Optimizing the tail of paired differences. We introduce TAILOR, a framework for synthesizing robust heuristic improvements with LLMs. Rather than computing OPT, we evaluate the candidate and baseline on the same workload and compute their paired difference, Δ(I)=H′(I)−H(I)\Delta(I) = H'(I) - H(I). This directly measures the impact of replacing the baseline and requires only running the two heuristics, making it practical feedback for iterative LLM search.

Even with paired differences, simple tail metrics provide poor feedback for LLM search. Optimizing a fixed percentile (e.g., the 95th percentile of Δ\Delta) ignores how severe regressions get beyond the cutoff, while using the single worst-case difference lets isolated outliers dominate heuristic selection (§ 5.2). We instead minimize the Conditional Value-at-Risk (CVaR) of paired differences [70, 71]. At β=0.95\beta=0.95, CVaRβ(Δ)\mathrm{CVaR}_{\beta}(\Delta) averages the worst 5% of candidate–baseline differences, capturing both how often regressions occur and how severe they are.

Certifying tail improvements without OPT. We show a negative population CVaRβ(Δ)\mathrm{CVaR}_{\beta}(\Delta) guarantees that replacing the baseline HH with H′H' reduces the average optimality gap in the worst 1−β1-\beta tail of the workload distribution. This guarantees an improvement relative to OPT without ever computing OPT, using only the observable performance differences between the two heuristics (§ 3).

Guaranteeing average improvement. CVaR has a second useful property: the average of the worst performance differences is always at least as large as their overall average. Therefore, if even the worst-tail average difference is negative, the overall average difference must also be negative. A negative paired CVaR therefore guarantees average improvement, without explicitly optimizing for the mean or imposing a separate constraint.

This guarantee holds for the full distribution, but in practice we can only evaluate a candidate on a finite sample. To account for sampling uncertainty, TAILOR evaluates the final heuristic on independent validation workloads and computes a statistical upper confidence bound on its paired CVaR [56]. If this bound is negative, we certify with 99% confidence that the heuristic improves both tail optimality gaps and average performance over the targeted distribution. We also introduce a simple check to detect when it is unlikely that we would be able to certify an improvement before synthesis. This enables us to avoid the expensive LLM-based synthesis when the requested certification target is unattainable (§ 3).

We evaluate TAILOR across three case studies on realistic workloads: Azure GPU Batch Admission [75, 6, 1], Azure VM Packing [60, 27], and Server Placement [68]. Holding the LLM and synthesis architecture fixed, we compare different synthesis objectives, measuring each heuristic’s average improvement and its performance relative to the baseline on the worst 5% of paired differences.

TAILOR improves tail performance over mean-optimized heuristics. On GPU Batch Admission, mean-optimized heuristics underperform the FCFS baseline on 7.5% of streams, with an average regression of 9.2% over the worst 5% of streams. Adding adversarial inputs does not eliminate regressions: RAISE [49] still regresses the baseline on 7.4% of streams. TAILOR regresses on fewer than 0.01% of streams (§ 2). On Server Placement, TAILOR turns an average regression over the worst 5% of inputs into an improvement. On VM Packing, it delivers a 25% larger average improvement over the worst 5% of inputs than mean-optimized heuristics (§ 4).

TAILOR improves tail performance more than percentile-based optimization. Across all three case studies, TAILOR delivers 46–62% larger average improvements over the baseline on the worst 5% of inputs than heuristics synthesized by optimizing the 95th percentile of paired differences (§ 2, § 4).

TAILOR certifies its tail improvements. Across the three case studies and four additional synthesis benchmarks, TAILOR certifies improvements in tail optimality gaps in 24 of 35 independent synthesis runs at 99% confidence, with successful certification on six of the seven benchmarks (§ 5.1).

TAILOR outperforms robust human-designed heuristics in the tail. Across six benchmarks with known robust human-designed heuristics, the best TAILOR-generated heuristics achieve a better worst-5% average relative to the same baseline. On Traffic Engineering and VM Packing, human-designed heuristics regress on average in their worst 5% of outcomes, while TAILOR-generated heuristics still improve over the baseline (§ 6).

TAILOR also improves average performance. Across all cases, TAILOR achieves better average performance over the baseline heuristic. Also on VM Packing and Server Placement, TAILOR beats mean-optimized heuristics and achieves 14% and 66% larger average improvements.

Motivation: What Should We Optimize for Robustness?

What should an LLM optimize when designing a replacement for an existing heuristic, when we aim to be more robust-in-tail while maintaining the average performance?

We discuss this through a running example: Azure GPU Batch Admission, using streams of requests from Azure LLM-inference traces [75, 61]. We model admission as an online knapsack problem: each request has a value proportional to its token count and a weight given by the batch capacity it consumes, and the batch has a fixed capacity. Requests arrive sequentially, and the heuristic must accept or reject each request without knowing how many more will arrive. The goal is to maximize the total value of admitted requests, which we use as a proxy for GPU utilization.

In this example, baseline HH is first-come, first-served (FCFS). A generated heuristic H′H' can do better by passing over low-value requests in anticipation of more valuable arrivals.

The risk is that the stream might end before those arrivals appear, leaving capacity unused. We express the performance of HH and H′H' as a minimization.

Ideally, we would evaluate each new heuristic H′H' against the optimum. However, computing OPT is expensive even on modest-sized instances [64]. OPT-based synthesis feedback is therefore computationally prohibitive. We therefore compare a candidate to the baseline. On the same stream II, we write Δ(I)=H′(I)−H(I)\Delta(I) = H'(I) - H(I); so Δ<0\Delta< 0 is an improvement and Δ>0\Delta> 0 is a regression.

We examine which synthesis objectives produce heuristics that improve on the baseline without severe regressions. Starting with mean optimization, we investigate whether harder training inputs or increasingly tail-aware objectives lead to more robust replacements.

We use Engram [38] with Claude Opus 5 as the backend model to synthesize heuristics. We train on the first two calendar days of Azure traces and evaluate on five later, held-out days, with no overlapping requests. For each objective, we run five independent syntheses, holding the model, harness, workloads, and search budget fixed. We additionally evaluate RAISE [49], a recent approach that incorporates adversarial instance search. Table 1 summarizes them, while Figure 2 shows their paired-difference distributions.

Synthesis objectiveMean cost improvement (%) ↑Regressions (%) ↓Worst-5% mean (%) ↓
Mean H′H'25.7±20.86.4±5.8+7.4±7.9
Mean Δ\Delta29.8±17.37.5±5.0+9.2±6.0
Mean Δ\Delta + attacker39.0±17.710.4±1.5+12.2±2.2
RAISE [49]35.5±3.47.4±2.8+8.6±3.1
95th pct. of H′H'17.2±10.61.6±1.9−0.6±4.2
95th pct. of Δ\Delta12.3±6.90.2±0.2−4.1±2.3
99th pct. of Δ\Delta8.7±4.9<0.01−4.6±2.6
Zhou et al. [81] (human)6.20.0−2.4
Mean worst 5% of Δ\Delta (ours)12.3±0.8<0.01−6.0±0.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′]\mathbb{E}[H-H']) and tail differences are normalized by the magnitude of the baseline’s average cost. Δ=H′−H\Delta= H' - H.

CDF plots comparing average and tail objectives

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\Delta= 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.

Start with the average. Most LLM-based heuristic design frameworks optimize average performance [72, 80, 48, 65, 12]. We compare minimizing the candidate’s mean cost, E[H′]\mathbb{E}[H'], and its mean difference from the baseline, E[Δ]\mathbb{E}[\Delta], which differ by a constant for a fixed workload distribution. Both achieve substantial average improvements, yet regress against FCFS on 6–8% of Azure streams (Figure 2, Table 1).

The striking observation is where the regressions occur.

These regressions are concentrated on short streams (Figure 3). The reason lies in the strategy the LLM discovers: the mean-optimized heuristic (Figure 4, left) aggressively rejects low-value requests in anticipation of more valuable future arrivals. On long streams, the heuristic can reject many low-value requests and still fill the batch. On short streams, however, each rejection risks leaving capacity unused, because few requests remain to replace it. Since the heuristic does not know when the stream will end, improvements on longer streams can outweigh severe regressions on shorter ones, making this risky strategy attractive under mean optimization.

Regression rate against stream length

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.

Generated heuristics for mean and paired-CVaR objectives

Figure 4. The objective changes how the LLM handles uncertainty about future arrivals. Excerpts from generated heuristics per objective. The mean-optimized heuristic derives its threshold from a forecast of remaining arrivals (left). The paired-CVaR heuristic tracks how many requests it has rejected and uses remaining capacity to govern later rejections (right).

What if we search for harder inputs? Recent work suggests that mean optimization may fail in the tail because training workloads do not sufficiently expose the agents to difficult cases [36, 82]. We test whether exposing the agent to harder workloads can prevent these regressions without changing the mean-based synthesis objective. We consider two approaches: RAISE [49], which generates adversarial workloads by perturbing request values while preserving stream lengths, and Mean Δ\Delta + attacker, which searches for difficult, unmodified Azure streams of varying lengths.

Neither eliminates regressions: RAISE and Mean Δ\Delta + attacker regress on 7.37% and 10.40% of held-out streams, respectively (Table 1). Finding difficult inputs does not determine how to weigh them against improvements elsewhere.

What if we optimize the tail percentiles? We first minimize

the candidate’s 95th-percentile cost. Although this reduces regressions (Table 1), a high cost of H′H' may simply reflect a difficult workload rather than poor performance relative to the baseline. Optimizing the 95th percentile of Δ\Delta further reduces regressions, but only controls the tail cutoff and ignores the regressions beyond it. Moving to the 99th percentile targets rarer regressions, but reduces average cost improvement from 12.3% to 8.7%. Neither percentile captures the severity of regressions throughout the tail.

Our approach: Look at the whole tail, not only its percentile. These results motivate an objective that accounts for the severity of tail regressions while preserving average performance. Unlike a percentile, Conditional Value-at-Risk (CVaR) captures the magnitude of losses throughout the tail. We therefore minimize CVaR⁡0.95(Δ)\operatorname{CVaR}_{0.95}(\Delta), the average of the worst 5% of paired differences [70, 10]. If this average is negative, the candidate improves on the baseline even on its worst 5% of paired outcomes, which implies improvement on average across the full workload distribution. Thus, a negative population CVaR provides a sufficient condition for average improvement while avoiding severe tail regressions.

This changes the strategy the LLM discovers. Rather than continually waiting for better arrivals, CVaR-generated policies limit how much they wait. The heuristic in Figure 4 (right) limits early rejections and adapts to remaining capacity, substantially reducing short-stream regressions (Figure 3). Interestingly, it independently discovers a mechanism similar to the human-designed heuristic of Zhou et al. [81], which also limits rejections. While the human heuristic achieves a 6.2% average cost improvement with no observed regressions, CVaR-generated policies achieve a 12.3% cost improvement with rare regressions (Table 1). Their measured tail improvements also extend beyond the 5% level used during synthesis (Figure 12).

Tail improvements over worst-case stream fractions

Figure 12. Tail improvements extend beyond the level used for synthesis. Mean Δ\Delta over the worst X%X\% of streams for each objective (lower is better). The dashed vertical line is X=5%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.

These results suggest that robust heuristic design requires an objective that measures both baseline-relative performance and the severity of tail losses. However, observed improvements alone do not establish robustness on unseen workloads. This motivates TAILOR, which uses the same paired-CVaR objective not only to guide heuristic synthesis, but after synthesis, to statistically certify improvements in tail optimality gaps, without computing OPT. We formalize this connection in the next section.

Tailor: Tail-Aware LLM Optimization for Robustness

§ 2 showed how the synthesis objective affects both heuristic performance and the strategies LLMs discover. TAILOR turns paired-CVaR feedback into a workflow for synthesizing and certifying robust heuristics without computing OPT (Figure 5). It consists of three stages: checking certificate feasibility, synthesizing candidate heuristics, and independently certifying improvements on unseen workloads.

TAILOR end-to-end workflow

Figure 5. TAILOR end-to-end workflow. Given a baseline heuristic, a lower bound, a requested tail level βreq\beta_{\mathrm{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.

Certifying Tail Improvement Without OPT

Our goal is to reduce the tail of the optimality gap (Figure 1). Let HH denote the baseline heuristic, H′H' a candidate replacement heuristic, and OPT⁡(I)\operatorname{OPT}(I) the optimal cost for workload I∼DI \sim\mathcal{D}. We express performance as a cost to minimize, so H(I)−OPT⁡(I)H(I)-\operatorname{OPT}(I) is the baseline’s optimality gap. Maximization problems are handled by negating the cost; all subsequent guarantees apply unchanged. At tail level β\beta, we want the worst 1−β1-\beta fraction of the candidate’s gaps to be smaller, on average, than the worst 1−β1-\beta fraction of the baseline’s gaps. Throughout the paper, the requested level βreq\beta_{\mathrm{req}} is 0.95.

Directly comparing these gaps requires computing OPT over many large-scale workloads, which can be prohibitively expensive for combinatorial problems and impractical for repeated LLM-based search (§C.1). Instead, we use the observable paired difference Δ(I)=H′(I)−H(I)\Delta(I)=H'(I)-H(I), obtained by evaluating both heuristics on the same workload.

An observable certificate. Since H′−OPT⁡=(H−OPT⁡)+ΔH' - \operatorname{OPT} = (H-\operatorname{OPT})+\Delta, subadditivity of CVaR [6, 1] gives

CVaR⁡β(H′−OPT⁡)−CVaR⁡β(H−OPT⁡)≤CVaR⁡β(Δ).(1)\operatorname{CVaR}_{\beta}(H'-\operatorname{OPT})-\operatorname{CVaR}_{\beta}(H-\operatorname{OPT}) \le\operatorname{CVaR}_{\beta}(\Delta). \tag*{(1)}

The left-hand side is the improvement we want to establish; the right-hand side is the quantity we can measure. In particular, if CVaR⁡β(Δ)<0\operatorname{CVaR}_{\beta}(\Delta)<0, then the candidate has a strictly smaller tail optimality gap than the baseline under D\mathcal{D}, even though we never computed OPT⁡\operatorname{OPT} (proof in §A.2). An analogous bound does not hold for quantiles.

Also, since the average of the worst 1−β1-\beta fraction is at least the overall average, we have:

E[H′−H]≤CVaR⁡β(H′−H).(2)\mathbb{E}[H^{\prime}-H]\leq\operatorname{CVaR}_{\beta}(H^{\prime}-H). \tag*{(2)}

Thus, a negative paired CVaR also implies an average improvement over the baseline.

If CVaR⁡β(H′−H)\operatorname{CVaR}_{\beta}(H^{\prime}-H) is negative, we certify improvements in both tail robustness (at β=0.95\beta=0.95, covering the worst 5% tail) and average performance relative to the baseline.

Checking Headroom Before Synthesis

Before searching for a heuristic with negative paired CVaR, we ask: can any feasible replacement heuristic achieve that certificate? For example, suppose the baseline is already optimal on 10% of workloads. No feasible candidate can improve on the baseline for these workloads, so H′(I)−H(I)≥0H^{\prime}(I)-H(I)\geq0 for at least 10% of the distribution where H′(I)≥H(I)=OPT⁡(I)H^{\prime}(I)\geq H(I)=\operatorname{OPT}(I). Consequently, the worst 5% of paired differences must also be nonnegative, implying CVaR⁡0.95(Δ)≥0\operatorname{CVaR}_{0.95}(\Delta)\geq0 for every feasible candidate. A negative certificate is therefore impossible at β=0.95\beta=0.95. In this example, β\beta must be below 0.9.

Detecting this limit without OPT. Determining where the baseline is optimal would itself require solving for OPT⁡\operatorname{OPT}. We show that a valid lower bound LB⁡(I)≤OPT⁡(I)\operatorname{LB}(I)\leq\operatorname{OPT}(I) can establish baseline optimality without computing OPT⁡\operatorname{OPT}. For example, in VM packing, dividing total resource demand by per-machine capacity and rounding up yields a lower bound on the number of machines required. Whenever H(I)=LB⁡(I)H(I)=\operatorname{LB}(I), the baseline is optimal. The probability of this event therefore determines a candidate-independent certification ceiling:

βceil=1−Pr⁡I∼D[H(I)=LB⁡(I)].(3)\beta^{\mathrm{ceil}}=1-\Pr_{I\sim\mathcal{D}}[H(I)=\operatorname{LB}(I)]. \tag*{(3)}

At requested tail βreq≥βceil\beta_{\mathrm{req}}\geq\beta^{\mathrm{ceil}}, no feasible candidate can achieve a strictly negative paired-CVaR certificate (App. § 11).

Preflight decision. TAILOR first estimates the fraction of workloads on which H=LB⁡H=\operatorname{LB} (Figure 5) from sampled workloads and uses a one-sided confidence bound to rule out certification only when the evidence is sufficient (App. § 11). Otherwise, synthesis proceeds. Passing this check does not guarantee that a certifiable candidate exists; it only means that we have not ruled one out. When a cheap valid lower bound is not available, preflight can be skipped.

Using CVaR to Design Candidate Heuristics

If the target has not been ruled out, TAILOR uses an LLM-based harness to propose candidate H′H^{\prime}, executes it alongside the baseline on training workloads, and returns the empirical CVaR⁡βreq(H′−H)\operatorname{CVaR}_{\beta_{\mathrm{req}}}(H^{\prime}-H) on the training data to the agent. Minimizing this score rewards policies that improve the worst baseline-relative outcomes, rather than allowing improvements elsewhere to conceal severe regressions (§ 2). Because candidates are assessed repeatedly during synthesis, TAILOR uses fewer training samples than the certification in the next step to keep training feedback affordable.

From a Candidate to a Statistical Certificate

After synthesis, we fix the selected candidate and evaluate it alongside the baseline on independent held-out workloads. Our theoretical guarantee requires the population paired CVaR to be negative. However, observing a negative empirical CVaR is not sufficient: the candidate might perform worse on workloads we have not sampled. We use the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality [17, 56] for two purposes. First, it guides the number of independent workloads needed for certification at a desired confidence level (δ\delta) and quantile resolution. Second, it provides an upper confidence bound UDKWU_{\mathrm{DKW}} on the population paired CVaR, accounting for sampling uncertainty (§A.5).

For a fixed candidate, if UDKW<0U_{\mathrm{DKW}} < 0, we certify improvements in both mean performance and tail optimality gaps with confidence at least 1−δ1-\delta. We use δ=0.01\delta= 0.01, corresponding to 99% confidence. Otherwise, the result is inconclusive, even if the empirical CVaR is negative.

Evaluations

We use Engram [38] with Claude Code (Opus 5), a $30 synthesis budget per run, and five independent runs per configuration. TAILOR optimizes paired CVaR at β=0.95\beta= 0.95. Final candidates are evaluated on held-out workloads not used during synthesis. We use 99% confidence for statistical certification (§A.5), approximately 28,000 independent workloads per benchmark. We express all problems as costs to minimize and define Δ=H′−H\Delta= H' - H, where negative values indicate improvements over the baseline. We report normalized mean cost improvement as −E[Δ]/∣E[H]∣-\mathbb{E}[\Delta]/|\mathbb{E}[H]| and normalized paired CVaR as CVaR⁡0.95(Δ)/∣E[H]∣\operatorname{CVaR}_{0.95}(\Delta)/|\mathbb{E}[H]|, both expressed as percentages. Higher mean cost improvement indicates better average performance, while lower paired CVaR indicates better tail performance. In particular, negative paired CVaR means that even the worst 5% of paired differences are negative on average.

Case-Study: Azure VM Packing

We study online VM packing using production Azure traces [60, 27]. VMs arrive sequentially and must be assigned to machines with sufficient CPU and memory capacity, aiming to minimize the number of machines used. The baseline is tight packing (Kubernetes “MostAllocated”) [44], which places each VM on the machine it fills most. We use a capacity-based lower bound on the optimum.

Figure 6(a) shows that paired-CVaR achieves the largest mean cost improvement and lowest empirical CVaR⁡0.95(Δ)\operatorname{CVaR}_{0.95}(\Delta) among the evaluated objectives. Compared with mean-optimized heuristics, it achieves 14% larger mean cost improvements and reduces empirical paired CVaR from −3.93% to −4.92%, a 25% larger tail improvement. Compared with optimizing the 95th percentile of Δ\Delta, paired-CVaR increases mean cost improvement from 5.26% to 8.54% and reduces empirical CVaR⁡0.95(Δ)\operatorname{CVaR}_{0.95}(\Delta) from −3.04% to −4.92%. Paired-CVaR is also the only objective that certifies all five synthesis runs, with no observed regressions and the lowest run-to-run variability.

Paired-CVaR results for Azure VM packing and server placement

Figure 6. Paired-CVaR objective achieves strong mean–tail trade-offs. Normalized mean cost improvement versus empirical paired CVaR at β=0.95\beta= 0.95 for (a) Azure VM packing and (b) server placement (kk-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.

Case-Study: Server Placement (kk-Median)

We consider kk-median server placement, where kk server locations are selected to minimize total client–server distance [68]. Workloads include spatially dispersed and clustered clients [9]. The baseline greedily selects locations that minimize service cost, and we use an LP relaxation as a lower bound. Unlike online admission control, all client locations are known, allowing us to test robustness under spatial workload variation rather than uncertain arrivals.

As shown in Figure 6(b), paired-CVaR achieves 66% larger mean cost improvements than mean-optimized heuristics (7.84% vs. 4.71%), while changing empirical CVaR⁡0.95(Δ)\operatorname{CVaR}_{0.95}(\Delta) from +0.65% to −0.57%. Mean-optimized heuristics have positive paired CVaR, while TAILOR-generated heuristics achieve negative paired CVaR. All five runs have negative empirical paired CVaR, and three of five are statistically certified (§A.5). In contrast, optimizing either the 99th percentile of Δ\Delta or the 95th percentile of H′H' certifies only two of five runs.

Across these case studies (§ 2, § 4), paired-CVaR offers the strongest mean–tail trade-off among the evaluated synthesis objectives. Paired-CVaR achieves negative empirical CVaR0.95(Δ)_{0.95}(\Delta) across all three problems and retains substantial mean improvements. It certifies all five synthesis runs on both Azure benchmarks and three of five on Server Placement.

Ablation Studies

The case studies show how synthesis objective affects heuristic performance and the strategies LLMs discover. We now evaluate if these improvements generalize across other benchmarks, how they compare with worst-case feedback and human-designed heuristics, and how certification depends on model capability and search architecture. Unless noted, we use the setup from § 4. Workload, complexity, and lower-bound details are in App. § 12.

Benchmarks We evaluate five additional benchmarks; Makespan is ruled out at preflight, leaving seven for synthesis.

Online Weighted Matching. Weighted edges arrive sequentially on a graph and must be accepted or rejected irrevocably, with no two accepted edges sharing an endpoint [41, 59]. The goal is to maximize the total weight of accepted edges. This models throughput allocation in datacenter networks [63, 34]. The baseline heuristic accepts an edge whenever both endpoints are available.

Two Dimensional Vector Bin Packing (VBP2D). We study offline and online resource packing, aiming to use as few machines as possible to meet CPU and memory demands [22, 33, 66]. The baseline for both is First Fit. These workloads differ from the Azure VM Packing and are synthetic workloads (App. § 12).

Traffic Engineering (TE MLU). We route traffic to minimize maximum link utilization [19, 29, 31, 10], using shortest-path routing as the baseline. We evaluate SWAN, Abilene, B4, Uninet, and Cogentco topologies [29, 31, 43].

Makespan. We assign jobs with processing times to identical machines, aiming to minimize the makespan [25]. The baseline is Longest Processing Time first (LPT), which assigns jobs in decreasing order of processing time to the least-loaded machine. This problem is ruled out in the preflight phase at requested certificate level because LPT matches the lower bound on 35.5% of workloads (§B.3).

Tailor Finds Certifiable Improvements Across Diverse Problems

Across seven different benchmarks, TAILOR certifies improvements in mean performance and tail optimality gaps in 24 of 35 independent synthesis runs (Figure 7). All five runs are certified

Mean cost improvement versus empirical paired-CVaR on held-out workloads

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]∣|\mathbb{E}[H]|, the baseline’s average cost on the certification set. Markers show mean ±\pm standard deviation over five independent synthesis runs. Labels indicate the number of certified runs out of five (Table 2).

on Azure GPU Batch Admission (§ 2), Azure VM Packing, and Offline VBP2D. Certification also succeeds in four of five runs on TE MLU, three of five on server placement, and two of five on Online Weighted Matching.

In Online VBP2D, candidates improve average performance, but none of the five runs certifies a tail improvement. Even though preflight does not rule out headroom (§B.3), no tested model (GPT-4o-mini, Sonnet 5.5, Opus 5), training objective (§ 2), or synthesis harness [38, 36] achieves certification (§ 6.1). Optimizing a tail-aware objective does not guarantee that search will find a certifiably robust heuristic, nor does passing preflight establish that one is reachable. So, TAILOR’s post-synthesis certification remains essential to catch these cases and prevent operators from deploying heuristics with unverified tail risk.

Small-Scale Worst-Case Optimization Does Not Ensure Tail Robustness

In this section, we ask whether a heuristic optimized to directly reduce the optimality gap on small-scale instances, where computing OPT is affordable, is also robust at larger scales. We use MetaEese [37] to discover large optimality gaps on these small-scale workloads and use the largest discovered gap as synthesis feedback. We compare this with distributional paired-CVaR feedback, using the same Opus 5 model and Engram harness. Both approaches are evaluated on the same larger, held-out workload distributions.

Figure 8 shows that reducing worst-case optimality gaps on small instances does not necessarily improve tail robustness on larger workloads. The clearest difference is on Online Weighted

Small-scale worst-case feedback comparison across TE MLU, Online VBP2D, and Online Matching

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.

Matching: paired-CVaR synthesis achieves negative empirical paired CVaR, while maximum-gap synthesis produces substantial tail regressions. The two perform similarly on TE MLU. On Online VBP2D, neither achieves negative empirical paired CVaR on average, but maximum-gap heuristics regress on 11% of held-out workloads, compared with 0.08% for paired-CVaR heuristics.

Generated Heuristics Outperform Human Controls

We evaluate the strength of the certified improvements by comparing generated heuristics with strong human-designed alternatives, and by measuring how conservative the certificate is relative to the true change in tail optimality gaps.

Comparison with human-designed heuristics. We compare the best heuristics generated by TAILOR with established human-designed controls (Table 4). Figure 9 reports their empirical paired-CVaR relative to the same baseline and workload distribution. Across all six benchmarks, TAILOR achieves a lower paired-CVaR than the human control.

Normalized paired-CVaR for TAILOR-generated heuristics and human-designed controls

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<0F_{0.95}<0 (§B.1). Lower is better; −100% reaches the theoretical floor, which need not be attainable.

ProblemBaselineHuman control
GPU Batch AdmissionFCFSZhou et al. [81]
Azure VM packingTight packingL2L_2 best-fit [66]
Server Placement (Metric kk-median)GreedyAdd2-swap local search [8]
Online weighted matchingAccept-if-freeProbe-based reservation
VBP2DFirst FitLP rounding [45]
Online VBP2DOnline First FitWeighted L2L_2 fit [66]
TE MLUShortest pathGreedy load balancing
MakespanLPT [25]MultiFit + LPT guard [15]

Table 4.

Since benchmark costs have different units, we normalize each value by the magnitude of the certificate floor F0.95=CVaR⁡0.95(LB−H)F_{0.95} = \operatorname{CVaR}_{0.95}(\mathrm{LB}-H) (§B.1). This is a candidate-independent lower bound on achievable paired-CVaR. A normalized value of −100% reaches this theoretical floor, which does not need to be attainable. TAILOR’s generated heuristics for Server Placement and Online Weighted Matching approach this bound. The best generated heuristics also match or outperform human-designed controls in average cost improvement across all six benchmarks. The largest differences are on GPU Batch Admission (12.2% vs. 6.2%) and Azure VM Packing (9.0% vs. 0.1%).

Relation to true optimality gaps. To assess the tightness of the

bound in Eq. (1), we solve 28,000 small-scale kk-median instances to optimality (§C.1)—enough that the empirical CDF of optimality gaps is resolved to within a DKW error of about 0.01 at 99% confidence (§A.5). In all five runs, the observed reduction in tail optimality gaps is larger than the improvement guaranteed by CVaR⁡0.95(H′−H)\operatorname{CVaR}_{0.95}(H^{\prime}-H), showing that the bound is conservative.

Model Capability and Search Architecture

We examine how model capability and search architecture affect certification. Holding paired-CVaR feedback fixed, we compare three models (GPT-4o-mini, Sonnet 5.5, and Opus 5) across five harnesses: Engram [[38], Engram with adversarial training inputs (§C.2), Robusta’s routed specialists [[36]], the evolutionary search method ShinkaEvolve [[46]], and Sequential Repair. Sequential Repair starts with an Engram-generated heuristic and uses successive sessions of coding-agents to identify regions where it can improve upon the baseline and propose targeted repairs (see App. § 12).

Figure 10 shows with GPT-4o-mini, none of the 150 runs certifies, regardless of harness. With stronger models, the four coding-agent harnesses perform increasingly alike: their tail improvement spread relative to the best harness across problems shrinks from 17% with Sonnet 5.5 to 6% with Opus 5. ShinkaEvolve, the evolutionary harness, trails in both tail improvement and certification rate compared to coding-agent harnesses.

Bar chart comparing coding-agent harnesses across GPT-4o-mini, Sonnet 5.5, and Opus 5

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.

In our experiments, as models became more capable, the difference between simple and advanced harnesses became less pronounced. However, the choice of objective still had a significant impact.

Discussion and Limitations

Training-time constraints do not guarantee SLO compliance. TAILOR optimizes solution quality, while enforcing code-execution latency constraints by rejecting candidates that exceed the allowance on training workloads. However, on unseen kk-median certification workloads, many generated heuristics exceed latency allowance (Figure 13). This suggests that latency should be included directly in the synthesis objective, alongside tail performance, rather than enforced only through training-time filtering.

Performance certification and isolated p95 latency of generated metric k-median candidates

Figure 13. Performance certification does not imply constraint compliance. Each point shows the certificate and isolated p95 latency of a generated metric kk-median candidate.

Certificates are relative to a baseline. Two heuristics certified on the same baseline aren’t always comparable and should be directly evaluated. However, certificates can be chained: if H′H' certifies against HH, and H′′H'' certifies against H′H', then H′′H'' also improves over HH, assuming the same workload and tail level (§A.3). This lets a certified heuristic serve as the baseline for future synthesis.

Certification is distribution-specific. TAILOR’s guarantees apply only to the workload distribution used for certification and may not hold under distribution shifts. A new distribution requires re-certification and, potentially, further synthesis. We leave robustness under distribution shifts to future work.

Certification requires regression bounds. Statistical certification requires an upper bound MM on how much worse a generated heuristic can perform than the baseline over the distribution. We currently derive these bounds manually, which can be hard and may yield overly conservative certificates. We leave automating this to future work.

Related Work

LLM-based heuristic design. FunSearch, EoH, ReEvo, LLaMEA, AlphaEvolve, and ShinkaEvolve use executable feedback to search for programs and heuristics [72, 48, 80, 76, 65, 46]. Agentic frameworks, including AIDE, AHD Agent, Glia, and Engram, use iterative experimentation and code refinement [32, 53, 28, 38]. ADRS, SkyDiscover, AdaEvolve, and EvoX apply LLM-driven search to systems problems [12, 52, 11, 51]. HeurGenix and EoH-S incorporate ideas from algorithm selection [79, 50, 69, 78, 30]. Rather than proposing a new search architecture, TAILOR focuses on the synthesis objective and certifying tail improvements relative to a baseline.

Heuristic analysis. MetaOpt searches for adversarial inputs that expose performance gaps between heuristics or against the optimum [64]. XPlain explains heuristic failures, while MetaEase uses source-code analysis to discover adversarial inputs [35, 37]. AIChilles identifies regressions in AI-generated programs and incorporates them into synthesis feedback [82]. While these methods identify failures, TAILOR proposes a scalable synthesis objective with guarantees that measures failure frequency and severity over a workload distribution and bounds changes in tail optimality gaps without computing OPT.

Risk measures and robustness. CVaR and its coherence properties are well established [6, 70, 71, 1]. TeaVaR uses CVaR to balance WAN throughput and availability [10], while Learn then Test provides finite-sample risk guarantees [3]. Learning-augmented algorithms study robustness to prediction errors [54, 67, 62, 47], and risk-sensitive online algorithms also consider CVaR [13]. TAILOR uses these concepts to provide systematic certification for distributional tail improvements in LLM-based heuristic design.

Conclusion

In this paper, we studied how to guide LLMs to design heuristics that improve tail performance without sacrificing average performance. We introduced TAILOR, which uses the CVaR of paired candidate–baseline cost differences as a scalable synthesis objective. We proved that a negative paired CVaR guarantees improvements in both average performance and tail optimality gaps, without computing the optimal solution. We developed finite-sample confidence bounds to certify these improvements on unseen workloads and a preflight check to rule out unattainable certification targets before synthesis. Across three case studies, TAILOR achieves the best mean–tail trade-off among the evaluated synthesis objectives. Across seven benchmarks, it generates heuristics certified at 99% confidence to improve both average performance and tail optimality gaps on six. On these six benchmarks, its best heuristics also outperform robust human-designed alternatives in the tail, with comparable or better average gains.

Theoretical Guarantees and Statistical Certification

This appendix presents the guarantees underlying TAILOR. We first establish the relationship between paired-CVaR and tail optimality gaps, then describe the statistical certification procedure and its application to our benchmarks.

Definitions and Assumptions

Let I∼DI \sim\mathcal{D} denote a workload drawn from the target distribution. We express all problems as cost minimization. We assume that HH, H′H', and OPT⁡\operatorname{OPT} are integrable and that both heuristics return feasible solutions, so

OPT⁡(I)≤min⁡{H(I),H′(I)}\operatorname{OPT}(I) \le\min\{H(I),H'(I)\}

for every workload II.

The two heuristics are evaluated on the same workload; their costs need not be independent.

For an integrable random variable XX and 0<β<10 < \beta< 1, CVaR can be expressed equivalently as

CVaR⁡β(X)=min⁡t∈R{t+E[(X−t)+]1−β}=11−β∫β1VaR⁡u(X) du(4)\begin{aligned} \operatorname{CVaR}_{\beta}(X)=\min_{t\in\mathbb{R}}\left\{t+\frac{\mathbb{E}[(X-t)^{+}]}{1-\beta}\right\} \\ &=\frac{1}{1-\beta}\int_{\beta}^{1}\operatorname{VaR}_{u}(X)\,\mathrm{d}u \tag*{(4)} \end{aligned}

Here z+=max⁡{z,0}z^{+}=\max\{z,0\} and VaR⁡u(X)\operatorname{VaR}_{u}(X) denotes the uu-quantile of XX [70, 71]. CVaR averages the upper 1−β1-\beta fraction of the distribution, accounting for probability mass at the quantile boundary.

The Optimum-Free Certificate

Proposition 1 (Subadditivity). For integrable XX, YY, CVaR⁡β(X+Y)≤CVaR⁡β(X)+CVaR⁡β(Y)\operatorname{CVaR}_{\beta}(X+Y)\le\operatorname{CVaR}_{\beta}(X)+\operatorname{CVaR}_{\beta}(Y).

Proof. For any s,t∈Rs,t\in\mathbb{R}, (X+Y−s−t)+≤(X−s)++(Y−t)+(X+Y-s-t)^{+}\le(X-s)^{+}+(Y-t)^{+}, so the variational expression in Eq. (4) for X+YX+Y at s+ts+t is at most the sum of the expressions for XX at ss and YY at tt. Minimizing over ss and tt separately gives the claim [6, 1].

Theorem 1 (Optimum-free tail certificate). Under the assumptions of §A.1, for any 0<β<10<\beta<1,

CVaR⁡β(H′−OPT⁡)−CVaR⁡β(H−OPT⁡)≤CVaR⁡β(H′−H).\operatorname{CVaR}_{\beta}(H'-\operatorname{OPT})-\operatorname{CVaR}_{\beta}(H-\operatorname{OPT}) \le\operatorname{CVaR}_{\beta}(H'-H).

Proof. Write H′−OPT⁡=(H−OPT⁡)+(H′−H)H'-\operatorname{OPT}=(H-\operatorname{OPT})+(H'-H), apply Prop. 1, and subtract the finite quantity CVaR⁡β(H−OPT⁡)\operatorname{CVaR}_{\beta}(H-\operatorname{OPT}).

Corollary 1 (Average improvement). E[H′−H]≤CVaR⁡β(H′−H)\mathbb{E}[H'-H]\le\operatorname{CVaR}_{\beta}(H'-H) for 0<β<10<\beta<1. A negative population certificate therefore also implies E[H′]<E[H]\mathbb{E}[H']<\mathbb{E}[H].

Proof. The quantile function (VaR) is nondecreasing, so its average over the upper 1−β1-\beta mass in Eq. (4) is at least its average over [0,1][0,1], which is the mean.

Certification as a Partial Order

Fix a distribution D\mathcal{D} and tail level β\beta. We say that BB improves on AA, written B≺AB\prec A, if CVaR⁡β(B−A)<0\operatorname{CVaR}_{\beta}(B-A)<0.

This relation is a strict partial order: a heuristic cannot improve on itself, improvements are transitive, and two heuristics cannot both improve on each other. These properties follow from CVaR⁡β(0)=0\operatorname{CVaR}_{\beta}(0)=0 and subadditivity. In particular, if C≺BC\prec B and B≺AB\prec A, then

CVaR⁡β(C−A)≤CVaR⁡β(C−B)+CVaR⁡β(B−A)<0.\operatorname{CVaR}_{\beta}(C-A)\le\operatorname{CVaR}_{\beta}(C-B)+\operatorname{CVaR}_{\beta}(B-A)<0.

The Empirical CVaR Estimator

In practice, we observe only a finite sample. For observations x(1)≤⋯≤x(n)x_{(1)}\le\cdots\le x_{(n)} and k=⌈βn⌉k=\lceil\beta n\rceil,

CVaR⁡^β(x)=∑i>kx(i)+(k−βn)x(k)(1−β)n(5)\widehat{\operatorname{CVaR}}_{\beta}(x)=\frac{\sum_{i>k}x_{(i)}+(k-\beta n)x_{(k)}}{(1-\beta)n} \tag*{(5)}

For a finite set of observations, Eq. (5) is Eq. (4) applied to the empirical measure, so Thm. 1 holds exactly on any finite paired sample.

Statistical Certification

Certification sample size. After synthesis, we fix the selected candidate H′H' and evaluate it alongside the baseline HH on an independent certification sample SS of size nn. These workloads are not used during synthesis or candidate selection. Since CVaR⁡β\operatorname{CVaR}_{\beta} measures the average of the worst 1−β1-\beta fraction of outcomes, we need sufficiently many observations to estimate this tail.

We use the one-sided Dvoretzky–Kiefer–Wolfowitz (DKW) inequality [17, 56] to guide sample sizing, which bounds the upper tail error by:

Pr⁡(VaR⁡β≤VaR⁡^β+η)≥1−e−2nη2.\Pr\left(\operatorname{VaR}_{\beta}\le\widehat{\operatorname{VaR}}_{\beta+\eta}\right)\ge1-e^{-2n\eta^{2}}.

For an upper confidence bound with probability 1−δ1-\delta, setting the right-hand side to 1−δ1-\delta gives the DKW error margin ε=ln⁡(1/δ)/(2n)\varepsilon=\sqrt{\ln(1/\delta)/(2n)}. To achieve a desired quantile resolution ε≤η\varepsilon\le\eta, we therefore need:

n≥ln⁡(1/δ)2η2(6)n\ge\frac{\ln(1/\delta)}{2\eta^{2}} \tag*{(6)}

Thus, higher confidence (smaller δ\delta) or finer quantile resolution (smaller η\eta) requires more samples. We use δ=0.01\delta=0.01 throughout, so achieving ε≤0.01\varepsilon\le0.01 requires n≥23,026n\ge23{,}026.

Finite-sample upper bound on CVaR. Even with many samples, a negative empirical paired CVaR does not guarantee a negative population CVaR: some rare, severe regressions may not appear in the sample. We therefore use DKW to derive an upper confidence bound on the true paired CVaR.

Let Δ=H′−H\Delta=H'-H, and suppose Δ(I)≤M\Delta(I)\le M for every workload II in the declared distribution. With probability at least 1−δ1-\delta, the one-sided DKW inequality guarantees

VaR⁡^u(Δ)≤VaR⁡^u+ε(Δ),u≤1−ε.\widehat{\operatorname{VaR}}_u(\Delta)\le\widehat{\operatorname{VaR}}_{u+\varepsilon}(\Delta),\qquad u\le1-\varepsilon.

This bounds the population quantiles using empirical quantiles shifted by ε\varepsilon. For the highest ε\varepsilon fraction, which may contain outcomes missing from the sample, we instead use the worst-case regression bound MM.

Since CVaR is the average of the upper-tail quantiles, integrating these bounds gives, for ε≤1−βreq\varepsilon\le1-\beta_{\mathrm{req}},

UDKW=11−βreq(∫βreq1−εVaR⁡^u+ε(Δ) du+εM)=(1−βreq−ε)CVaR⁡^βreq+ε(Δ)+εM1−βreq.(7)\begin{aligned} U_{\mathrm{DKW}}=\frac{1}{1-\beta_{\mathrm{req}}}\left(\int_{\beta_{\mathrm{req}}}^{1-\varepsilon}\widehat{\operatorname{VaR}}_{u+\varepsilon}(\Delta)\,\mathrm{d}u+\varepsilon M\right) \\ &=\frac{(1-\beta_{\mathrm{req}}-\varepsilon)\widehat{\operatorname{CVaR}}_{\beta_{\mathrm{req}}+\varepsilon}(\Delta)+\varepsilon M}{1-\beta_{\mathrm{req}}}. \tag*{(7)} \end{aligned}

The first term measures the observed tail, while the second accounts for potentially unseen regressions. More samples reduce ε\varepsilon, while a tighter MM reduces the penalty for unseen outcomes.

Certification guarantee. For a fixed candidate and an independent certification sample SS, the bound satisfies

Pr⁡S[CVaR⁡βreq(Δ)≤UDKW(S)]≥1−δ.(8)\Pr_{S}\left[\operatorname{CVaR}_{\beta_{\mathrm{req}}}(\Delta)\le U_{\mathrm{DKW}}(S)\right]\ge1-\delta. \tag*{(8)}

If UDKW<0U_{\mathrm{DKW}}<0, we certify improvements in both mean performance and tail optimality gaps, by Thm. 1 and Cor. 1. For each fixed candidate, the probability of incorrectly certifying a nonnegative population paired CVaR is at most δ\delta. We use δ=0.01\delta=0.01, giving 99% confidence per candidate.

Bounding regressions (MM) Certification requires an upper bound MM on Δ(I)=H′(I)−H(I)\Delta(I)=H'(I)-H(I) for every workload in the target distribution. We derive these bounds from the generated programs and workload constraints, rather than from observed regressions.

Offline Problems. For offline problems, a heuristic can compute a candidate solution and compare it with the baseline before returning it. If it keeps the candidate only when it is no worse than the baseline, then Δ(I)≤0\Delta(I)\le0 and M=0M=0. This applies to all five VBP2D programs and three programs each for TE MLU and kk-median.

For the remaining two kk-median programs, which do not compare their solutions against the baseline, we use a bound that applies to any feasible solution. Each workload contains at most 70 sites in [0,1000]2[0,1000]^2, of which at least three are selected as servers. Under the Manhattan metric, each unselected site contributes at most 2000 to the total service cost. Thus, the maximum possible cost, and hence regression, is M=(70−3)×2000=1.34×105M=(70-3)\times2000=1.34\times10^5.

The remaining two TE MLU programs (reps 1 and 4) also compare against the baseline, but their MLU calculations can differ slightly from the evaluation harness due to floating-point rounding. They retain the baseline routing unless their own calculation indicates an improvement, subject to a tolerance of 10−910^{-9}. We bound the numerical disagreement using at most K=5.52×106K=5.52\times10^6 arithmetic operations, unit roundoff u=2−53u=2^{-53}, and a maximum ratio of total to minimum link capacity of 534.6 (Cogentco). The resulting disagreement is below 3.3×10−73.3\times10^{-7}. Since the harness reports MLU to six decimal places, we conservatively use M=10−6M=10^{-6}.

Online Problems. Unlike offline heuristics, online policies cannot undo earlier decisions. We therefore bound the largest cumulative loss each generated program can incur relative to the baseline.

In Online Weighted Matching, each stream consists of groups of arriving edges. Two programs can make a worse decision only in the first group, after which they follow the observed regime. Their maximum regression is therefore bounded by that group's weight, M=4M=4. The other three programs can lose weight in every group. Bounding their losses over the longest possible streams gives M∈{336,328,328}M\in\{336,328,328\}.

In GPU Batch Admission, each program’s decisions depend only on the request value level (1–8), the remaining capacity, their weight, and the number of rejected requests. This finite state space allows us to use dynamic programming to find the maximum possible loss against FCFS over all valid request streams. The resulting bounds are M∈{0.60,0.65,0.80,1.10,2.25}×106M\in\{0.60,0.65,0.80,1.10,2.25\}\times10^6.

For Online VBP2D, two out of five programs reverted to HH, so M=0M=0. The other three programs use at most nn bins, where n≤40OPTn\le40\mathrm{OPT} and OPT≤80\mathrm{OPT}\le80. Their regression is therefore bounded by n−OPT≤30OPT≤240n-\mathrm{OPT}\le30\mathrm{OPT}\le240, giving M=240M=240.

Azure VM Packing uses a finite population instances (15 machine groups over 96 hours). We evaluate every instance and compute the population CVaR⁡β(Δ)\operatorname{CVaR}_{\beta}(\Delta) exactly, so no statistical confidence bound is needed.

Certification Results. Table 2 summarizes the five synthesis runs per benchmark. For sampled workloads, UU denotes the 99% DKW upper confidence bound on paired CVaR. For Azure VM Packing, UU is the exact population CVaR. A negative UU certifies improvements in both average performance and tail optimality gaps.

BenchmarkUU (%)Certified
Metric kk-median−0.22 to +371.683/5
Online VBP2D0.00 to +93.070/5
Online weighted matching−0.42 to +5.542/5
VBP2D−0.29 to −0.185/5
TE MLU−0.32 to 0.004/5
GPU Batch Admission (Azure)−4.23 to −2.805/5
Azure VM Packing−5.17 to −4.855/5
Total24/35

Table 2. Certification at β=0.95\beta=0.95. Range of UU across five synthesis runs, normalized by the magnitude of the baseline’s mean cost. For sampled distributions, U=UDKWU=U_{\mathrm{DKW}} with δ=0.01\delta=0.01; for Azure VM Packing, UU is the exact finite-population CVaR. Negative values indicate certified improvements.

Certification Bounds

Candidate-Independent Floor and Ceiling

Before searching for a better heuristic, we can determine two limits: how much improvement is theoretically possible, and when certification is impossible.

How much improvement is possible? Suppose we know a lower bound LB≤OPT\mathrm{LB}\leq\mathrm{OPT} on the optimal cost. Since no feasible candidate can perform better than OPT\mathrm{OPT}, we obtain the following bound.

Theorem 2 (Certificate floor). For any feasible candidate H′H',

CVaR⁡β(H′−H)≥CVaR⁡β(OPT−H)≥CVaR⁡β(LB−H)=:Fβ.(9)\operatorname{CVaR}_{\beta}(H'-H)\geq\operatorname{CVaR}_{\beta}(\mathrm{OPT}-H) \geq\operatorname{CVaR}_{\beta}(\mathrm{LB}-H)=:F_{\beta}. \tag*{(9)}

Proof. Since H′≥OPT≥LBH'\geq\mathrm{OPT}\geq\mathrm{LB}, subtracting HH preserves these inequalities. The result follows from the monotonicity of CVaR.

The floor Fβ≤0F_{\beta}\leq0 tells us how negative the certificate could possibly become. When Fβ<0F_{\beta}<0, we measure how much of this potential improvement a candidate achieves:

∣min⁡{0,CVaR⁡β(H′−H)}∣∣Fβ∣∈[0,1].(10)\frac{\left|\min\{0,\operatorname{CVaR}_{\beta}(H'-H)\}\right|}{|F_{\beta}|}\in[0,1]. \tag*{(10)}

A value closer to one means the candidate is closer to the theoretical floor. However, this floor may be unreachable, especially if LB is loose.

When is certification impossible? If the baseline already matches LB on many instances, there may not be enough room for a negative tail certificate.

Corollary 2 (Certification ceiling). Let βceil=1−Pr⁡[H=LB]\beta^{\mathrm{ceil}}=1-\Pr[H=\mathrm{LB}]. For any β≥βceil\beta\geq\beta^{\mathrm{ceil}}, no feasible candidate can achieve a negative CVaR certificate.

Proof. Since LB−H≤0\mathrm{LB}-H\leq0, and equals zero whenever H=LBH=\mathrm{LB}, its worst 1−β1-\beta fraction consists entirely of zeros when 1−β≤Pr⁡[H=LB]1-\beta\leq\Pr[H=\mathrm{LB}]. Thus Fβ=0F_{\beta}=0. By Thm. 2, every feasible candidate has CVaR⁡β(H′−H)≥0\operatorname{CVaR}_{\beta}(H'-H)\geq0.

Preflight with Sampling Confidence

Draw nn i.i.d. preflight instances and let KK be the number on which HH attains LB. The one-sided Clopper–Pearson [14] lower bound on p0=Pr⁡[H=LB]p_0=\Pr[H=\mathrm{LB}] at confidence 1−δ1-\delta is

plo={0,K=0,Beta⁡−1(δ;K,n−K+1),K>0,p_{\mathrm{lo}}= \begin{cases} 0, & K=0,\\ \operatorname{Beta}^{-1}(\delta;K,n-K+1), & K>0, \end{cases}

where Beta⁡−1\operatorname{Beta}^{-1} is the beta quantile. If plo>1−βreqp_{\mathrm{lo}}>1-\beta_{\mathrm{req}}, the requested level is ruled out at that confidence. The binomial coverage requires i.i.d. sampling and exact equality H=LBH=\mathrm{LB} under a valid lower bound; stratified or weighted preflight samples need inference matched to that design.

When Is Certification Impossible or Inconclusive?

The Online VBP2D result raises a practical question: does a failed certification indicate an unattainable target or simply an unsuccessful synthesis attempt? Preflight can establish some impossibility cases without launching synthesis, but passing preflight does not prove that a certifiable candidate exists.

An unattainable paired-CVaR target (Makespan). For Makespan, the LPT baseline matches a valid lower bound on 35.49% of sampled workloads, giving an estimated certification ceiling β^ceil=0.6451\widehat{\beta}^{\mathrm{ceil}}=0.6451. At βreq=0.95\beta_{\mathrm{req}}=0.95, certification can be ruled out when the lower confidence bound on this fraction exceeds 5%. The preflight test evaluates this condition before synthesis, without computing OPT. The human MULTIFIT control can nonetheless improve average performance. Thus preflight rules out this particular certificate, not all possible performance improvements.

A target not ruled out, but not achieved (Online VBP2D). Here the estimated ceiling is 0.9997, so the preflight condition does not rule out a certificate at βreq=0.95\beta_{\mathrm{req}}=0.95. Nevertheless, none of the tested synthesised methods obtains one. This is an inconclusive search outcome, not proof of impossibility. More broadly, the ceiling is a sufficient obstruction to a negative paired-CVaR certificate, not a necessary condition for tail optimality-gap improvement.

Validation Against the True Optimum

We validate the paired CVaR on small-scale Metric kk-Median instances for Engram’s heuristics. We solve 28,000 certification instances to optimality using Gurobi [26], and compute LP lower bounds using GLOP [24]. The baseline, GreedyAdd, matches the lower bound on 0.767% of instances, giving a certification ceiling of βceil=0.9923\beta^{\mathrm{ceil}}=0.9923.

Table 3: Small-scale Metric kk-Median validation at β=0.95\beta= 0.95 using Engram (five Opus runs). The baseline tail optimality gap is 2,173.

RunPaired CVaRTrue changeH′=OPTH'=\mathrm{OPT}
1−6.3−1685.479.1%
2−27.0−2117.394.9%
3−12.7−1734.469.6%
4−27.4−2142.895.5%
5−27.7−2156.997.6%

Table 3.

Table 4: Baselines and human-designed comparisons. Makespan is ruled out in preflight.

Table 3 compares the paired CVaR with the true change in tail optimality gap across five Opus runs. The theoretical bound (Thm. 1) holds in every run, including at β=0.90\beta= 0.90 and 0.99 (not shown). The paired CVaR is conservative because the worst paired differences and the worst optimality gaps need not occur on the same instances.

Benchmarks and Experimental Methodology

Table 5 summarizes the workload distributions used in our synthetic benchmarks. Certification uses independently sampled instances not seen during synthesis.

BenchmarkWorkload distribution
Online Weighted Matching8–80 groups of weighted paths, with uniformly random arrival orders and weights.
VBP2D16–400 items with randomly generated two-dimensional resource demands and unit-capacity bins.
Online VBP2D8–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 MLUFive real network topologies with varying uniformly random traffic patterns, load levels, and link failures.
Makespan2–26 machines with uniformly randomly generated job processing times, plus constructed difficult instances.

Table 5. Workload distributions used for synthetic benchmarks.

Cost of the Offline Optimum

TAILOR needs no optimum, but a reader may ask whether one could simply compute it on large scale. Table 6 lists each benchmark’s offline problem, its hardness, an exact algorithm, the lower-bound we used in the preflight and its time complexity. Computing the optimum does not scale to realistic instances. For VBP2D, exhaustively evaluating all 101010^{10} five-item sequences took 1.8 minutes on 16 cores, but evaluating all 102010^{20} ten-item sequences is projected to take 10510^5 years!

Table 6: Offline optimum and preflight lower bound per benchmark. Every bound is a relaxation of the offline optimum. nn: items, jobs, clients, or vertices; dd: demands; CC: knapsack capacity; O∗O^* hides polynomial factors.

BenchmarkOffline optimumLower bound LB(II)LB Time Complexity
Server Placement (Metric kk-median)kk median; NP-hard [39, 58]; all center sets, O(nk+1)O(n^{k+1})LP relaxation of the kk-median program; integral, hence exact, on 92% of instancesone LP
GPU Batch Admission (Online Knapsack)0/1 knapsack; weakly NP-hard [40]; DP, O(nC)O(nC) [55]negated fractional-knapsack bound on captured value, filling in decreasing density order [16]O(nlog⁡n)O(n\log n)
Online Weighted Matchingmax-weight matching; polynomial, O(n∣E∣+n2log⁡n)O(n\lvert E\rvert+n^2\log n) [18, 20], but one solve per instance12∑vmax⁡e∋vwe\frac{1}{2}\sum_v \max_{e\ni v} w_e (negated for minimization): each vertex is matched at most once and each matched edge is counted at both ends; exact on the disjoint gadget grammarO(∣E∣)O(\lvert E\rvert)
VBP2D, Online VBP2D2D vector bin packing; strongly NP-hard [21, 77]; subset DP, O∗(3n)O^*(3^n)volume: max⁡d⌈∑isi,d/C⌉\max_d\lceil\sum_i s_{i,d}/C\rceil, the bins the fullest dimension alone requires [55]; exact on the constructed Online VBP2D groupsO(n)O(n)
TE MLUsingle-path routing; NP-hard [42]; all path choices, O(4dd)O(4^d d)fluid relaxation: split every demand freely over its path menu and minimize maximum link utilization [19]one LP
MakespanP∥Cmax⁡P\Vert C_{\max}; strongly NP-hard [21]; subset DP, O∗(3n)O^*(3^n)max⁡(⌈∑jpj/m⌉,max⁡jpj)\max(\lceil\sum_j p_j/m\rceil,\max_j p_j): average load and longest jobO(n)O(n)

Table 6.

Synthesis Architectures and Adversarial Inputs

Figure 11 shows the candidate architectures used in our experiments, showing how heuristics are generated and how they operate at deployment.

!Candidate architectures: (a) Robusta (Routed Specialists) [36]; (b) Sequential repair. bbox=0.11,0.15,0.86,0.77

Figure 11. Candidate architectures. Each robot represents Engram [38], where successive coding-agent sessions build on the programs produced by earlier sessions. (a) Routed specialists divide the input space into regions and independently search for a heuristic (H1′,…,HK′H'_1,\ldots,H'_K) for each region. At deployment, the router selects one heuristic per instance. (b) Sequential repair starts with an Engram-generated heuristic and iteratively adds targeted repairs for regions where the candidate still matches the baseline despite room for improvement indicated by the lower bound. At deployment, at most one repair runs per instance, and its solution is used only if it improves upon the original.

We generate the adversarial examples from two sources. First we leverage the family of hard adversarial samples introduced by prior work [64, 37]. Second, we modify AIChilles [82] and use an LLM to generate samples that provide large performance gaps against either the exact optimum or a better feasible solution. Since the optimum is expensive, we cannot generate many such samples.

Additional Results

Additional Results for Azure GPU Batch Admission

Figure 12 examines whether these improvements extend beyond the 5% tail used during synthesis. Paired-CVaR maintains favorable measured tail performance across worst-case fractions ranging from 20% to 0.5%, including more extreme tails than those explicitly optimized. While these results suggest that the benefits are not limited to the chosen tail level, they do not establish guarantees at other tail levels.

Training-Time Constraint Enforcement Does Not Guarantee SLO Compliance

During synthesis, we enforce latency constraints by rejecting candidates that exceed the latency allowance on training instances. However, satisfying these constraints during training does not guarantee compliance on larger, unseen workloads.

Figure 13 shows this limitation for metric kk-median, where the latency allowance is max⁡(5ms,2.5×median baseline time)\max(5\mathrm{ms},2.5\times\text{median baseline time}). Despite training-time filtering, most generated candidates exceed the 5 ms allowance in isolated evaluation, including candidates that achieve substantial improvements in tail performance.

These results suggest that strong performance certificates do not guarantee SLO compliance, motivating the incorporation of constraints directly into the synthesis objective rather than relying solely on training-time rejection of constraint violations.

References

  1. [1]Acerbi, C. and Tasche, D. On the coherence of expected shortfall. Journal of Banking and Finance, 26(7):1487–1503, 2002.arxiv.org/abs/cond-mat/0104295
  2. [2]Agarwal, A., Arun, V., Ray, D., Martins, R., and Seshan, S. Towards provably performant congestion control. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24), pp. 951–978, 2024.
  3. [3]Angelopoulos, A. N., Bates, S., Candès, E. J., Jordan, M. I., and Lei, L. Learn then test: Calibrating predictive algorithms to achieve risk control. The Annals of Applied Statistics, 19(2):1641–1662, 2025. doi: 10.1214/24-AOAS1998.DOI
  4. [4]Arashloo, M. T., Ghobadi, M., Rexford, J., and Walker, D. Hotcocoa: Hardware congestion control abstractions. In Proceedings of the 16th ACM Workshop on Hot Topics in Networks, HotNets ’17, pp. 108–114, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450355698. doi: 10.1145/3152434.3152457. URL https://doi.org/10.1145/3152434.3152457.
  5. [5]Arashloo, M. T., Beckett, R., and Agarwal, R. Formal methods for network performance analysis. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23), 2023.
  6. [6]Artzner, P., Delbaen, F., Eber, J.-M., and Heath, D. Coherent measures of risk. Mathematical Finance, 9(3):203–228, 1999.
  7. [7]Arun, V., Arashloo, M. T., Saeed, A., Alizadeh, M., and Balakrishnan, H. Toward formally verifying congestion control behavior. In Proceedings of the 2021 ACM SIGCOMM 2021 Conference, SIGCOMM ’21, 2021.DOI
  8. [8]Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., and Pandit, V. Local search heuristics for k-median and facility location problems. SIAM Journal on Computing, 33(3):544–562, 2004.DOI
  9. [9]Bhattacharya, S., Chalermsook, P., Mehlhorn, K., and Neumann, A. New approximability results for the robust k-median problem. In Algorithm Theory – SWAT 2014, volume 8503 of Lecture Notes in Computer Science, pp. 50–61. Springer, 2014. doi: 10.1007/978-3-319-08404-6_5. URL https://arxiv.org/abs/1309.4602.
  10. [10]Bogle, J., Bhatia, N., Ghobadi, M., Menache, I., Bjørner, N., Valadarsky, A., and Schapira, M. TEAVAR: Striking the right utilization-availability balance in WAN traffic engineering. In ACM SIGCOMM, pp. 29–43. ACM, 2019.DOI
  11. [11]Cemri, M., Agrawal, S., Gupta, A., Liu, S., Cheng, A., Mang, Q., Naren, A., Erdogan, L. E., Sen, K., Zaharia, M., Dimakis, A., and Stoica, I. AdaEvolve: Adaptive LLM driven zeroth-order optimization, 2026. URL https://arxiv.org/abs/2602.20133.
  12. [12]Cheng, A., Liu, S., Pan, M., Li, Z., Wang, B., Krentsel, A., Xia, T., Cemri, M., Park, J., Yang, S., Chen, J., Agrawal, L. Desai, A., Xing, J., Sen, K., Zaharia, M., and Stoica, I. Barbarians at the gate: How AI is upending systems research. arXiv preprint arXiv:2510.06189, 2025.arxiv.org/abs/2510.06189
  13. [13]Christianson, N., Sun, B., Low, S., and Wierman, A. Risk-sensitive online algorithms (extended abstract). In Conference on Learning Theory (COLT), volume 247 of Proceedings of Machine Learning Research, pp. 1140–1141, 2024.
  14. [14]Clopper, C. J. and Pearson, E. S. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404–413, 1934.DOI
  15. [15]Coffman, E. G., Garey, M. R., and Johnson, D. S. An application of bin-packing to multiprocessor scheduling. SIAM Journal on Computing, 7(1):1–17, 1978.DOI
  16. [16]Dantzig, G. B. Discrete-variable extremum problems. Operations Research, 5(2):266–288, 1957.DOI
  17. [17]Dvoretzky, A., Kiefer, J., and Wolfowitz, J. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, 27(3):642–669, 1956.
  18. [18]Edmonds, J. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449–467, 1965.
  19. [19]Fortz, B. and Thorup, M. Internet traffic engineering by optimizing OSPF weights. In IEEE INFOCOM, pp. 519–528. IEEE, 2000.
  20. [20]Gabow, H. N. Data structures for weighted matching and nearest common ancestors with linking. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 434–443, 1990.DOI
  21. [21]Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
  22. [22]Garey, M. R., Graham, R. L., Johnson, D. S., and Yao, A. C.-C. Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory, Series A, 21(3):257–298, 1976.DOI
  23. [23]Goel, S., Mikek, B., Aly, J., Arun, V., Saeed, A., and Akella, A. Quantitative verification of scheduling heuristics, 2023.
  24. [24]Google. Advanced LP solving: OR-Tools. https://developers.google.com/optimization/lp/lp_advanced, 2026. Documentation for the GLOP linear programming solver; accessed October 2026.
  25. [25]Graham, R. L. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17 (2):416–429, 1969.DOI
  26. [26]Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual. https://doc.gurobi.com/projects/optimizer/en/current/, 2026. Accessed October 2026.
  27. [27]Hadary, O., Marshall, L., Menache, I., Pan, A., Greeff, E. E., Dion, D., Dorminey, S., Joshi, S., Chen, Y., Russinovich, M., and Moscibroda, T. Protean: Vm allocation service at scale. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pp. 845–861, 2020.
  28. [28]Hamadanian, P., Karimi, P., Nasr-Esfahany, A., Noorbakhsh, K., Chandler, J., ParandehGheibi, A., Alizadeh, M., and Balakrishnan, H. Glia: A human-inspired ai for automated systems design and optimization, 2025. URL https://arxiv.org/abs/2510.27176.
  29. [29]Hong, C.-Y., Kandula, S., Mahajan, R., Zhang, M., Gill, V., Nanduri, M., and Wattenhofer, R. Achieving high utilization with software-driven WAN. In ACM SIGCOMM, pp. 15–26. ACM, 2013.
  30. [30]Hutter, F., Hoos, H. H., and Leyton-Brown, K. Sequential model-based optimization for general algorithm configuration. In Learning and Intelligent Optimization (LION), pp. 507–523, 2011.
  31. [31]Jain, S., Kumar, A., Mandal, S., Ong, J., Poutievski, L., Singh, A., Venkata, S., Wanderer, J., Zhou, J., Zhu, M., Zolla, J., Hölzle, U., Stuart, S., and Yadav, A. B4: Experience with a globally-deployed software defined WAN. In ACM SIGCOMM, pp. 3–14. ACM, 2013.
  32. [32]Jiang, Z., Schmidt, D., Srikanth, D., Xu, D., Kaplan, I., Jacenko, D., and Wu, Y. AIDE: AI-driven exploration in the space of code, 2025. URL https://arxiv.org/abs/2502.13138.
  33. [33]Johnson, D. S., Demers, A., Ullman, J. D., Garey, M. R., and Graham, R. L. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3(4):299–325, 1974.
  34. [34]Jyothi, S. A., Singla, A., Godfrey, P. B., and Kolla, A. Measuring and understanding throughput of network topologies. In SC ’16: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 761–772, 2016. doi: 10.1109/SC.2016.64.
  35. [35]Karimi, P., Pirelli, S., Kakarla, S. K. R., Beckett, R., Segarra, S., Li, B., Namyar, P., and Arzani, B. Towards safer heuristics with xplain. In Proceedings of the 23rd ACM Workshop on Hot Topics in Networks, HotNets ’24, pp. 68–76, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400712722. doi: 10.1145/3696348.3696884. URL https://doi.org/10.1145/3696348.3696884.
  36. [36]Karimi, P., Rouhana, D., Namyar, P., Kakarla, S. K. R., Arun, V., and Arzani, B. Robust heuristic algorithm design with llms, 2025. URL https://arxiv.org/abs/2510.08755.
  37. [37]Karimi, P., Kakarla, S. K. R., Beckett, R., Segarra, S., Namyar, P., Alizadeh, M., and Arzani, B. Heuristic analysis from source code via Symbolic-Guided optimization. In 23rd USENIX Symposium on Networked Systems Design and Implementation (NSDI 26), pp. 2151–2174. USENIX Association, 2026. URL https://www.usenix.org/conference/nsdi26/presentation/karimi.
  38. [38]Karimi, P., Noorbakhsh, K., Alizadeh, M., and Balkrishnan, H. Improving coherence and persistence in agentic ai for system optimization. In Proceedings of the ACM Conference on AI and Agentic Systems (CAIS), pp. 124–160, 2026. doi: 10.1145/3786335.3813138.
  39. [39]Kariv, O. and Hakimi, S. L. An algorithmic approach to network location problems. II: The p-medians. SIAM Journal on Applied Mathematics, 37(3):539–560, 1979.
  40. [40]Karp, R. M. Reducibility among combinatorial problems. In Complexity of Computer Computations, pp. 85–103. Plenum Press, 1972.
  41. [41]Karp, R. M., Vazirani, U. V., and Vazirani, V. V. An optimal algorithm for on-line bipartite matching. In ACM Symposium on Theory of Computing (STOC), pp. 352–358. ACM, 1990.
  42. [42]Kleinberg, J. M. Approximation Algorithms for Disjoint Paths Problems. PhD thesis, Massachusetts Institute of Technology, 1996.
  43. [43]Knight, S., Nguyen, H. X., Falkner, N., Bowden, R., and Roughan, M. The Internet topology zoo. IEEE Journal on Selected Areas in Communications, 29(9):1765–1775, 2011.
  44. [44]Kubernetes Authors. Scheduler configuration: NodeResourcesFit. https://kubernetes.io/docs/reference/scheduling/config/#scoring, 2024. Kubernetes documentation; Most Allocated scoring strategy.
  45. [45]Kulik, A., Mnich, M., and Shachnai, H. Improved approximations for vector bin packing via iterative randomized rounding. In IEEE Symposium on Foundations of Computer Science (FOCS), pp. 1366–1376. IEEE, 2023.arxiv.org/abs/2205.12828
  46. [46]Lange, R. T., Imajuk, Y., and Cetin, E. ShinkaEvolve: Towards open-ended and sample-efficient program evolution. arXiv preprint arXiv:2509.19349, 2025.arxiv.org/abs/2509.19349
  47. [47]Lechowicz, A., Christianson, N., Sun, B., Bashir, N., Hajiesmaili, M., Wierman, A., and Shenoy, P. Online conversation with switching costs: Robust and learning-augmented algorithms. In ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, pp. 45–46, 2024. doi: 10.1145/3652963.3655074.DOI
  48. [48]Liu, F., Tong, X., Yuan, M., Lin, X., Luo, F., Wang, Z., Lu, Z., and Zhang, Q. Evolution of heuristics: Towards efficient automatic algorithm design using large language model. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 32201–32223. PMLR, 2024.arxiv.org/abs/2401.02051
  49. [49]Liu, F., Figalli, A., Owen, P., and Serra, N. RAISE: Llm-based automated heuristic design with robust adversary instance search, 2026.arxiv.org/abs/2606.31801
  50. [50]Liu, F., Liu, Y., Zhang, Q., Tong, X., and Yuan, M. EoH-S: Evolution of heuristic set using LLMs for automated heuristic design. In Proceedings of the 40th AAAI Conference on Artificial Intelligence, volume 40, pp. 37090–37098. AAAI Press, 2026. doi: 10.1609/aaai.v40i43.41038.DOI
  51. [51]Liu, S., Agarwal, S., Maheswaran, M., Cemri, M., Li, Z., Mang, Q., Naren, A., Boneh, E., Cheng, A., Pan, M. Z., Du, A., Keutzer, K., Cheung, A., Dimakis, A. G., Sen, K., Zaharia, M., and Stoica, I. EvoX: Meta-evolution for automated discovery, 2026. URL https://arxiv.org/abs/2602.23413.
  52. [52]Liu, S., Cemri, M., Agarwal, S., Krentsel, A., Naren, A., Mang, Q., Li, Z., Gupta, A., Maheswaran, M., Cheng, A., Pan, M., Boneh, E., Ramchandran, K., Sen, K., Zaharia, M., Dimakis, A. G., and Stoica, I. SkyDiscover: A flexible, adaptive framework for AI-driven scientific and algorithmic discovery. In Proceedings of the ACM Conference on AI and Agentic Systems, CAIS ’26, pp. 1223–1227. Association for Computing Machinery, 2026. doi: 10.1145/3786335.3813221.DOI
  53. [53]Lv, H., Lu, N., Zhou, Z., Ong, Y.-S., and Liu, S. AHD Agent: Agentic reinforcement learning for automatic heuristic design, 2026. URL https://arxiv.org/abs/2605.08756.
  54. [54]Lykouris, T. and Vassilvitskii, S. Competitive caching with machine learned advice. Journal of the ACM, 68 (4):1–25, 2021. doi: 10.1145/3447579.DOI
  55. [55]Martello, S. and Toth, P. Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, 1990.DOI
  56. [56]Massart, P. The tight constant in the dvoretzky–kiefer–wolfowitz inequality. The Annals of Probability, 18(3):1269–1283, 1990.DOI
  57. [57]Megiddo, N. and Modha, D. S. ARC: A self-tuning, low overhead replacement cache. In 2nd USENIX Conference on File and Storage Technologies (FAST 03), pp. 115–130. USENIX Association, 2003.
  58. [58]Megiddo, N. and Supowit, K. J. On the complexity of some common geometric location problems. SIAM Journal on Computing, 13(1):182–196, 1984.DOI
  59. [59]Mehta, A. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8(4):265–368, 2013.DOI
  60. [60]Microsoft Azure. Azure public dataset: Azure traces for packing 2020. https://github.com/Azure/AzurePublicDataset/releases/download/dataset-packing-2020/azurevmallocation_dataset2020_AzurePackingTraceV1.zip, 2020. Azure/Azure-PublicDataset repository.
  61. [61]Microsoft Azure. Azure LLM inference trace 2024 (AzurePublicDataset). https://github.com/Azure/AzurePublicDataset, 2024. CC-BY; code and conversation services, one week each.
  62. [62]Mitzenmacher, M. and Vassilvitskii, S. Algorithms with predictions. Communications of the ACM, 65(7):33–35, 2022. doi: 10.1145/3528087.DOI
  63. [63]Namyar, P., Supittayapornpong, S., Zhang, M., Yu, M., and Govindan, R. A throughput-centric view of the performance of datacenter topologies. In Proceedings of the 2021 ACM SIGCOMM 2021 Conference, SIGCOMM ’21, pp. 349–369, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383837. doi: 10.1145/3452296.3472913. URL https://doi.org/10.1145/3452296.3472913.
  64. [64]Namyar, P., Arzani, B., Beckett, R., Segarra, S., Raj, H., Krishnaswamy, U., Govindan, R., and Kandula, S. Finding adversarial inputs for heuristics using multi-level optimization. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24), pp. 927–949. USENIX Association, 2024. doi: 10.1145/3696348.3696854 URL https://doi.org/10.1145/3696348.3696854.
  65. [65]Novikov, A., Vũ, N., Eisenberger, M., Dupont, E., Huang, P.-S., Wagner, A. Z., Shirobokov, S., Kozlovskii, B., Ruiz, F. J. R., Mehrabian, A., Kumar, M. P., See, A., Chaudhuri, S., Holland, G., Davies, A., Nowozin, S., Kohli, P., and Balog, M. AlphEvolve: A coding agent for scientific and algorithmic discovery. arXiv preprint arXiv:2506.13131, 2025.arxiv.org/abs/2506.13131
  66. [66]Panigrahy, R., Talwar, K., Uyeda, L., and Wieder, U. Heuristics for vector bin packing. Technical report, Microsoft Research, 2011.
  67. [67]Purohit, M., Svitkina, Z., and Kumar, R. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2018.
  68. [68]Qiu, L., Padmanabhan, V. N., and Voelker, G. M. On the placement of web server replicas. In Proceedings of IEEE INFOCOM, volume 3, pp. 1587–1596. IEEE, 2001. doi: 10.1109/INFCOM.2001.916655.DOI
  69. [69]Rice, J. R. The algorithm selection problem. In Advances in Computers, volume 15, pp. 65–118. Elsevier, 1976.DOI
  70. [70]Rockafellar, R. T. and Uryasev, S. Optimization of conditional value-at-risk. Journal of Risk, 2(3):21–41, 2000. doi: 10.21314/JOR.2000.038.DOI
  71. [71]Rockafellar, R. T. and Uryasev, S. Conditional value-at-risk for general loss distributions. Journal of Banking and Finance, 26(7):1443–1471, 2002. doi: 10.1016/S0378-4266(02)00271-6.DOI
  72. [72]Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J. R., Ellenberg, J. S., Wang, P., Fawzi, O., Kohli, P., and Fawzi, A. Mathematical discoveries from program search with large language models. Nature, 625(7995):468–475, 2024.
  73. [73]Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, R. A., and Price, T. G. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, pp. 23–34. ACM, 1979. doi: 10.1145/582095.582099.DOI
  74. [74]Seyhani, A., Zhao, J., Gupta, A., Walker, D., and Arashloo, M. T. Buffy: A formal language-based framework for network performance analysis. In Proceedings of the 23rd ACM Workshop on Hot Topics in Networks, HotNets ’24, pp. 95–102, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400712722.DOI
  75. [75]Stojkovic, J., Zhang, C., Goiri, Í., Torrellas, J., and Choukse, E. DynmoLLM: Designing LLM inference clusters for performance and energy efficiency. In 2025 IEEE International Symposium on High Performance Computer Architecture (HPCA), pp. 1348–1362, 2025. doi: 10.1109/HPCA61900.2025.00102.DOI
  76. [76]van Stein, N. and Bäck, T. LLaMEA: A large language model evolutionary algorithm for automatically generating metaheuristics. IEEE Transactions on Evolutionary Computation, 29(2):331–345, 2025. doi: 10.1109/TEVC.2024.3497793.DOI
  77. [77]Woeginger, G. J. There is no asymptotic PTAS for two-dimensional vector packing. Information Processing Letters, 64(6):293–297, 1997.DOI
  78. [78]Xu, L., Hutter, F., Hoos, H. H., and Leyton-Brown, K. Satzilla: Portfolio-based algorithm selection for sat. Journal of Artificial Intelligence Research, 32:565–606, 2008.DOI
  79. [79]Yang, X., Zhang, L., Qian, H., Song, L., and Bian, J. HeurAgenix: Leveraging LLMs for solving complex combinatorial optimization challenges, 2025.arxiv.org/abs/2506.15196
  80. [80]Ye, H., Wang, J., Cao, Z., Berto, F., Hua, C., Kim, H., Park, J., and Song, G. ReEvo: Large language models as hyper-heuristics with reflective evolution. In Advances in Neural Information Processing Systems, volume 37, 2024.arxiv.org/abs/2402.01145
  81. [81]Zhou, Y., Chakrabarty, D., and Lukose, R. Budget constrained bidding in keyword auctions and online knapsack problems. In Internet and Network Economics (WINE), pp. 566–576, 2008.
  82. [82]Zhou, Y., Li, A., Silla, A., Liu, Z., and Sekar, V. Aichilles: Automatically uncovering hidden weaknesses in ai-evolved systems. arXiv preprint arXiv:2606.15834, 2026.arxiv.org/abs/2606.15834

Paper details

vlnc:W_nw2dhd6v
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents