acceptodds
Under review as a conference paper at ICLR 2027

CO-Agent: Cost-Aware Combinatorial Optimization via Verifier-Guided Distillation and Skill Evolution

Abstract

Language-model agents can generate optimization programs, invoke mathematical solvers, and repair execution failures, but strong performance often comes at the cost of large models and repeated inference. We investigate how small language models can coordinate these capabilities to solve combinatorial optimization (CO) problems under limited computational budgets. We introduce CO-Agent, a framework that combines a compact planner and generator with a solver harness and an evolving repository of reusable optimization skills. The framework integrates three complementary learning mechanisms. First, cost-aware planner optimization learns to allocate generation, solver, and refinement resources from the outcomes of complete agent trajectories. Second, verifier-guided distillation trains the generator using re-executed and verified teacher corrections on states visited by the student. Third, repository-level skill evolution evaluates candidate skills by their marginal contribution to deployed-agent utility under natural retrieval, accounting for retrieval interference and negative transfer. A shared execution–verification loop grounds all three mechanisms in feasibility, solution quality, and computational cost. Experiments on CO-Bench, FrontierCO, and HeuriGym demonstrate that CO-Agent achieves competitive solution quality with lower inference cost, while ablation and continual-evolution studies show the complementary benefits of the three mechanisms and sustained improvements in skill reuse.

Primary area:
optimization
Keywords:
Combinatorial Optimization, LLM Agents, Verifier-Guided Learning

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_tiKFOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces CO-Agent, a compact language-model agent for combinatorial optimization. It combines cost-aware planner training (CARP), verifier-guided distillation from teacher repairs on student-visited states (CO-VGOPD), and repository-level skill evolution (AUSE). The agent generates, executes, verifies, and repairs solver code within a computational budget. Experiments on CO-Bench, FrontierCO, and HeuriGym report improved solution quality and feasibility, supported by component ablations, quality–cost comparisons, and continual skill-evolution studies.

Critical strengths
  1. Repository-level skill evaluation addresses a meaningful failure mode. AUSE evaluates whether inserting a skill improves the deployed agent under natural retrieval, rather than assuming that standalone skill quality translates into system-level gains. The comparisons with and without RMU admission, together with the negative-transfer analysis, provide useful evidence for this design.

  2. The experiments examine several aspects of the system. Beyond final performance, the paper includes training-objective comparisons, component ablations, budget generalization, and previous-task retention. These studies help distinguish the intended roles of planning, corrective distillation, and skill evolution.

Critical weaknesses
  1. The evaluation protocol does not sufficiently establish fairness or generalization. The paper states that training and repository evolution use training/development data, but does not specify the task and instance counts, split construction, or separation of problem families across training, skill evolution, admission, and final testing. This is particularly important for the claimed generalization on HeuriGym. Table 1 also does not identify the backbone models, inference budgets, or solver access used by the agent baselines. Comparing a trained agent with a learned skill repository against larger direct-generation models demonstrates system capability, but does not isolate the contribution of the proposed learning mechanisms. Stronger controls would use the same trained generator, tools, initial repository, and explicit inference limits.

  2. The central cost-efficiency claims are difficult to assess from the reported measurements. Appendix A.1 defines cost as a weighted combination of normalized model calls, tokens, solver time, execution time, and wall-clock time, but does not provide the numerical weights and reference quantities needed to reproduce the comparison. Absolute resource measurements and sensitivity to these choices are also needed, since the components partly overlap. Excluding the teacher from deployment cost is reasonable, but training and repository-evolution costs should be reported separately to establish the practical trade-off. There is also an unresolved reporting discrepancy: Table 3 gives the full system a gap of 4.7 and FR of 95.2%, whereas Table 1 reports 4.7/92.0% on CO-Bench and 26.4/95.2% on FrontierCO. The setting behind Table 3 is not identified.

Questions for authors
  1. Could you provide the task and instance counts for each training, development, skill-evolution, admission, and test split? Are evaluation problem families unseen during both model training and repository construction?

  2. Which backbone, token budget, candidate budget, solver limits, and tool access are used for each agent baseline? Do the gains remain when these methods share the same trained generator and initial skill repository?

  3. What numerical weights and normalization constants define the reported cost? Could you provide absolute token usage, model calls, solver time, and end-to-end latency, alongside separate training and repository-construction costs?

  4. Which benchmark and configuration does Table 3 evaluate, and how should its full-system numbers be reconciled with Table 1?

  5. How are admission neighborhoods sampled and refreshed during repeated skill evolution? Are the reported RMU and NTR measured on separate evaluation tasks? A 95% bootstrap interval for one candidate does not by itself address repeated adaptive selection on the same admission set.

2 comments

We thank the reviewer for these thoughtful and detailed questions covering data partitioning, baseline fairness, cost accounting, table interpretation, and the statistical protocol of our skill evolution pipeline. Below we address each comment point-by-point.


Comment 1 Could you provide the task and instance counts for each training, development, skill-evolution, admission, and test split? Are evaluation problem families unseen during both model training and repository construction?

Response: We thank the reviewer for this careful question regarding data splits and potential leakage. We answer from two separate perspectives, covering model training and AUSE skill evolution: (1) For model training of CARP and CO-VGOPD, we adopt three combinatorial optimization benchmarks: CO-Bench (36 problem families, 6482 instances), FrontierCO (8 problem families, 416 instances), and HeuriGym (9 problem families, 218 instances). Splitting is performed at the problem-family level following an 8:2 partition. Within the 80% of problem families allocated to the training pool, we randomly sample 80% of their instances for training and the remaining 20% for validation. The held-out 20% of problem families together with all their associated instances constitute the test set. (2) For the AUSE skill-evolution pipeline, we initialize the skill repository with 46 clustered optimization skills derived from OptSkills. All skill evolution and admission procedures are carried out using the training splits of the three benchmarks, while final evaluation is performed on the test split.

Crucially, all problem families and instances in the test set remain unseen during both model training and skill repository construction, which effectively prevents data leakage.

Modifications: Appendix C.1, Dataset partitions.


Comment 2 Which backbone, token budget, candidate budget, solver limits, and tool access are used for each agent baseline? Do the gains remain when these methods share the same trained generator and initial skill repository?

Response: Thank you for this valuable question. We report token consumption and solving turns for CO-Agent and all baselines in Appendix B.1 (Cost reporting), with visualizations in Figure 6–8. We further add a controlled ablation in Appendix C.6 and Table 6 on the CO-Bench test set, where we adopt the same trained Qwen3-4B generator and initial skill repository. Although using our skill repository or our generator individually improves the baselines, these variants still lag behind the full CO-Agent. This confirms our gains are not only from the generator or static skills, but rely on the CARP planner and AUSE evolution mechanism. Moreover, we have explicitly documented the backbone, token budget, candidate budget, solver limits and tool access rules for each agent baseline in Appendix C.1 to ensure comparison fairness. We hope these additions address your concern, and we would appreciate your favorable consideration.

Modifications: Appendix B.1, Appendix C.6, Table 6.


Comment 3 What numerical weights and normalization constants define the reported cost? Could you provide absolute token usage, model calls, solver time, and end-to-end latency, alongside separate training and repository-construction costs?

Response: Thank you for this question. We have supplemented the absolute raw cost statistics for CO-Agent and all baselines in Appendix B.1 (Cost reporting), including token consumption, model call counts, solver runtime and end-to-end wall-clock latency, visualized in Figure 6–8. The numerical aggregation weights and fixed normalization constants for the unified trajectory cost are also explicitly stated there in: αm=0.30,αt=0.30,αs=0.25,αe=0.10,αw=0.05\alpha_m=0.30,\alpha_t=0.30,\alpha_s=0.25,\alpha_e=0.10,\alpha_w=0.05, with reference constants Cmodelref=120.0C^{\text{ref}}_{\text{model}}=120.0, Ctokenref=3500.0C^{\text{ref}}_{\text{token}}=3500.0, Csolverref=320.0C^{\text{ref}}_{\text{solver}}=320.0, Cexecref=100.0C^{\text{ref}}_{\text{exec}}=100.0, Cwallref=1050.0C^{\text{ref}}_{\text{wall}}=1050.0. The one-time separate training of CARP, CO-VGOPD and the AUSE skill repository construction costs approximately 120 GPU-hours on RTX 4090, excluding the inference evaluation overhead on held-out test instances. We hope these details fully clarify our cost definition and resource consumption. We would appreciate your favorable consideration if the response addresses your concern.

Modifications: Appendix B.1

Comment 4 Which benchmark and configuration does Table 3 evaluate, and how should its full-system numbers be reconciled with Table 1?

Response: We thank the reviewer for this question. We conduct ablation studies separately on all three benchmarks. In the original manuscript, Table 3 only presented ablation results from CO-Bench and contained an entry error where the FR value was incorrectly taken from FrontierCO. We have reprocessed the ablation experiments and revised Table 3 to report metrics averaged across the three benchmarks. Meanwhile, we have added the unified trajectory cost metric to Table 1 to clearly demonstrate the cost advantage of CO-Agent.

Modifications: Table 1, Table 3.


Comment 5 How are admission neighborhoods sampled and refreshed during repeated skill evolution? Are the reported RMU and NTR measured on separate evaluation tasks? A 95% bootstrap interval for one candidate does not by itself address repeated adaptive selection on the same admission set.

Response: We thank the reviewer for raising this important question regarding the reliability of repository-level admission in AUSE. We appreciate this observation and agree that the original manuscript did not sufficiently clarify the admission protocol and the statistical scope of the bootstrap evaluation.

(1) Admission-neighborhood construction and refreshing. In the current implementation, AUSE is designed as a two-stage process consisting of local skill evolution followed by repository-level admission. During local evolution, multiple rounds of parent selection, offspring generation, and fitness evaluation are performed on the evolution neighborhood. Once this process terminates, a single locally selected candidate is submitted for repository-level admission. Admission is therefore performed once at the end of each skill-evolution process, rather than repeatedly for intermediate offspring. The current implementation does not include an additional dynamic refreshing mechanism for admission neighborhoods, which we now clarify in the revised manuscript.

(2) RMU and NTR evaluation. Both RMU and NTR are computed on the same admission evaluation task set through paired counterfactual evaluations. Specifically, we execute the original repository and the augmented repository on identical problem instances under the same natural-retrieval mechanism and execution protocol. This paired design controls for differences in problem difficulty and isolates the marginal effect of adding the candidate skill. More importantly, it evaluates the behavior of the complete agent after repository augmentation, rather than relying solely on the candidate skill's standalone fitness. This distinction is central to AUSE: a skill is admitted based on its actual contribution to the deployed agent, accounting for both retrieval behavior and potential negative transfer.

(3) Repeated adaptive selection and bootstrap interpretation. We agree with the reviewer that a 95% bootstrap interval for an individual candidate does not, by itself, provide statistical guarantees against repeated adaptive selection on a shared admission set. In our current implementation, the bootstrap interval is intended to quantify the uncertainty of the paired RMU estimate for the candidate being evaluated, rather than to claim control over arbitrary repeated adaptive testing. We acknowledge that repeatedly reusing the same admission tasks across multiple skill-evolution processes could introduce a risk of overfitting to the admission set. Addressing this issue through more rigorous admission-task refreshing and statistical control across repeated admission decisions is an important direction for future work.

We sincerely appreciate the reviewer for highlighting this issue, which has helped us improve the transparency of AUSE and identify an important direction for its further development.

Thank you again for your suggestion.

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

This paper studies how a small model (Qwen3-4B) can solve combinatorial optimization problems under a limited compute budget. To improve performance while controlling costs, the authors propose three learning mechanisms: CARP trains the planner with GRPO, considering feasibility, solution quality, and cost; CO-VGOPD uses a 14B teacher to repair failures encountered by the student, retains only verifier-approved improvements, and weights distillation by the size of the improvement; AUSE evolves skills through submodular parent selection and decides whether to admit them into the repository using repository marginal utility (RMU) and negative transfer rate (NTR), measured by comparing performance before and after insertion.

Across CO-Bench, FrontierCO, and HeuriGym, the 4B CO-Agent outperforms 32B reasoning models and many other baselines.

Critical strengths
  1. Improving small models' ability to solve combinatorial optimization problems while reducing costs is a meaningful research direction.
  2. The execution framework is reasonably designed.
  3. The evaluation covers a broad range of baselines and experiments, with comprehensive ablation studies.
Critical weaknesses

The novelty is limited: the three modules mainly adapt existing methods, namely Flow-GRPO, TGOPD, and evolutionary heuristic design methods such as EoH/HiFo.

The claim of lower cost lacks sufficient evidence: the main results table (Table 1) does not report costs, and training costs are not reported at all.

The fairness of the comparisons is unclear: the paper does not specify the backbones or compute budgets used by the LLM agent baselines.

Important reproducibility details are missing: key hyperparameter values are not provided, the source and size of the training data are unclear, and the teacher is described only as a "14B-class" model without specifying the exact model.

Questions for authors

Could you provide additional information to address the weaknesses above?

1 comment

We appreciate your thoughtful critique on the novelty of our modules, cost evidence, comparison fairness and missing reproducibility details. These comments push us to better articulate our tailored CO-specific innovations and solidify the empirical support for our method. Our responses are as follows.

Comment 1 The novelty is limited: the three modules mainly adapt existing methods, namely Flow-GRPO, TGOPD, and evolutionary heuristic design methods such as EoH/HiFo.

Response: We appreciate this comment. We acknowledge that our framework draws inspiration from existing approaches including Flow-GRPO, TGOPD, and evolutionary heuristic methods like EoH and HiFo. Nevertheless, Flow-GRPO and TGOPD are not originally designed for combinatorial optimization, and EoH and HiFo do not perform evolution over optimization skills. Each of our modules incorporates non-trivial custom designs tailored to combinatorial optimization. CARP employs a reward function specially aligned with CO objectives, and Figure 4 verifies that CARP achieves better performance than Flow-GRPO. CO-VGOPD adopts a distinct loss formulation compared with TGOPD. Unlike EoH and HiFo, which evolve prompts directly, AUSE evolves executable optimization skills and features a dedicated submodular utility function for repository-level admission, which constitutes one of our key contributions. These problem-specific adaptations and refined training designs lead to the consistent empirical gains observed in our experiments, particularly under the practical setting where both solution quality and computational cost must be optimized jointly.


Comment 2 The claim of lower cost lacks sufficient evidence: the main results table (Table 1) does not report costs, and training costs are not reported at all.

Response: We appreciate this comment pointing out the insufficient evidence for our cost advantage claim. To address this issue, we have extended Table 1 by incorporating the unified trajectory cost for all compared methods on each of the three benchmarks. The augmented results directly support the conclusion that CO-Agent achieves superior efficiency. Beyond inference-time trajectory cost, we also enrich training-side documentation in Appendix C.1 (EXPERIMENT SETUP). This subsection covers dataset partition protocols, full hyperparameter settings, hardware specifications and training schedules. These materials provide transparent information about the offline training overhead and facilitate full experimental reproducibility.

Modifications: Table 1 (added cost columns), Appendix C.1.


Comment 3 The fairness of the comparisons is unclear: the paper does not specify the backbones or compute budgets used by the LLM agent baselines.

Response: We thank the reviewer for raising this concern about comparison fairness. We have clarified the backbone model and computational budget settings for all LLM-agent baselines in the revised manuscript. All baseline LLM agents adopt the same Qwen3-4B backbone (without enabling native reasoning) and are constrained to identical token budgets, solver access privileges and tool invocation limits as CO-Agent. This consistent setup ensures a fair comparison across all evaluated methods.

Modifications: Appendix C.1.


Comment 4 Important reproducibility details are missing: key hyperparameter values are not provided, the source and size of the training data are unclear, and the teacher is described only as a "14B-class" model without specifying the exact model.

Response: We appreciate this comment on reproducibility. We have supplemented all missing key details in Appendix C.1 (EXPERIMENT SETUP). First, we report the exact identifier of the teacher model, which is Qwen3-14B. Second, we list the complete set of hyperparameters for CARP, CO-VGOPD and AUSE. Third, we elaborate the source, family-level partition rule and scale of the training, validation and test datasets for all three benchmarks. Together, these specifications provide sufficient information for reproducing our experiments.

Modifications: Appendix C.1.

In summary, we have clarified the distinctions between our modules and prior related methods, strengthened the evidence for our cost advantage, standardized baseline settings for fair comparison, and completed all missing hyperparameter and dataset documentation. We hope these revisions adequately address your concerns.

We further note that CO-Agent is built for the explicit trade-off between solution quality and inference cost. Its delicate training mechanisms and new skill evolution paradigm are core innovations of our framework. Our vision is to enable CO-Agent to serve as a practical optimization tool on affordable personal computers. We view this work as a valuable exploratory step toward real-world, low-resource combinatorial optimization. We hope our revisions resolve your questions and kindly ask you to consider upgrading your evaluation.

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

CO-Agent explores how compact language-model agents can solve combinatorial optimization problems under limited computational budgets. The framework combines planning, code generation, and reusable optimization skills, using execution and verification feedback to improve the solving process. Experiments across several benchmarks examine solution quality and computational efficiency.

Critical strengths
  1. The paper addresses a practically relevant problem by studying optimization agents under limited computational resources. Its focus on compact models is relevant to making capable AI systems more accessible and efficient.
  2. The work also raises useful questions about sustained agent improvement through accumulated knowledge, and the experiments cover diverse optimization settings.
Critical weaknesses
  1. Cost reporting lacks sufficient detail on token consumption and the number of solving turns. The normalization constants and aggregation weights are also unspecified. So the claimed efficiency advantage is difficult to verify.
  2. The full-system result in Table 3 does not match the benchmark-specific results in Table 1. It appears to combine the best Gap from CO-Bench with the best FR from FrontierCO. I think there's no reason to do that. It makes the ablation results difficult to interpret.
  3. Important experimental details including data partitions and training schedules remain unclear.
Questions for authors
  1. Could the authors provide token consumption and the number of solving turns for CO-Agent and the baselines, along with the normalization constants and weights used to calculate cost?
  2. Could the authors clarify whether the Gap and FR in Table 3 come from the same benchmark and evaluation setting? Providing uncertainty estimates for Tables 2–4 would also be helpful.
  3. A fuller description of data partitions and training schedules would help reproducing the experiments.
3 comments

We thank you for your careful and thorough review. Your questions about cost computation, table consistency and experimental reproducibility helped us fix critical reporting gaps and strengthen the empirical grounding of our efficiency claims. Below we address each comment point-by-point.

Comment 1 Cost reporting lacks sufficient detail on token consumption and the number of solving turns. The normalization constants and aggregation weights are also unspecified. So the claimed efficiency advantage is difficult to verify. Could the authors provide token consumption and the number of solving turns for CO-Agent and the baselines, along with the normalization constants and weights used to calculate cost?

Response: We appreciate this important comment regarding the transparency of our cost metric. To facilitate reproducibility, we have enriched the cost reporting section in Appendix B.1. We now provide disaggregated resource consumption of CO-Agent and all compared baselines on the three benchmarks, covering token consumption and solving turns, with supporting visualizations in Figure 6 to 8. The normalization constants and aggregation weights for each cost component are also fully documented in this appendix, where the unified trajectory cost aggregates five normalized resource terms (model, token, solver, execution, wall-clock) with weights αm=0.30,αt=0.30,αs=0.25,αe=0.10,αw=0.05\alpha_m=0.30,\alpha_t=0.30,\alpha_s=0.25,\alpha_e=0.10,\alpha_w=0.05, using fixed reference constants. Moreover, we have integrated the unified trajectory cost into Table 1. The updated experimental results demonstrate that CO-Agent achieves superior solution quality while incurring the lowest computational cost, clearly verifying its efficiency advantage.

Modifications: Appendix B.1, Figure 6–8, Table 1.


Comment 2 The full-system result in Table 3 does not match the benchmark-specific results in Table 1. It appears to combine the best Gap from CO-Bench with the best FR from FrontierCO. I think there's no reason to do that. It makes the ablation results difficult to interpret. Could the authors clarify whether the Gap and FR in Table 3 come from the same benchmark and evaluation setting? Providing uncertainty estimates for Tables 2–4 would also be helpful.

Response: We thank the reviewer for identifying this critical typo. Originally, there was an error when populating the ablation table: we mistakenly mixed the best Gap from CO-Bench and the best FR from FrontierCO, which led to inconsistent reporting. In the revised manuscript, Table 3 now reports the average performance across all three benchmarks for each ablation variant, where Gap, FR and Cost for every variant are computed on the same set of benchmarks and under identical evaluation protocols. We have also supplemented uncertainty estimates (standard deviations) for Tables 2, 3 and 4.

Modifications: Table 3 (corrected ablation values), Tables 2–4 (added standard deviations).


Comment 3 Important experimental details including data partitions and training schedules remain unclear. A fuller description of data partitions and training schedules would help reproducing the experiments.

Response: We thank the reviewer for the suggestion to enrich experimental details for reproducibility. We have added a dedicated section in Appendix C.1 (EXPERIMENT SETUP), which contains three paragraphs: Dataset partitions, Model and hyperparameter configurations, and Hardware and training setup. These complementary details facilitate the reproduction of our experiments.

Modifications: Appendix C.1.

To summarize, we have supplemented fine-grained resource statistics, clarified the cost aggregation formula, fixed the misaligned ablation table, and added comprehensive experimental setup details in the appendix. All these revisions make our results interpretable and fully reproducible.

Beyond the revisions responding to your questions, we emphasize that CO-Agent is an agent framework designed to explicitly balance solving quality and computational cost. Its cost planning, solver configuration, carefully crafted training pipeline and novel optimization-skill evolution mechanism bring innovations to both algorithm and architecture design. As a practical follow-up direction, we plan to conduct model quantization in future work. Our long-term vision is to turn CO-Agent into an accessible optimization solver that runs on low-cost consumer PCs. We believe this work represents a promising and practical exploration toward lightweight, deployable combinatorial optimization agents. We hope these revisions address your concerns and would appreciate your consideration for raising our score.

The cross-benchmark mixing is fixed, but Table 3 still does not state that its values are averaged over three benchmarks or how Gap is rescaled, provides no per-benchmark ablations, and the text still reports 0.66→1.00 for w/o CARP while the table shows 0.33→0.61. I am keeping my score unchanged.

We appreciate this feedback. We have added per-benchmark ablation results in Appendix C.7. The Gap metric is computed as ∣obj−opt∣/∣opt∣|\text{obj}-\text{opt}|/|\text{opt}| for each instance, which is then normalized and averaged across the three benchmarks for Table 3. We have also fixed the inconsistent numerical description (0.66→1.000.66\rightarrow1.00) in the main text to match Table 3 (0.33→0.610.33\rightarrow0.61). Thank you again for your valuable comments.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.