BiFE: Search-Efficient Discovery of CPU-Only Branching Policies via LLM-based Bi-Fidelity Evolution

Ce Zhang; Bin Zhang; Zhiwei Xu; Hao Chen; Xinyue Lu; Shanwei Fan; Yingxuan Teng; Guoliang Fan

cs.AISep 29, 2026

BiFE: Search-Efficient Discovery of CPU-Only Branching Policies via LLM-based Bi-Fidelity Evolution

Authors: Ce Zhang, Bin Zhang, Zhiwei Xu, Hao Chen, Xinyue Lu, Shanwei Fan, Yingxuan Teng, Guoliang Fan

Organizations: Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences · Shandong University

Abstract

In branch-and-bound (B&B) for mixed-integer linear programming (MILP), branching variable selection critically impacts efficiency. Existing neural branching policies often require GPU inference, while CPU-efficient symbolic expressions lack the representational capacity for complex logic. Large Language Model (LLM)-generated code provides a flexible search space for designing lightweight branching rules with diverse algorithmic logic. To discover effective rules within LLM-based evolutionary frameworks, a core challenge arises: full B&B evaluation on real instances is prohibitively expensive, whereas offline imitation learning suffers from distribution shift. To address this, we introduce a Bi-Fidelity Evolutionary framework (BiFE). It employs low-fidelity imitation scores as a rapid pre-screener and selectively applies high-fidelity on-instance evaluation only to elite candidates, effectively balancing search efficiency with performance reliability. Experiments validate both the search efficiency of BiFE and the competitiveness of its discovered rules, which outperform the SCIP solver and other baselines on CPUs, and even surpass certain GPU-based neural policies.

Figures & tables

Figure 1: The overall framework of BiFE. To balance search efficiency and rule quality, $F_{HF}$ evaluates heuristics via expensive MILP solving while $F_{LF}$ offers a cheap surrogate by measuring consistency with strong-branching decisions. An LLM generator produces new heuristics through three operations: initialization, crossover, and mutation. The evolutionary process has two stages: (1) Initialization: the LLM generates an initial population, ranked by $F_{LF}$ with the top $\alpha$ forming the elite set $\mathcal{E}$ for $F_{HF}$ evaluation. (2) Evolutionary Loop: parent selection is elite-prioritized, where elites are ranked by $F_{HF}$ and others by $F_{LF}$ , and selected parents are passed to the LLM for crossover or mutation. New candidates with $F_{LF}$ exceeding threshold $\tau$ undergo $F_{HF}$ evaluation and are admitted into $\mathcal{E}$ . Survival selection retains all elites and fills the remaining slots from the general population. This selective allocation lets BiFE explore broadly with $F_{LF}$ while using $F_{HF}$ to correct the surrogate on promising candidates.

Figure 2: LLM-based rule generator. Given an operation instruction (initialization, crossover, or mutation), a problem description, and a rule template, the LLM generates a new rule. The LLM-generated rules undergo evolution and selection within the BiFE framework to yield an optimal rule.

Method	CA		SC		MIS		CFL
	Nodes	Time	Nodes	Time	Nodes	Time	Nodes	Time
RPB	$8.79\mathopen{(}3.97\mathclose{)}$	$2.31\mathopen{(}1.60\mathclose{)}$	$24.93\mathopen{(}8.88\mathclose{)}$	$6.13\mathopen{(}1.75\mathclose{)}$	$30.71\mathopen{(}9.47\mathclose{)}$	$8.74\mathopen{(}1.72\mathclose{)}$	$65.51\mathopen{(}5.64\mathclose{)}$	$33.70\mathopen{(}2.07\mathclose{)}$
FiLM	$57.68\mathopen{(}2.93\mathclose{)}$	$2.01\mathopen{(}1.47\mathclose{)}$	$87.23\mathopen{(}4.00\mathclose{)}$	$5.20\mathopen{(}1.68\mathclose{)}$	$108.52\mathopen{(}10.57\mathclose{)}$	$13.78\mathopen{(}2.48\mathclose{)}$	$228.93\mathopen{(}3.17\mathclose{)}$	$30.82\mathopen{(}2.29\mathclose{)}$
Symb4CO	$63.10\mathopen{(}3.06\mathclose{)}$	$1.59\mathopen{(}1.48\mathclose{)}$	$114.74\mathopen{(}4.37\mathclose{)}$	$4.93\mathopen{(}1.76\mathclose{)}$	$70.00\mathopen{(}7.07\mathclose{)}$	$6.35\mathopen{(}1.66\mathclose{)}$	$264.45\mathopen{(}3.12\mathclose{)}$	$33.19\mathopen{(}2.44\mathclose{)}$
GS4CO	$59.66\mathopen{(}3.03\mathclose{)}$	$1.93\mathopen{(}1.43\mathclose{)}$	$112.26\mathopen{(}4.34\mathclose{)}$	$5.21\mathopen{(}1.70\mathclose{)}$	$146.25\mathopen{(}10.29\mathclose{)}$	$8.66\mathopen{(}2.03\mathclose{)}$	$273.15\mathopen{(}3.01\mathclose{)}$	$40.22\mathopen{(}2.36\mathclose{)}$
GNN	$59.41\mathopen{(}3.09\mathclose{)}$	$3.65\mathopen{(}1.99\mathclose{)}$	$92.33\mathopen{(}3.66\mathclose{)}$	$32.36\mathopen{(}3.24\mathclose{)}$	$51.74\mathopen{(}6.16\mathclose{)}$	$9.67\mathopen{(}2.27\mathclose{)}$	$217.83\mathopen{(}3.03\mathclose{)}$	$70.79\mathopen{(}2.64\mathclose{)}$

Table 1: The experimental results on standard benchmarks. Values are reported as geometric mean (geometric standard deviation) over 100 solving attempts per method. Bold font marks the best time among CPU-evaluated methods (our core focus), underline marks cases where the best CPU method additionally outperforms all GPU-evaluated methods. Nodes are reported for completeness but not the primary evaluation metric, and

\star

in the Nodes column marks cases that hit the 1000s time limit.

Method	BIP		OTS		NNV
	PDI	Gap	Nodes	Time	Nodes	Time
RPB	$81057.56\mathopen{(}1.24\mathclose{)}$	$93.47\mathopen{(}13.99\mathclose{)}$	$939.91\mathopen{(}9.01\mathclose{)}$	$320.62\mathopen{(}2.60\mathclose{)}$	$372.96\mathopen{(}31.85\mathclose{)}$	$22.96\mathopen{(}7.85\mathclose{)}$
Symb4CO	$89220.25\mathopen{(}1.07\mathclose{)}$	$132.48\mathopen{(}11.95\mathclose{)}$	$1474.2^{\star}\mathopen{(}3.17\mathclose{)}$	$544.89\mathopen{(}1.94\mathclose{)}$	$365.89\mathopen{(}60.40\mathclose{)}$	$25.43\mathopen{(}15.50\mathclose{)}$
GS4CO	$87270.12\mathopen{(}1.12\mathclose{)}$	$118.91\mathopen{(}12.09\mathclose{)}$	$2107.4^{\star}\mathopen{(}2.11\mathclose{)}$	$961.48\mathopen{(}1.16\mathclose{)}$	$502.99\mathopen{(}80.20\mathclose{)}$	$25.55\mathopen{(}18.31\mathclose{)}$
GNN	$87835.06\mathopen{(}1.08\mathclose{)}$	$88.39\mathopen{(}6.29\mathclose{)}$	$269.80^{\star}\mathopen{(}2.96\mathclose{)}$	$479.07\mathopen{(}2.42\mathclose{)}$	$254.01^{\star}\mathopen{(}18.54\mathclose{)}$	$58.55\mathopen{(}11.49\mathclose{)}$
LLM4Branch	$\textbf{\lx@text@underline{76010.83}}\mathopen{(}1.30\mathclose{)}$	$72.25\mathopen{(}14.12\mathclose{)}$	$4709.2^{\star}\mathopen{(}2.29\mathclose{)}$	$785.75\mathopen{(}1.51\mathclose{)}$	$362.27\mathopen{(}23.67\mathclose{)}$	$18.32\mathopen{(}4.49\mathclose{)}$

Table 2: Experimental results on real-world benchmarks. Similarly, values are reported as geometric mean (geometric standard deviation) over 100 solving attempts per method. Bold marks the best gap/PDI/time among CPU methods, underline indicates the best CPU method outperforms all GPU methods.

\star

indicates hitting the 1000s time limit.

Method	SC	CA	CFL	MIS
BiFE w/o $F_{LF}$	4.66	1.52	29.38	6.54
BiFE	4.58	1.51	28.29	6.26

Table 3: Times of rules designed by BiFE and BiFE w/o

F_{LF}

on the test instances of standard benchmarks.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Benchmarks	Parameters	Test	Transfer
Set Covering	Items Sets	500 1000	1000 1000
Combinatorial Auctions	Items Bids	100 500	200 1000
Maximum Independent Set	Nodes Affinity	500 4	1000 4
Capacitated Facility Location	Customers Facilities	100 100	200 100

Appendix

Table 4: Size of the test and transfer instances in standard benchmarks

Method	CA		SC		MIS		CFL
	Nodes	Time	Nodes	Time	Nodes	Time	Nodes	Time
BiFE	$70.50\mathord{\pm}3.11$	$1.51\mathord{\pm}1.41$	$109.17\mathord{\pm}4.10$	$4.58\mathord{\pm}1.67$	$81.75\mathord{\pm}7.75$	$6.26\mathord{\pm}1.62$	$266.52\mathord{\pm}2.99$	$28.29\mathord{\pm}2.22$
STRCMP	$8.88\mathord{\pm}3.77$	$2.69\mathord{\pm}1.52$	$23.06\mathord{\pm}8.46$	$7.20\mathord{\pm}1.73$	$25.93\mathord{\pm}9.76$	$4.81\mathord{\pm}2.03$	$70.86\mathord{\pm}5.77$	$32.61\mathord{\pm}2.03$

Appendix

Table 5: Comparison between BiFE and STRCMP on standard benchmarks.

Parameter	Value
Population size	8
Initial population size	16
Number of instances in $F_{HF}$	20
Random seed per $F_{HF}$ instance	0
Maximum sampled heuristics (LLM calls)	100
LLM output time limit (s)	60

Appendix

Table 6: Hyperparameter settings of the evolutionary algorithm.

Setting	Holm-adjusted $p$	BiFE win/tie/loss
CA Test	0.4128	12/0/8
SC Test	0.6146	15/0/5
MIS Test	0.9354	12/0/8
CFL Test	0.0018	18/0/2
CA Transfer	0.0499	17/0/3
SC Transfer	1.0000	10/0/10

Appendix

Table 7: Exact two-sided Wilcoxon signed-rank tests comparing instance-level solving time of BiFE and LLM4Branch. Each test uses 20 instance-level geometric means, obtained by aggregating five seeds per instance. Values are Holm-adjusted

p

-values across all eight comparisons; bold values are below 0.05.

Explore similar work

May 11, 2026cs.AI

LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs

Efficient branching policies are essential for accelerating Mixed Integer Linear Programming (MILP) solvers. Their design has long relied on hand-crafted heuristics, and now machine learning has emerged as a promising paradigm to automate this process. However, existing learning-based methods are often hindered by their dependence on expensive expert demonstrations and the gap between training objectives and the solver's end-to-end performance. In this work, we propose LLM4Branch, a novel framework that leverages Large Language Models (LLMs) to automate the discovery of efficient branching policies. Specifically, the discovered policy is an executable program with a program skeleton generated by the LLM and a parameter vector, which is optimized via a zeroth-order method over a few instances with their end-to-end performance feedback. Extensive experiments on standard MILP benchmarks demonstrate that LLM4Branch establishes a new state-of-the-art among CPU-based methods and achieves performance competitive with advanced GPU-based models. Codes are available at https://github.com/hzn18/LLM4Branch.

Zhinan Hou, Xingchen Li, Yankai Zhang +2

Department of Automation, BNRist, Tsinghua University, Beijing, China.

Mixed-Integer Programming Large Language Model Policy Optimization Openai

Ask PDF

May 28, 2026cs.CL

Compute Allocation in Evolutionary Search: From Depth-Breadth to Multi-Armed Bandits

LLM-guided evolutionary search (Evolve systems) has reached state-of-the-art results on mathematical and combinatorial tasks, yet most existing systems report only the best of many runs and leave the run-to-run distribution undocumented. We ask how a fixed budget of LLM calls should be allocated, and how reliably a single run reaches the reported numbers. Sweeping the depth-breadth grid over five models and three tasks, we identify two empirical regularities: a fitness-compute envelope along which capability ordering largely collapses on effective FLOPs, and a bilinear depth-breadth fit with task-specific interaction; both are gated by model-task capability. Motivated by these regularities, we propose BaSE (Bandit-based Self-Evolving), a multi-armed bandit that allocates LLM calls across parallel trajectories. Without changing the model, prompt, or evaluator, BaSE improves mean fitness by 12.3% over the strongest island-protocol baseline across 8 (model, task) cells, with the largest gains on high-variance settings: a reliability gain from allocation alone.

Sixue Xing, Haoyu He, Kerui Wu +4

University of Notre Dame · 2Northeastern University · University of Massachusetts Amherst +4

Evolutionary Search Bandits Large Language Model Tool Use Physical Activities

Ask PDF

Aug 6, 2026cs.AI

MicroEvo: Knowledge-Guided LLM Sampling for Efficient Microarchitecture Design Space Exploration

Microarchitecture design space exploration suffers from expansive search spaces and expensive PPA evaluation, leaving only a small simulation budget for design decision-making. Existing methods perform blind search without considering microarchitectural dependencies and fail to learn from the iterative search effectively, leading to wasted evaluations and weak Pareto convergence. In this paper, we propose MicroEvo, a knowledge-guided framework that couples off-the-shelf LLMs with Monte Carlo Tree Search (MCTS) for multi-objective microarchitecture optimization. MicroEvo combines LLM-driven evolutionary operators, a Pareto-aware tree policy that balances Pareto contribution and diversity, an active knowledge accumulation mechanism that extracts and reuses optimization insights, and state-aware directives that adapt the search behavior online. Experiments show that MicroEvo improves Pareto-front quality by up to 36.2% over NSGA-II and achieves 10.6x higher search efficiency, and also demonstrates strong scalability to a complex industrial-scale core. The code repository is available at: https://github.com/GEAR-SEU/MicroEvo-ICCAD-26.

Jia Xiong, Runkai Li, Chenxu Niu +11

Southeast University · National Center of Technology Innovation for EDA · NVIDIA Corporation +4

Evolutionary Search Neural Architecture Search Hardware Efficiency Alphaevolve Monte Carlo Tree Search Prompt Optimization+1

Ask PDF