acceptodds
Under review as a conference paper at ICLR 2027

FARE: Fingerprint-Aware Representative Evaluation for LLM-Based Heuristic Discovery

Abstract

LLM-based heuristic discovery iteratively proposes, scores, and selects programs using feedback from an evaluation harness. The harness does not merely measure quality; it defines the objective that discovery optimizes. Evaluating every deployment scenario is infeasible because operating conditions vary continuously and interact combinatorially, so discovery must optimize against a finite scenario bank. Over successive iterations, the discovery loop can exploit gaps in this bank, so its high-scoring programs may fail under unseen conditions. Enlarging the bank raises the cost of evaluating every candidate program and may waste budget on behaviorally redundant scenarios. We introduce FARE (Fingerprint-Aware Representative Evaluation). FARE runs diverse probe programs offline on a scenario pool and fingerprints each scenario by its normalized probe scores. It then selects a compact training bank of scenarios by -medoids under program disagreement distance, so that every pool scenario has a nearby selected scenario as its representative. FARE reserves the unselected scenarios as a held-out test bank that discovery never sees, so the train–held-out gap measures generalization beyond the training bank. FARE also reports the representation error: the mean distance from each pool scenario to its representative. When a program's score is a smooth function of the fingerprint, the representation error bounds the average error of predicting a pool scenario's score from its representative's score. We evaluate FARE against four alternative bank-construction methods on two case studies, scheduling and congestion control, using 5G-Eval, our automated full-stack 5G platform built on real network software. Across three LLMs, FARE's top-ranked candidate program has the highest pool score in almost all model–pool combinations compared with the four alternatives.

Primary area:
optimization
Keywords:
LLM-based heuristic discovery, Evaluation harness, Representative evaluation, Benchmark overfitting, Systems and networking heuristics

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_6LWGOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces FARE, a method that constructs scenario fingerprints based on normalized probe scores. It then employs k-medoids clustering to select representative scenarios, thereby reducing the evaluation cost during LLM-based heuristic discover. The authors validate this approach within the context of 5G scheduling and ECN marking, reporting superior overall performance compared to alternative scenario-selection strategies.

Critical strengths
  1. Rather than selecting scenarios only to preserve the ranking of probe programs, FARE focuses on whether different scenarios capture distinct program behaviors. The experiments show that the Order oracle can closely preserve the full-pool ranking of probe programs while still failing to cover some scenario clusters.

  2. The authors validate their method on a full-stack 5G emulation platform and report both the one-time fingerprinting cost and the reduction in candidate evaluation cost, rather than relying only on offline clustering metrics.

Critical weaknesses
  1. The 'Program Disagreement Distance' (PDD) metric measures the mean absolute difference in normalized probe scores between scenarios, rather than changes in the relative performance of probe programs. If all probe programs score lower by a similar amount on a harder scenario, PDD may be large even when their relative ranking remains unchanged. Conversely, even a small change in scores could lead to a reversal in the relative ranking of programs. As a result, FARE's clustering objective may emphasize differences in scenario difficulty rather than differences in relative program performance.

  2. The upper bound established in Proposition 1 depends on program-specific Lipschitz constants and approximation errors. For the scheduling task, the reported Lipschitz scale L=14.6L=14.6 and representation error δ⋆=0.152\delta^\star=0.152 give Lδ∗≈2.22L\delta^*\approx 2.22, which already exceeds the maximum possible score difference of 1, even before adding the 2ϵπ2\epsilon_\pi term. Thus, the resulting bound is trivial under these values. Furthermore, estimating ϵπ\epsilon_\pi for newly generated programs appears to require full-pool evaluation, making the bound difficult to use during search to assess how well the selected scenarios represent the pool.

Questions for authors
  1. Why does PDD use absolute differences in normalized probe scores without separating scenario difficulty from differences in relative probe performance?

  2. Beyond the leave-one-probe-out test in Appendix F.2, how does FARE handle highly correlated or redundant probe programs? If the proportions of different probe families change, does the selection of representative scenarios remain stable?

  3. Could you provide a non-trivial error bound for Proposition 1 based on the parameters used in practice, and explain how the constants required for new programs can be determined without evaluating the entire pool of scenarios?

Reviewer_nFRQOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

FARE studies the construction of scenario banks for LLM-based heuristic discovery, where the evaluation bank also defines the search objective. It represents scenarios using the scores of probe programs and selects representative scenarios with k-medoids. The remaining scenarios are reserved for evaluation after discovery. Experiments on scheduling and ECN marking in the 5G-EVAL software platform compare several bank-construction methods. FARE obtains the highest pool score in five of six model-task combinations and ties in the remaining combination.

Critical strengths
  1. A useful perspective on evaluation during algorithm search. The paper recognizes that the evaluation scenarios also influence the direction of the search. Selecting representative scenarios using behavioral fingerprints is a reasonable way to address this issue.

  2. A substantial system implementation and an informative analysis of its limitations. The two control tasks use a full-stack 5G software platform, with detailed interfaces, scenarios, and search configurations. Section 5.2 tests transfer to newly discovered programs, and Section 6 gives a concrete failure case for fixed fingerprints. This analysis helps delimit what the method establishes.

Critical weaknesses
  1. The end-to-end search gains need independent replication. Table 1 does not report variability across independent complete discovery runs. The five interacting islands belong to one search process; Figure 5 assesses bank fidelity using random subsets, and Appendix F.1 repeats evaluations of seed programs. Neither quantifies variability in the final outcome of the complete search. Although the results across three LLMs are encouraging, the ECN margins over the strongest competing bank method are only 0-0.02. Representative independent search repetitions would help determine whether these gains and method rankings are reproducible. This concern bears directly on the main empirical comparison; it does not establish that the reported gains are absent.
Questions for authors
  1. Are independent complete discovery runs available for a representative comparison, especially on ECN? Reporting the distribution of final pool scores and method rankings would address the main uncertainty. Repeating every configuration is not necessary, and repeated evaluation of a fixed program would answer a different question.
Reviewer_CpBgOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

LLM-driven program search, such as AlphaEvolve, judges each candidate program only by its scores on a fixed set of test scenarios, so over many iterations it can exploit gaps in that set and produce programs that fail under conditions the set does not cover. Adding more scenarios reduces this risk, but it makes the evaluation of every candidate more expensive. The paper therefore proposes FARE, which picks a small set that still represents a larger pool of scenarios: it runs 15 fixed "probe" programs on every pool scenario, groups scenarios on which the probes score alike, and keeps one representative per group. On two 5G control tasks with three LLMs, programs found with the FARE set score highest on the full pool in five of six settings.

Critical strengths
  • The paper makes a useful point clearly: in LLM program search, the evaluation harness does not just measure quality but defines the objective.
  • It shows that scenario parameters say little about how programs behave on a scenario, which is worth knowing for anyone who builds benchmarks from parameter grids.
  • The 5G-Eval platform runs full-stack cellular experiments on real open-source network software from a single scenario file, and others can reuse it.
Critical weaknesses

1. How well the FARE's selection score predicts the discovered programs will be is not quantified.

FARE minimizes the representation error δ*, the average fingerprint distance from each pool scenario to its representative. However, Proposition 1 provides no informative guarantee on the scheduler: at the reported constants, its leading term alone is 14.6 × 0.152, while scores lie in [0, 1]. Moreover, the proposition bounds per-scenario reconstruction error, not the discrepancy between the unweighted training-bank mean used by search and the pool mean. The weighting results expose this distinction: weighting representatives by cluster size leaves the selected scenarios and δ* unchanged, yet scheduler pool scores fall from 0.72/0.73 to 0.62/0.65. These results suggest that coverage alone does not explain the gains; how the bank weights scenarios also matters. The paper therefore needs a clearer justification for why minimizing δ* yields an effective search objective.

2. FARE decides which scenarios are alike using 15 existing programs, but the new programs found by search can treat those scenarios very differently.

FARE treats scenarios with similar probe scores as interchangeable, but this similarity need not transfer to newly generated programs. Section 6 provides a concrete example: S38 and S27 are nearly identical in fingerprint space, yet FARE’s own programs score 0.38 and 0.95 on them. This limitation directly concerns the paper’s motivation: a fixed proxy may cease to be reliable as search optimizes against it. The authors acknowledge the issue, but neither the selection procedure nor the bound controls it during discovery. The central question is therefore what makes probe-defined coverage reliable for the evolving program population, rather than merely representative for the probes.

3. The paper is motivated by failures under new conditions, but every result is measured on scenarios from the same pool.

Figure 1 motivates FARE through a failure to transfer from static to mobile channels. FARE can address the omission of such conditions from the training bank only if they are already represented in the candidate pool. All reported evaluations use this same pool, so they assess transfer to unselected scenarios, not robustness to conditions absent from the pool. Section 4.2 explicitly acknowledges this scope, but the broader motivation can obscure the distinction. The contribution would be more precise if framed as constructing an effective, compact search objective for a given scenario pool, with its relevance to deployment depending on how well that pool represents deployment conditions.

Questions for authors

What supports the link from probe-defined coverage to reliable optimization over newly generated programs? How should the weighting results be reconciled with the proposed coverage-based explanation?

Reviewer_LoQ3OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies how to select a small evaluation bank for LLM-based heuristic discovery. To do this, the authors present FARE, which represents each scenario using normalized scores from 15 probe programs and selects representatives with k-medoids. The selected scenarios define the search objective, and the remaining scenarios are evaluated after discovery. The authors run experiments on scheduling and congestion control on a full 5G software stack, using three LLMs and four selection baselines and show that FARE has the highest pool score in five of six comparisons and ties in the sixth.

Critical strengths

Repeated evaluation is expensive. Also, searching against a narrow scenario bank can produce brittle heuristics. These issues make the reduction from 39 to 8 scenarios for scheduling and from 37 to 10 for congestion control an important and worthwhile endeavor .

The authors test the generated C programs against real network software in a full 5G stack, which greatly enhances the credibiltiy of their findings. I also liked the failure analysis.

The authors are also clear about some of the experimental limitations in their paper, such that the held-out results measure generalization within the existing pool.

Critical weaknesses

I am not sure what the specific FARE design adds over the closest selection methods. Anchor Points already uses reference-model behavior and k-medoids, and tinyBenchmarks includes clustering by reference-model score vectors. FARE changes the distance and normalization and uses an unweighted bank as an adaptive search objective. Neither prior selection rule is directly compared under the same discovery protocol. A direct comparison is needed to establish what FARE adds beyond representative selection in general.

More replication is needed to support the gains. Table 1 does not report uncertainty across independent discovery runs, and the end-to-end Random comparison uses one selected bank. The congestion-control advantage over the strongest baseline is just between 0 and 0.02. Without repeated searches and repeated evaluations of the discovered programs, it is hard to judge whether these gains are reliable.

Questions for authors

How does FARE compare with adapted Anchor Points and the score-clustering approach in tinyBenchmarks when the probes, bank size, and discovery budget are kept the same?

How many independent discovery runs are behind Table 1? Can you report uncertainty from different search seeds, random-bank draws, and repeated evaluations of the final programs?

Section 4.2 says that small representation error prevents a candidate from scoring well on the bank while failing in an unrepresented region. How does this follow from an average-error bound with program-dependent residuals? Section 6 shows that nearly identical fingerprints can hide large differences in candidate scores. I do not see how the proposition supports the stronger claim.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.