Learning to Guide Local Search for MPE Inference in Probabilistic Graphical Models Brij Malhotra, Shivvrat Arya, Tahrima Rahman, Vibhav Gogate Abstract Most Probable Explanation (MPE) inference in Probabilistic Graphical Models (PGMs) is a fundamental yet computationally challenging problem arising in domains such as diagnosis, planning, and structured prediction. In many practical settings, the graphical model remains fixed while inference must be performed repeatedly for varying evidence patterns. Stochastic Local Search (SLS) algorithms scale to large models but rely on myopic best-improvement rule that prioritizes immediate likelihood gains and often stagnate in poor local optima. Heuristics such as Guided Local Search (GLS+) partially alleviate this limitation by modifying the search landscape, but their guidance cannot be reused effectively across multiple inference queries on the same model. We propose a neural amortization framework for improving local search in this repeated-query regime. Exploiting the fixed graph structure, we train an attention-based network to score local moves by predicting their ability to reduce Hamming distance to a near-optimal solution. Our approach integrates seamlessly with existing local search procedures, using this signal to balance short-term likelihood gains with long-term promise during neighbor selection. We provide theoretical intuition linking distance-reducing move selection to improved convergence behavior, and empirically demonstrate consistent improvements over SLS and GLS+ on challenging high-treewidth benchmarks in the amortized inference setting. 1 Introduction Probabilistic Graphical Models (PGMs) [ 24 ] efficiently encode joint probability distributions over a large set of random variables, enabling structured reasoning under uncertainty. A fundamental inference task in these models is the Most Probable Explanation (MPE) query, where the goal is to find the most likely assignment of values to unobserved variables given observed evidence. Despite its importance in domains such as diagnosis, vision, and planning, MPE inference is NP-hard and becomes increasingly intractable as models grow in size, density, and treewidth. This scalability barrier continues to limit the applicability of PGMs in large-scale and real-world settings. A broad range of algorithmic paradigms have been developed to address MPE inference. Exact methods, including variable elimination [ 14 ] and AND/OR Branch-and-Bound (AOBB) [ 27 ] , exploit problem structure to guarantee optimality. However, their time and memory requirements scale exponentially with the model’s induced width, rendering them impractical for large or densely connected graphs. Although AOBB operates in an anytime fashion, its performance deteriorates as bounding quality and caching effectiveness degrade with increasing complexity. As a result, practitioners often turn to approximate inference techniques when exact solvers fail to return solutions within feasible resource budgets. Stochastic local search (SLS) methods offer a compelling alternative for large-scale MPE inference. These methods require minimal memory, improve solutions incrementally, and parallelize naturally, making them well suited for larger graphical models. More broadly, local search has achieved strong empirical performance across large combinatorial optimization problems, including the Traveling Salesman Problem, Weighted MaxSAT, and Vehicle Routing [ 20 ] . A typical local search algorithm alternates between intensification , which exploits the local neighborhood of the current solution, and diversification , which promotes exploration to escape local optima. Intensification strategies include best-improvement, first-improvement, and steepest descent [ 2 ] , while diversification is implemented through mechanisms such as controlled randomness, adaptive memory, or neighborhood perturbations schemes based on metaheuristics including Simulated Annealing [ 36 ] , Tabu Search [ 17 ] , Guided Local Search (GLS) [ 41 ] , Variable Neighborhood Search [ 7 ] , and Large Neighborhood Search [ 38 ] . Achieving an effective balance between the two operations is essential for robust performance. In the context of MPE inference, the best-improvement heuristic is a standard intensification strategy for SLS. At each step, it selects the neighboring assignment that maximally increases log-likelihood. While effective in the immediate neighborhood, this heuristic is inherently myopic and frequently becomes trapped in poor local optima, especially in high-dimensional models with high treewidth [ 22 ] . Penalty-based extensions such as GLS [ 34 , 21 ] attempt to mitigate this issue by discouraging revisits to previously explored states. However, these penalties are non-persistent and query-specific, preventing the reuse of accumulated structural knowledge across multiple MPE queries on the same fixed graphical model. This exposes a fundamental limitation of existing GLS approaches: they lack a mechanism to amortize long-horizon experience. To address both the short-sightedness of SLS and the non-transferability of GLS-style penalties, we introduce an amortized lookahead strategy for neighbor selection [ 29 ] . In the idealized setting where the optimal solution is known, the best intensification move from any state is one that reduces the Hamming distance of a state to the known optimal solution, as such moves reach the optimum in the minimum number of steps. However, this oracle information is unavailable at inference time, since the optimal assignment is precisely the quantity being sought. Our key observation is that this guidance can be approximated from solved instances. We therefore learn a neural model from (near-)optimal solutions that predicts which local moves are likely to reduce Hamming distance, enabling amortized inference that guides search toward globally promising regions across queries. Concretely, we first obtain near-optimal solutions for a small set of training queries using an anytime MPE solver [ 28 ] . We then train an attention-based neural network to score candidate neighbors of a given assignment by estimating their likelihood of reducing Hamming distance to a high-quality solution. At inference time, these learned scores are combined with the standard best-improvement heuristic, enabling the search to balance immediate likelihood gains against long-term progress. This integration yields a reusable, amortized lookahead mechanism for local search [ 37 ] . By distilling long-horizon search behavior into a learned policy, our approach improves exploration while sharing guidance across all future MPE queries on the same graphical model. Contributions. This paper makes the following contributions: • We introduce an amortized lookahead framework that formulates neighbor selection in local search for MPE inference as a supervised learning problem, explicitly balancing short-term likelihood improvement with long-term convergence. • We propose a principled data generation strategy that leverages anytime MPE solvers and Hamming distance–based supervision to label neighboring assignments by their likelihood of reducing distance to a near-optimal solution. • We demonstrate that augmenting SLS and GLS+ with our learned lookahead strategy consistently improves solution quality and efficiency on large and challenging graphical models. 2 Background Notation: We denote random variables by uppercase letters (e.g., X ), and their assignments by corresponding lowercase letters (e.g., x ). Bold uppercase letters (e.g., \mathbf{X} ) denote sets of variables, while bold lowercase letters (e.g., \mathbf{x} ) denote corresponding value assignments. Given a full assignment \mathbf{x} to \mathbf{X} and a subset \mathbf{Y}\subseteq\mathbf{X} , we denote by \mathbf{x}_{\mathbf{Y}} the projection of \mathbf{x} onto \mathbf{Y} . A probabilistic graphical model (PGM) is a triple \mathcal{M}=\langle\mathbf{X},\mathbf{F},G\rangle , where (1) \mathbf{X}=\{X_{1},\dots,X_{n}\} is a set of discrete random variables; (2) each X_{i} takes values from a finite domain D_{X_{i}} ; (3) \mathbf{F}=\{f_{1},\dots,f_{m}\} is a collection of log-potential functions such that each f_{i} is defined over a subset \mathbf{S}(f_{i})\subseteq\mathbf{X} (its scope ); and (4) G=(\mathcal{V},\mathcal{E}) is the undirected primal graph with \mathcal{V}=\mathbf{X} and an edge (X_{a},X_{b})\in\mathcal{E} whenever X_{a} and X_{b} co-occur in the scope of some f_{i}\in\mathbf{F} . The model induces the joint distribution P_{\mathcal{M}}(\mathbf{x})\propto\exp\!\left(\sum_{f\in\mathbf{F}}f(\mathbf{x}_{\mathbf{S}(f)})\right). We focus on the most probable explanation (MPE) task: given observed evidence variables \mathbf{E}\subset\mathbf{X} with assignment \mathbf{e} , find the most likely assignment to the query variables \mathbf{Q}=\mathbf{X}\setminus\mathbf{E} . Formally, \displaystyle\text{MPE}(\mathbf{Q},\mathbf{e}) \displaystyle=\arg\max_{\mathbf{q}}\;\text{ln}\Big(P_{\mathcal{M}}(\mathbf{q}\mid\mathbf{e})\Big) \displaystyle=\arg\max_{\mathbf{q}}\sum_{f\in\mathbf{F}}f\big((\mathbf{q},\mathbf{e})_{\mathbf{S}(f)}\big) (1) This problem is NP-hard in general and remains intractable for many expressive model classes [ 10 , 11 , 12 , 9 ] . Exact algorithms for MPE include bucket elimination [ 14 ] , which performs variable elimination via local reparameterization; AND/OR Branch-and-Bound framework [ 27 ] , a search-based approach that exploits graphical structure through AND/OR search spaces and soft arc consistency methods, implemented in solvers such as DAOOPT [ 32 ] & Toulbar2 [ 16 ] respectively that operate in an anytime manner, progressively refining feasible solutions and bounds and providing certificates of optimality upon termination. In contrast, local search methods operate over complete assignments through iterative refinement. Given a current assignment \mathbf{x} , candidate updates are generated by exploring its neighborhood . We focus on the standard 1-flip neighborhood , defined as \mathcal{N}(\mathbf{x})=\{\mathbf{x}^{\prime}:\mathbf{x}^{\prime}\text{ differs from }\mathbf{x}\text{ in exactly one query variable }Q_{i}\in\mathbf{Q}\} , where the selected variable Q_{i} is reassigned to a different value in its domain. A variety of local search strategies have been proposed for MPE inference. Penalty-based metaheuristics, such as Guided Local Search (GLS) [ 34 ] and its enhanced variant GLS+ [ 21 ] , combine greedy or stochastic best-improvement moves with adaptive penalties to escape local optima. Structure-aware heuristics further exploit graphical topology: Subtree-Tree Local Search (STLS) [ 31 ] searches over cutset variables while solving the remaining tree-structured subproblem exactly, while more recently a variable neighborhood search framework guided by tree decompositions that progressively expands neighborhood complexity to improve solution quality was proposed [ 33 ] . Heuristics are central to the effectiveness of local search methods in combinatorial optimization, where large and structured search spaces make exhaustive exploration infeasible. Across a wide range of satisfaction and optimization problems, carefully designed neighbor-selection strategies play a crucial role in balancing greedy improvement with exploration of promising regions, directly influencing convergence speed and solution quality [ 43 , 25 , 6 , 8 ] . Recently, learning-based approaches have emerged as a powerful mechanism for augmenting local search heuristics by amortizing guidance from past search trajectories to inform and improve future optimization decisions. Prior work has explored neural and adaptive strategies for this purpose, including regret-based penalties for local search in the traveling salesperson problem [ 40 ] , learned neighborhood selection policies within Large Neighborhood Search frameworks for MaxSAT [ 19 ] , and bandit-based methods that adaptively select constraints when search stalls [ 44 ] . Together, these works show a growing trend of learning to amortize search, improving convergence and solution quality. The challenges addressed by these approaches closely parallel those encountered in MPE inference for PGMs, where high-dimensional structured spaces and complex dependencies give rise to numerous poor local optima. As in other combinatorial settings, effective MPE inference relies critically on neighbor-selection heuristics that balance immediate objective improvement with exploration of promising long-term trajectories. Motivated by this connection, we propose a neural lookahead framework that evaluates candidate moves not only by their instantaneous likelihood gain but also by their estimated long-term potential, addressing a core limitation of greedy local search strategies. 3 Learning to Guide Local Search A widely used greedy approach in local search is the best-improvement heuristic, which selects the neighbor \mathbf{x}^{\prime}\in\mathcal{N}(\mathbf{x}) of \mathbf{x} that maximizes the immediate gain in the objective. More formally, given \mathbf{x} , define the log-potential function F as F(\mathbf{x})=\sum_{f\in F}f(\mathbf{x}_{S(f)}), and the log-likelihood gain of moving to a neighbor \mathbf{x}^{\prime} as \mathcal{S}_{\mathrm{LL}}(\mathbf{x}^{\prime}\mid\mathbf{x})=F(\mathbf{x}^{\prime})-F(\mathbf{x}). The best-improvement heuristic selects a neighbor \mathbf{x}^{\prime}\in\mathcal{N}(\mathbf{x}) that maximizes \mathcal{S}_{\mathrm{LL}}(\mathbf{x}^{\prime}\mid\mathbf{x}) . This rule is attractive because \mathcal{S}_{\mathrm{LL}} is exact and always available at test time. However, it is inherently myopic: repeated greedy updates often trap the search in poor local optima and prevent exploration of more promising regions. A distance-based view of progress. To reason about sustained progress, it is useful to temporarily separate objective improvement from trajectory quality and ask a simpler question: does the search move toward an optimal MPE solution? Let \mathbf{x}^{\ast} denote an optimal MPE assignment. To measure the distance between two assignments \mathbf{x} and \mathbf{z} , we use the Hamming distance d_{H}(\mathbf{x},\mathbf{z}) , defined as the number of query variables Q_{i}\in\mathbf{Q} on which they assign different values (the evidence variables are fixed and therefore identical in both assignments). Suppose we had access to an oracle that outputs d_{H}(\mathbf{x},\mathbf{x}^{\ast}) . Then, given a starting assignment \mathbf{x} , a 1-flip local search could always select a neighbor \mathbf{x}^{\prime}\in\mathcal{N}(\mathbf{x}) that decreases the distance by 1, converging in exactly d_{H}(\mathbf{x},\mathbf{x}^{\ast}) steps, which is optimal. However, strict optimality is not required for convergence. As we show in the following theorem, even a noisy oracle which selects a distance-reducing move with probability \alpha>0.5 ensures that the search converges in bounded expected time: Theorem 1 (Convergence) . Let \{\mathbf{x}_{t}\}_{t\geq 0} be the sequence of assignments generated by 1-flip local search, with \mathbf{x}_{t} denoting the state at step t . Assume the process is absorbing at the target assignment, i.e., if \mathbf{x}_{t}=\mathbf{x}^{\ast} then \mathbf{x}_{t+1}=\mathbf{x}^{\ast} . Define h_{t}:=d_{H}(\mathbf{x}_{t},\mathbf{x}^{\ast}) as the Hamming distance to \mathbf{x}^{\ast} , and let \tau^{\ast}:=\inf\{t\geq 0:h_{t}=0\} be the hitting time of \mathbf{x}^{\ast} . If at every non-terminal state the executed move reduces h_{t} with probability \alpha>1/2 , then \mathbb{E}[h_{t+1}\mid\mathbf{x}_{t}]\leq h_{t}-(2\alpha-1),\quad\text{and}\quad\mathbb{E}[\tau^{\ast}]\leq\tfrac{h_{0}}{2\alpha-1}. Theorem 1 states that for reliable progress, the search must select a distance-reducing move more often than not ( \alpha>0.5 ). Since our method selects the neighbor with the highest predicted score, \alpha is a top-1 ranking statistic representing the probability that the selected move reduces the Hamming distance. Defining the set of distance-reducing neighbors as \mathcal{N}_{\downarrow}(\mathbf{x}):=\{\mathbf{z}\in\mathcal{N}(\mathbf{x}):d_{H}(\mathbf{z},\mathbf{x}^{\ast})=d_{H}(\mathbf{x},\mathbf{x}^{\ast})-1\} , we formalize \alpha as: \alpha=\Pr\!\left[\mathbf{x}_{t+1}\in\mathcal{N}_{\downarrow}(\mathbf{x}_{t})\mid d_{H}(\mathbf{x}_{t},\mathbf{x}^{\ast})>0\right] Thus, strict score calibration is unnecessary; the learned policy need only rank distance-reducing moves above non-reducing ones often enough to ensure \alpha>1/2 along the trajectory. Learning a surrogate oracle. In practice, since the optimal assignment \mathbf{x}^{\ast} is typically unavailable, we supervise the model using a reference assignment \hat{\mathbf{x}} produced by an anytime solver. We label a neighbor \mathbf{x}^{\prime}\in\mathcal{N}(\mathbf{x}) as positive ( y=1 ) if it reduces the Hamming distance to \hat{\mathbf{x}} (i.e., d_{H}(\mathbf{x}^{\prime},\hat{\mathbf{x}}) 50 points), red indicates lower performance, and darker shades represent larger differences. Across most graphical models, augmenting local search with BEACON consistently improves performance, as reflected by the predominantly green regions in both heatmaps. The gains are strongest early in the search, where neural-guided neighbor selection helps escape poor initial assignments and accelerates convergence. Although baseline methods narrow the gap with more steps, BEACON -enhanced variants typically retain an advantage even at 4,000 steps, indicating sustained effectiveness of the learned guidance. For BEACON-Greedy (left panel of Figure 2 ), the improvements are often substantial, with dark green regions dominating across most models with only minor regressions on some WCSP instances (dark red). BEACON-GLS+ (right panel) delivers more uniform gains by overcoming the lack of amortization in standard GLS+, which must relearn penalties for each query. By transferring learned structural knowledge across queries, BEACON reaches high-quality solutions earlier much faster which is most pronounced on large WCSP and RUS benchmarks where dark green regions persist. Overall, these results demonstrate that BEACON both enhances greedy local search by escaping local optima and highlights the benefits of amortized, transferable guidance across queries. Table 1 : Percentage improvement of BEACON-Greedy over Greedy at different step budgets. Steps 500 1000 2000 4000 BN-30 52.47 53.62 54.98 55.41 BN-32 69.64 65.51 66.90 67.61 BN-45 62.50 67.15 69.10 70.43 BN-61 57.98 64.96 68.35 70.80 BN-65 75.45 76.58 77.06 77.41 Prm-60 77.93 79.91 83.69 84.71 Prm-62 81.45 84.13 85.72 86.09 Orc-100 41.71 41.30 41.94 41.91 Grid20 11.45 10.07 9.17 8.48 Grid40-1 3.57 5.81 6.10 6.09 Grid40-2 4.05 7.36 7.86 7.68 Grid80 -1.02 0.01 5.60 6.06 Pdg-18 16.50 16.86 17.70 16.40 Pdg-30 -0.88 4.03 3.70 3.80 DL-5 1.30 9.26 9.47 7.74 1405 -1.81 -1.92 -1.97 -1.92 1407 -0.39 -0.40 -0.39 -0.38 Le450-2 1.17 0.60 0.39 0.25 Le450-3 7.25 5.02 3.89 3.15 Le450-4 25.19 20.58 16.90 13.98 Rus20-1 7.24 3.30 2.06 1.43 Rus50-1 7.60 4.16 2.83 1.67 Rus50-2 6.46 3.54 2.30 1.55 Rus100-1 6.83 3.30 1.93 0.93 Rus100-2 6.35 2.88 1.56 0.84 Table 2 : Percentage improvement of BEACON-GLS+ over GLS+ at different step budgets. Steps 500 1000 2000 4000 BN-30 49.42 36.56 19.29 8.21 BN-32 46.23 30.28 13.36 5.52 BN-45 42.62 29.19 17.55 8.55 BN-61 26.74 15.11 7.26 1.46 BN-65 20.19 4.78 -0.36 -0.52 Prm-60 82.00 33.07 -2.06 -1.22 Prm-62 45.55 -0.42 0.35 1.58 Orc-100 35.99 8.48 -1.55 -0.90 Grid20 5.20 2.21 0.93 0.40 Grid40-1 3.28 4.38 3.07 2.14 Grid40-2 3.69 5.78 4.00 2.42 Grid80 -1.02 0.01 5.24 3.75 Pdg-18 9.70 4.79 2.53 0.52 Pdg-30 0.92 0.48 -0.38 -2.04 DL-5 4.97 -5.14 -3.19 -2.52 1405 0.94 0.38 0.00 -0.12 1407 0.09 0.03 -0.03 -0.01 Le450-2 0.74 0.65 0.32 0.11 Le450-3 4.00 2.82 0.85 0.74 Le450-4 15.09 5.08 2.02 1.04 Rus20-1 6.67 4.23 2.39 1.67 Rus50-1 7.48 4.36 2.80 1.90 Rus50-2 6.43 3.89 2.51 1.78 Rus100-1 6.82 2.00 1.41 1.17 Rus100-2 6.35 1.47 1.00 0.95 Percentage Increase in the Log-Likelihood. Tables 1 and 2 report the percentage improvement in log-likelihood achieved by BEACON-Greedy and BEACON-GLS+ relative to their respective baselines. We compute this metric as \frac{1}{N}\sum_{i=1}^{N}\frac{\mathcal{LL}_{D}^{(i)}-\mathcal{LL}_{S}^{(i)}}{|\mathcal{LL}_{S}^{(i)}|}\times 100 , where \mathcal{LL}_{S}^{(i)} and \mathcal{LL}_{D}^{(i)} denote the baseline and BEACON -enhanced log-likelihood for instance i , respectively. Each row in both tables corresponds to a graphical model, identified in the first column, followed by four entries reporting results for step budgets of 500, 1000, 2000, and 4000. Positive values indicate that the BEACON -augmented method attains higher log-likelihood than its baseline, while negative values indicate degradation. Larger magnitudes correspond to greater relative changes. Because log-likelihood scales vary across models due to differences in partition functions, values are not comparable across rows. Table 1 shows that BEACON-Greedy achieves substantial improvements over the Greedy baseline, typically remaining positive as search progresses. This confirms that neural guidance effectively mitigates premature convergence to poor local optima, yielding faster progress and higher-quality solutions. Table 2 demonstrates moderate but consistent gains for BEACON-GLS+ , particularly in early search stages. By leveraging amortization to transfer offline-learned structural knowledge, BEACON accelerates convergence and improves final solution quality. This advantage remains robust even as the step budget increases, particularly on challenging WCSP and RUS benchmarks where BEACON-GLS+ maintains a clear performance lead. Summary. Experiments on 25 high-treewidth probabilistic graphical models show that augmenting local search with BEACON consistently improves performance. When integrated into Greedy and GLS+ , BEACON -enhanced methods reach higher-quality solutions in significantly fewer steps, whereas baseline methods require substantially more iterations to attain comparable log-likelihoods. The advantage is most pronounced early in the search, where neural guidance enables rapid escape from poor initial regions and faster convergence to high-quality assignments. These results demonstrate that attention-based neighbor selection accelerates convergence and often yields superior solutions compared with conventional best-improvement local search. We also provide a comparison of BEACON against state-of-the-art non–local-search solvers, including DAOOPT [ 32 ] and TOULBAR2 [ 16 ] , in Appendix E . 5 Conclusion We propose a neural-guided lookahead strategy for neighbor selection in local search for MPE inference in probabilistic graphical models. By augmenting best-improvement with an optimality-aware neural scoring function, the method guides search toward higher log-likelihood regions and reduces premature convergence to poor local optima. The learned guidance captures transferable structural information from (near-)optimal assignments, enabling more efficient test-time search. As a result, high-quality solutions are reached significantly faster than with methods such as GLS+, which must relearn heuristics for each query. Experiments on high-treewidth PGMs demonstrate consistent performance gains across diverse models, highlighting learned guidance as an effective drop-in enhancement to classical local search. Limitations and Future Work. Our approach entails several natural trade-offs. As with most learned components, performance can be sensitive to distributional shifts and the choice of the hyperparameter \lambda , although we find the method to be stable across a wide range of settings in practice. Training relies on supervision from approximate solvers, which may introduce some bias but enables scalability to problem instances where exact MPE solutions are unavailable. The current one-step Hamming-based guidance focuses on local improvements and may miss longer-horizon gains. Additionally, scoring all neighbors with a neural model can add nontrivial computational overhead in models with large variable domains. Finally, unlike exact inference methods, convergence guarantees depend on predictor accuracy. These considerations point to several promising directions for future work, including richer and less biased supervision sources, multi-step lookahead architectures, adaptive weighting mechanisms, and extensions to broader classes of discrete optimization problems. Appendix A Proofs of the Theoretical Results A.1 Proof of Theorem 1 : (Convergence) Proof. Let \{x_{t}\}_{t\geq 0} denote the sequence of assignments produced by one–flip local search, and let h_{t}=d_{H}(x_{t},x^{\ast}) be the Hamming distance to the optimal assignment x^{\ast} . At each non–optimal state, by assumption, the executed move reduces the distance by one with probability \alpha and increases it by one with probability (1-\alpha) . Thus the conditional expectation satisfies \mathbb{E}[h_{t+1}\mid h_{t}]=h_{t}-(2\alpha-1). Taking total expectation on both sides and unrolling this recurrence yields \mathbb{E}[h_{t}]=\mathbb{E}[h_{t-1}]-(2\alpha-1)=h_{0}-t(2\alpha-1), valid as long as the process has not yet been absorbed at h_{t}=0 . Hence the expected distance decreases linearly with t at rate (2\alpha-1) per step. Now define the stopping time \tau^{\ast}:=\inf\{t\geq 0:h_{t}=0\}, which represents the first time the process reaches the optimum. Because h_{t} is non–negative and decreases in expectation by a fixed amount at each step (Equation 3), the process has a strictly positive drift toward zero. Intuitively, each step removes on average (2\alpha-1) units of distance, and the total distance to remove is h_{0} . Taking expectations and applying the law of total expectation gives \mathbb{E}[h_{\tau^{\ast}}]=\mathbb{E}\!\left[h_{0}-(2\alpha-1)\tau^{\ast}\right]=0, since h_{\tau^{\ast}}=0 at absorption. Rearranging yields (2\alpha-1)\,\mathbb{E}[\tau^{\ast}]=h_{0}. Because the decrease per step is an expectation (not deterministic), this identity gives an upper bound on the true expected hitting time: \mathbb{E}[\tau^{\ast}]\leq\frac{h_{0}}{2\alpha-1}. High–probability behavior. Since h_{t} changes by at most one per step and exhibits a positive drift of (2\alpha-1) toward zero when \alpha>\tfrac{1}{2} , standard concentration results for drift processes with bounded increments (e.g., Azuma–Hoeffding or additive drift tail bounds) imply that the hitting time \tau^{\dagger} concentrates around its expectation and has an exponentially decaying tail above \mathbb{E}[\tau^{\dagger}] . For clarity, we focus on the expected hitting-time guarantee in Theorem 1 and omit an explicit tail expression. ∎ A.2 Data Generation for Neighbor Scoring Our goal in this section is to describe a concrete pipeline for constructing supervised training data for neighbor scoring . The final learning problem is the following: given a current assignment \mathbf{x} (consistent with evidence) and a 1-flip neighbor \mathbf{x}^{\prime}\in\mathcal{N}(\mathbf{x}) , we want a model to score \mathbf{x}^{\prime} so that, within the neighborhood \mathcal{N}(\mathbf{x}) , moves that are distance-reducing (with respect to a high-quality target assignment) are ranked above moves that are not. MPE queries and notation. Let \mathcal{M} be a probabilistic graphical model over variables \mathbf{X} with factors \mathbf{F} and evidence \mathbf{e} . For a query set \mathbf{Q}\subset\mathbf{X} , let \mathbf{E}=\mathbf{X}\setminus\mathbf{Q} denote the evidence variables. Evidence variables are fixed to \mathbf{e} , and local search only modifies the query variables. We write \mathbf{x} for a complete assignment to \mathbf{X} that is consistent with evidence (i.e., \mathbf{x}_{\mathbf{E}}=\mathbf{e} ), and we write \mathbf{x}_{\mathbf{Q}} for its restriction to the query variables. To measure progress toward a target assignment on the query variables, we use Hamming distance restricted to \mathbf{Q} : d_{H}(\mathbf{x},\mathbf{y})\;=\;\left|\left\{Q_{i}\in\mathbf{Q}\;:\;x_{Q_{i}}\neq y_{Q_{i}}\right\}\right|. Because \mathbf{E} is fixed, any neighbor move changes exactly one query variable and therefore changes d_{H}(\cdot,\cdot) by exactly 1 . Reference assignments for supervision. In principle, one may define supervision with respect to the optimal MPE solution \mathbf{x}^{\ast} . In practice, however, computing \mathbf{x}^{\ast} is infeasible for large, high-treewidth models. Instead, for each training query we compute a high-quality reference assignment \hat{\mathbf{x}} using an anytime MPE solver with a fixed computational budget. This reference solution provides a stable surrogate target that induces a well-defined notion of distance-reducing moves. Formally, for a state \mathbf{x} and a neighbor \mathbf{x}^{\prime}\in\mathcal{N}(\mathbf{x}) , we define the binary supervision signal y(\mathbf{x},\mathbf{x}^{\prime})\;=\;\mathbb{I}\!\left[d_{H}(\mathbf{x}^{\prime},\hat{\mathbf{x}})