Learning Early-to-Final Solution Consistency for MILP Acceleration

# Learning Early-to-Final Solution Consistency for MILP Acceleration
Source: [https://arxiv.org/html/2608.19953](https://arxiv.org/html/2608.19953)
Chengrui GaoChenguang WangHaopu ShangZherong ZhangKe XueJixiang LuWeiyong YangChao QianThanks:Corresponding author\. Email:qianc@lamda\.nju\.edu\.cn\.

###### Abstract

Mixed\-Integer Linear Programming \(MILP\) is a fundamental problem class in operations research and combinatorial optimization, with broad applications to industrial decision\-making\. Owing to their NP\-hardness, however, modern solvers may struggle to find high\-quality solutions for challenging MILP instances within practical time limits\. Recent learning\-based approaches seek to accelerate MILP solving by directly predicting high\-quality solutions from static instance\-level features, such as variable\-constraint bipartite graphs\. Yet accurate solution prediction from instance features alone is difficult, and these methods largely overlook the information revealed during the solver’s search process\. In this paper, we find that solutions produced at the early search stage of MILP solvers, which are computationally cheap to obtain, are often structurally close to the solutions found after full\-budget search\. Motivated by this observation, we propose a new solver\-informed paradigm that shifts the learning target from variable assignment toearly\-to\-final consistency: for each variable, we predict whether its early\-stage assignment should persist in full\-budget solutions\. The predicted consistency naturally guides downstream search, for instance by fixing the assignments deemed consistent\. At inference time, we further ensemble consistency predictions across multiple early\-stage solutions to improve robustness\. Experiments across four MILP benchmarks show our method improves prediction\-guided search across diverse downstream pipelines\. With Gurobi, our proposed method reduces the primal gap by 56\.9% on average and closes it completely on combinatorial auction instances\. Besides, we transferred the Gurobi\-trained model zero\-shot to SCIP without adaptation, achieving a 36\.4% average gap reduction across benchmarks\. Code is available at:https://github\.com/lamda\-bbo/EnCore\.

## 1Introduction

Mixed\-Integer Linear Programming \(MILP\) is a fundamental modeling language for combinatorial optimization and decision making, with broad applications in scheduling\([8](https://arxiv.org/html/2608.19953#bib.bib22)\), routing\([20](https://arxiv.org/html/2608.19953#bib.bib23)\), network design\([5](https://arxiv.org/html/2608.19953#bib.bib25)\)and production planning\([27](https://arxiv.org/html/2608.19953#bib.bib24)\)\. Prevailing MILP solvers employ branch\-and\-bound\([19](https://arxiv.org/html/2608.19953#bib.bib26)\)frameworks to systematically explore the combinatorial search space while guaranteeing optimality\. Built upon this, the MILP community has developed a variety of sophisticated techniques\([28](https://arxiv.org/html/2608.19953#bib.bib27);[1](https://arxiv.org/html/2608.19953#bib.bib1)\)over the past decades, including presolve, cutting planes, primal heuristics, and branching strategies, which further reduce the search space and accelerate the solving process\. However, solving MILP remains computationally expensive for modern solvers due to their inherent NP\-hardness\([17](https://arxiv.org/html/2608.19953#bib.bib28)\)\.

In real\-world applications, most MILP instances are derived from similar problem classes with varying parameters, exhibiting shared structural patterns that can be naturally exploited by machine learning methods\. As investigated by[3](https://arxiv.org/html/2608.19953#bib.bib2), learning models can capture these patterns from instance characteristics and historical solving experiences, and infer effective optimization strategies\. Such learned knowledge can be integrated into MILP solvers to accelerate the optimization process\([10](https://arxiv.org/html/2608.19953#bib.bib4);[23](https://arxiv.org/html/2608.19953#bib.bib10);[26](https://arxiv.org/html/2608.19953#bib.bib8)\)\. Existing learning\-based methods for MILP can be broadly classified into three types: \(1\)learning solver decisions, where machine learning models are employed to guide individual solver component, such as branching, node selection, and cutting plane selection\([18](https://arxiv.org/html/2608.19953#bib.bib3);[10](https://arxiv.org/html/2608.19953#bib.bib4);[12](https://arxiv.org/html/2608.19953#bib.bib5);[7](https://arxiv.org/html/2608.19953#bib.bib11);[32](https://arxiv.org/html/2608.19953#bib.bib6);[24](https://arxiv.org/html/2608.19953#bib.bib7);[31](https://arxiv.org/html/2608.19953#bib.bib30)\); \(2\)learning solver configurations, where models automatically tune algorithmic parameters or select suitable configurations for different instances\([15](https://arxiv.org/html/2608.19953#bib.bib9);[23](https://arxiv.org/html/2608.19953#bib.bib10)\); and \(3\)learning solution predictions, where models directly predict complete or partial solutions to provide high\-quality initial solutions or reduce the search space\([26](https://arxiv.org/html/2608.19953#bib.bib8)\)\.

Among the solution prediction methods, recent advances have focused on two directions: improving learning\-guided search mechanisms and enhancing prediction capacity\. On the search side, early studies such as neural diving\([26](https://arxiv.org/html/2608.19953#bib.bib8)\)fixed high\-confidence variable assignments predicted by neural models, producing reduced MILP instances for efficient downstream optimization\. Building upon this idea,[14](https://arxiv.org/html/2608.19953#bib.bib12)replaced hard variable fixing with a trust\-region search strategy, reducing the risk of being trapped by inaccurate assignment\. More recently,[25](https://arxiv.org/html/2608.19953#bib.bib13)proposed to alternate prediction with trust\-region correction, further improving robustness against prediction errors\. On the prediction side,[34](https://arxiv.org/html/2608.19953#bib.bib29)represented MILPs as geometric feature sequences and used multi\-scale attention to overcome expressiveness limitations of graph\-based models\. Meanwhile,[22](https://arxiv.org/html/2608.19953#bib.bib16)introduced a flow\-matching generator that jointly models integer and continuous variables to enhance solution generation quality, while[29](https://arxiv.org/html/2608.19953#bib.bib17)exploited variable interactions through inter\-variable contrastive learning and an intra\-constraint competitive graph network\. However, these methods still follow the conventional paradigm of predicting a complete solution directly from the MILP formulation\. Under this paradigm, the model is required to determine all variable assignments, leading to a prediction task that approaches the complexity of solving the original MILP\.

In this paper, we begin by analyzing how primal solutions evolve during the search of modern MILP solvers\. Across all evaluated benchmarks, we observe that the solution quality improves rapidly in the early stage of the search and then progresses much more slowly with only local corrections, indicating that early incumbents are highly informative about the final, full\-budget assignments\. On workload apportionment, for instance, an early incumbent already agrees with the final solution on95\.63%95\.63\\%of the binary variables \(as shown in Figure[2](https://arxiv.org/html/2608.19953#S3.F2)\)\. Given such an informative starting point, the optimal solution need not be reconstructed from scratch\. Conditioned on what the solver has already produced, the learning task reduces to deciding which of its assignments to trust\.

Based on this insight, we propose a new*solver\-informed*paradigm that reformulates solution prediction as an*early\-to\-final consistency estimation*problem\. Given an MILP graphGG, an early solutionXE​SX^\{ES\}, and a reference solutionX∗X^\{\*\}obtained from a full\-budget run, conventional solution prediction learnsP⁡\(X∗∣G\)P\(X^\{\*\}\\mid G\)and thus requires the model to infer all variable assignments from static instance features alone\. In contrast, we estimateP⁡\(xi∗=xiE​S∣G,XE​S\),P\(x\_\{i\}^\{\*\}=x\_\{i\}^\{ES\}\\mid G,X^\{ES\}\),namely the probability that each early assignment persists in the final solution\. This target can substantially ease the learning task\. Conditioned on the rich anchorXE​SX^\{ES\}, the model only needs to identify a relatively small fraction of assignments that have yet to stabilize\. Theoretically, we prove that conditioning on the early solution can strictly increases the best achievable accuracy of predicting the full\-budget solution, under a mild posterior\-crossing condition, and that this information gain provably persists under finite\-sample model selection\. Moreover, since the predicted consistent assignments are drawn from a feasible early solution, fixing them preserves feasibility and concentrates the subsequent search on assignments that the solver has left unresolved\.

We evaluate our method on multiple MILP benchmarks with Gurobi\([13](https://arxiv.org/html/2608.19953#bib.bib21)\)as the target solver and integrate it into existing prediction\-based search frameworks\. Experimental results show that our proposed refiner consistently reduces the primal gap in most evaluated settings\. Specifically, it reduces the primal gap of Predict\-and\-Search\([14](https://arxiv.org/html/2608.19953#bib.bib12)\)by 56\.9% on average and closes the gap on combinatorial auction instances\. Furthermore, without retraining, the model trained with Gurobi\-generated data can be directly transferred to SCIP\([1](https://arxiv.org/html/2608.19953#bib.bib1)\)\. These results demonstrate that the proposed early\-to\-final consistency prediction paradigm is clearly effective and showcases transferability across different solvers\.

## 2Preliminaries

### Mixed Integer Linear Programming

A mixed\-integer linear program \(MILP\) is an optimization problem with a linear objective and linear constraints, where a subset of decision variables is restricted to integer values\. We formulate a MILP instance as

minx∈𝐑n\\displaystyle\\min\_\{x\\in\\mathbf\{R\}^\{n\}\}𝒄⊤​𝒙\\displaystyle\\bm\{c\}^\{\\top\}\\bm\{x\}\(1\)s\.t\.\\displaystyle\\text\{s\.t\.\}𝐀​𝒙≤𝒃,\\displaystyle\\mathbf\{A\}\\bm\{x\}\\leq\\bm\{b\},𝒍≤𝒙≤𝒖,\\displaystyle\\bm\{l\}\\leq\\bm\{x\}\\leq\\bm\{u\},xi∈𝐙​∀i∈ℐ,\\displaystyle x\_\{i\}\\in\\mathbf\{Z\}\\;\\forall i\\in\\mathcal\{I\},where𝒙=\(x1,…,xn\)\\bm\{x\}=\(x\_\{1\},\\ldots,x\_\{n\}\)is the vector of decision variables,𝒄∈𝐑n\\bm\{c\}\\in\\mathbf\{R\}^\{n\}is the objective coefficient vector,𝐀∈𝐑m×n\\mathbf\{A\}\\in\\mathbf\{R\}^\{m\\times n\}is the constraint matrix, and𝒃∈𝐑m\\bm\{b\}\\in\\mathbf\{R\}^\{m\}is the right\-hand\-side vector\. The bounds𝒍,𝒖∈\(𝐑∪\{±∞\}\)n\\bm\{l\},\\bm\{u\}\\in\(\\mathbf\{R\}\\cup\\\{\\pm\\infty\\\}\)^\{n\}defines the variable domains, andℐ⊆\{1,…,n\}\\mathcal\{I\}\\subseteq\\\{1,\\ldots,n\\\}is the index set of variables required to take integer values\. An important special case is that of binary variables, for whichxi∈\{0,1\}x\_\{i\}\\in\\\{0,1\\\}\. General integer variables can be transformed into binary variables using standard preprocessing techniques\.

### Graph Representations for MILP

Learning\-based MILP methods commonly encode an instance as a bipartite graph\([30](https://arxiv.org/html/2608.19953#bib.bib31);[10](https://arxiv.org/html/2608.19953#bib.bib4)\)\. For the MILP formulated in Eq\. \([1](https://arxiv.org/html/2608.19953#S2.E1)\), the associated graph is defined asG=\(𝒱,𝒞,ℰ\)G=\(\\mathcal\{V\},\\mathcal\{C\},\\mathcal\{E\}\), where𝒱=\{v1,…,vn\}\\mathcal\{V\}=\\\{v\_\{1\},\\ldots,v\_\{n\}\\\}and𝒞=\{q1,…,qm\}\\mathcal\{C\}=\\\{q\_\{1\},\\ldots,q\_\{m\}\\\}denote the sets of variable nodes and constraint nodes, corresponding to decision variables and constraints, respectively\. An edge\(vi,qj\)∈ℰ\(v\_\{i\},q\_\{j\}\)\\in\\mathcal\{E\}is introduced when the coefficient𝐀j​i\\mathbf\{A\}\_\{ji\}is non\-zero\.

Each node is initialized with features describing its role in the MILP\([14](https://arxiv.org/html/2608.19953#bib.bib12)\)\. A variable nodeviv\_\{i\}contains the objective coefficientcic\_\{i\}, the lower and upper boundslil\_\{i\}anduiu\_\{i\}, and an indicator of whetherxix\_\{i\}is continuous or integer\. A constraint nodeqjq\_\{j\}contains the right\-hand\-side valuebjb\_\{j\}and an encoding of its constraint sense, such as≤\\leq,==, or≥\\geq\. In addition, each edge carries the matrix coefficientAj​iA\_\{ji\}as its edge feature\. Collectively, these node and edge attributes provide a description of the local algebraic structure of the MILP instance, which serves as the input representation for graph neural networks \(GNN\)\.

### Solution Predictions for MILP

Solution prediction methods learn a mapping from an MILP instance to variable assignments, which can be exploited to reduce the search space for acceleration\. Most existing predictors take the static bipartite graphGGas input and employ a graph convolutional network \(GCN\) or a related message\-passing GNN to compute variable embeddings, from which the final predictions are decoded\.

Lethi\(ℓ\)h\_\{i\}^\{\(\\ell\)\}be the embedding of variable nodeviv\_\{i\}at layerℓ\\ell, and letgj\(ℓ\)g\_\{j\}^\{\(\\ell\)\}be the embedding of constraint nodeqjq\_\{j\}\. A common bipartite message\-passing layer first aggregates messages from variables to constraints and then sends messages back to variables:

gj\(ℓ\+1\)=ϕC\(ℓ\)\(gj\(ℓ\),∑i:\(vi,qj\)∈ℰψC\(ℓ\)\(hi\(ℓ\),Aj​i\)\),hi\(ℓ\+1\)=ϕV\(ℓ\)\(hi\(ℓ\),∑j:\(vi,qj\)∈ℰψV\(ℓ\)\(gj\(ℓ\+1\),Aj​i\)\),\\begin\{array\}\[\]\{rcl\}g\_\{j\}^\{\(\\ell\+1\)\}&=&\\phi\_\{C\}^\{\(\\ell\)\}\\left\(g\_\{j\}^\{\(\\ell\)\},\\sum\_\{i:\(v\_\{i\},q\_\{j\}\)\\in\\mathcal\{E\}\}\\psi\_\{C\}^\{\(\\ell\)\}\(h\_\{i\}^\{\(\\ell\)\},A\_\{ji\}\)\\right\),\\\\\[5\.69054pt\] h\_\{i\}^\{\(\\ell\+1\)\}&=&\\phi\_\{V\}^\{\(\\ell\)\}\\left\(h\_\{i\}^\{\(\\ell\)\},\\sum\_\{j:\(v\_\{i\},q\_\{j\}\)\\in\\mathcal\{E\}\}\\psi\_\{V\}^\{\(\\ell\)\}\(g\_\{j\}^\{\(\\ell\+1\)\},A\_\{ji\}\)\\right\),\\end\{array\}whereψC\(ℓ\)\\psi\_\{C\}^\{\(\\ell\)\}andψV\(ℓ\)\\psi\_\{V\}^\{\(\\ell\)\}are message functions, andϕC\(ℓ\)\\phi\_\{C\}^\{\(\\ell\)\}andϕV\(ℓ\)\\phi\_\{V\}^\{\(\\ell\)\}are node\-update functions\. These functions are usually implemented as multilayer perceptrons with nonlinear activations\. Each update depends on both neighboring node embeddings and the corresponding edge weightAj​iA\_\{ji\}\.

AfterLLmessage\-passing layers, the predictor applies a variable\-level readout to each final variable embedding\. For binary integer variables, a common formulation trains a predictorfθf\_\{\\theta\}on the graphGGto estimate a target solutionX∗X^\{\*\}:

p^i=σ⁡\(rθ​\(hi\(L\)\)\)=fθ​\(G\)i≈P⁡\(xi∗=1∣G\),\\hat\{p\}\_\{i\}=\\sigma\\\!\\left\(r\_\{\\theta\}\(h\_\{i\}^\{\(L\)\}\)\\right\)=f\_\{\\theta\}\(G\)\_\{i\}\\approx P\(x\_\{i\}^\{\*\}=1\\mid G\),whererθr\_\{\\theta\}is a learnable readout function andσ\\sigmais the sigmoid function\. The outputp^i\\hat\{p\}\_\{i\}is the predicted probability that variableiitakes value one in the reference solution\. The predictions can then be used to construct a partial assignment, define a neighborhood around a candidate solution, or fix variables before invoking the solver on a reduced MILP\.

## 3Method

### Motivation

We begin with an observation about the dynamics of modern MILP solvers: the primal and dual gaps typically decrease sharply at the beginning of the solve, after which progress becomes much slower and is spread over a long period of search\. Figure[1](https://arxiv.org/html/2608.19953#S3.F1)illustrates this behavior with the evolution of the primal gap on example instances; the same qualitative pattern holds across solvers and problem classes \(App\.[A](https://arxiv.org/html/2608.19953#A1)\)\. This behavior suggests a two\-stage view of MILP solving\. In the*fast descent stage*, the solver rapidly discovers useful early solutions and tightens bounds through presolve, heuristics, cutting planes, and early branch\-and\-bound decisions\. In the*long exploration stage*, the solver spends most of its time searching for further improvements, proving bounds, and resolving difficult variables\.

This two\-stage view motivates a new prediction target for learning\-based MILP solving\. In contrast to the prevailing paradigm, which constructs a full solution directly from the static MILP graph, we propose anEarly\-to\-final solutionConsistency prediction paradigm, termedEnCore\. Specifically, given an early solutionXE​SX^\{ES\}collected after the fast\-descent stage, we estimate the probability that the early assignment of each variable persists in the full\-budget solutionX∗X^\{\*\}\. This target distinguishes assignments that have likely stabilized from those that merit further exploration, thereby directing both learning and search effort toward the decisions that remain open after the fast descent\.

The proposed paradigm rests on the premise that the early solution is informative of the final one\. We now examine this premise empirically\. Figure[2](https://arxiv.org/html/2608.19953#S3.F2)compares each early solutionXE​SX^\{ES\}with the full\-budget solutionX∗X^\{\*\}by counting the flipped integer variables\. Across benchmark classes, the early solutions exhibit agreement with the final ones, and the discrepancies tend to concentrate on a limited subset of variables rather than spreading arbitrarily across the instance\. These observations indicate that the early solution carries rich information about the final solution, making it a valuable reference worth exploiting\.

\(a\)Gurobi Results\(b\)SCIP Results
Figure 1:Evolution of the primal gap over the solving process with Gurobi \(left\) and SCIP \(right\) on set covering instances\. The time axis is scaled to highlight the early phase−200​s0\\\!\-\\\!200\\,\\mathrm\{s\}\. Results on other problem classes are provided in App\.[A](https://arxiv.org/html/2608.19953#A1)\.\(a\)Gurobi on CA\(b\)Gurobi on WA\(c\)SCIP on CA\(d\)SCIP on WA
Figure 2:Distributions of flipped integer variables between early and full\-budget solutions\. ‘CA’ and ‘WA’ stand for combinatorial auction and workload apportionment, respectively\.
### Consistency Prediction

Given the MILP graphGGand the collected early solutionXE​SX^\{ES\}, we design a consistency predictor that estimates, for each integer variable, the probability that its early assignment agrees with the full\-budget solutionX∗X^\{\*\}\. The predictor must fuse two heterogeneous sources of information: the structural description of the instance, encoded in the bipartite variable–constraint graph, and the variable assignments in the early solution\. We achieve this fusion at the input level, where each integer\-variable node is augmented with its early assignmentxiE​Sx\_\{i\}^\{ES\}as an additional feature\. Through rounds of variable\-to\-constraint and constraint\-to\-variable message passing, the network can thus assess each assignment jointly with the constraints it appears in and the assignments of neighboring variables, which provides the evidence needed to judge whether the assignment will persist\. The backbone is a bipartite graph neural network with half\-convolutions, a standard architecture for MILP representation learning\([14](https://arxiv.org/html/2608.19953#bib.bib12);[25](https://arxiv.org/html/2608.19953#bib.bib13)\)\. A variable\-level readout then produces the consistency probabilityp^i\\hat\{p\}\_\{i\}for each integer variable\. Architectural details are provided in Appendix[B](https://arxiv.org/html/2608.19953#A2)\.

To train the predictor, we fundamentally reshape the learning target, rather than imitating the complete solutionsX∗X^\{\*\}\. Since the early solution already encodes substantial information about the final one, the remaining task is not to predict every variable value from scratch, but to assess which early assignments are likely to persist in the final solution\. We therefore define the binary consistency labelyi=𝟏\[xi∗=xiE​S\]y\_\{i\}=\\mathbf\{1\}\[x\_\{i\}^\{\*\}=x\_\{i\}^\{ES\}\]for each integer variableii, and train the predictorfθf\_\{\\theta\}so that

p^i=fθ​\(G,XE​S\)i≈P⁡\(xi∗=xiE​S∣G,XE​S\)\.\\hat\{p\}\_\{i\}=f\_\{\\theta\}\(G,X^\{ES\}\)\_\{i\}\\approx P\(x\_\{i\}^\{\*\}=x\_\{i\}^\{ES\}\\mid G,X^\{ES\}\)\.
For each training instanceGG, we collect an early solutionXE​SX^\{ES\}and pair it with the full\-budget solutionX∗X^\{\*\}\. The collection procedure is described later in this section\. The predictor is then trained on the early\-to\-final consistency labels with the binary cross\-entropy loss,

ℒ\(θ\)=−∑i∈ℐ\[yilogp^i\+\(1−yi\)log\(1−p^i\)\]\.\\mathcal\{L\}\(\\theta\)=\-\\sum\_\{i\\in\\mathcal\{I\}\}\\left\[y\_\{i\}\\log\\hat\{p\}\_\{i\}\+\(1\-y\_\{i\}\)\\log\(1\-\\hat\{p\}\_\{i\}\)\\right\]\.This consistency target reshapes the learning task: rather than constructing the full solution from the static graph alone, the model refines an informative reference solution by assessing the stability of each assignment, which is a more focused and better\-conditioned problem\. Moreover, the conditioning solutionXE​SX^\{ES\}provides a rich source of instance\-specific information that purely graph\-based predictors cannot access\.

#### Early Solution Collection\.

We collect early solutions at the transition fromfast descenttolong exploration\. During the solving process, we monitor feasible\-solution improvement events and estimate the local dual\-gap decay rate over a sliding window, i\.e\., the gap reduction within the window divided by the elapsed time\. The run is terminated once this rate first falls below a threshold, indicating that rapid bound improvement has mostly ended, and the last explored solution is taken as the early solutionXE​SX^\{ES\}\. In practice, we additionally impose a minimum probing time to avoid stopping before a meaningful dual bound, and a maximum time to restrict the runtime cost\. Details are included in App\.[C](https://arxiv.org/html/2608.19953#A3)\.

#### Inference\-Time Augmentation\.

The early solution available for conditioning is not unique\. Depending on when the collection run terminates, the solver may return slightly different solutions, and a variable predicted stable under one of them may still be predicted fluctuating under another\. To mitigate this sensitivity, we employ the last few improving solutions for inference\-time augmentation\. Let\{X1,…,XK\}\\\{X\_\{1\},\\ldots,X\_\{K\}\\\}denote the lastKKimproving solutions found during the collection run, withXK=XE​SX\_\{K\}=X^\{ES\}\. The trained predictor processes eachXkX\_\{k\}as the conditioning solution\. Since a consistency score is always expressed relative to the value taken in its own conditioning solution, the resulting predictions must be aligned to the common referenceXE​SX^\{ES\}\. To this end, we flip the sign of each logit whose corresponding variable takes a different value inXkX\_\{k\}than inXE​SX^\{ES\}, as a high consistency score for such a variable argues against the reference value\. The aligned logits are then averaged,

p¯i=σ⁡\(1K​∑k=1Kτk,i​p^k,i\),\\bar\{p\}\_\{i\}=\\sigma\\\!\\left\(\\frac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}\\tau\_\{k,i\}\\hat\{p\}\_\{k,i\}\\right\),whereτk,i=\+1\\tau\_\{k,i\}=\+1ifxk,i=xiE​Sx\_\{k,i\}=x^\{ES\}\_\{i\}and−1\-1otherwise\. The ensembled probabilityp¯i\\bar\{p\}\_\{i\}replacesp^i\\hat\{p\}\_\{i\}as the consistency score ofxiE​Sx^\{ES\}\_\{i\}used by the downstream search methods\.

### Combine EnCore with Search Methods

Our consistency predictor is independent of the downstream search strategy\. In most learning\-based MILP accelerators, the method must select a subset of variables whose predicted values are trusted, and the search space is then reduced accordingly\. The central question is therefore which assignments can be trusted\. Existing methods trust an assignment when the model is confident in its own prediction, so both the value and its evidence come from the model alone\. In contrast, ourearly\-to\-final consistencydesign trusts values that the solver has already realized in a feasible early solution, and scores them by predicting whether they persist after the full solving process\. Specifically, we rank variables by their consistency scorep¯i\\bar\{p\}\_\{i\}and select the top\-ranked ones\. Each selected variableiiis constrained to its early valuexiE​Sx\_\{i\}^\{ES\}, while the remaining variables are left to the downstream search mechanism\. This consistency\-based design offers two main advantages: \(1\)Feasibility\. The fixed values are drawn from a feasible solution, so fixing them never destroys feasibility, which model\-generated assignments cannot guarantee\. \(2\)Alignment with the search process\. The consistency signals originate from the solver’s own search trajectory, and thus naturally guide the model toward the variables that the solver has yet to resolve\.

## 4Theoretical Analysis

Our method depends on the premise that conditioning on the early solutionXE​SX^\{ES\}makes predicting the full\-budget solutionX∗X^\{\*\}fundamentally easier than predicting from the instance graph alone\. In this section, we formalize it by answering two questions: \(1\) Can the early solution improve the best achievable prediction accuracy, and under what condition is the gain strict \(Theorem[1](https://arxiv.org/html/2608.19953#Thmtheorem1)\)? \(2\) Does this gain survive when the predictor must be selected from finite training instances \(Theorem[2](https://arxiv.org/html/2608.19953#Thmtheorem2)\)? Complete proofs are in Appendix[F](https://arxiv.org/html/2608.19953#A6)\.

Let𝒟\\mathcal\{D\}be the distribution over triples\(G,XE​S,X∗\)\(G,X^\{ES\},X^\{\*\}\), and letJJbe a uniformly weighted variable index within an instance, so thatPr⁡\(x^J=xJ∗\)\\Pr\(\\widehat\{x\}\_\{J\}=x^\{\*\}\_\{J\}\)is the expected per\-instance variable accuracy, i\.e\., the population variable\-level evaluation criterion used in our analysis\. A message\-passing predictor at variableJJconsiders only the instance features in its receptive MILP graphℛJ\\mathcal\{R\}\_\{J\}, while EnCore additionally attaches early assignmentsXℛJE​SX^\{ES\}\_\{\\mathcal\{R\}\_\{J\}\}to construct the augmented input𝒰J=\(ℛJ,XℛJE​S\)\\mathcal\{U\}\_\{J\}=\(\\mathcal\{R\}\_\{J\},X^\{ES\}\_\{\\mathcal\{R\}\_\{J\}\}\)\.

A solution predictorhhmapsℛJ\\mathcal\{R\}\_\{J\}to a prediction ofxJ∗x^\{\*\}\_\{J\}, matching the conventional paradigm\. A consistency predictoraaobserves𝒰J\\mathcal\{U\}\_\{J\}and decides whether to retain the early value, inducing

ha​\(𝒰J\)=\{xJE​S,a⁡\(𝒰J\)=1,1−xJE​S,a⁡\(𝒰J\)=0\.h\_\{a\}\(\\mathcal\{U\}\_\{J\}\)=\\begin\{cases\}x^\{ES\}\_\{J\},&a\(\\mathcal\{U\}\_\{J\}\)=1,\\\\ 1\-x^\{ES\}\_\{J\},&a\(\\mathcal\{U\}\_\{J\}\)=0\.\\end\{cases\}GivenxJE​Sx^\{ES\}\_\{J\}, consistency decisions and final assignments determine each other \(see Appendix[F](https://arxiv.org/html/2608.19953#A6)\), so the two paradigms can be compared as predictors ofxJ∗x^\{\*\}\_\{J\}\.

#### Information gain of the early solution\.

Define the best population accuracies attainable from each input,

Asol∗\\displaystyle A^\{\*\}\_\{\\mathrm\{sol\}\}:=suphPr⁡\(h⁡\(ℛJ\)=xJ∗\),\\displaystyle:=\\sup\_\{h\}\\Pr\\bigl\(h\(\\mathcal\{R\}\_\{J\}\)=x^\{\*\}\_\{J\}\\bigr\),Acon∗\\displaystyle A^\{\*\}\_\{\\mathrm\{con\}\}:=supaPr⁡\(ha​\(𝒰J\)=xJ∗\)\.\\displaystyle:=\\sup\_\{a\}\\Pr\\bigl\(h\_\{a\}\(\\mathcal\{U\}\_\{J\}\)=x^\{\*\}\_\{J\}\\bigr\)\.If𝒟\\mathcal\{D\}were known, these would be achieved by the Bayes\-optimal rules on each input\([6](https://arxiv.org/html/2608.19953#bib.bib32)\)\. Their comparison isolates the informational value of the early solution from any modeling concern\.

###### Theorem 1\.

For any fixed early\-solution collection procedure,Acon∗≥Asol∗A^\{\*\}\_\{\\mathrm\{con\}\}\\geq A^\{\*\}\_\{\\mathrm\{sol\}\}\. LetηJ:=Pr⁡\(xJ∗=1∣𝒰J\)\\eta\_\{J\}:=\\Pr\(x^\{\*\}\_\{J\}=1\\mid\\mathcal\{U\}\_\{J\}\)\. The inequality is strict if

Pr⁡\(Pr⁡\(ηJ<12∣ℛJ\)\>0and​Pr⁡\(ηJ\>12∣ℛJ\)\>0\)\>0\.\\Pr\\\!\\left\(\\begin\{aligned\} &\\Pr\(\\eta\_\{J\}<\\tfrac\{1\}\{2\}\\mid\\mathcal\{R\}\_\{J\}\)\>0\\\\ &\\text\{and \}\\Pr\(\\eta\_\{J\}\>\\tfrac\{1\}\{2\}\\mid\\mathcal\{R\}\_\{J\}\)\>0\\end\{aligned\}\\right\)\>0\.

###### Proof sketch\.

Every solution predictorhhdefinesah\(𝒰J\)=𝟏\{h\(ℛJ\)=xJE​S\}a\_\{h\}\(\\mathcal\{U\}\_\{J\}\)=\\mathbf\{1\}\\\{h\(\\mathcal\{R\}\_\{J\}\)=x^\{ES\}\_\{J\}\\\}, for whichhah​\(𝒰J\)=h⁡\(ℛJ\)h\_\{a\_\{h\}\}\(\\mathcal\{U\}\_\{J\}\)=h\(\\mathcal\{R\}\_\{J\}\)\. Hence the augmented input can reproduce every solution predictor\. For strictness, conditional Jensen’s inequality\([16](https://arxiv.org/html/2608.19953#bib.bib33)\)shows that refining the input strictly increases Bayes accuracy under the stated condition\. ∎

The inequality itself is unsurprising since additional input can never hurt a Bayes\-optimal predictor\. The substantive content is about the strictness condition, which we call*posterior crossing*: for a non\-negligible set of instance inputs, different early assignments compatible with the same instance structure favor different final values\. In this regime, no predictor on instance features alone, however expressive, can resolve the ambiguity, while the early solution can\. Figure[2](https://arxiv.org/html/2608.19953#S3.F2)provides complementary empirical motivation by showing that early\-to\-final discrepancies are often concentrated on a small fraction of variables\.

#### A sparse\-correction reading of the gain\.

Leta∗a^\{\*\}be the Bayes rule on the augmented input,p=Pr⁡\(xJE​S≠xJ∗\)p=\\Pr\(x^\{ES\}\_\{J\}\\neq x^\{\*\}\_\{J\}\)represents the early\-solution error rate,ρ=Pr⁡\(a∗​\(𝒰J\)=0\)\\rho=\\Pr\(a^\{\*\}\(\\mathcal\{U\}\_\{J\}\)=0\)denotes its flipping rate, andqqis the precision on flipped variables, whereq\>1/2q\>1/2due to the Bayes optimality\. Then we have

1−Acon∗\\displaystyle 1\-A^\{\*\}\_\{\\mathrm\{con\}\}=p−ρ⁡\(2​q−1\),\\displaystyle=p\-\\rho\(2q\-1\),Acon∗−Asol∗\\displaystyle A^\{\*\}\_\{\\mathrm\{con\}\}\-A^\{\*\}\_\{\\mathrm\{sol\}\}=1−Asol∗−p\+ρ⁡\(2​q−1\)\.\\displaystyle=1\-A^\{\*\}\_\{\\mathrm\{sol\}\}\-p\+\\rho\(2q\-1\)\.The gain is positive exactly whenp<1−Asol∗\+ρ⁡\(2​q−1\)p<1\-A^\{\*\}\_\{\\mathrm\{sol\}\}\+\\rho\(2q\-1\)\. This identity captures the residual nature of EnCore: corrections withq\>1/2q\>1/2remove more errors than they introduce, and when early\-to\-final discrepancies are sparse, learning can focus on a targeted subset of unstable assignments\. The condition can also hold when1−p<Asol∗1\-p<A^\{\*\}\_\{\\mathrm\{sol\}\}\(see Appendix[F](https://arxiv.org/html/2608.19953#A6)\), showing that the early solution is valuable not only as a feasible candidate but also as an informative conditioning signal\.

#### Finite\-sample guarantee\.

Theorem[1](https://arxiv.org/html/2608.19953#Thmtheorem1)optimizes over all rules and thus characterizes only the information available in principle\. However, the predictor is selected from finite data in practice, and one may worry whether the population gain can survive estimation errors\. Following the standard finite\-class empirical\-risk\-minimization analysis based on Bernstein’s inequality and a union bound\([4](https://arxiv.org/html/2608.19953#bib.bib34)\), we fix a finite class𝒜=\{a1,…,aN\}\\mathcal\{A\}=\\\{a\_\{1\},\\dots,a\_\{N\}\\\}of consistency rules before observingmmindependent training instances, and leta^\\widehat\{a\}minimize the average proportion of variable errors; only instances need be independent, matching how MILP training data are collected\. The class advantage decomposes asΔ𝒜=ΔB−α𝒜\\Delta\_\{\\mathcal\{A\}\}=\\Delta\_\{\\mathrm\{B\}\}\-\\alpha\_\{\\mathcal\{A\}\}, whereΔB:=Acon∗−Asol∗\\Delta\_\{\\mathrm\{B\}\}:=A^\{\*\}\_\{\\mathrm\{con\}\}\-A^\{\*\}\_\{\\mathrm\{sol\}\}is the gain from Theorem[1](https://arxiv.org/html/2608.19953#Thmtheorem1)andα𝒜:=Acon∗−maxa∈𝒜⁡Acc⁡\(ha\)\\alpha\_\{\\mathcal\{A\}\}:=A^\{\*\}\_\{\\mathrm\{con\}\}\-\\max\_\{a\\in\\mathcal\{A\}\}\\mathrm\{Acc\}\(h\_\{a\}\)is the approximation gap, withAcc⁡\(h\)=Pr⁡\(hJ=xJ∗\)\\mathrm\{Acc\}\(h\)=\\Pr\(h\_\{J\}=x^\{\*\}\_\{J\}\)\. Motivated by the sparse discrepancies in Figure[2](https://arxiv.org/html/2608.19953#S3.F2), we assume the expected per\-instance flip rate satisfiesmaxa∈𝒜⁡𝔼⁡\[sa\]≤s¯\\max\_\{a\\in\\mathcal\{A\}\}\\mathbb\{E\}\[s\_\{a\}\]\\leq\\bar\{s\}\.

###### Theorem 2\.

Leth^E​S=ha^\\widehat\{h\}\_\{ES\}=h\_\{\\widehat\{a\}\}, and leth^sol\\widehat\{h\}\_\{\\mathrm\{sol\}\}be any possibly data\-dependent solution predictor\. For everyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta,

Acc⁡\(h^E​S\)−Acc⁡\(h^sol\)≥ΔB−α𝒜−εm​\(δ\)\\displaystyle\\mathrm\{Acc\}\(\\widehat\{h\}\_\{ES\}\)\-\\mathrm\{Acc\}\(\\widehat\{h\}\_\{\\mathrm\{sol\}\}\)\\geq\\Delta\_\{\\mathrm\{B\}\}\-\\alpha\_\{\\mathcal\{A\}\}\-\\varepsilon\_\{m\}\(\\delta\)\\displaystyle,εm​\(δ\)=2​2​s¯m​ln⁡2​Nδ\+83​m​ln⁡2​Nδ\\displaystyle\\varepsilon\_\{m\}\(\\delta\)=2\\sqrt\{\\frac\{2\\bar\{s\}\}\{m\}\\ln\\frac\{2N\}\{\\delta\}\}\+\\frac\{8\}\{3m\}\\ln\\frac\{2N\}\{\\delta\}\\displaystyle\.

###### Proof sketch\.

Use the rule that always keeps the early solution as a common reference\. A candidate differs from it only on variables it flips, so its instance\-level loss difference has variance at mosts¯\\bar\{s\}\. Bernstein’s inequality with a union bound over theNNrules\([4](https://arxiv.org/html/2608.19953#bib.bib34)\)then controls all empirical loss differences simultaneously\. Empirical risk minimization converts this into the penaltyεm​\(δ\)\\varepsilon\_\{m\}\(\\delta\), while Bayes optimality lower\-bounds the risk of every instance\-input solution predictor\. ∎

Thus the learned consistency predictor provably outperforms*any*solution predictor, even one trained with unlimited data, wheneverΔB\>α𝒜\+εm​\(δ\)\\Delta\_\{\\mathrm\{B\}\}\>\\alpha\_\{\\mathcal\{A\}\}\+\\varepsilon\_\{m\}\(\\delta\)\. The dominant term ofεm​\(δ\)\\varepsilon\_\{m\}\(\\delta\)scales ass¯/m\\sqrt\{\\bar\{s\}/m\}rather than1/m\\sqrt\{1/m\}: sparse correction rules are cheaper to select reliably\. A numerical illustration in Appendix[F](https://arxiv.org/html/2608.19953#A6.SSx6)shows that under representative parameters, fewer than200200training instances suffice, which is similar to the typical sizes of training datasets\.

In summary, Theorem[1](https://arxiv.org/html/2608.19953#Thmtheorem1)establishes that the early solution provides a strict population\-level information gain under a stated posterior\-crossing condition, and the sparse\-correction identity explains where the gain comes from: repairing a small, better\-than\-chance set of unstable assignments\. Theorem[2](https://arxiv.org/html/2608.19953#Thmtheorem2)shows that this gain persists under finite\-sample model selection, with a sample cost discounted by the very sparsity that motivates our design\. Together, they justify shifting the learning target from full solution prediction to early\-to\-final consistency estimation\.

## 5Experiments

### Experimental Setup

Table 1:Main results with Gurobi\. Obj is the final feasible objective and Gap is the absolute gap to the in\-study BKS\. Arrows indicate the preferred objective direction; bold marks the best learning\-based result or a positive gap reduction\.Figure 3:Average primal gap to the BKS versus time under a 1,000\-second time limit\. EnCore starts after the early solution collection\. Each curve is shown only after all test instances have obtained a feasible solution\.#### Benchmarks\.

Following[25](https://arxiv.org/html/2608.19953#bib.bib13), we evaluate EnCore on Combinatorial Auctions \(CA\)\([21](https://arxiv.org/html/2608.19953#bib.bib18)\), Set Covering \(SC\)\([2](https://arxiv.org/html/2608.19953#bib.bib19)\), Workload Apportionment \(WA\), and Item Placement \(IP\)\([9](https://arxiv.org/html/2608.19953#bib.bib20)\)\. These benchmarks cover MILPs with diverse scales and structures\. For zero\-shot transfer, we additionally evaluate on the eleven\-instance MIPLIB IIS benchmark considered by[25](https://arxiv.org/html/2608.19953#bib.bib13), following the IIS setting introduced by[33](https://arxiv.org/html/2608.19953#bib.bib14)\. The benchmark is a structurally related subset of MIPLIB centered on binary set\-covering formulations, while exhibiting substantial variation in problem size, constraint structure, and sparsity\. Dataset sources and instance statistics are reported in App\.[D](https://arxiv.org/html/2608.19953#A4)\.

#### Baselines and variants\.

We compare against the native MILP solver and three prediction\-guided search pipelines: Neural Diving \(ND\)\([26](https://arxiv.org/html/2608.19953#bib.bib8)\), Predict\-and\-Search \(PS\)\([14](https://arxiv.org/html/2608.19953#bib.bib12)\), and Apollo\-MILP \(Apollo\)\([25](https://arxiv.org/html/2608.19953#bib.bib13)\)\. For each learning\-based pipeline, we replace its original solution predictor with our consistency predictor while keeping other configurations; the resulting methods are denoted as EnCore\-ND, EnCore\-PS, and EnCore\-Apollo\. This design isolates the contribution of the proposed consistency prediction mechanism from downstream solver policies\.

#### Evaluation protocol\.

All methods use a 1,000\-second end\-to\-end budget that includes early\-solution collection, inference, and downstream solving\. For a fair comparison, EnCore does not use the collected early solutions to warm\-start the final search\. For EnCore\-Apollo, early solutions are collected once and reused across correction rounds\. We report the final feasible objective, its absolute gap to the best\-known solution \(BKS\), and the gap reduction relative to the corresponding solution predictor baseline\. The BKS is the best mean final objective among all evaluated methods, including the 3,600\-second Gurobi reference\.

### Main Results

Table[1](https://arxiv.org/html/2608.19953#S5.T1)reports the final objectives under Gurobi\. Substituting EnCore for the original solution predictor reduces the final gap in 11 of the 12 settings \(4 benchmarks×\\times3 search mechanisms\), by 38\.7%, 56\.9%, and 36\.2% on average for ND, PS, and Apollo, respectively\. The sole exception is Apollo on SC, where the gap grows marginally from 0\.19 to 0\.20\. On CA, EnCore\-PS finds the best solution among all compared methods, improving on the 3,600\-second Gurobi incumbent by 179\.15 within a 1,000\-second budget, and EnCore\-Apollo also exceeds this reference \(\+42\.56\)\. On SC, WA, and IP, where the baselines have already been close to the BKS, EnCore still removes 43\.5%, 47\.8%, and 60\.0% of the best baseline gap\. Remarkably, EnCore remains effective even under weak easy\-to\-final consistency\. On CA, where 19% of the variables flip between the early and final solutions, the consistency predictor still captures the learnable patterns underlying these flips, allowing EnCore to achieve a 100% average gap reduction\.

Figure[3](https://arxiv.org/html/2608.19953#S5.F3)traces the primal gap over time\. Although the best EnCore variant on each benchmark begins prediction\-guided search only after the 60\-second collection stage, it catches up with its corresponding baseline at 71, 241, 164, and 93 seconds of end\-to\-end runtime on CA, SC, WA, and IP, respectively, and remains ahead thereafter\. EnCore\-PS overtakes all competitors early on CA and attains the lowest gap on SC and WA, with the late\-stage separation shown in the insets\. On IP, EnCore\-Apollo exhibits the strongest late\-stage anytime performance and widens its lead over time\.

#### Zero\-shot cross\-solver transfer to SCIP\.

We directly apply the Gurobi\-trained checkpoint to SCIP\-generated trajectories without retraining or model selection\. As shown in Table[2](https://arxiv.org/html/2608.19953#S5.T2), EnCore\-ND consistently improves all four benchmarks, reducing the absolute gap by 53\.6%, 22\.0%, 33\.1%, and 50\.7% on CA, SC, WA, and IP, respectively\. Moreover, EnCore\-PS also improves performance on CA, WA, and IP\. These results show that the learned consistency representation remains informative under a solver shift\.

Table 2:Zero\-shot transfer from Gurobi to SCIP under a 1,000\-second total budget\. Bold marks the best result\. The BKS is presented in Table[1](https://arxiv.org/html/2608.19953#S5.T1)\.
#### Zero\-shot cross\-family transfer to MIPLIB IIS\.

We train our EnCore models on the mixed SC, CA, WA, and IP instances, and evaluate them on the eleven unseen MIPLIB instances used by[25](https://arxiv.org/html/2608.19953#bib.bib13)under the same 1,000\-second budget\. The clearest advantage of EnCore is about feasibility\. With ND, the original predictor finds feasible solutions on only 3 of 11 instances, while EnCore\-ND succeeds on all 11\. With PS and Apollo, where the baselines already achieve full feasibility, EnCore still yields consistent improvements in mean objectives\. These results demonstrate that our proposed EnCore exhibits greater reliability and robustness than existing methods when faced with substantial distribution shifts\. Details are provided in Appendix[D](https://arxiv.org/html/2608.19953#A4)\.

### Ablation Study

Table[3](https://arxiv.org/html/2608.19953#S5.T3)presents a cumulative ablation of the Predict\-and\-Search pipeline\. Adding early solutions as input features alone improves most benchmarks\. However, the consistency target contributes substantially larger gains than the extra features themselves, indicating that reformulating the prediction objective is empirically effective\. Finally, introducing early\-solution ensembling further improves CA, SC, and WA, delivering a smaller but complementary robustness benefit\.

Table 3:Ablation study of key components under the Predict\-and\-Search pipeline\. Average objective values are reported\.#### Trade\-off Analysis of Early\-Solution Collection

Figure[4](https://arxiv.org/html/2608.19953#S5.F4)varies the collection budgetTmaxT\_\{\\max\}under the fixed 1,000\-second total budget\. Across all benchmarks, performance peaks at a smallTmaxT\_\{\\max\}: a short collection stage suffices to obtain informative early solutions, whereas largerTmaxT\_\{\\max\}leads to diminishing improvements in early\-solution quality while consuming more time budget for downstream search\.

Figure 4:Average final objective of EnCore\-PS under different maximum early\-solution collection times\.

## 6Conclusion

In this paper, we presented EnCore, a solver\-informed paradigm that accelerates MILP solving via early\-to\-final solution consistency prediction\. Instead of constructing complete solutions from the static MILP formulation alone, EnCore conditions on feasible solutions collected during the early search stage and identifies the assignments likely to persist under a full solving budget\. The resulting consistency scores integrate seamlessly with diverse prediction\-guided search frameworks, and ensembling multiple early solutions further enhances robustness\. Theoretically, we showed that conditioning on early solutions yields a strict gain in achievable prediction accuracy, and that this gain survives finite\-sample model selection at a cost discounted by correction sparsity\. Empirically, EnCore consistently improves prediction\-guided solving across four benchmarks and generalizes zero\-shot to unseen solvers and problem families\. Future work will explore jointly learning consistency prediction and downstream search policies\.

## References

- Achterberg \(2009\)T\. AchterbergSCIP: solving constraint integer programs\.Mathematical Programming Computation1\(1\),pp\. 1–41\.External Links:[Document](https://dx.doi.org/10.1007/s12532-008-0001-1)Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p1.1),[§1](https://arxiv.org/html/2608.19953#S1.p6.1)\.
- Balas and Ho \(1980\)E\. Balas and A\. HoSet covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study\.InCombinatorial Optimization,Vol\.12,pp\. 37–60\.Cited by:[Appendix D](https://arxiv.org/html/2608.19953#A4.SSx1.p1.1),[§5](https://arxiv.org/html/2608.19953#S5.SSx1.SSS0.Px1.p1.1)\.
- Bengioet al\.\(2021\)Y\. Bengio, A\. Lodi, and A\. ProuvostMachine learning for combinatorial optimization: a methodological tour d’horizon\.European Journal of Operational Research290\(2\),pp\. 405–421\.External Links:[Document](https://dx.doi.org/10.1016/j.ejor.2020.07.063)Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p2.1)\.
- Boucheronet al\.\(2013\)S\. Boucheron, G\. Lugosi, and P\. MassartConcentration inequalities: a nonasymptotic theory of independence\.Oxford University Press,Oxford\.Cited by:[Appendix F](https://arxiv.org/html/2608.19953#A6.SSx5.SSS0.Px1.p1.1),[Appendix F](https://arxiv.org/html/2608.19953#A6.SSx5.SSS0.Px2.p1.2),[§4](https://arxiv.org/html/2608.19953#S4.SS0.SSS0.Px3.p1.1),[§4](https://arxiv.org/html/2608.19953#S4.SS0.SSS0.Px3.p2.1.1)\.
- Crainic \(2000\)T\. G\. CrainicService network design in freight transportation\.European Journal of Operational Research122\(2\),pp\. 272–288\.Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p1.1)\.
- Devroyeet al\.\(1996\)L\. Devroye, L\. Györfi, and G\. LugosiA probabilistic theory of pattern recognition\.Stochastic Modelling and Applied Probability, Vol\.31,Springer,New York\.External Links:[Document](https://dx.doi.org/10.1007/978-1-4612-0711-5)Cited by:[§4](https://arxiv.org/html/2608.19953#S4.SS0.SSS0.Px1.p1.2)\.
- Ferberet al\.\(2020\)A\. Ferber, B\. Wilder, B\. Dilkina, and M\. TambeMIPaaL: mixed integer program as a layer\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.34,New York, NY, USA,pp\. 1504–1511\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v34i02.5509)Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p2.1)\.
- Floudas and Lin \(2005\)C\. A\. Floudas and X\. LinMixed integer linear programming in process scheduling: modeling, algorithms, and applications\.Annals of Operations Research139\(1\),pp\. 131–162\.Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p1.1)\.
- Gasseet al\.\(2022\)M\. Gasse, S\. Bowly, Q\. Cappart, J\. Charfreitag, L\. Charlin, D\. Chételat, A\. Chmiela, J\. Dumouchelle, A\. M\. Gleixner, A\. M\. Kazachkov, E\. B\. Khalil, P\. Lichocki, A\. Lodi, M\. Lubin, C\. J\. Maddison, C\. Morris, D\. J\. Papageorgiou, A\. Parjadis, S\. Pokutta, A\. Prouvost, L\. Scavuzzo, G\. Zarpellon,et al\.The machine learning for combinatorial optimization competition \(ML4CO\): results and insights\.InProceedings of the NeurIPS 2021 Competitions and Demonstrations Track,Proceedings of Machine Learning Research, Vol\.176,pp\. 220–231\.Cited by:[Appendix D](https://arxiv.org/html/2608.19953#A4.SSx1.p1.1),[§5](https://arxiv.org/html/2608.19953#S5.SSx1.SSS0.Px1.p1.1)\.
- Gasseet al\.\(2019\)M\. Gasse, D\. Chételat, N\. Ferroni, L\. Charlin, and A\. LodiExact combinatorial optimization with graph convolutional neural networks\.InAdvances in Neural Information Processing Systems 32,Vol\.32,Vancouver, BC, Canada\.Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p2.1),[§2](https://arxiv.org/html/2608.19953#S2.SSx2.p1.1)\.
- Gleixneret al\.\(2021\)A\. Gleixner, G\. Hendel, G\. Gamrath, T\. Achterberg, M\. Bastubbe, T\. Berthold, P\. M\. Christophel, K\. Jarck, T\. Koch, J\. Linderoth, M\. Lübbecke, H\. D\. Mittelmann, D\. Ozyurt, T\. K\. Ralphs, D\. Salvagnin, and Y\. ShinanoMIPLIB 2017: data\-driven compilation of the 6th mixed\-integer programming library\.Mathematical Programming Computation13\(3\),pp\. 443–490\.External Links:[Document](https://dx.doi.org/10.1007/s12532-020-00194-3),[Link](https://doi.org/10.1007/s12532-020-00194-3)Cited by:[Appendix D](https://arxiv.org/html/2608.19953#A4.SSx4.p1.1)\.
- Guptaet al\.\(2020\)P\. Gupta, M\. Gasse, E\. B\. Khalil, P\. Mudigonda, A\. Lodi, and Y\. BengioHybrid models for learning to branch\.InAdvances in Neural Information Processing Systems 33,Vol\.33,Virtual,pp\. 18087–18097\.Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p2.1)\.
- Gurobi Optimization, LLC \(2026\)Gurobi Optimization, LLCGurobi Optimizer Reference Manual\.External Links:[Link](https://www.gurobi.com/)Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p6.1)\.
- Hanet al\.\(2023\)Q\. Han, L\. Yang, Q\. Chen, X\. Zhou, D\. Zhang, A\. Wang, R\. Sun, and X\. LuoA GNN\-Guided Predict\-and\-Search Framework for Mixed\-Integer Linear Programming\.InThe 11th International Conference on Learning Representations,Kigali, Rwanda\.Cited by:[Appendix B](https://arxiv.org/html/2608.19953#A2.SS0.SSS0.Px1.p1.1),[Appendix B](https://arxiv.org/html/2608.19953#A2.SS0.SSS0.Px2.p1.1),[Appendix D](https://arxiv.org/html/2608.19953#A4.SSx1.p1.1),[Appendix D](https://arxiv.org/html/2608.19953#A4.SSx2.p1.1),[§1](https://arxiv.org/html/2608.19953#S1.p3.1),[§1](https://arxiv.org/html/2608.19953#S1.p6.1),[§2](https://arxiv.org/html/2608.19953#S2.SSx2.p2.1),[§3](https://arxiv.org/html/2608.19953#S3.SSx2.p1.1),[§5](https://arxiv.org/html/2608.19953#S5.SSx1.SSS0.Px2.p1.1)\.
- Hutteret al\.\(2009\)F\. Hutter, H\. H\. Hoos, K\. Leyton\-Brown, and T\. StützleParamILS: an automatic algorithm configuration framework\.Journal of Artificial Intelligence Research36,pp\. 267–306\.External Links:[Document](https://dx.doi.org/10.1613/jair.2861)Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p2.1)\.
- Kallenberg \(2021\)O\. KallenbergFoundations of modern probability\.3 edition,Springer,Cham\.Cited by:[§4](https://arxiv.org/html/2608.19953#S4.SS0.SSS0.Px1.p2.1.1)\.
- Karp \(1972\)R\. M\. KarpReducibility among combinatorial problems\.InProceedings of the Symposium on the Complexity of Computer Computations,Yorktown Heights, New York, USA,pp\. 85–103\.Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p1.1)\.
- Khalilet al\.\(2016\)E\. B\. Khalil, P\. Le Bodic, L\. Song, G\. Nemhauser, and B\. DilkinaLearning to branch in mixed integer programming\.InProceedings of the Thirtieth AAAI Conference on Artificial Intelligence,Vol\.30,Phoenix, AZ, USA,pp\. 724–731\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v30i1.10080)Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p2.1)\.
- Land and Doig \(1960\)A\. H\. Land and A\. G\. DoigAn automatic method of solving discrete programming problems\.Econometrica28\(3\),pp\. 497–520\.Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p1.1)\.
- Laporte \(1992\)G\. LaporteThe vehicle routing problem: an overview of exact and approximate algorithms\.European Journal of Operational Research59\(3\),pp\. 345–358\.External Links:ISSN 0377\-2217Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p1.1)\.
- Leyton\-Brownet al\.\(2000\)K\. Leyton\-Brown, M\. Pearson, and Y\. ShohamTowards a universal test suite for combinatorial auction algorithms\.InProceedings of the 2nd ACM Conference on Electronic Commerce,Minneapolis, MN, USA,pp\. 66–76\.Cited by:[Appendix D](https://arxiv.org/html/2608.19953#A4.SSx1.p1.1),[§5](https://arxiv.org/html/2608.19953#S5.SSx1.SSS0.Px1.p1.1)\.
- Liet al\.\(2026\)H\. Li, H\. Yuan, H\. Zhang, J\. Lin, D\. Ge, M\. Wang, and Y\. YeFMIP: joint continuous\-integer flow for mixed\-integer linear programming\.InThe 14th International Conference on Learning Representations,Rio de Janeiro, Brazil\.Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p3.1)\.
- Liet al\.\(2023\)S\. Li, W\. Ouyang, M\. B\. Paulus, and C\. WuLearning to configure separators in branch\-and\-cut\.InAdvances in Neural Information Processing Systems,Vol\.36,New Orleans, LA, USA,pp\. 60021–60034\.Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p2.1)\.
- Linget al\.\(2024\)H\. Ling, Z\. Wang, and J\. WangLearning to stop cut generation for efficient mixed\-integer linear programming\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,Vancouver, BC, Canada,pp\. 20759–20767\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v38i18.30064)Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p2.1)\.
- Liuet al\.\(2025\)H\. Liu, J\. Wang, Z\. Geng, X\. Li, Y\. Zong, F\. Zhu, J\. Hao, and F\. WuApollo\-MILP: an alternating prediction\-correction neural solving framework for mixed\-integer linear programming\.InThe 13th International Conference on Learning Representations,Singapore\.Cited by:[Appendix D](https://arxiv.org/html/2608.19953#A4.SSx1.p1.1),[Appendix D](https://arxiv.org/html/2608.19953#A4.SSx2.p1.1),[Appendix D](https://arxiv.org/html/2608.19953#A4.SSx4.p1.1),[§1](https://arxiv.org/html/2608.19953#S1.p3.1),[§3](https://arxiv.org/html/2608.19953#S3.SSx2.p1.1),[§5](https://arxiv.org/html/2608.19953#S5.SSx1.SSS0.Px1.p1.1),[§5](https://arxiv.org/html/2608.19953#S5.SSx1.SSS0.Px2.p1.1),[§5](https://arxiv.org/html/2608.19953#S5.SSx2.SSS0.Px2.p1.1)\.
- Nairet al\.\(2020\)V\. Nair, S\. Bartunov, F\. Gimeno, I\. von Glehn, P\. Lichocki, I\. Lobov, B\. O’Donoghue, N\. Sonnerat, C\. Tjandraatmadja, P\. Wang, R\. Addanki, T\. Hapuarachchi, T\. Keck, J\. Keeling, P\. Kohli, I\. Ktena, Y\. Li, O\. Vinyals, and Y\. ZwolsSolving mixed integer programs using neural networks\.External Links:2012\.13349Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p2.1),[§1](https://arxiv.org/html/2608.19953#S1.p3.1),[§5](https://arxiv.org/html/2608.19953#S5.SSx1.SSS0.Px2.p1.1)\.
- Nam and Logendran \(1992\)S\. Nam and R\. LogendranAggregate production planning — a survey of models and methodologies\.European Journal of Operational Research61\(3\),pp\. 255–272\.Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p1.1)\.
- Padberg and Rinaldi \(1991\)M\. Padberg and G\. RinaldiA branch\-and\-cut algorithm for the resolution of large\-scale symmetric traveling salesman problems\.SIAM Review33\(1\),pp\. 60–100\.Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p1.1)\.
- Puet al\.\(2026\)T\. Pu, J\. Li, Y\. Gao, S\. Liu, Z\. Geng, H\. Liu, C\. Chen, and C\. FanCoCo\-MILP: inter\-variable contrastive and intra\-constraint competitive MILP solution prediction\.InProceedings of the AAAI Conference on Artificial Intelligence,Singapore,pp\. 24882–24890\.Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p3.1)\.
- Salvagnin \(2016\)D\. SalvagninDetecting semantic groups in mip models\.InIntegration of AI and OR Techniques in Constraint Programming,pp\. 329–341\.Cited by:[§2](https://arxiv.org/html/2608.19953#S2.SSx2.p1.1)\.
- Stranget al\.\(2026\)P\. Strang, Z\. Alès, C\. Bissuel, O\. Juan, S\. Kedad\-Sidhoum, and E\. RachelsonPlanning in branch\-and\-bound: model\-based reinforcement learning for exact combinatorial optimization\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.40,pp\. 25627–25635\.Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p2.1)\.
- Tanget al\.\(2020\)Y\. Tang, S\. Agrawal, and Y\. FaenzaReinforcement learning for integer programming: learning to cut\.InProceedings of the 37th International Conference on Machine Learning,Vol\.119,Vienna, Austria,pp\. 9367–9376\.Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p2.1)\.
- Wanget al\.\(2024\)H\. P\. Wang, J\. Liu, X\. Chen, X\. Wang, P\. Li, and W\. YinDIG\-MILP: a deep instance generator for mixed\-integer linear programming with feasibility guarantee\.Transactions on Machine Learning Research\.External Links:ISSN 2835\-8856,[Link](https://openreview.net/forum?id=MywlrEaFqR)Cited by:[Appendix D](https://arxiv.org/html/2608.19953#A4.SSx4.p1.1),[§5](https://arxiv.org/html/2608.19953#S5.SSx1.SSS0.Px1.p1.1)\.
- Wanget al\.\(2026\)R\. Wang, X\. Li, and M\. WangMILPnet: a multi\-scale architecture with geometric feature sequence representations for advancing MILP problems\.InThe 14th International Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.19953#S1.p3.1)\.

## Appendix ASolver Behavior

Figures[5](https://arxiv.org/html/2608.19953#A1.F5)and[7](https://arxiv.org/html/2608.19953#A1.F7)show the primal gap versus solving time for Gurobi and SCIP on the four benchmarks\. Figures[6](https://arxiv.org/html/2608.19953#A1.F6)and[8](https://arxiv.org/html/2608.19953#A1.F8)show the distributions of integer variables flipped between the early and full\-budget solutions\. Figure[9](https://arxiv.org/html/2608.19953#A1.F9)reports the same analyses on MIPLIB\.

\(a\)CA\(b\)SC\(c\)WA\(d\)IP
Figure 5:Primal gap versus solving time for Gurobi\.\(a\)CA\(b\)SC\(c\)WA\(d\)IP
Figure 6:Early\-to\-final flip distributions for Gurobi; red and green dashed lines denote the mean and median\.\(a\)CA\(b\)SC\(c\)WA\(d\)IP
Figure 7:Primal gap versus solving time for SCIP\.\(a\)CA\(b\)SC\(c\)WA\(d\)IP
Figure 8:Early\-to\-final flip distributions for SCIP; red and green dashed lines denote the mean and median\.\(a\)Primal gap over time\.\(b\)Aggregate flip distribution\.\(c\)Per\-instance flip percentages\.
Figure 9:Solver behavior on the MIPLIB IIS dataset with Gurobi\.
## Appendix BModel Structure

#### Graph Representation\.

We follow the MILP representation of[14](https://arxiv.org/html/2608.19953#bib.bib12), adding only one dimension to each variable node to encode its early\-solution value\. Detailed feature definitions are provided in Table[4](https://arxiv.org/html/2608.19953#A2.T4)\.

IndexFeatureDescriptionVariable\-node features0ObjectiveNormalized objective coefficient\.1Variable coefficientAverage variable coefficient across all constraints\.2Variable degreeDegree of the variable node in the bipartite graph\.3Maximum coefficientMaximum variable coefficient across all constraints\.4Minimum coefficientMinimum variable coefficient across all constraints\.5Variable typeIndicator of whether the variable is integer\.6–17Position embeddingBinary encoding of the variable’s order among all variables\.18Early\-solution valueValue of the variable in the early solution collected as described in Appendix[C](https://arxiv.org/html/2608.19953#A3)\.Constraint\-node features0Constraint coefficientAverage of the nonzero coefficients in the constraint\.1Constraint degreeDegree of the constraint node in the bipartite graph\.2BiasNormalized right\-hand side of the constraint\.3SenseSense of the constraint\.Edge features0CoefficientCoefficient connecting the constraint and variable nodes\.Table 4:Graph features for input\.
#### Network architecture\.

We strictly follow the network architecture proposed by[14](https://arxiv.org/html/2608.19953#bib.bib12), modifying only the variable encoder to accommodate the additional early\-solution feature\. Each variable node is represented by 19 input features, consisting of the original 18 features and the early\-solution value introduced by our method\. Constraint nodes and edges have 4 and 1 input features, respectively\. All node representations are embedded into a 64\-dimensional latent space\.

For an input feature vector of dimensiondd, the node encoder is defined as

Encd⁡\(x\)=ReLU⁡\(W2​ReLU⁡\(W1​LN⁡\(x\)\)\),\\operatorname\{Enc\}\_\{d\}\(x\)=\\operatorname\{ReLU\}\\\!\\left\(W\_\{2\}\\,\\operatorname\{ReLU\}\\\!\\left\(W\_\{1\}\\operatorname\{LN\}\(x\)\\right\)\\right\),whereW1:ℝd→ℝ64W\_\{1\}\\colon\\mathbb\{R\}^\{d\}\\rightarrow\\mathbb\{R\}^\{64\}andW2:ℝ64→ℝ64W\_\{2\}\\colon\\mathbb\{R\}^\{64\}\\rightarrow\\mathbb\{R\}^\{64\}\. Accordingly, the variable and constraint encoders useEnc19\\operatorname\{Enc\}\_\{19\}andEnc4\\operatorname\{Enc\}\_\{4\}, respectively, while the scalar edge feature is normalized byLayerNorm⁡\(1\)\\operatorname\{LayerNorm\}\(1\)\.

The model performs two rounds of bidirectional message passing between variable and constraint nodes:

V→C→V→C→V\.V\\rightarrow C\\rightarrow V\\rightarrow C\\rightarrow V\.For a directed edgej→ij\\rightarrow i, the message is computed as

mi​j=WM​ReLU⁡\[LN⁡\(WL​hi\+WE​ei​j\+WR​hj\)\],m\_\{ij\}=W\_\{M\}\\,\\operatorname\{ReLU\}\\\!\\left\[\\operatorname\{LN\}\\\!\\left\(W\_\{L\}h\_\{i\}\+W\_\{E\}e\_\{ij\}\+W\_\{R\}h\_\{j\}\\right\)\\right\],wherehih\_\{i\}andhjh\_\{j\}denote the target and source node representations, andei​je\_\{ij\}is the encoded edge feature\. Incoming messages are summed and normalized:

m¯i=LN⁡\(∑j∈𝒩⁡\(i\)mi​j\)\.\\bar\{m\}\_\{i\}=\\operatorname\{LN\}\\\!\\left\(\\sum\_\{j\\in\\mathcal\{N\}\(i\)\}m\_\{ij\}\\right\)\.The target node representation is then updated by

hi′=WU,2​ReLU⁡\(WU,1​\[hi∥m¯i\]\),h\_\{i\}^\{\\prime\}=W\_\{U,2\}\\,\\operatorname\{ReLU\}\\\!\\left\(W\_\{U,1\}\[h\_\{i\}\\mathbin\{\\\|\}\\bar\{m\}\_\{i\}\]\\right\),where∥\\mathbin\{\\\|\}denotes concatenation,WU,1:ℝ128→ℝ64W\_\{U,1\}\\colon\\mathbb\{R\}^\{128\}\\rightarrow\\mathbb\{R\}^\{64\}, andWU,2:ℝ64→ℝ64W\_\{U,2\}\\colon\\mathbb\{R\}^\{64\}\\rightarrow\\mathbb\{R\}^\{64\}\.

Finally, each variable representation is mapped to a scalar logit:

ℓv=wout⊤​ReLU⁡\(Wout​hv\),\\ell\_\{v\}=w\_\{\\mathrm\{out\}\}^\{\\top\}\\operatorname\{ReLU\}\\\!\\left\(W\_\{\\mathrm\{out\}\}h\_\{v\}\\right\),where the final output layer has no bias\. The predicted probabilityσ⁡\(ℓv\)\\sigma\(\\ell\_\{v\}\)indicates whether the early\-solution value of variablevvis consistent with its value in the full\-budget reference solution\.

## Appendix CEarly Solution Collection Details

We first quantify the progress of the dual bound using the average dual\-gap decay rate, and then describe the early\-solution collection procedure in Algorithm[1](https://arxiv.org/html/2608.19953#alg1)\. Specifically, for thekk\-th monitoring interval, the decay rate is defined as

rk=\|Dka−Dkb\|tkb−tka,r\_\{k\}=\\frac\{\\left\|D\_\{k\_\{a\}\}\-D\_\{k\_\{b\}\}\\right\|\}\{t\_\{k\_\{b\}\}\-t\_\{k\_\{a\}\}\},\(2\)wherekak\_\{a\}andkbk\_\{b\}denote the observations at the beginning and end of the interval, respectively;DkaD\_\{k\_\{a\}\}andDkbD\_\{k\_\{b\}\}are the corresponding dual gaps; andtkat\_\{k\_\{a\}\}andtkbt\_\{k\_\{b\}\}are their wall\-clock times\. Thus,rkr\_\{k\}measures the average absolute reduction in the dual gap per unit time during thekk\-th monitoring interval\.

Algorithm 1Early Solution Collection0:MILP instance

GG, minimum probing time

TminT\_\{\\min\}, maximum probing time

TmaxT\_\{\\max\}, window size

ww, decay threshold

ϵ\\epsilon
0:Early solution

XE​SX^\{ES\}and probing time

tprobet\_\{\\mathrm\{probe\}\}
1:Initialize an empty callback record list

ℛ\\mathcal\{R\}\.

2:Start a probing solver run on

GG\.

3:whilethe solver is runningdo

4:ifa MIPSOL callback occurs at time

tkt\_\{k\}then

5:Record the explored solution

XkX\_\{k\}and relative dual gap

DkD\_\{k\}\.

6:Append

\(tk,Xk,Dk\)\(t\_\{k\},X\_\{k\},D\_\{k\}\)to

ℛ\\mathcal\{R\}\.

7:if

\|ℛ\|≥w\|\\mathcal\{R\}\|\\geq wthen

8:Let

kak\_\{a\}and

kbk\_\{b\}be the first and last records in the latest

ww\-record window\.

9:Compute

rkr\_\{k\}by Eq\. \([2](https://arxiv.org/html/2608.19953#A3.E2)\)\.

10:if

tk≥Tmint\_\{k\}\\geq T\_\{\\min\}and

rk<ϵr\_\{k\}<\\epsilonthen

11:Stop the probing run\.

12:endif

13:endif

14:endif

15:ifthe elapsed probing time reaches

TmaxT\_\{\\max\}then

16:Stop the probing run\.

17:endif

18:endwhile

19:Set

XE​SX^\{ES\}to the last explored solution during probing\.

20:Set

tprobet\_\{\\mathrm\{probe\}\}to the elapsed probing time\.

21:return

XE​SX^\{ES\}and

tprobet\_\{\\mathrm\{probe\}\}\.

## Appendix DExperimental Details

### Benchmark Details

We evaluate on the four benchmark families used by Apollo\-MILP\([25](https://arxiv.org/html/2608.19953#bib.bib13)\)\. Combinatorial Auctions \(CA\) instances follow the CATS generator\([21](https://arxiv.org/html/2608.19953#bib.bib18)\), Set Covering \(SC\) follows the classical construction of[2](https://arxiv.org/html/2608.19953#bib.bib19), and Workload Apportionment \(WA\) and Item Placement \(IP\) come from ML4CO\([9](https://arxiv.org/html/2608.19953#bib.bib20)\)\. CA is a maximization problem, whereas SC, WA, and IP are minimization problems\. Table[5](https://arxiv.org/html/2608.19953#A4.T5)reports average instance sizes\. We use 240 training, 60 validation, and 100 testing instances, following the settings in[14](https://arxiv.org/html/2608.19953#bib.bib12)and[25](https://arxiv.org/html/2608.19953#bib.bib13)\. We train all models with 500 epochs and a learning rate of 0\.001\.

Table 5:Statistical information of the benchmark instances\.
### Protocols for Combining EnCore with Downstream Search Methods

This section details how EnCore is integrated with the three downstream methods evaluated in Section[5](https://arxiv.org/html/2608.19953#S5)\. Following the evaluation protocol proposed by[14](https://arxiv.org/html/2608.19953#bib.bib12)and[25](https://arxiv.org/html/2608.19953#bib.bib13), every run is given a total wall\-clock budget of10001000s, and all overhead introduced by EnCore—including the time spent collecting the early solution—is counted against this budget\. LettE​St\_\{ES\}denote the time used to obtain the early solutionxE​Sx^\{ES\}on a given instance\.

#### Predict\-and\-Search and Neural Diving\.

Both methods consume the predictor output once, before the final solve, so the integration requires no change to their search procedures\. Given an instance, we run the solver on the original MILP fortE​St\_\{ES\}seconds and record the early solutionxE​Sx^\{ES\}together with the associated solving\-process features\. The consistency predictor then assigns each binary variable a scorep¯i\\bar\{p\}\_\{i\}, the estimated probability thatxiE​Sx\_\{i\}^\{ES\}agrees with the reference solution\. Since both methods specify their fixing budgets separately for the two binary values, selection is value\-conditioned: we rank the variables withxiE​S=0x\_\{i\}^\{ES\}=0byp¯i\\bar\{p\}\_\{i\}and retain the topk0k\_\{0\}, and independently retain the topk1k\_\{1\}among those withxiE​S=1x\_\{i\}^\{ES\}=1\. On CA under Predict\-and\-Search, for example, the setting\(k0,k1,Δ\)=\(600,0,20\)\(k\_\{0\},k\_\{1\},\\Delta\)=\(600,0,20\)selects the600600zero\-valued variables with the highest consistency scores and no one\-valued ones, and the resulting partial assignment\{xi=0\}\\\{x\_\{i\}=0\\\}defines the center of a search neighborhood of radiusΔ=20\\Delta=20\. Neural Diving consumes the selection in the same way except that the assignments are imposed as hard fixings and the reduced MILP is solved\. In both cases the solver is restarted from scratch with a budget of1000−tE​S1000\-t\_\{ES\}seconds, so that the end\-to\-end wall\-clock time matches that of the baselines\.

#### Apollo\-MILP\.

Apollo\-MILP performs four prediction–correction rounds with per\-round budgets of100100s,100100s,200200s, and600600s\. Extending the protocol above directly would require collecting a fresh early solution at the start of every round, which is too costly: the collection phase alone would consume a non\-negligible fraction of the100100s rounds\. We instead adopt the following assumption\. Since Apollo\-MILP realizes its fixing step by imposing bound constraints on the selected variables rather than by restructuring the problem, we assume that the early search behavior of the bounded problem stays close to that of the original instance, so that the early values realized on the original instance remain informative anchors throughout the iterative process\. Under this assumption, we collect the early solution only once, on the original instance and in exactly the same way as above, and reusexE​Sx^\{ES\}and its consistency scores in the prediction step of every round\. Each round applies the same value\-conditioned selection, restricted to the variables not yet fixed in earlier rounds\. To keep the total budget unchanged, the collection costtE​St\_\{ES\}is charged to the final round, whose budget becomes600−tE​S600\-t\_\{ES\}seconds, while the first three rounds are left untouched; the overall wall\-clock time thus remains10001000s\.

### Evaluation Protocol

#### Hardware\.

All experiments are conducted on a Linux server \(Ubuntu 20\.04\.6 LTS\) equipped with an Intel Xeon Platinum 8124M CPU \(72 logical cores, 3\.50GHz\), 256GB of RAM, and an NVIDIA GeForce RTX 3090 GPU \(24GB\)\. Neural network training and inference run on the GPU, while all solver calls run on the CPU\. The solver configuration \(e\.g\., thread count\) is kept identical across all methods on each benchmark\.

#### Metrics\.

We report the final feasible objective and its absolute primal gap

gapabs=\|z−zBKS\|,\\mathrm\{gap\}\_\{\\mathrm\{abs\}\}=\|z\-z\_\{\\mathrm\{BKS\}\}\|,\(3\)wherezzis the mean final objective of a method andzBKSz\_\{\\mathrm\{BKS\}\}is the best\-known solution \(BKS\) on the corresponding benchmark\. The BKS is defined as the best mean final objective observed among all evaluated methods, including a 3,600\-second Gurobi run: Gurobi provides this reference on SC, WA, and IP, while EnCore\-PS provides it on CA\. The BKS is thus an in\-study best\-observed reference rather than an independently certified optimum\. To quantify the benefit of our method over a downstream baseline, we additionally report the relative gap reduction

Improvement=gapbase−gapoursgapbase×100%\.\\mathrm\{Improvement\}=\\frac\{\\mathrm\{gap\}\_\{\\mathrm\{base\}\}\-\\mathrm\{gap\}\_\{\\mathrm\{ours\}\}\}\{\\mathrm\{gap\}\_\{\\mathrm\{base\}\}\}\\times 100\\%\.\(4\)

### Zero\-Shot MIPLIB IIS Transfer Protocol

The IIS setting traces to[33](https://arxiv.org/html/2608.19953#bib.bib14), which formed a two\-instance dataset from MIPLIB:iis\-glass\-covwas used for training andiis\-hc\-covfor testing\. Apollo\-MILP later expanded this setting into an eleven\-instance subset of MIPLIB 2017\([11](https://arxiv.org/html/2608.19953#bib.bib15);[25](https://arxiv.org/html/2608.19953#bib.bib13)\)\. Specifically, it selected instances according to similarities measured with 100 human\-designed structural features, then discarded instances whose presolving exceeded 300 seconds or whose inference exceeded GPU memory\. Apollo\-MILP used eight of the resulting instances for training and three—ramos3,scpj4scip, andscpl4—for testing\. In contrast, we use all eleven instances exclusively as a zero\-shot test set\. The instances range from 214 to 200,000 variables and from 32,805 to 2,000,000 nonzero coefficients\.

In this experiment, both predictors are trained on the union of the CA, SC, WA, and IP training sets\. They are validated on the union of the corresponding validation sets, and checkpoint selection uses only this combined validation set\. The selected checkpoints are frozen before evaluation on IIS\. No MIPLIB instance is used for training, validation, fine\-tuning, or checkpoint selection\.

Table[6](https://arxiv.org/html/2608.19953#A4.T6)gives the overall performance while Table[7](https://arxiv.org/html/2608.19953#A4.T7)gives the instance\-level results\. The PS improvement is mainly attributable toramos3andex1010\-pi, partially offset byscpk4\. Apollo\+Ours improvesex1010\-pi, degrades onramos3, and ties on the remaining instances\.

Table 6:Zero\-shot cross\-family transfer to the MIPLIB IIS subset\. Mean Obj is the mean of the per\-instance final objectives\. Feas\. reports the number of instances with a finite feasible objective\.†means computed only over its three feasible instances\.Table 7:Final objectives on the eleven MIPLIB IIS instances\. All instances are minimization problems\. Bold marks the lowest objective in each row; a dash indicates that no finite feasible solution was found\.

## Appendix EHyperparameter Settings

### Early Solution Collection

For early\-solution collection, we set the sliding\-window size tow=5w=5, the dual\-gap decay threshold toϵ=0\.01%\\epsilon=0\.01\\%/s, the minimum probing time toTmin=20T\_\{\\min\}=20seconds, and the maximum probing time toTmax=60T\_\{\\max\}=60seconds\. We use an ensemble size ofK=3K=3for SC, CA and WA and useK=2K=2for IP\.

### Neighborhood Search Parameters

We report the hyper\-parameters we used in our study\. EnCore and baselines use the same hyper\-parameters\. Table[8](https://arxiv.org/html/2608.19953#A5.T8)shows the hyperparameters of Predict\-and\-Search and EnCore\-PS, and the Neural Diving and EnCore\-ND uses the same\(k0,k1\)\(k\_\{0\},k\_\{1\}\)\. Table[9](https://arxiv.org/html/2608.19953#A5.T9)shows the Apollo hyperparameters for baseline Apollo\-MILP and EnCore\-apollo\.

Table 8:The partial solution size parameters\(k0,k1\)\(k\_\{0\},k\_\{1\}\)and neighborhood parameterΔ\\Delta\.Table 9:Hyperparameters\(k0\(i\),k1\(i\),Δ\(i\)\)\(k\_\{0\}^\{\(i\)\},k\_\{1\}^\{\(i\)\},\\Delta^\{\(i\)\}\)for Apollo\-MILP\.

## Appendix FDetails and Proofs for the Theoretical Analysis

### Population Setting and Notation

Let𝒟\\mathcal\{D\}be the probability distribution over all triples consisting of an MILP graph, the early solution produced by the fixed collection procedure, and the full\-budget solution\. Draw

Z=\(G,XE​S,X∗\)∼𝒟\.Z=\(G,X^\{ES\},X^\{\*\}\)\\sim\\mathcal\{D\}\.Letℬ⁡\(G\)\\mathcal\{B\}\(G\)be the set of binary\-variable indices inGG\. Assume\|ℬ⁡\(G\)\|≥1\|\\mathcal\{B\}\(G\)\|\\geq 1almost surely\. To represent the per\-instance variable average compactly, conditional onZZ, chooseJJfromℬ⁡\(G\)\\mathcal\{B\}\(G\), giving every index probability1/\|ℬ⁡\(G\)\|1/\|\\mathcal\{B\}\(G\)\|\. We useJJfor this random index in population quantities andrrfor a deterministic summation index\.

Fix the message\-passing depthLL\. Forr∈ℬ⁡\(G\)r\\in\\mathcal\{B\}\(G\), letℛr\\mathcal\{R\}\_\{r\}denote the part of the static graph and its features withinLLmessage\-passing steps of variablerr, and letXℛrE​SX^\{ES\}\_\{\\mathcal\{R\}\_\{r\}\}denote the early assignments attached to the variable nodes in this local input\.

For any assignment predictorhh, define

ℓh​\(Z\)\\displaystyle\\ell\_\{h\}\(Z\):=1\|ℬ⁡\(G\)\|∑r∈ℬ⁡\(G\)𝟏\{hr≠xr∗\},\\displaystyle:=\\frac\{1\}\{\|\\mathcal\{B\}\(G\)\|\}\\sum\_\{r\\in\\mathcal\{B\}\(G\)\}\\mathbf\{1\}\\\{h\_\{r\}\\neq x\_\{r\}^\{\*\}\\\},R⁡\(h\)\\displaystyle R\(h\):=E⁡\[ℓh​\(Z\)\]=Pr⁡\(hJ≠xJ∗\),\\displaystyle:=\\mathrm\{E\}\[\\ell\_\{h\}\(Z\)\]=\\Pr\(h\_\{J\}\\neq x\_\{J\}^\{\*\}\),Acc⁡\(h\)\\displaystyle\\operatorname\{Acc\}\(h\):=1−R⁡\(h\)\.\\displaystyle:=1\-R\(h\)\.Here a direct predictionhrh\_\{r\}is a function ofℛr\\mathcal\{R\}\_\{r\}, whereas an induced consistency prediction may also useXℛrE​SX^\{ES\}\_\{\\mathcal\{R\}\_\{r\}\}\. The corresponding posteriors are

ηG\\displaystyle\\eta\_\{G\}:=Pr⁡\(xJ∗=1∣ℛJ\),\\displaystyle:=\\Pr\(x\_\{J\}^\{\*\}=1\\mid\\mathcal\{R\}\_\{J\}\),ηE​S\\displaystyle\\eta\_\{ES\}:=Pr⁡\(xJ∗=1∣ℛJ,XℛJE​S\)\.\\displaystyle:=\\Pr\(x\_\{J\}^\{\*\}=1\\mid\\mathcal\{R\}\_\{J\},X^\{ES\}\_\{\\mathcal\{R\}\_\{J\}\}\)\.Their Bayes errors are

bG\\displaystyle b\_\{G\}:=E⁡\[min⁡\{ηG,1−ηG\}\],\\displaystyle:=\\mathrm\{E\}\[\\min\\\{\\eta\_\{G\},1\-\\eta\_\{G\}\\\}\],bE​S\\displaystyle b\_\{ES\}:=E⁡\[min⁡\{ηE​S,1−ηE​S\}\]\.\\displaystyle:=\\mathrm\{E\}\[\\min\\\{\\eta\_\{ES\},1\-\\eta\_\{ES\}\\\}\]\.ThusAsol∗=1−bGA\_\{\\mathrm\{sol\}\}^\{\*\}=1\-b\_\{G\}is the best population accuracy attainable from the static local input, and1−bE​S1\-b\_\{ES\}is the best assignment accuracy attainable when the early assignments are also observed\.

### Consistency–Assignment Equivalence

#### Lemma 1 \(label–assignment equivalence\)\.

Forr∈ℬ⁡\(G\)r\\in\\mathcal\{B\}\(G\), letyr=𝟏\{xrE​S=xr∗\}y\_\{r\}=\\mathbf\{1\}\\\{x\_\{r\}^\{ES\}=x\_\{r\}^\{\*\}\\\}\. Given a binary consistency predictiony^r\\widehat\{y\}\_\{r\}, retainxrE​Sx\_\{r\}^\{ES\}wheny^r=1\\widehat\{y\}\_\{r\}=1and use its binary complement otherwise\. The induced assignmentx^r\\widehat\{x\}\_\{r\}satisfies

𝟏\{x^r≠xr∗\}=𝟏\{y^r≠yr\}\.\\mathbf\{1\}\\\{\\widehat\{x\}\_\{r\}\\neq x\_\{r\}^\{\*\}\\\}=\\mathbf\{1\}\\\{\\widehat\{y\}\_\{r\}\\neq y\_\{r\}\\\}\.Equivalently, for a consistency ruleaa, define

ha​\(G,XE​S\)r:=xrE​S⊕\(1−a​\(G,XE​S\)r\)\.h\_\{a\}\(G,X^\{ES\}\)\_\{r\}:=x\_\{r\}^\{ES\}\\mathbin\{\\oplus\}\(1\-a\(G,X^\{ES\}\)\_\{r\}\)\.Then

ℓha\(Z\)=1\|ℬ⁡\(G\)\|∑r∈ℬ⁡\(G\)𝟏\{a\(G,XE​S\)r≠yr\}\.\\ell\_\{h\_\{a\}\}\(Z\)=\\frac\{1\}\{\|\\mathcal\{B\}\(G\)\|\}\\sum\_\{r\\in\\mathcal\{B\}\(G\)\}\\mathbf\{1\}\\\{a\(G,X^\{ES\}\)\_\{r\}\\neq y\_\{r\}\\\}\.\(5\)

#### Proof\.

For binary values,xr∗=xrE​S⊕\(1−yr\)x\_\{r\}^\{\*\}=x\_\{r\}^\{ES\}\\mathbin\{\\oplus\}\(1\-y\_\{r\}\)\. XOR by the same value preserves equality, soha​\(G,XE​S\)r≠xr∗h\_\{a\}\(G,X^\{ES\}\)\_\{r\}\\neq x\_\{r\}^\{\*\}exactly whena​\(G,XE​S\)r≠yra\(G,X^\{ES\}\)\_\{r\}\\neq y\_\{r\}\. Averaging overℬ⁡\(G\)\\mathcal\{B\}\(G\)proves Eq\. \([5](https://arxiv.org/html/2608.19953#A6.E5)\)\.□\\Box

The induced assignmenthah\_\{a\}is used only to compare variable\-level prediction errors\. In the downstream search method, assignments predicted inconsistent are left free rather than forcibly complemented, so these identities characterize the variable\-level prediction task, while the downstream objective and runtime effects are evaluated empirically\.

Conversely, every direct solution predictorhhdefines a consistency rule

ah\(G,XE​S\)r:=𝟏\{h\(ℛr\)=xrE​S\}\.a\_\{h\}\(G,X^\{ES\}\)\_\{r\}:=\\mathbf\{1\}\\\{h\(\\mathcal\{R\}\_\{r\}\)=x\_\{r\}^\{ES\}\\\}\.The induced predictor satisfieshah​\(G,XE​S\)r=h⁡\(ℛr\)h\_\{a\_\{h\}\}\(G,X^\{ES\}\)\_\{r\}=h\(\\mathcal\{R\}\_\{r\}\)\. Thus consistency prediction with the augmented input can reproduce every direct predictor based on the static local input\.

LetYJ=𝟏\{xJE​S=xJ∗\}Y\_\{J\}=\\mathbf\{1\}\\\{x\_\{J\}^\{ES\}=x\_\{J\}^\{\*\}\\\}and

ξJ:=Pr⁡\(YJ=1∣ℛJ,XℛJE​S\)\.\\xi\_\{J\}:=\\Pr\(Y\_\{J\}=1\\mid\\mathcal\{R\}\_\{J\},X^\{ES\}\_\{\\mathcal\{R\}\_\{J\}\}\)\.For a fixed variablerr,ξr\\xi\_\{r\}denotes the corresponding conditional posterior evaluated atrr\. SincexJE​Sx\_\{J\}^\{ES\}is observed in the augmented local input,

ξJ=xJE​S​ηE​S\+\(1−xJE​S\)​\(1−ηE​S\)\.\\xi\_\{J\}=x\_\{J\}^\{ES\}\\eta\_\{ES\}\+\(1\-x\_\{J\}^\{ES\}\)\(1\-\\eta\_\{ES\}\)\.Consequently,

min⁡\{ξJ,1−ξJ\}=min⁡\{ηE​S,1−ηE​S\},\\min\\\{\\xi\_\{J\},1\-\\xi\_\{J\}\\\}=\\min\\\{\\eta\_\{ES\},1\-\\eta\_\{ES\}\\\},so the Bayes consistency error equalsbE​Sb\_\{ES\}\. Under variable\-level00–11prediction loss, the optimal rule predicts11whenξJ≥1/2\\xi\_\{J\}\\geq 1/2and00otherwise\. By Lemma 1, its induced assignment accuracy isAcon∗=1−bE​SA\_\{\\mathrm\{con\}\}^\{\*\}=1\-b\_\{ES\}\. Because the label transformation is bijective afterxJE​Sx\_\{J\}^\{ES\}is observed, this is also the Bayes accuracy of a direct assignment predictor using the same augmented input\. Theorem[1](https://arxiv.org/html/2608.19953#Thmtheorem1)therefore compares the information in the augmented input with that in the static input, rather than attributing a Bayes advantage to the consistency relabeling itself\.

### Proof of Theorem[1](https://arxiv.org/html/2608.19953#Thmtheorem1)

The population accuracy difference can be written as

Acon∗−Asol∗=bG−bE​S≥0\.A\_\{\\mathrm\{con\}\}^\{\*\}\-A\_\{\\mathrm\{sol\}\}^\{\*\}=b\_\{G\}\-b\_\{ES\}\\geq 0\.\(6\)The inequality is strict if there exists an eventℰ∈σ⁡\(ℛJ\)\\mathcal\{E\}\\in\\sigma\(\\mathcal\{R\}\_\{J\}\)withPr⁡\(ℰ\)\>0\\Pr\(\\mathcal\{E\}\)\>0such that, almost surely onℰ\\mathcal\{E\},

Pr⁡\(ηE​S<12∣ℛJ\)\\displaystyle\\Pr\(\\eta\_\{ES\}<\\tfrac\{1\}\{2\}\\mid\\mathcal\{R\}\_\{J\}\)\>0,\\displaystyle\>0,Pr⁡\(ηE​S\>12∣ℛJ\)\\displaystyle\\Pr\(\\eta\_\{ES\}\>\\tfrac\{1\}\{2\}\\mid\\mathcal\{R\}\_\{J\}\)\>0\.\\displaystyle\>0\.In words, the same static local input can be paired with early assignments that make either final value more likely\.

#### Proof of Theorem[1](https://arxiv.org/html/2608.19953#Thmtheorem1)\.

The tower property gives

ηG=E⁡\[ηE​S∣ℛJ\]\.\\eta\_\{G\}=\\mathrm\{E\}\[\\eta\_\{ES\}\\mid\\mathcal\{R\}\_\{J\}\]\.\(7\)Usingmin⁡\{t,1−t\}=12−\|t−12\|\\min\\\{t,1\-t\\\}=\\tfrac\{1\}\{2\}\-\|t\-\\tfrac\{1\}\{2\}\|, the Bayes accuracy gap is

Acon∗−Asol∗\\displaystyle A\_\{\\mathrm\{con\}\}^\{\*\}\-A\_\{\\mathrm\{sol\}\}^\{\*\}=E⁡\[\|ηE​S−12\|\]\\displaystyle=\\mathrm\{E\}\[\|\\eta\_\{ES\}\-\\tfrac\{1\}\{2\}\|\]−E⁡\[\|ηG−12\|\]\.\\displaystyle\-\\mathrm\{E\}\[\|\\eta\_\{G\}\-\\tfrac\{1\}\{2\}\|\]\.Conditional Jensen’s inequality and Eq\. \([7](https://arxiv.org/html/2608.19953#A6.E7)\) imply

E⁡\[\|ηE​S−12\|∣ℛJ\]≥\|ηG−12\|\.\\mathrm\{E\}\[\|\\eta\_\{ES\}\-\\tfrac\{1\}\{2\}\|\\mid\\mathcal\{R\}\_\{J\}\]\\geq\|\\eta\_\{G\}\-\\tfrac\{1\}\{2\}\|\.Taking expectations proves Eq\. \([6](https://arxiv.org/html/2608.19953#A6.E6)\)\. If the refined posterior lies on both sides of1/21/2with positive conditional probability, the conditional absolute\-value inequality is strict\. The stated positive\-probability condition therefore givesAcon∗\>Asol∗A\_\{\\mathrm\{con\}\}^\{\*\}\>A\_\{\\mathrm\{sol\}\}^\{\*\}\.□\\Box

#### Scope of the comparison\.

The two optima compared in Theorem[1](https://arxiv.org/html/2608.19953#Thmtheorem1)range over functions of the same receptive field:Asol∗A\_\{\\mathrm\{sol\}\}^\{\*\}is the Bayes accuracy given the static local inputℛJ\\mathcal\{R\}\_\{J\}, andAcon∗A\_\{\\mathrm\{con\}\}^\{\*\}is the Bayes accuracy given the augmented local input\(ℛJ,XℛJE​S\)\(\\mathcal\{R\}\_\{J\},X^\{ES\}\_\{\\mathcal\{R\}\_\{J\}\}\), at the same fixed depthLL\. Statements in the main text about “any solution predictor”, or about what “no predictor on instance features alone” can achieve, therefore quantify over predictors whose decision at a variable is a measurable function of its static local input, however large that function class is; they do not compare against predictors with a strictly larger input scope\. In particular, ifX∗X^\{\*\}were almost surely determined by the full graphGG—for example, a unique optimal solution returned by a deterministic solver—then the whole\-graph posterior would be\{0,1\}\\\{0,1\\\}\-valued, posterior crossing could not occur at the whole\-graph level, and a whole\-graph predictor would attain perfect accuracy in principle, leaving no information\-theoretic gain for the early solution\. The strict\-gain content of Theorem[1](https://arxiv.org/html/2608.19953#Thmtheorem1)is thus per locality level: for every fixed message\-passing depth, augmenting the local input strictly improves the best achievable accuracy whenever posterior crossing occurs at that depth\. This is the operative comparison for the models considered in this line of work, including ours and the baselines, which are all message\-passing GNNs whose receptive field is fixed by the architecture and is typically far smaller than the benchmark graphs\. Moreover, on practical benchmarksX∗X^\{\*\}retains genuine randomness givenGG: instances frequently admit multiple optimal or near\-optimal solutions, and the incumbent returned under a time budget depends on tie\-breaking, thread timing, and budget truncation rather than onGGalone\. Under such residual randomness the whole\-graph posterior is not\{0,1\}\\\{0,1\\\}\-valued either, so posterior crossing—and hence a strict gain from the early solution—can occur at any input scope, including the full graph\.

### Sparse\-Correction Identity

The Bayes consistency rule is

a∗\(G,XE​S\)r:=𝟏\{ξr≥12\}\.a^\{\*\}\(G,X^\{ES\}\)\_\{r\}:=\\mathbf\{1\}\\\{\\xi\_\{r\}\\geq\\tfrac\{1\}\{2\}\\\}\.Define the event

𝒞∗:=\{ξJ<12\}=\{a∗\(G,XE​S\)J=0\},\\mathcal\{C\}^\{\*\}:=\\\{\\xi\_\{J\}<\\tfrac\{1\}\{2\}\\\}=\\\{a^\{\*\}\(G,X^\{ES\}\)\_\{J\}=0\\\},and define

p:=Pr⁡\(YJ=0\),ρ:=Pr⁡\(𝒞∗\)\.p:=\\Pr\(Y\_\{J\}=0\),\\qquad\\rho:=\\Pr\(\\mathcal\{C\}^\{\*\}\)\.Ifρ\>0\\rho\>0, also define

q:=Pr⁡\(YJ=0∣𝒞∗\)\.q:=\\Pr\(Y\_\{J\}=0\\mid\\mathcal\{C\}^\{\*\}\)\.Thenq\>1/2q\>1/2, anda∗a^\{\*\}satisfies

bE​S=R⁡\(ha∗\)\\displaystyle b\_\{ES\}=R\(h\_\{a^\{\*\}\}\)=p−ρ⁡\(2​q−1\),\\displaystyle=p\-\\rho\(2q\-1\),\(8\)ΔB:=Acon∗−Asol∗\\displaystyle\\Delta\_\{\\mathrm\{B\}\}:=A\_\{\\mathrm\{con\}\}^\{\*\}\-A\_\{\\mathrm\{sol\}\}^\{\*\}=bG−p\+ρ⁡\(2​q−1\)\.\\displaystyle=b\_\{G\}\-p\+\\rho\(2q\-1\)\.ThusΔB\>0\\Delta\_\{\\mathrm\{B\}\}\>0exactly when

p<bG\+ρ⁡\(2​q−1\)\.p<b\_\{G\}\+\\rho\(2q\-1\)\.\(9\)Forp≥bGp\\geq b\_\{G\}andρ\>0\\rho\>0, this is equivalent to

q\>12\+p−bG2​ρ\.q\>\\frac\{1\}\{2\}\+\\frac\{p\-b\_\{G\}\}\{2\\rho\}\.Ifρ=0\\rho=0, thenbE​S=pb\_\{ES\}=pandΔB=bG−p\\Delta\_\{\\mathrm\{B\}\}=b\_\{G\}\-p\.

#### Derivation\.

For any consistency ruleaa, retaining an assignment has error1−YJ1\-Y\_\{J\}, whereas using its binary complement has errorYJY\_\{J\}\. Hence

R⁡\(ha\)=p\+E⁡\[\(2​YJ−1\)​\(1−a​\(G,XE​S\)J\)\]\.R\(h\_\{a\}\)=p\+\\mathrm\{E\}\[\(2Y\_\{J\}\-1\)\(1\-a\(G,X^\{ES\}\)\_\{J\}\)\]\.\(10\)On𝒞∗\\mathcal\{C\}^\{\*\}, the conditional probability ofYJ=0Y\_\{J\}=0isqq\. Substitutinga∗a^\{\*\}into Eq\. \([10](https://arxiv.org/html/2608.19953#A6.E10)\) gives

R⁡\(ha∗\)=p\+ρ⁡\(1−q\)−ρ​q=p−ρ⁡\(2​q−1\)\.R\(h\_\{a^\{\*\}\}\)=p\+\\rho\(1\-q\)\-\\rho q=p\-\\rho\(2q\-1\)\.Moreover,

q=1−E⁡\[ξJ∣𝒞∗\]\>12\.q=1\-\\mathrm\{E\}\[\\xi\_\{J\}\\mid\\mathcal\{C\}^\{\*\}\]\>\\tfrac\{1\}\{2\}\.The rulea∗a^\{\*\}is the pointwise Bayes classifier forYJY\_\{J\}, so Lemma 1 givesR⁡\(ha∗\)=bE​SR\(h\_\{a^\{\*\}\}\)=b\_\{ES\}\. Subtracting this risk frombGb\_\{G\}proves Eq\. \([8](https://arxiv.org/html/2608.19953#A6.E8)\); the remaining statements follow by rearrangement\. Ifρ=0\\rho=0,a∗a^\{\*\}retains the early solution almost surely, and its error ispp\.□\\Box

### Finite\-Sample Analysis

The population result ranges over all possible rules\. For the finite\-sample result, fix before observing the training instances a finite class𝒜\\mathcal\{A\}ofN:=\|𝒜\|≥1N:=\|\\mathcal\{A\}\|\\geq 1consistency rules whose variable\-level decisions use the augmented local inputs defined above\. LetZ1,…,ZmZ\_\{1\},\\ldots,Z\_\{m\}be i\.i\.d\. training instances from𝒟\\mathcal\{D\}\. Suppose training and test instances follow𝒟\\mathcal\{D\}\. Define

A𝒜∗\\displaystyle A\_\{\\mathcal\{A\}\}^\{\*\}:=maxa∈𝒜⁡Acc⁡\(ha\),\\displaystyle:=\\max\_\{a\\in\\mathcal\{A\}\}\\operatorname\{Acc\}\(h\_\{a\}\),Δ𝒜\\displaystyle\\Delta\_\{\\mathcal\{A\}\}:=A𝒜∗−Asol∗=bG−mina∈𝒜⁡R⁡\(ha\)\.\\displaystyle:=A\_\{\\mathcal\{A\}\}^\{\*\}\-A\_\{\\mathrm\{sol\}\}^\{\*\}=b\_\{G\}\-\\min\_\{a\\in\\mathcal\{A\}\}R\(h\_\{a\}\)\.RecallΔB:=Acon∗−Asol∗\\Delta\_\{\\mathrm\{B\}\}:=A\_\{\\mathrm\{con\}\}^\{\*\}\-A\_\{\\mathrm\{sol\}\}^\{\*\}, and define the finite\-class approximation gap

α𝒜:=Acon∗−A𝒜∗\.\\alpha\_\{\\mathcal\{A\}\}:=A\_\{\\mathrm\{con\}\}^\{\*\}\-A\_\{\\mathcal\{A\}\}^\{\*\}\.ThenΔ𝒜=ΔB−α𝒜\\Delta\_\{\\mathcal\{A\}\}=\\Delta\_\{\\mathrm\{B\}\}\-\\alpha\_\{\\mathcal\{A\}\}, separating the population information gain from the approximation cost of the finite class\. For an instanceZZ, letsa​\(Z\)s\_\{a\}\(Z\)be the proportion of binary variables that ruleaawould flip\. Assume every candidate flips at most a proportions¯∈\[0,1\]\\bar\{s\}\\in\[0,1\]on average:

sa​\(Z\)\\displaystyle s\_\{a\}\(Z\):=1\|ℬ⁡\(G\)\|​∑r∈ℬ⁡\(G\)\(1−a​\(G,XE​S\)r\),\\displaystyle:=\\frac\{1\}\{\|\\mathcal\{B\}\(G\)\|\}\\sum\_\{r\\in\\mathcal\{B\}\(G\)\}\(1\-a\(G,X^\{ES\}\)\_\{r\}\),maxa∈𝒜⁡E⁡\[sa​\(Z\)\]\\displaystyle\\max\_\{a\\in\\mathcal\{A\}\}\\mathrm\{E\}\[s\_\{a\}\(Z\)\]≤s¯\.\\displaystyle\\leq\\bar\{s\}\.ThusΔ𝒜\\Delta\_\{\\mathcal\{A\}\}is the population accuracy difference between the best rule available in𝒜\\mathcal\{A\}and the best predictor based only on the static local input\. It can be nonpositive if the finite class does not contain a sufficiently accurate consistency rule\.

For a predictor that depends on the realized training sample and any training randomness,R⁡\(h\)R\(h\)andAcc⁡\(h\)\\operatorname\{Acc\}\(h\)below denote conditional population quantities evaluated on a fresh test triple independent of that training information\.

Letakeep​\(G,XE​S\)r≡1a\_\{\\mathrm\{keep\}\}\(G,X^\{ES\}\)\_\{r\}\\equiv 1\. Thenhakeep​\(G,XE​S\)=XE​Sh\_\{a\_\{\\mathrm\{keep\}\}\}\(G,X^\{ES\}\)=X^\{ES\}andR⁡\(hakeep\)=pR\(h\_\{a\_\{\\mathrm\{keep\}\}\}\)=p\. Define the loss change relative to this baseline by

Da​\(Z\)\\displaystyle D\_\{a\}\(Z\):=ℓha​\(Z\)−ℓhakeep​\(Z\),\\displaystyle:=\\ell\_\{h\_\{a\}\}\(Z\)\-\\ell\_\{h\_\{a\_\{\\mathrm\{keep\}\}\}\}\(Z\),D^a\\displaystyle\\widehat\{D\}\_\{a\}:=1m​∑k=1mDa​\(Zk\)\.\\displaystyle:=\\frac\{1\}\{m\}\\sum\_\{k=1\}^\{m\}D\_\{a\}\(Z\_\{k\}\)\.
#### Lemma 2 \(uniform concentration\)\.

Following the finite\-class Bernstein–union\-bound argument\([4](https://arxiv.org/html/2608.19953#bib.bib34)\), we apply concentration to instance\-level loss differences relative to the always\-retain rule\. For everyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta,

supa∈𝒜\|D^a−E⁡\[Da\]\|\\displaystyle\\sup\_\{a\\in\\mathcal\{A\}\}\|\\widehat\{D\}\_\{a\}\-\\mathrm\{E\}\[D\_\{a\}\]\|≤βE​S,\\displaystyle\\leq\\beta\_\{ES\},βE​S\\displaystyle\\beta\_\{ES\}:=2​s¯m​ln⁡2​Nδ\+43​m​ln⁡2​Nδ\.\\displaystyle:=\\sqrt\{\\frac\{2\\bar\{s\}\}\{m\}\\ln\\frac\{2N\}\{\\delta\}\}\+\\frac\{4\}\{3m\}\\ln\\frac\{2N\}\{\\delta\}\.

#### Proof\.

A rule differs from the always\-retain baseline only on assignments that it marks inconsistent, so

\|Da​\(Z\)\|\\displaystyle\|D\_\{a\}\(Z\)\|≤sa​\(Z\)≤1,\\displaystyle\\leq s\_\{a\}\(Z\)\\leq 1,Var⁡\(Da​\(Z\)\)\\displaystyle\\operatorname\{Var\}\(D\_\{a\}\(Z\)\)≤E⁡\[Da​\(Z\)2\]≤E⁡\[sa​\(Z\)\]≤s¯\.\\displaystyle\\leq\\mathrm\{E\}\[D\_\{a\}\(Z\)^\{2\}\]\\leq\\mathrm\{E\}\[s\_\{a\}\(Z\)\]\\leq\\bar\{s\}\.Thus, when candidate corrections modify only a small proportion of early assignments, their loss differences have lower variance; this is the finite\-class sparse\-correction effect captured bys¯\\bar\{s\}\. Also,\|Da​\(Z\)−E⁡\[Da\]\|≤2\|D\_\{a\}\(Z\)\-\\mathrm\{E\}\[D\_\{a\}\]\|\\leq 2\. \(The sharper bound\|Da​\(Z\)−E⁡\[Da\]\|≤sa​\(Z\)\+s¯≤1\+s¯\|D\_\{a\}\(Z\)\-\\mathrm\{E\}\[D\_\{a\}\]\|\\leq s\_\{a\}\(Z\)\+\\bar\{s\}\\leq 1\+\\bar\{s\}is available, since\|Da​\(Z\)\|≤sa​\(Z\)\|D\_\{a\}\(Z\)\|\\leq s\_\{a\}\(Z\)and\|E⁡\[Da\]\|≤s¯\|\\mathrm\{E\}\[D\_\{a\}\]\|\\leq\\bar\{s\}; we retain the simpler constant22, which only inflates the second\-order term and keeps the penalty identical to the main\-text statement\.\) To make the additive constant explicit, start from the two\-sided Bernstein inequality in exponential form\([4](https://arxiv.org/html/2608.19953#bib.bib34), Theorem 2\.10\): for a variance proxyσ2\\sigma^\{2\}and centered rangecc,

Pr⁡\(\|D^a−E⁡\[Da\]\|≥ϵ\)≤2​exp⁡\(−m​ϵ22​σ2\+2​c​ϵ/3\)\.\\Pr\\\!\\left\(\|\\widehat\{D\}\_\{a\}\-\\mathrm\{E\}\[D\_\{a\}\]\|\\geq\\epsilon\\right\)\\leq 2\\exp\\\!\\left\(\-\\frac\{m\\epsilon^\{2\}\}\{2\\sigma^\{2\}\+2c\\epsilon/3\}\\right\)\.Bounding the right\-hand side by2​e−t2e^\{\-t\}gives the quadratic conditionm​ϵ2≥2​σ2​t\+2​c​t​ϵ/3m\\epsilon^\{2\}\\geq 2\\sigma^\{2\}t\+2ct\\epsilon/3, whose positive root satisfies

ϵ=c​t3​m\+2​σ2​tm\+c2​t29​m2≤2​σ2​tm\+2​c​t3​m,\\epsilon=\\frac\{ct\}\{3m\}\+\\sqrt\{\\frac\{2\\sigma^\{2\}t\}\{m\}\+\\frac\{c^\{2\}t^\{2\}\}\{9m^\{2\}\}\}\\leq\\sqrt\{\\frac\{2\\sigma^\{2\}t\}\{m\}\}\+\\frac\{2ct\}\{3m\},where the inequality usesa\+b≤a\+b\\sqrt\{a\+b\}\\leq\\sqrt\{a\}\+\\sqrt\{b\}\. Substituting the variance proxyσ2=s¯\\sigma^\{2\}=\\bar\{s\}and the rangec=2c=2shows that the deviation2​s¯​t/m\+4​t/\(3​m\)\\sqrt\{2\\bar\{s\}t/m\}\+4t/\(3m\)is sufficient; the additive form is conservative relative to the exponential form because of this square\-root relaxation\. That is, for every fixedaaandt\>0t\>0,

Pr⁡\(\|D^a−E⁡\[Da\]\|\>2​s¯​tm\+4​t3​m\)≤2​e−t\.\\Pr\\left\(\|\\widehat\{D\}\_\{a\}\-\\mathrm\{E\}\[D\_\{a\}\]\|\>\\sqrt\{\\frac\{2\\bar\{s\}t\}\{m\}\}\+\\frac\{4t\}\{3m\}\\right\)\\leq 2e^\{\-t\}\.Settingt=ln⁡\(2​N/δ\)t=\\ln\(2N/\\delta\)and applying a union bound over𝒜\\mathcal\{A\}proves the claim\.□\\Box

#### Theorem[2](https://arxiv.org/html/2608.19953#Thmtheorem2)\(restated\)\.

Leta^\\widehat\{a\}minimize the empirical00–11risk over𝒜\\mathcal\{A\}, and writeh^E​S:=ha^\\widehat\{h\}\_\{ES\}:=h\_\{\\widehat\{a\}\}\. Leth^sol\\widehat\{h\}\_\{\\mathrm\{sol\}\}be any possibly data\-dependent direct predictor determined without access to the fresh test triple and whose test\-time decisions use only the static local inputs\. Define

εm​\(δ\):=2​2​s¯m​ln⁡2​Nδ\+83​m​ln⁡2​Nδ\.\\varepsilon\_\{m\}\(\\delta\):=2\\sqrt\{\\frac\{2\\bar\{s\}\}\{m\}\\ln\\frac\{2N\}\{\\delta\}\}\+\\frac\{8\}\{3m\}\\ln\\frac\{2N\}\{\\delta\}\.With probability at least1−δ1\-\\delta,

Acc⁡\(h^E​S\)−Acc⁡\(h^sol\)≥Δ𝒜−εm​\(δ\)=ΔB−α𝒜−εm​\(δ\)\.\\operatorname\{Acc\}\(\\widehat\{h\}\_\{ES\}\)\-\\operatorname\{Acc\}\(\\widehat\{h\}\_\{\\mathrm\{sol\}\}\)\\geq\\Delta\_\{\\mathcal\{A\}\}\-\\varepsilon\_\{m\}\(\\delta\)=\\Delta\_\{\\mathrm\{B\}\}\-\\alpha\_\{\\mathcal\{A\}\}\-\\varepsilon\_\{m\}\(\\delta\)\.On the same event,

R⁡\(h^E​S\)−mina∈𝒜⁡R⁡\(ha\)≤εm​\(δ\)\.R\(\\widehat\{h\}\_\{ES\}\)\-\\min\_\{a\\in\\mathcal\{A\}\}R\(h\_\{a\}\)\\leq\\varepsilon\_\{m\}\(\\delta\)\.

#### Proof\.

Subtracting the same empirical loss ofakeepa\_\{\\mathrm\{keep\}\}from every candidate preserves the empirical minimizer\. On the event in Lemma 2, choose

a𝒜∗∈arg​mina∈𝒜⁡R​\(ha\)\.a\_\{\\mathcal\{A\}\}^\{\*\}\\in\\operatorname\*\{arg\\,min\}\_\{a\\in\\mathcal\{A\}\}R\(h\_\{a\}\)\.Then

E⁡\[Da^\]\\displaystyle\\mathrm\{E\}\[D\_\{\\widehat\{a\}\}\]≤D^a^\+βE​S≤D^a𝒜∗\+βE​S\\displaystyle\\leq\\widehat\{D\}\_\{\\widehat\{a\}\}\+\\beta\_\{ES\}\\leq\\widehat\{D\}\_\{a\_\{\\mathcal\{A\}\}^\{\*\}\}\+\\beta\_\{ES\}≤E⁡\[Da𝒜∗\]\+2​βE​S\.\\displaystyle\\leq\\mathrm\{E\}\[D\_\{a\_\{\\mathcal\{A\}\}^\{\*\}\}\]\+2\\beta\_\{ES\}\.BecauseR⁡\(ha\)=p\+E⁡\[Da\]R\(h\_\{a\}\)=p\+\\mathrm\{E\}\[D\_\{a\}\], it follows that

R⁡\(h^E​S\)\\displaystyle R\(\\widehat\{h\}\_\{ES\}\)≤R⁡\(ha𝒜∗\)\+2​βE​S\\displaystyle\\leq R\(h\_\{a\_\{\\mathcal\{A\}\}^\{\*\}\}\)\+2\\beta\_\{ES\}\(11\)=1−A𝒜∗\+2​βE​S\\displaystyle=1\-A\_\{\\mathcal\{A\}\}^\{\*\}\+2\\beta\_\{ES\}=bG−Δ𝒜\+2​βE​S\.\\displaystyle=b\_\{G\}\-\\Delta\_\{\\mathcal\{A\}\}\+2\\beta\_\{ES\}\.Condition on the realized training sample\. Any resulting direct predictor whose test decision uses only the static local input has, by Bayes optimality,

R⁡\(h^sol\)≥bG\.R\(\\widehat\{h\}\_\{\\mathrm\{sol\}\}\)\\geq b\_\{G\}\.\(12\)Combining Eqs\. \([11](https://arxiv.org/html/2608.19953#A6.E11)\) and \([12](https://arxiv.org/html/2608.19953#A6.E12)\) gives

Acc⁡\(h^E​S\)−Acc⁡\(h^sol\)\\displaystyle\\operatorname\{Acc\}\(\\widehat\{h\}\_\{ES\}\)\-\\operatorname\{Acc\}\(\\widehat\{h\}\_\{\\mathrm\{sol\}\}\)=R⁡\(h^sol\)−R⁡\(h^E​S\)\\displaystyle=R\(\\widehat\{h\}\_\{\\mathrm\{sol\}\}\)\-R\(\\widehat\{h\}\_\{ES\}\)≥Δ𝒜−2​βE​S\.\\displaystyle\\geq\\Delta\_\{\\mathcal\{A\}\}\-2\\beta\_\{ES\}\.Sinceεm​\(δ\)=2​βE​S\\varepsilon\_\{m\}\(\\delta\)=2\\beta\_\{ES\}, the theorem follows\.□\\Box

#### A sufficient sample size\.

IfΔ𝒜\>0\\Delta\_\{\\mathcal\{A\}\}\>0and

m\>max⁡\{32​s¯​ln⁡\(2​N/δ\)Δ𝒜2,16​ln⁡\(2​N/δ\)3​Δ𝒜\},m\>\\max\\left\\\{\\frac\{32\\bar\{s\}\\ln\(2N/\\delta\)\}\{\\Delta\_\{\\mathcal\{A\}\}^\{2\}\},\\frac\{16\\ln\(2N/\\delta\)\}\{3\\Delta\_\{\\mathcal\{A\}\}\}\\right\\\},\(13\)thenεm​\(δ\)<Δ𝒜\\varepsilon\_\{m\}\(\\delta\)<\\Delta\_\{\\mathcal\{A\}\}\. Consequently, with probability at least1−δ1\-\\delta,Acc⁡\(h^E​S\)\>Acc⁡\(h^sol\)\\operatorname\{Acc\}\(\\widehat\{h\}\_\{ES\}\)\>\\operatorname\{Acc\}\(\\widehat\{h\}\_\{\\mathrm\{sol\}\}\)\.

#### Proof\.

LetΛ:=ln⁡\(2​N/δ\)\\Lambda:=\\ln\(2N/\\delta\)\. The two bounds in Eq\. \([13](https://arxiv.org/html/2608.19953#A6.E13)\) imply

2​2​s¯​Λm<Δ𝒜2,8​Λ3​m<Δ𝒜2\.2\\sqrt\{\\frac\{2\\bar\{s\}\\Lambda\}\{m\}\}<\\frac\{\\Delta\_\{\\mathcal\{A\}\}\}\{2\},\\qquad\\frac\{8\\Lambda\}\{3m\}<\\frac\{\\Delta\_\{\\mathcal\{A\}\}\}\{2\}\.Adding the inequalities givesεm​\(δ\)<Δ𝒜\\varepsilon\_\{m\}\(\\delta\)<\\Delta\_\{\\mathcal\{A\}\}; Theorem[2](https://arxiv.org/html/2608.19953#Thmtheorem2)then yields the claim\.□\\Box

### Illustrative Calculations

#### Population gain\.

The sparse\-correction condition can hold even when the early solution itself is less accurate than direct prediction\. For example, take

p=0\.21,Asol∗=0\.82,ρ=0\.12,q=0\.70\.p=0\.21,\\qquad A\_\{\\mathrm\{sol\}\}^\{\*\}=0\.82,\\qquad\\rho=0\.12,\\qquad q=0\.70\.These numerical values are purely illustrative\. The right\-hand side of Eq\. \([9](https://arxiv.org/html/2608.19953#A6.E9)\) is

1−Asol∗\+ρ⁡\(2​q−1\)=0\.18\+0\.12​\(0\.40\)=0\.228\.1\-A\_\{\\mathrm\{sol\}\}^\{\*\}\+\\rho\(2q\-1\)=0\.18\+0\.12\(0\.40\)=0\.228\.Thusp=0\.21<0\.228p=0\.21<0\.228\. The early solution alone has accuracy0\.790\.79, which is below the direct\-prediction accuracy0\.820\.82, whereas identifying the inconsistent assignments gives

Acon∗=1−\[0\.21−0\.12​\(0\.40\)\]=0\.838\.A\_\{\\mathrm\{con\}\}^\{\*\}=1\-\\left\[0\.21\-0\.12\(0\.40\)\\right\]=0\.838\.The early\-solution input therefore raises the accuracy from0\.820\.82to0\.8380\.838, an improvement of1\.81\.8percentage points\.

#### Finite\-sample bound\.

For a numerical evaluation of the bound, consider a fixed class ofN=4N=4correction rules constructed to satisfyE⁡\[sa\]≤0\.0180\\mathrm\{E\}\[s\_\{a\}\]\\leq 0\.0180\. The values¯=0\.0180\\bar\{s\}=0\.0180uses the1\.80%1\.80\\%median WA early\-to\-final difference in Figure[2](https://arxiv.org/html/2608.19953#S3.F2)as an illustrative correction\-budget scale, withE⁡\[sa\]≤s¯\\mathrm\{E\}\[s\_\{a\}\]\\leq\\bar\{s\}retained as the stated rule\-class assumption\. Set the confidence level to1−δ=0\.91\-\\delta=0\.9and take a deliberately conservative illustrative class advantageΔ𝒜=0\.12\\Delta\_\{\\mathcal\{A\}\}=0\.12\. Here

ln⁡2​Nδ=ln⁡80≈4\.382\.\\ln\\frac\{2N\}\{\\delta\}=\\ln 80\\approx 4\.382\.The two terms on the right\-hand side of Eq\. \([13](https://arxiv.org/html/2608.19953#A6.E13)\) are

32​s¯​ln⁡\(2​N/δ\)Δ𝒜2\\displaystyle\\frac\{32\\bar\{s\}\\ln\(2N/\\delta\)\}\{\\Delta\_\{\\mathcal\{A\}\}^\{2\}\}≈175\.3,\\displaystyle\\approx 175\.3,16​ln⁡\(2​N/δ\)3​Δ𝒜\\displaystyle\\frac\{16\\ln\(2N/\\delta\)\}\{3\\Delta\_\{\\mathcal\{A\}\}\}≈194\.8\.\\displaystyle\\approx 194\.8\.Thus the convenient sufficient condition in Eq\. \([13](https://arxiv.org/html/2608.19953#A6.E13)\) would requirem=195m=195\. It is conservative because it separately bounds each of the two terms inεm\\varepsilon\_\{m\}byΔ𝒜/2\\Delta\_\{\\mathcal\{A\}\}/2\. Directly solvingεm​\(0\.1\)<0\.12\\varepsilon\_\{m\}\(0\.1\)<0\.12, namely

2​2​\(0\.0180\)m​ln⁡80\+83​m​ln⁡80<0\.12,\\displaystyle 2\\sqrt\{\\frac\{2\(0\.0180\)\}\{m\}\\ln 80\}\+\\frac\{8\}\{3m\}\\ln 80<0\.12,givesm\>188\.19m\>188\.19, so the smallest integer sample size satisfying the exact inequality ism=189m=189\.

#### Consistency requirement on the parameters\.

The illustrative values above are not jointly free\. A rule that flips a proportionsa​\(Z\)s\_\{a\}\(Z\)of assignments changes the induced assignment on at most that fraction of variables, so its accuracy exceeds the always\-retain accuracy by at most the expected flip rate:Acc⁡\(ha\)≤\(1−p\)\+E⁡\[sa\]≤\(1−p\)\+s¯\\operatorname\{Acc\}\(h\_\{a\}\)\\leq\(1\-p\)\+\\mathrm\{E\}\[s\_\{a\}\]\\leq\(1\-p\)\+\\bar\{s\}\. Consequently,

Δ𝒜=A𝒜∗−Asol∗≤bG−p\+s¯,\\Delta\_\{\\mathcal\{A\}\}=A\_\{\\mathcal\{A\}\}^\{\*\}\-A\_\{\\mathrm\{sol\}\}^\{\*\}\\leq b\_\{G\}\-p\+\\bar\{s\},and the choices¯=0\.0180\\bar\{s\}=0\.0180,Δ𝒜=0\.12\\Delta\_\{\\mathcal\{A\}\}=0\.12implicitly requiresbG−p≥0\.102b\_\{G\}\-p\\geq 0\.102: the Bayes error of static local prediction must exceed the early\-solution error rate by roughly ten percentage points or more\. On WA, where the1\.80%1\.80\\%median early\-to\-final difference suggestsp≈0\.018p\\approx 0\.018, this amounts tobG≳0\.12b\_\{G\}\\gtrsim 0\.12; that is, even the best predictor using only the static local input must mislabel at least about12%12\\%of the binary variables\. This is a substantive assumption about the difficulty of static prediction on the benchmark, not a consequence of the theorems, and we state it so that the example is read as a self\-consistent operating point rather than a measured one\. Smaller, still positive class advantages remain valid and simply rescale the sufficient sample size, which grows likeΔ𝒜−2\\Delta\_\{\\mathcal\{A\}\}^\{\-2\}in Eq\. \([13](https://arxiv.org/html/2608.19953#A6.E13)\)\.

Each MILP instance is one independent observation, so labels within an instance may be arbitrarily dependent\. Accordingly, the penalty depends onmm, the number of instances, rather than the total number of variable labels\. The result assumes a fixed finite rule class selected by empirical variable\-level00–11prediction loss\. Its formal scope is finite\-rule model selection, providing an abstraction that isolates instance\-level estimation and the sparse\-correction variance effect\. In practice the predictor is a GNN trained by stochastic optimization with validation\-based checkpoint selection, a procedure better described as comparing a small, data\-dependent set of candidates—the checkpoints and configurations actually evaluated—than as exact empirical risk minimization over a class fixed in advance\. Theorem[2](https://arxiv.org/html/2608.19953#Thmtheorem2)should therefore be read as an idealized account of that selection stage: it isolates the instance\-level estimation cost and explains why sparse correction classes are cheap to select among, but it is not a uniform\-convergence guarantee for the full GNN function class\. Statements in the main text about the gain persisting under finite\-sample model selection refer to this abstraction layer\.

#### Relation to the deployed algorithm\.

Two design choices of the deployed system fall outside the formal statements above and are worth flagging explicitly\. First, the analysis scores rules by variable\-level00–11accuracy—equivalently, thresholding the posterior at1/21/2over*all*binary variables—whereas the deployed method ranks variables by the predicted consistency probability and fixes only the top\-ranked ones under a budget chosen by the downstream method\. The theorems thus quantify the information available in the scores; how the scores are consumed by a ranking\-based fixing rule is evaluated empirically\. Second, the posteriors in this appendix condition on a single early solution, whereas at inference time the system averages, per variable, the logits computed from the lastKKimproving solutions after aligning them to the reference solutionXE​SX^\{ES\}\. Because conditioning on the tuple of the lastKKsolutions only enlarges the input, Theorem[1](https://arxiv.org/html/2608.19953#Thmtheorem1)applies verbatim to the ensembled variant, while the specific alignment\-and\-averaging estimator is a practical variance\-reduction heuristic whose effect is evaluated empirically\.