- 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
- The question that the paper studies is useful and clear.
- 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.
- The experimentation is generally clean. The authors used a published benchmark and frozen verifiers and evaluators to provide fair comparison.
Critical weaknesses
- 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.
- 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
- 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?
- 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
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.
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.
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.