acceptodds
Desk rejected at ICLR 2027

HeuriGuide: Calibrating LLM Authority for Test-Time Heuristic Design

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Large language models (LLMs) have recently emerged as a powerful tool for automated heuristic design (AHD) in combinatorial optimization. Most existing LLM-based AHD algorithms employ an outer agent to optimize a strategy, an algorithmic procedure that constructs a solution, during development and then deploy it unchanged, missing the opportunity to adapt the strategy to individual test-time instances. We therefore systematically investigate placing an inner LLM agent directly into the test-time solving process. Since LLM-generated output can be unstable, the central design question is how to calibrate the inner agent's authority at test time. By imposing progressively greater procedural guidance on the inner agent, we propose three inner-agent organizations: a solution generator that directly generates a solution for each test instance, a strategy adapter that selects and adapts existing strategies, and a strategy router that only selects among strategies curated by the outer agent. We evaluate these three agent organizations on HeuriGym, a benchmark comprising nine combinatorial optimization problems across four domains. Averaged across all nine problems, QCI increases monotonically with procedural guidance, from 0.599 for the solution generator to 0.787 for the strategy adapter and 0.805 for the strategy router, compared with 0.728 for the outer-agent-only baseline. The strategy router also performs best on most individual problems. However, on E-graph Extraction, a problem for which the baseline fails entirely, success requires allowing the inner agent to generate beyond the curated strategies. Together, these results suggest using strong procedural guidance by default while relaxing procedural guidance when curated strategies prove insufficient.

Primary area:
optimization
Keywords:
Automated Heuristic Design, Combinatorial Optimization, Test-Time Adaptation, LLM Agents, Strategy Routing

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 3 reviews, above 27% of the others.
Reviewer_CqqkOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The authors propose HeuriGuide, a framework for LLM agents solving combinatorial optimization problems. Most prior work evolves a single solver during development and then deploys it unchanged. Instead the proposed framework consists of an outer agent and an inner agent. At development time, the outer agent improves on the heuristics based on demonstration instances. At deployment time, the proposed heuristics is frozen and the inner agent uses it to solve the given problem. The main focus of the paper is on how much authority the inner agent should have during deployment. The authors examined three different inner-agent organizations: 1. The inner agent directly constructs a solution (Solution Generator), 2. The inner agent selects a strategy and optionally adapt it (Strategy Adapter), 3. The inner agent selects a frozen strategy (Strategy Router). The authors tested their different organizations on HeuriGym, a benchmark consisting of nine different combinatorial optimization problems, and compared performance with the released benchmark scores. The third organization, where the inner agent selects a frozen strategy seems to perform the best on most problems. On some problems, like E-graph extraction, however, the ordering of the organizations is reversed. Therefore, the authors suggest that one should not define the inner agent’s authority a priori. The paper evaluates all three modes with GPT-5.4 on the nine HeuriGym problems. The average QCI rises from 0.599 (generator) to 0.787 (adapter) to 0.805 (router), compared with 0.728 for the official HeuriGym baseline. E-graph Extraction (EE) is the exception to this trend: all portfolio strategies fail on the same instances, and the modes with more freedom do better.

Critical strengths
  1. The question that the paper studies is useful and clear.
  2. The presentation of the paper is easy to follow. Figure 1 and 2 convey the entire design of the paper, making it easy to understand.
  3. The experimentation is generally clean. The authors used a published benchmark and frozen verifiers and evaluators to provide fair comparison.
Critical weaknesses
  1. The experimental settings and controls are not strong enough to support the central claim.
  • The three organizations differ among themselves not only in terms of the authority of the inner agent. For example, the adapter evaluate more strategies than the router, since it not only evaluates the selected strategy but also the untried portfolio ones. So it is unclear whether the comparison can be attributed to adaptation vs selection.
  • Standard parameters like model configuration, decoding settings, demonstration set size, test set size, prompts, etc. are all missing
  • The baseline is the released HeuriGym benchmark numbers, which differ a lot in setup from the authors. It would be interesting to see whether the proposed framework has any benefits when compared with a stronger agentic baselines, or if the findings can be used to guide the adaptations of previous works like HeurAgenix. As the authors mentioned themselves in the Related Work section, HeurAgenix is very similar to the strategy router design of this paper, which is what the authors find to be the best performing organization most of the time, it is unclear what new insight the paper adds.
  • Test time resource usage should be reported as well since the three organizations differ substantially in things like model calls, solve executions, and retries.
  1. The paper only tested one model, GPT-5.4, which makes it hard to draw general conclusions on agent designs as the authors maintained. Implementation details are missing.
Questions for authors
  1. Can the authors provide more controlled metrics: for example, with a common frozen strategy portfolio, and controlling for runtime across organization, how does the comparison look like?
  2. What insights can the authors provide for other people relying on the framework since the ranking of the organizations depend on the problems? Can the failure on E-graph be examined further to provide insights as to when should one increase or decrease inner agent authority?
3 comments
AuthorsOpenReview ↗

Response to Reviewer Cqqk

Response to Reviewer Cqqk

Thank you for the thorough review. Tables A to F we refer to below are in the general response.

W1. The adapter evaluates more strategies than the router, so the comparison does not isolate adaptation from selection.

The two effects can be measured separately, and both measurements support the paper's conclusion.

Generated code. It is the final solution on 8 of the adapter's 213 instances: six on EE, one on TM and one on PDTW. On EE the best possible selection over the adapter's portfolio gives 0.434 (Fig. 7), and the adapter reaches 0.680 (best of three), so generated code contributes 0.246. On the other 205 instances the adapter's solution comes from a frozen strategy.

Evaluating more strategies. On the router's portfolio, running every strategy and keeping the best gives 0.867, against 0.787 for the router's single choice, so extra evaluation is worth at most 0.08.

Extra evaluation is an advantage for the adapter, and the router still has the higher QCI (0.795 vs. 0.777) with one LLM call and at most two strategy runs per instance. Adaptation pays off on EE, where selection is bounded by the portfolio, which is the paper's second finding.

W2. Model configuration, decoding settings, set sizes and prompts are missing.

Section E in general response lists the model, the decoding setting, the search budget and the time limit, and Table F gives the demonstration and test set sizes.

W3. The baseline differs in setup; a stronger agentic baseline such as HeurAgenix is missing, and it is unclear what the paper adds beyond it.

Table A adds HeurAgenix under the router's development token budget: 0.681 against 0.795, with the router ahead on eight of the nine problems and cheaper on all nine. The released baseline is kept as a reference point. The two designs differ in what is selected. HeurAgenix chooses among single-step heuristics evolved by its own pipeline, and is designed to re-select during construction; under the matched budget it made one selection per instance. The router chooses among complete, verifier-tested strategies curated by the outer agent.

W4. Test-time resource usage is not reported.

Table D reports tokens,and time per test instance, and Table C the totals; the router is the lowest on each. Table A gives the token comparison with HeurAgenix (7.52M vs. 6.30M).

W5. Only one model is tested.

All three organizations and HeurAgenix use the same model, so the comparisons are controlled. The framework does not depend on a particular model: the outer and inner agents only need a chat-completion interface. We are running the three organizations with more LLMs, namely Gemini and Kimi, all under the same protocol: the nine problems, the same frozen verifiers and evaluators, G=5, K=3, a 300 s limit and three complete evaluations per model.

Q1. Results with a common frozen portfolio and controlled runtime.

Tables B1 to B3 compare thirteen selection policies on one frozen portfolio, and our answer to W1 separates evaluation from generation. The router is also the fastest organization: one evaluation takes 34 s per instance, against 58 s for the generator and 95 s for the adapter.

Q2. What should users of the framework take away, given that the ranking depends on the problem? Can the EE failure be examined further?

Rule of thumb: Deploy the strategy router by default, and allow code generation when the scale gap between demonstration and test instances is extreme. The gap is measured by input file size before test time. On EE the two demonstration graphs are 1–2 kB and the test graphs are 144 kB–11 MB, a gap of about 7,000×; on the other eight problems the gap is much smaller (at most 320×). EE is the one problem where generated code clearly beats selection.

The EE failure. All frozen strategies share one extraction routine and fail on resnet50, vgg and nasrnn with the same error: a root e-class left without a selected node. The generated code is written around that constraint (root-first extraction, reachability tracking, cycle detection, a final repair pass) and solves two of the three graphs. The new experiments added for this rebuttal agree: every selector in Tables B1–B3 stays low on EE (kNN 0.172, random forest 0.174, routing table 0.326, oracle over the router's portfolio 0.544), and HeurAgenix's independently generated pool fails on the same three graphs. When the test instances are far larger than anything seen in development, the portfolio shares a failure mode that no selector can avoid, and only generated code gets past it.

AuthorsOpenReview ↗

Follow-up on Our Rebuttal

Dear Reviewer Cqqk,

Thank you again for your valuable comments on our submission.

As the discussion phase is approaching its end, we would appreciate your feedback on whether our rebuttal has adequately addressed your concerns. If any questions remain, we would be happy to provide further clarification.

If our responses have addressed your concerns, we would also appreciate your consideration in updating your evaluation accordingly.

Thank you for your time and consideration.

Reviewer_CqqkOpenReview ↗

response to authors

Thank you for your responses and clarifications, including the additional tables. Overall, I don't think the technical contribution is sufficiently significant. I maintain my initial score.

Reviewer_HoxgOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper explores the use of a test-time LLM agent to solve combinatorial optimization problems, rather than relying solely on a fixed heuristic discovered during development. The authors introduce HeuriGuide to study three test-time setups with varying degrees of freedom, namely direct solution generation, strategy adaptation with code editing, and strategy selection from a pre-built portfolio. Across nine tasks in the HeuriGym benchmark, the authors find that selecting from a fixed portfolio generally gives the highest overall score, while code adaptation is only helpful when the existing portfolio fails.

Critical strengths
  1. The paper tests the three test time prompting setups across all nine combinatorial problems in the HeuriGym benchmark.
  2. The experimental comparison provides empirical observations on when running verified code outperforms freeform LLM generation at test time.
Critical weaknesses
  1. The methodological contribution appears somewhat incremental. While exploring different test time roles for LLMs is an interesting direction, comparing direct generation, code adaptation, and portfolio selection closely resembles classical concepts in hyper-heuristics and algorithm selection. The paper would be stronger if it introduced a deeper algorithmic mechanism or a formal decision framework beyond comparing these three prompting paradigms.
  2. Several implementation details are missing due to the absence of an appendix. Key components, including the prompt templates, failure fingerprint representations, casebook definitions, and the training configuration of the outer agent, are only briefly mentioned in the main text, which may present challenges for reproducibility.
Questions for authors
  1. Why does Table 2 only report the best outcome out of three runs instead of the average score and standard deviation? Could you provide the mean and variance across runs to prove that the performance gains are reproducible and not due to chance?
  2. How many LLM calls, total tokens, and wall-clock seconds does each setup consume per test instance? Could you provide a comparison where all methods are constrained to the same test-time computational budget?
  3. Why does the strategy router perform worse than the baseline on Technology Mapping and Protein Sequence Design? What causes the selection mechanism to fail on these two tasks?
  4. On tasks where existing strategies work well, how does your LLM strategy router compare to simple machine learning classifiers or standard portfolio selection algorithms that choose among the same strategies?
2 comments
AuthorsOpenReview ↗

Response to Reviewer Hoxg

Response to Reviewer Hoxg

Thank you for the detailed questions. Tables A to F we refer to below are in the general response.

W1. The contribution is incremental and resembles hyper-heuristics and algorithm selection; a formal decision framework is missing.

The contribution is a controlled comparison across these lines of work, which, to our knowledge, has not been made before. Direct construction, generation hyper-heuristics and algorithm selection have each been studied inside their own pipelines. HeuriGuide places them under one outer loop, one verifier and one budget, so that the LLM's test-time authority is the only variable. Two results follow that the separate literatures do not give: less authority yields a higher QCI at a lower cost (0.597, 0.777, 0.795; Table C), and the order reverses on EE, where selection is bounded by the portfolio. Tables B2 and B3 compare the router directly with standard selectors on the same portfolio and features; all of them are below the router (0.632 to 0.788 vs. 0.795).

We suggest a simple rule for choosing how much authority to give the inner agent, based on one quantity measured before test time: the scale gap between demonstration and test instances, measured by input file size. If the gap is extreme, allow code generation. On EE the two demonstration graphs are 1–2 kB and the test graphs are 144 kB–11 MB, a gap of about 7,000×; on the other eight problems the gap is much smaller (at most 320×). EE is the one problem where generated code clearly beats selection.

W2. Implementation details are missing.

Section E in general response gives the configuration and the instance counts. The code will be released upon acceptance.

Q1. Mean and standard deviation instead of best of three.

See Table E: router 0.795±0.0030.795 \pm 0.003, adapter 0.777±0.0080.777 \pm 0.008, generator 0.597±0.0020.597 \pm 0.002. The ordering is unchanged. The paper's Fig. 3 already plots the three-run mean with its range, and Table 2 will report mean ±\pm sd.

Q2. Calls, tokens and time per setup; comparison under the same budget.

Table D gives the figures per test instance for one evaluation: router 7k tokens, one LLM call and 34 s; adapter 11k tokens, 2.4 calls and 95 s; generator 423k tokens and 58 s. Table C gives the totals for development plus three evaluations (9.29M, 16.34M and 296.64M). The router is the cheapest on every measure, so a common budget would constrain the other two organizations, not the router.

Q3. Why is the router below the baseline on TM and PSD?

On TM the router is within 0.024 of the baseline (0.559 vs. 0.583) and ahead of HeurAgenix (0.550) and the adapter (0.371). The remaining gap comes from the demonstration set. The five demonstration circuits have 66–224 LUTs in the reference mapping, while 19 of the 31 test circuits are larger, up to 47,559 LUTs. On the 12 test circuits inside the demonstration range the router reaches 0.685 (0.673 on the seven that are not demonstration circuits); on the 19 larger circuits, which the demonstrations do not cover, it reaches 0.486.

On PSD the router and the baseline are essentially tied (0.921 vs. 0.933), and the router is ahead of HeurAgenix (0.877) and the adapter (0.660). Its selection is at the oracle level (oracle 0.945; trained selectors in Tables B2 and B3 0.938–0.942). The difference of 0.012 comes from two of the 24 instances, the protein–DNA complexes 1d66 and 1lmb, which HeurAgenix does not solve either. On the other 22 instances the quality is 0.925.

Q4. Comparison with simple classifiers or standard portfolio selection where strategies work well.

Tables B2 and B3 give this comparison: over all nine problems the simple classifiers reach 0.784 and 0.788 and the standard portfolio-selection methods 0.632 to 0.782, against the router's 0.795, and the router needs no separately trained model.

Thank you for the rebuttal and for addressing my questions. I also apologize for my delayed response.

I have one new question regarding the appendix. It does not seem to be included after the manuscript. Could you please clarify where Section E, Table E, and Table D can be found?

My further comments are below.

First, I still find the manuscript difficult to follow for readers who are not very familiar with this research area. Several statements are confusing. In line 46, the paper states that "most existing LLM-based AHD algorithms employ an outer agent to optimize a strategy." However, the caption of Figure 1 says that "an outer agent iteratively improves what will be deployed," while the figure itself appears to show the outer agent generating an inner agent. In addition, I find both Figures 1 and 2 rather uninformative. They do not help readers outside this area, at least in my experience, understand the pipeline of HeuriGuide or recognize the key technical differences from prior methods.

Second, the paper does not convince me that the technical contribution is sufficiently significant for this venue. The proposed agent system appears to be substantially built around generating and improving algorithm code, much like a variety of relevant methods. The main difference seems to reside in the incremental agent modules.

Overall, I believe the manuscript is not yet ready for publication, and I regret that I will maintain my original score of 2 (weak reject).

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

This paper proposes HeuriGuide, a framework for calibrating LLM authority in test-time heuristic design. It investigates three agent organizations: solution generation, strategy adaptation, and strategy routing. Experiments on nine HeuriGym problems show that stronger procedural guidance generally improves performance, with the strategy router achieving the highest overall QCI of 0.805. However, direct generation or adaptation can outperform routing when existing strategy portfolios are insufficient.

Critical strengths
  1. The paper addresses a relevant problem in LLM-based automated heuristic design by investigating how test-time agent authority affects solution quality.
  2. The comparison of three agent organizations provides a clear experimental framework for understanding the trade-off between flexibility and reliability.
  3. Experiments across nine optimization problems, together with selection ablations and instance-level analyses, provide useful evidence supporting the main conclusions.
Critical weaknesses
  1. The methodological novelty is somewhat limited, as the three agent organizations largely build upon existing heuristic generation, selection, and adaptation techniques.
  2. The computational overhead of different organizations is insufficiently analyzed. Comparisons under matched LLM-call budgets and total execution costs would strengthen the conclusions.
  3. The experimental comparison with closely related methods, particularly dynamic heuristic selection approaches such as HeurAgenix, is limited, making it difficult to assess the advantages over existing techniques.
Questions for authors
  1. How do the three organizations compare under matched computational budgets, including LLM calls and strategy execution costs?
  2. Can the authors provide a direct comparison with existing test-time heuristic selection methods?
  3. To what extent do the performance improvements result from stronger strategy portfolios rather than the proposed test-time agent organizations?
3 comments
AuthorsOpenReview ↗

Response to Reviewer s2u1

Response to Reviewer s2u1

Thank you for the constructive comments. Tables A to F we refer to below are in the general response.

W1. Novelty is limited because the three organizations build on existing generation, selection and adaptation techniques.

The novelty of our paper is that it treats the LLM's test-time authority as a design variable and measures its effect in isolation. Existing LLM systems for heuristic design each fix one test-time role for the LLM (write the solution, write code, or pick a heuristic) inside their own pipeline, so the differences between them cannot be attributed to that role. To our knowledge, no prior work varies this authority while the benchmark, verifiers, evaluators, model and development protocol stay fixed. The paper makes three contributions.

  1. A framework. Three organizations that span the authority range (generate the solution, adapt a strategy, select a strategy) under one outer loop, one verifier and one budget.
  2. A finding that is not obvious in advance. Giving the LLM less authority at test time gives a higher QCI at a lower cost: generator 0.597 with 296.64M tokens, adapter 0.777 with 16.34M, router 0.795 with 9.29M (Table C).
  3. A characterization of when the order reverses. On EE all frozen strategies fail on the same instances and only generated code helps (Fig. 7). This case can be recognized before test time: the scale gap between demonstration and test instances is about 7,000× on EE and at most 320× on the other eight problems.

The new experiments strengthen these points: the router outperforms HeurAgenix under matched tokens (Table A) and all standard selectors on the same portfolio (Tables B2 and B3).

W2, Q1. Cost under matched budgets, including LLM calls and strategy execution.

The organization with the highest QCI is also the cheapest: router 9.29M tokens, adapter 16.34M, generator 296.64M (Table C), and per test instance the router needs the fewest tokens, one LLM call and the least time (Table D). A matched budget would therefore constrain the generator and the adapter, not the router. In execution, the router runs at most two strategies per instance; running all of them would give at most 0.867 (Table B1). HeurAgenix was run under the router's development token budget (Table A).

W3, Q2. Comparison with HeurAgenix and with test-time selection methods.

With matched development tokens, HeurAgenix reaches 0.681 and the router 0.795, and HeurAgenix leads only on EE (Table A). On the router's portfolio, standard selectors trained on its demonstration data reach 0.750 to 0.788, all below the router (Tables B2 and B3).

Q3. How much of the improvement comes from the portfolio and how much from the test-time organization?

The two are linked: a verified portfolio exists only because the test-time authority is restricted. The solution generator has full authority and no portfolio, and reaches 0.597. With the router's frozen portfolio, the fallback alone gives 0.441, a random strategy 0.702, the router 0.795 and the oracle 0.867 (Tables B1 and B3). The router's selection recovers more than half of the gap between random choice and the oracle, more than any standard selector. The organization also decides the result when selection is bounded by the portfolio: on EE no selection policy over the adapter's portfolio can exceed 0.434 (Fig. 7), and the adapter reaches 0.680 in its best run (0.625 on average) by generating code.

AuthorsOpenReview ↗

Follow-up on Our Rebuttal

Dear Reviewer s2u1,

Thank you again for your valuable comments on our submission.

As the discussion phase is approaching its end, we would appreciate your feedback on whether our rebuttal has adequately addressed your concerns. If any questions remain, we would be happy to provide further clarification.

If our responses have addressed your concerns, we would also appreciate your consideration in updating your evaluation accordingly.

Thank you for your time and consideration.

Thank you for the detailed response. The comparison with HeurAgenix addresses my concern about the baseline by matching the development token budget. The reported token counts and runtimes clarify the cost of each approach.

On the same strategy portfolio, the router scores 0.795, while the strongest standard selector scores 0.788. This small difference leaves me unsure how much the router adds. The evaluation includes the demonstration instances. I encourage the authors to report results on unseen instances separately.

The new results strengthen the evaluation. I still have concerns about the limited methodological novelty. I maintain my rating of 2

Comments on the paper

3 comments
AuthorsOpenReview ↗

General response to all reviewers (1/3)

General response to all reviewers (1/3)

We thank the reviewers for their careful reading. All new results and tables are collected here, and the individual responses refer to Tables A to F. All new results use GPT-5.4 at temperature 0 and the same frozen verifiers, evaluators and instances as the paper.

Summary of new results

  • Comparison with HeurAgenix (s2u1, Cqqk). With its development tokens matched to the router's, HeurAgenix reaches a nine-problem QCI of 0.681 and our strategy router 0.795 (Table A).

  • Comparison with standard algorithm selection (s2u1, Hoxg, Cqqk). On the router's frozen portfolio, standard selectors trained on the router's own demonstration data reach 0.750 to 0.788, below our router's 0.795 (Tables B1 to B3).

  • Cost (s2u1, Hoxg, Cqqk). The router uses the fewest tokens of the three organizations (9.29M) and our solution generator the most (296.64M) (Table C). Per test instance the router also needs the fewest tokens and the least time (Table D).

  • Variance (Hoxg). Over three complete evaluations: router 0.795±0.0030.795 \pm 0.003, adapter 0.777±0.0080.777 \pm 0.008, generator 0.597±0.0020.597 \pm 0.002 (Table E).

  • Setup details (Hoxg, Cqqk). Section E lists the configuration and the instance counts.

A. HeurAgenix under a matched token budget

We ran HeurAgenix (Yang et al., 2025) on all nine problems. Its development phase (heuristic generation and evolution) was capped at the tokens the router used for development on the same problem. At test time it uses its own LLM selector per instance. HeurAgenix needs problem-specific helper functions; ours check feasibility, describe the state and evaluate the objective, and none of them constructs, precomputes or ranks solutions.

Table A. HeurAgenix and the strategy router. Tokens = development plus one complete evaluation. Bold marks the better value.

ProblemHeurAgenix QCIValidRouter QCI (mean of 3)HeurAgenix tokensRouter tokens
OS0.95123/240.989891k738k
TM0.55030/310.559852k633k
GR0.93321/240.956764k751k
EE0.49013/230.329742k600k
IOP0.55328/280.924951k812k
PSD0.87722/240.921766k628k
PR0.79218/200.970926k837k
CP0.92212/140.959721k646k
PDTW0.0651/300.551912k660k
Overall0.6810.7957.52M6.30M

The router leads on eight problems and uses fewer tokens on all nine. HeurAgenix leads on E-graph Extraction (0.490 vs. 0.329), the problem on which the paper shows that selection is bounded by the portfolio. HeurAgenix uses 19% more tokens because its selector makes two calls per instance.

AuthorsOpenReview ↗

General response to all reviewers (3/3)

General response to all reviewers (3/3)

C. Token cost and run time

Table C reports total tokens for development plus the three evaluations behind the reported QCI (nine problems, 218 instances).

Table C. Total tokens over the nine problems (development plus three evaluations).

SystemQCITotal tokens
Solution generator0.597296.64M
Strategy adapter0.77716.34M
Strategy router0.7959.29M

QCI is the mean of three evaluations. Cost and QCI rank the three organizations in opposite order, so the router's lead does not come from more compute. The generator uses about 32 times the router's tokens because every instance is written into the prompt and every solution is written out in full. The router reads instance features only and makes one LLM call per instance.

Table D. Resources per test instance in one evaluation.

OrganizationLLM tokensRun time
Solution generator423k58 s
Strategy adapter11k95 s
Strategy router7k34 s

Tokens and time are the totals of one evaluation divided by the 218 instances. The router makes one LLM call per instance and runs at most two strategies; the adapter makes 2.4 calls on average.

D. Mean and standard deviation over three evaluations

The paper already shows the spread across runs: Fig. 3 plots, for every problem, the mean of the three complete evaluations with min–max whiskers, and Sec. 4.2 states that the nine-problem mean varies by at most 0.014 across them. Table E gives the numbers.

Table E. Nine-problem QCI of each complete evaluation.

OrganizationRun 1Run 2Run 3Mean ±\pm sdBest of three
Strategy router0.7950.7990.7930.795±0.0030.795 \pm 0.0030.805
Strategy adapter0.7860.7740.7720.777±0.0080.777 \pm 0.0080.787
Solution generator0.5980.5980.5950.597±0.0020.597 \pm 0.0020.599
Benchmark baseline0.728 (released)

Best of three takes the best complete run per problem, as in Table 2. The ordering of the three organizations is the same for the means, and the router's lowest run (0.793) is above the adapter's highest run (0.786).

E. Setup details

All three organizations and HeurAgenix use GPT-5.4 at temperature 0, G=5 generations, K=3 candidate solvers per generation, Docker with 8 CPU cores per problem, and a time limit of 300 s per instance. The baseline row is a reference point; the controlled comparisons are those among the three organizations and with HeurAgenix. The code will be released upon acceptance.

Table F. Demonstration and evaluated instances per problem.

ProblemDemonstration instancesEvaluated instances
OS524
TM531
GR624
EE223
IOP628
PSD524
PR520
CP514
PDTW630

As in the benchmark's scoring, the evaluated set includes the demonstration instances.

AuthorsOpenReview ↗

General response to all reviewers (2/3)

General response to all reviewers (2/3)

B. Standard selection methods on the router's portfolio

The paper analyzes the router's selection in two figures. Fig. 5 shows that the executed strategy is close to the best one in the portfolio: 82% of the scoreable instances reach η ≥ 0.9 and 56% attain the per-instance best. Fig. 6 compares the router with its own components and with the per-instance oracle (Table B1). Neither figure includes standard algorithm-selection methods; Tables B2 and B3 add them. All thirteen policies choose among the same frozen strategies and are scored by an offline replay in which every strategy was run on every instance, so there are no LLM calls and no run-to-run noise. The trained selectors use the same information as the router: the strategy outcomes of its demonstration runs and its instance features. Every policy executes the strategy it chooses and falls back to the fallback strategy if that solution is invalid.

Table B1. Policies in Fig. 6 of the paper (nine-problem QCI, reproduced by the replay).

PolicyQCI
Fallback strategy only0.441
Routing table only0.692
Inner agent only0.762
Strategy router0.795
Per-instance oracle = run every strategy0.867

Table B2. Simple machine-learning classifiers trained on the demonstration data (new).

PolicyQCI
Random forest classifier0.784
kNN (k = 3)0.788
Strategy router0.795

Table B3. Standard portfolio-selection methods (new).

PolicyQCI
Single best solver, raw mean cost (= routing-table global default)0.632
Random strategy per instance (mean of 2,000 draws)0.702
Pairwise voting classifiers0.750
Per-strategy performance regression (SATzilla-style)0.777
Single best solver, normalized score0.782
Strategy router0.795
  • Single best solver. One strategy is used for all instances of a problem: the one with the lowest raw mean cost on the demonstration instances (the routing table's global default), or the one with the highest mean normalized score.
  • kNN. Take the three demonstration instances with the most similar instance features and choose the strategy with the best mean score on them.
  • Random forest classifier. Predicts, from the instance features, which strategy was best on a demonstration instance.
  • Per-strategy performance regression (SATzilla-style). One regression model per strategy predicts its score from the instance features; the strategy with the highest prediction is chosen.
  • Pairwise voting. One classifier per pair of strategies predicts which of the two is better; the strategy with the most votes is chosen.
  • Offline replay of the router. The choices the router made in one complete evaluation, re-scored with the replay data; it confirms that the replay agrees with the actual runs (0.787 vs. 0.795).

All standard methods in Tables B2 and B3 are below the router.

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

Related papers

Discussion (0)

Sign in to comment.