acceptodds
Under review as a conference paper at ICLR 2027

Evolving Evaluation Gates for Efficient LLM-Based MILP Branching Policy Search

Abstract

Efficient branching policies can substantially accelerate Mixed Integer Linear Programming (MILP) solvers, but discovering such policies remains computationally expensive. Recent LLM-based frameworks, such as LLM4Branch, automate branching-policy discovery by generating executable policy programs and optimizing their parameters with solver feedback. However, this process still requires many costly MILP solves during candidate evaluation, especially in the zeroth-order parameter optimization stage. In this work, we study whether this evaluation cost can be reduced without changing the final validation protocol or the branching-policy search space. We propose a computation-aware Stage-2 pre-evaluation gate that operates inside the Bayesian optimization loop: before each proposed parameter trial is evaluated by the solver, the gate uses historical trial behavior, local objective structure, uncertainty checks, and early-stop signals to decide whether the trial should be evaluated or safely skipped with a conservative penalty. We further introduce a curated and archive-evolved gate policy pool, allowing gate strategies to be selected and adapted across candidate programs. Experiments on standard MILP benchmarks show that the proposed gate consistently saves a nontrivial number of training MILP solves, while preserving competitive final policy quality in several settings. Our results suggest that LLM-guided branching-policy discovery can be made more computation-efficient by optimizing not only the policies themselves, but also the evaluation process used to discover them.

Primary area:
optimization
Keywords:
Large Language Models, Mixed Integer Linear Programming, Branching Policies, Bayesian Optimization, Mathematical Optimization, Operations Research

Reviews

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

This paper addresses the heavy solver evaluation bottleneck during LLM-guided MILP branching policy discovery (e.g., LLM4Branch). The authors propose an evaluation gate inside the Stage-2 Bayesian optimization loop that inspects BO-state signals to decide whether to evaluate or skip a proposed parameter trial, assigning skipped trials a conservative penalty. Across four standard MILP benchmark families, the method saves 5.19%–18.92% of Stage-2 solver calls while maintaining final policy quality.

Critical strengths

Exploring the design of MILP branching policies based on LLM is a frontier and impactful research direction.

Critical weaknesses
  1. As shown in Table 2, the discovered policies offer no significant solving performance improvements on held-out sets, and solving time even degrades on hard cauctions instances (+14.53%). Because branching policy search is performed offline as a one-off procedure, saving modest offline search time at the expense of downstream solving quality offers marginal practical value. Moreover, the pipeline strictly follows LLM4Branch, with the simple modification being an early-skipping gate heuristic inside the inner-loop BO. These makes the novelty and value of this maniscript incremental and below the bar for ICLR.

  2. Several notations are ambiguous or missing definitions, such as TpT_p in Equation (8). Furthermore, because the framework relies heavily on LLM4Branch, the paper had better provide a more clear introduction of LLM4Branch in the background section.

Questions for authors
  1. What specific LLM (e.g., model name, version), prompting strategy, and decoding settings were used during policy generation?

  2. How is the gate decision in Equation (5) concretely implemented?

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

The paper augments LLM4Branch with trial-level gates inside Bayesian parameter optimization. Gates decide whether to run training MILP evaluations, with skipped trials receiving artificial penalty feedback. A gate pool and archive support gate selection, aiming to reduce policy-discovery cost while preserving final branching-program quality.

Critical strengths
  • A useful fine-grained intervention: Repeated MILP evaluations during parameter tuning are expensive, making selective evaluation practically relevant. The intervention operates within each program’s parameter search, while final parameters are selected from genuinely evaluated trials.
Critical weaknesses
  • The central algorithm is insufficiently specified. The claimed eight gates are described through qualitative policy families rather than executable decision rules. Penalties, uncertainty/audit mechanisms, and archive rewards, selection, and updates are also incompletely defined. Algorithm 1 specifies the surrounding workflow without resolving these central operations. These omissions go beyond minor hyperparameters: they prevent a precise understanding, assessment, and reproduction of the proposed method.
  • The technical advance is limited, and its incremental value and scope are not established experimentally. Program generation, filtering, and parameter optimization largely follow LLM4Branch. The additions are primarily heuristic trial screening, artificial feedback, and archive-based selection. Their advantage over simpler budget-allocation mechanisms remains unclear. There are no matched-compute controls using fewer BO trials, random skipping, or simple stopping rules. Solver-call counts alone do not establish end-to-end efficiency. Cross-benchmark reuse of gate settings and archive history, their configuration costs, and gate/archive transfer are also unestablished. The evidence therefore supports, at most, a localized efficiency modification rather than a sufficiently demonstrated broader methodological contribution.
Questions for authors
  • Core mechanism: Please provide an operational specification of the gate pool and archive selection/update mechanism.
  • Incremental value and actual efficiency: Does the existing evidence establish an advantage over reduced BO budgets or simple skipping rules under matched actual compute, including gate configuration and archive overhead?
  • Artificial feedback: Why should skipped trials update BO through artificial penalty observations? Do existing ablations or audit records establish the benefit, sensitivity, and risk of rejecting improving configurations?
  • Cross-task reuse: Are identical gate settings used across benchmark families, and is the archive reset for each search? Is there existing evidence that gates or archive experience transfer and reduce configuration or exploration costs on new tasks?
Reviewer_4mTxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper addresses the computational cost of LLM-based branching-policy discovery for MILP solvers. Building on an LLM4Branch-style pipeline, in which an LLM generates executable branching-policy programs and Stage-2 Bayesian optimization (BO) tunes their numerical parameters through repeated training MILP solves, the authors propose a trial-level evaluation gate that operates inside the Stage-2 BO loop. Before each proposed parameter trial is evaluated, the gate uses lightweight BO-state features to decide whether to run the training solves or to skip the trial. Skipped trials return a conservative penalty, set slightly above the current best objective, so that the BO ask–tell loop remains well defined. The authors further maintain a pool of gate policies with different quality–cost trade-offs, with policy selection guided by an archive that rewards candidate quality and compute savings while penalizing excessive skipping; gate metadata are kept separate from the outer program search. Held-out evaluation remains ungated throughout. Compute savings are reported both as direct savings and as observed reduction relative to a matched no-gate baseline. Experiments on four MILP benchmarks report direct saving rates of 5.19%–18.92%, with held-out runtime changes that vary by benchmark and difficulty level, along with a single-run ablation using a frozen initial gate pool on combinatorial auctions.

Critical strengths
  • The paper appears interesting to me. Unlike existing work like AlphaEvolve or FunSearch which focus on searching for better heuristics, this paper instead optimizes the evaluation overheads during parameter optimizing. This is important, as evaluating candidate programs/parameters is the major cost during evolving.

  • The proposed gating scheme is applied only to Stage-2 BO, which does not affect the outer layer of LLM program evolution and the final held-out evaluation, making the method applicable to a wide range of heuristic design method.

  • The authors clearly distinguished direct and observed saving in computation accouting, and faithfully attributed the most of observed reduction to the change of # of candidates on facilitates benchmark. I also appreciate the authors for reporting negative results (e.g., on indset and cauctions hard).

Critical weaknesses
  • Given fixed BO iteration budget, skipping evaluation is largely equivalent to reducing the number of effective BO iterations (except the conservative penalty). Moreover, according to Fig. 6, most skips happen at the end of BO iterations, which is effectively equivalent to early-stopping. I therefore would like to see additional results of (i) reduce n_call and (ii) random skip.

  • It is unclear to me that how gating policies are embodied (e.g., rule? code? LLM? or simple MLP?). If they are embodied by rule and code, the authors should explicitly document in appendix; if they are embodied by LLM or MLP, the training recipes and data should also be documented.

  • It is also unclear how archive evolution is implemented, especially which elements to evolve, who perform the evolve. I think this is critical to reproduce the research.

  • The use of conservative penalty is also unclear. Neither the schedule of λt\lambda_t is specified nor ablated. In addition, I think the use of conservative penalty also needs justifications.

Questions for authors

N.A.

Comments on the paper

1 comment

Dear authors and reviewers,

The author-reviewer discussion period closes on November 18 (AoE). Please engage in response periods so that we have our issues discussed thoroughly.

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.