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

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.