acceptodds
Under review as a conference paper at ICLR 2027

Learning to Sample from Power Distributions for Amortized MPE Inference in Probabilistic Graphical Models

Abstract

We propose a neural sampling approach for repeated most probable explanation (MPE) inference on a fixed probabilistic graphical model (PGM). Our approach learns to sample from the power family \(P_\beta(q\mide) \propto P(q\mide)^\beta\), where increasing \(\beta\) concentrates probability on high-probability configurations and progressively biases sampling toward MPE solutions. We instantiate this formulation with a factor-reading neural sampler that directly uses the PGM's potentials to generate assignments conditioned on the observed evidence. The sampler is amortized across evidence queries and trained with a reverse-KL objective and a curriculum that progressively increases \(\beta\), requiring neither labeled MPE solutions nor computation of normalizing constants. At inference time, we draw samples from the learned proposal and return the highest-scoring assignment, with optional query-specific test-time refinement using the same objective to further improve solution quality. Across nine PGMs, a single sample per query achieves higher mean solution quality than the evaluated neural MPE baselines. With query-specific refinement, our method also outperforms the evaluated branch-and-bound solvers on six benchmark PGMs under matched wall-clock budgets. Beyond direct MPE inference, we analyze how the power parameter \(\beta\) affects distributional fidelity and MPE solution quality, and show that the learned proposals can improve existing inference procedures by warm-starting annealed sequential Monte Carlo and guiding branch-and-bound search.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Variational Inference, Most Probable Explanation, Probabilistic Graphical Models

Reviews

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

The problem addressed in the paper is the most probable explanation (MPE) inference in probabilistic graphical models (PGMs). The approach taken considers a power family of conditional probabilities parametrized on a parameter \beta taking integer positive values. A consequence of the actual formula used (with a conditional probability raised to the power of \beta) is that as \beta grows sampling gets biased towards MPE solutions, as in a sense using a power (and then normalizing the resulting values back into a probability distribution) amplifies the gap between various probability values in a distribution. A neural sampler is trained with a reverse (exclusive) KL minimization. Training creates a so-called ladder of proposals, meaning that a checkpoint model is stored for each value \beta within one global training. During inference, the sampler is used to draw samples, and a highest-scoring assignment is returned. An empirical evaluation is performed on PGMs of several types, including the grid family, the graph coloring family and synthetic spin glasses on 6-regular graphs. The evaluation includes a comparative analysis of checkpoints, followed by a best-of-K analysis for single-shot MPE inference. The evaluation further contains analyses focused on test-time training, warm-start annealing and branch-and-bound variable ordering.

Critical strengths

The empirical analysis is rather broad in terms of the types of studies, with dedicated sections on multiple analyses, as mentioned in the summary of the review. Results show benefits on top of baselines considered. The technical approach appears to be sensible.

Critical weaknesses

The paper is difficult to follow for an audience that exceeds a circle of experts, and it give the impression that it is written for an expert audience. For example, some technical concepts are used without any introduction, including central concepts such as node discovery. The conclusion of some of the empirical analyses as well as the significance of some of the results are not clearly articulated (e.g., Table 1). Figures have a poor size/resolution of fonts, making them impossible to interpret unless the reader zooms into the pdf document.

Questions for authors

No specific questions to the authors.

2 comments
AuthorsOpenReview ↗

Response to Reviewer DDTz

We thank the reviewer for the careful reading. The concerns are about presentation, and we address each below.

Undefined central concepts

We will define each central concept at first use and add a short notation table and a plain-language method overview before the formal objective. In particular:

  • Mode discovery. The modes of a distribution are its highest-probability configurations. For MPE these are the target assignments. As the power β\beta grows, the power posterior PβP_{\beta} concentrates its mass on these modes, so a sampler trained at larger β\beta increasingly proposes near-modal assignments, and best-of-KK selection discovers them. We will state this where the term first appears.
  • Power posterior. Pβ(q∣e)∝P(q∣e)βP_{\beta}(\mathbf{q}\mid\mathbf{e}) \propto P(\mathbf{q}\mid\mathbf{e})^{\beta}, the evidence-conditioned distribution raised to the power β\beta and renormalized, which interpolates from the posterior at β=1\beta=1 toward the MPE as β→∞\beta\to\infty.
  • Order-agnostic masked reveal sampler, reverse (exclusive) KL, best-of-KK, amortization over evidence, and the checkpoint ladder will each get a one-line definition at first use.

Articulating the conclusions, including Table 1

We will add an explicit takeaway to each analysis. For Table 1, the point is that a single training run yields a whole family of proposals indexed by β\beta, and the table shows how the deployed power is chosen. Reading across β\beta, diversity (the mean per-site Gini index) falls monotonically as β\beta grows, while best-of-128128 validation log⁡P\log P improves and then turns over on the more multimodal instances. This exposes a concentration-versus-coverage trade-off and identifies, per instance, the validation-selected power (bold, the row maximum in log⁡P\log P) used at deployment. We will state this conclusion in the caption and the surrounding text, and do the same for the other analyses so each section ends with its result in one sentence.

Figures

We will regenerate all figures with substantially larger axis, tick, legend, and annotation fonts, and export them as vector (resolution-independent) graphics so they are legible at normal zoom. We will also thin the densest panels so individual series are distinguishable in print.

General readability

We will restructure the method and experiments for a broader audience, leading with an intuitive overview of the power-sampling idea before the formal objective, defining notation on first use, and signposting what each experiment establishes. The goal is that a reader outside the immediate subarea can follow the main argument without reconstructing the terminology.

Summary

The concerns are presentation, and the revision will define the central concepts (including mode discovery) at first use, articulate the conclusion of each analysis including Table 1, enlarge and vectorize the figures, and add a plain-language overview and notation table. None of these change the results. They make the paper readable outside the immediate subarea.

Thank you for the response, I confirm reading and considering it.

Reviewer_hZ6DOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes amortized MPE inference for fixed graphical models by learning proposals for increasingly concentrated power distributions. A factor-reading message-passing network generates assignments through a masked-reveal process and is trained using a trajectory-level reverse-KL objective with REINFORCE.

A curriculum increases the power parameter and retains intermediate checkpoints. At deployment, the sampler returns the best of several generated assignments and can undergo query-specific test-time training. Experiments compare against neural MPE predictors and branch-and-bound solvers, and investigate warm-starting SMC and guiding search.

Critical strengths

1. The amortized inference setting is well motivated. Repeated evidence-conditioned queries on a fixed PGM provide a reasonable setting in which substantial offline training may be worthwhile.

2. The reported solution-quality improvements are large. The sampler substantially improves over the evaluated neural predictors across the nine main instances, with additional gains from sampling and test-time refinement.

3. The distinction between trajectory and marginal likelihood is acknowledged. The manuscript explicitly recognizes that averaging over reveal orders makes the marginal proposal probability intractable and instead optimizes an extended-space objective.

4. The downstream integration experiments are useful. SMC initialization and branch-and-bound guidance demonstrate potential applications beyond standalone sample selection.

Critical weaknesses

W1. The distributional evaluation requires clarification The marginal proposal probability is stated to be intractable, but the paper subsequently reports conditional log-likelihood, rank correlations involving logqθlogq_{\theta} , and “exact” marginal KL values.

It is unclear whether these quantities use the true marginal proposal, a fixed reveal order, a trajectory-conditional probability, or an estimator over reveal orders. These are different quantities. In particular, expected trajectory-conditional log-probability is not generally the marginal log-likelihood.

Moreover, Figure 2 does not support a matching-power fidelity pattern on the larger instances. For example, the β=1\beta=1 checkpoint has the highest displayed CLL in every GRID-40 target column, while on GLASS-400 the β=2\beta=2 checkpoint is best for the displayed higher-power targets. The interpretation should match these results.

W2. Hard-constraint handling is unspecified. The method claims to consume hard constraints, but a softmax sampler can assign positive probability to infeasible configurations. If such configurations have zero target probability, the reverse KL is infinite and the REINFORCE signal contains log0

The paper needs to specify whether it uses feasibility masking, finite penalties, clipping, or another mechanism, and how this changes the stated objective.

**W3. The arbitrary-arity architecture does not explicitly encode factor argument roles.$$ The any-arity backbone combines a fixed factor-table embedding with a sum of the other variables’ hidden states. For an asymmetric higher-order potential, this pooling can discard which variable occupies which table axis.

Without role-sensitive features or another mechanism, permuting the states of two other arguments can leave the factor-to-variable message unchanged despite changing the relevant potential values. This limits the claimed generality of the factor-reading architecture and deserves direct analysis.

W4. The comparisons do not sufficiently isolate the value of learned sampling. The one-sample method is substantially slower than the one-shot neural baselines. Test-time training also combines a strong learned initialization, repeated sampling, and parameter adaptation.

A particularly important missing control is to initialize stochastic local search, annealing, or another optimizer from the same neural samples and give it the same remaining budget. Likewise, frozen-proposal sampling should be compared with test-time parameter updates under matched time.

W5. Statistical and curriculum controls are incomplete. Most main tables do not report variability across independently trained models. The curriculum evaluation is concentrated on one small instance. Furthermore, if the random-β\beta baseline is not conditioned on β\beta, it optimizes a different objective rather than learning a comparable power-indexed family.

The description of training as “data-free” is also misleading: training uses Gibbs-generated complete assignments to construct the evidence distribution. No MPE labels are required, but sampled training data are still used.

Questions for authors

Q1. How exactly are marginal CLL, rank fidelity, and exact KL computed when reveal-order marginalization is intractable?

Q2. How are zero-probability assignments handled during training and evaluation?

Q3. How does the any-arity backbone distinguish argument positions in asymmetric factor tables?

Q4. Does test-time training outperform frozen-proposal sampling and search initialized from the same samples under matched time?

Q5. What is the initial importance-weight correction when SMC starts from an approximate neural proposal rather than the exact intermediate power distribution?

Q6. Can the main results be replicated across independent training seeds, with uncertainty intervals and hardware details for all timed baselines?

6 comments
AuthorsOpenReview ↗

Response to Reviewer hZ6D [Part 1/5]

We thank the reviewer for the detailed, soundness-focused review. We answer each weakness with an experiment or a precise clarification, summarized here and detailed in the sections below. All of the new experiments and fixes in this response will be incorporated into the revised paper and its appendix. None of the points weakens the Table 2 and Table 3 results, whose nine instances are all pairwise.

Summary of the entire response. Detailed response follows

  1. W1. We clarified the three distributional quantities. CLL is a coverage score and a lower bound on the marginal, rank fidelity is the quantity the MPE argument relies on, and exact KL is reported only on the enumerable GLASS-12. This agrees with the reviewer's reading of Figure 2, and we will state it in Section 4.
  2. W2. A hard constraint is a zero entry in a factor table. We floor it to a small positive value, so log⁡P\log P is finite for every assignment and the training signal never contains log⁡0\log 0. A violated constraint receives a steep finite penalty that grows with β\beta. We claim no exact feasibility guarantee.
  3. W3. This concern touches none of the headline results. Every instance in Table 2 and Table 3 uses the position-aware pairwise backbone, which is immune to it. The asymmetric-pooling issue is confined to the any-arity backbone, which appears in the paper only in the Table 5 ordering experiment. Even there we have addressed it with a per-slot role embedding, which improves the BN-30 ordering result by 169169 nats over the submitted number (Table A), and we will add the full with-fix and without-fix ablation on BN-30 and BN-45.
  4. W4. We added the two matched-budget controls the reviewer asked for. Table B warm-starts SA and PT from our samples to isolate the initialization, and the gain is positive on all nine instances for PT and on seven of nine for SA (the two small exceptions are instances where cold SA already exceeds our samples). Table C compares the frozen proposal against the test-time update to isolate the adaptation, which helps most on the hardest instance and is instance-dependent elsewhere.
  5. W5. We added training-seed variance on GLASS-400 and GRID-20 (Table E, agreement within 1.01.0 nat) and explained that the curriculum ablation runs on an enumerable instance because it needs exact KL. We will correct the random-β\beta and data-free wording and add the SMC initial weight, its ESS, and the hardware details to the paper.

W1 and Q1: the distributional quantities, and Figure 2

The three quantities are distinct.

QuantityDefinitionWhat it measures
CLLEq∼PβEτ(log⁡qθ(q∣e,τ))E_{\mathbf{q} \sim P^{\beta}} E_{\tau}\left(\log q_\theta(\mathbf{q} \mid \mathbf{e},\tau)\right)coverage of targets drawn from PβP^{\beta} (parallel tempering), order-averaged, a Jensen lower bound on the intractable marginal log⁡qθ(q∣e)\log q_\theta(\mathbf{q} \mid \mathbf{e})
Rank fidelitySpearman ρ(log⁡P(q∣e),log⁡qθβ(q∣e,τ))\rho\left(\log P(\mathbf{q} \mid \mathbf{e}), \log q_\theta^{\beta}(\mathbf{q} \mid \mathbf{e},\tau)\right) over samples q∼Pβ\mathbf{q} \sim P^{\beta} (each checkpoint's target)agreement of the two scorings on the target's samples, which transfers to the sampler's own draws because positive powers preserve order
Exact KLKL(qθ∥Pβ)KL\left(q_\theta \| P^{\beta}\right) with qθ(q∣e)q_\theta(\mathbf{q} \mid \mathbf{e}) enumeratedreported only on GLASS-12 (n=12n=12)

CLL scores parallel-tempering targets q∼Pβ\mathbf{q} \sim P^{\beta} under the sampler. Since the marginal qθ(q∣e)=∑τp(τ∣e)qθ(q∣e,τ)q_\theta(\mathbf{q} \mid \mathbf{e})=\sum_\tau p(\tau \mid \mathbf{e}) q_\theta(\mathbf{q} \mid \mathbf{e},\tau) is intractable, we score each target with the order-averaged trajectory-conditional log-probability, which is a Jensen lower bound, Eτ(log⁡qθ(q∣e,τ))≤log⁡Eτ(qθ(q∣e,τ))=log⁡qθ(q∣e)E_{\tau}\left(\log q_\theta(\mathbf{q} \mid \mathbf{e},\tau)\right)\le \log E_{\tau}\left(q_\theta(\mathbf{q} \mid \mathbf{e},\tau)\right)=\log q_\theta(\mathbf{q} \mid \mathbf{e}). Exact KL is computed only where enumeration is feasible, on GLASS-12.

We agree with the reviewer's reading of Figure 2. CLL is a coverage score, so the broadest (lowest-β\beta) checkpoint tends to win the CLL columns (β=1\beta=1 on GRID-40, β=2\beta=2 on the higher-power GLASS-400 columns). This is not a matching-power diagonal pattern, and we claim none for CLL. The MPE argument rests on rank fidelity, not CLL, because PP and qθβq_\theta^{\beta} rank the draws from qθβq_\theta^{\beta} similarly, so best-of-KK under log⁡P\log P recovers high-probability configurations even where the proposal under-covers mass. We will state CLL as a coverage lower bound in Section 4, restrict the exact-KL claim to GLASS-12, and carry the deployment argument through rank fidelity.

AuthorsOpenReview ↗

[Part 2/5]

W2 and Q2: hard constraints give a finite penalty

A hard constraint here is a zero entry in a factor table (a forbidden assignment mapped to 00), replaced with a small positive value at load. The method uses finite penalties by flooring, not feasibility masking. Zero entries are floored to 10−410^{-4} at load, and the scorer floors each factor at ϵ=10−6\epsilon=10^{-6} before the logarithm, log⁡P(x)=∑flog⁡max⁡(θf(x),10−6).\log P(x)=\sum_f \log\max \big(\theta_f(x),10^{-6}\big). So log⁡Pβ(x)=βlog⁡P(x)\log P^{\beta}(x)=\beta\log P(x) is finite for every assignment, including infeasible ones, and the reverse KL and REINFORCE signal never contain log⁡0\log 0. A violated hard factor contributes about βlog⁡(10−4)\beta\log(10^{-4}), a steep finite penalty that β\beta amplifies, driving the sampler off infeasible configurations as β\beta grows. This is exercised on the LE450 coloring instances, whose adjacency constraints enter as floored zeros. We claim no exact feasibility guarantee. Flooring makes the tempered target a proper distribution, which the objective description will state.

W3 and Q3: argument roles in asymmetric factors (one backbone, with a fix and a comparison)

This limitation does not affect any result in Table 2 or Table 3. It applies to one of the paper's two backbones, the any-arity factor-graph backbone (both backbones are defined in the architecture appendix). All nine instances in Table 2 and Table 3 (grids, spin glasses, coloring WCSPs) use the other one, the position-aware pairwise backbone, which is immune to the problem. The any-arity backbone appears in the paper only in the branch-and-bound variable-value ordering experiment on BN-30 and BN-45 (Table 5), so this concern is separate from every headline result.

The pairwise backbone is position-aware, so it avoids the problem. It forms two directed edges per factor carrying the table and its transpose, and reads target and neighbor from fixed separate slots, so argument position is explicit and never pooled away (even for an asymmetric pairwise potential). Per-instance arities are in the appendix.

The any-arity backbone's factor-to-variable message builds the target context as the leave-one-out sum $ctx_v= \sum_{u \in s(f)} h_u - h_v $ , permutation-symmetric over the other arguments, and shares the encoded table across scope slots with no slot index. For a potential not symmetric under permuting its arguments (a directed CPT P(child∣parents)P(\mathrm{child}\mid\mathrm{parents}) ), the message cannot tell which axis the target occupies. This is a real limitation of the any-arity backbone, triggered by asymmetric factors. A symmetric higher-order potential is still read correctly, so the issue is asymmetry rather than high arity.

Our factor encoding follows SINE's, reading each factor through its full potential table. The remedy is a per-slot role embedding. We concatenate a learned embedding of the target's scope-slot index into the message, so the head can align the shared table to the target's axis (the slot index is already computed, so this is a one-line change). We compared it against the symmetric variant on BN-30, a Bayesian network of 1089 arity-33 directed CPTs, the asymmetric case at issue.

Table A. BN-30 variable-value ordering inside branch-and-bound (SCIP), the experiment in the paper's Table 5, on its 100100 queries, β=6\beta=6. Anytime log⁡P\log P at 10/30/6010/30/60 s. The submitted row is the published any-arity backbone (symmetric pooling); the fix adds a per-slot role embedding.

Any-arity backbone on BN-30, SCIP ordering1010s3030s6060s
symmetric pooling (as submitted, Table 5)−900.6-900.6−655.6-655.6−637.3-637.3
++ per-slot role embedding−471.1-471.1−468.6-468.6−468.0-468.0

The per-slot role embedding improves the ordering result by 169169 nats at 6060 s over the submitted number, on this asymmetric higher-order instance. This is evidence that the fix addresses the pooling limitation the reviewer identified, since the role embedding supplies the target's argument position, the information the symmetric message was missing. We thank the reviewer for pointing this out, as it identified a genuine flaw in how the any-arity backbone reads asymmetric factors. The third instance in that ordering experiment, GRID-20B, uses the pairwise backbone and is unaffected. We have run the fix versus no-fix ablation on BN-30 above and will add it along with BN-45 and an explicit statement of the limitation, to the appendix.

AuthorsOpenReview ↗

[Part 3/5]

W4 and Q4: isolating the value of learned sampling

Ours+TTT combines three things: a learned initialization, repeated sampling, and parameter adaptation. The reviewer asks to separate these with matched-budget controls, and also notes that the one-sample method is slower than the one-shot baselines. We answer with three matched-budget comparisons, one per table below. Higher is better throughout, and LE450 values are negative log⁡P\log P.

Table B: warm-started SA and PT isolate the initialization

Table B. 6060 s/query budget. Ours, Ours+TTT: best-of-KK at deployed β\beta, sub-second to seconds/query. PT, SA: cold anytime solvers. ++ warm: gain when the solver is seeded from our samples.

InstanceOursOurs+TTTPT @60s++ warmSA @60s++ warm
GRID-20621.9625.4621.1+4.4+4.4625.1−1.9-1.9
GRID-402664.62673.12591+78.9+78.92566+102.6+102.6
GRID-8010728107329963+778.1+778.18800+1940.7+1940.7
GLASS-400742.9755.8754.6+6.7+6.7760.4−1.8-1.8
GLASS-800148615071494+27.5+27.51447+70.1+70.1
GLASS-1200223722682225+58.5+58.52078+196.1+196.1
LE450-2−18251-18251−18214-18214−18182-18182−4.9-4.9−18182-18182−8.9-8.9
LE450-3−8597-8597−8469-8469−8330-8330−23.4-23.4−8329-8329−28.7-28.7
LE450-4−4225-4225−3967-3967−3717-3717−21.6-21.6−3718-3718−24.5-24.5

As a standalone amortized solver (Ours, Ours+TTT) we win on the large grids, where classical search fails to scale in budget, are competitive on the glasses with Ours+TTT winning the larger two, and concede quality on LE450 coloring to the PT and SA solvers, where our value is purely amortized cost. In the ++ warm columns the only change is the starting population, so the gain isolates the initialization. Warm-starting refines our samples at the deployed power rather than re-annealing from high temperature, so it exploits a strong initialization instead of re-exploring. On the grids and spin glasses, where our samples already lie near high-probability configurations, it improves PT throughout and SA on all but the two smallest instances (GRID-20, GLASS-400), where cold SA is already strong, with large gains on the bigger ones (up to +1941+1941 for SA on GRID-80). On the LE450 coloring instances it is negative, as cold SA and PT already reach near-optimal colorings by exploring from high temperature, so refining our higher-β\beta, lower-diversity samples at the deployed power has little headroom and underperforms the cold run. Warm-starting therefore trades exploration for exploitation, a net gain where the proposal is already aligned with the optimum.

Reusing our samples inside another solver is not specific to SA and PT. The same ladder warm-starts annealed SMC and supplies branch-and-bound ordering elsewhere in the paper. At 6060 s/query the warm-started SA and PT of Table B beat Ours+TTT on eight of nine instances, so we report Ours+TTT not as the best use of a 6060 s budget but as the standard neural refinement, the form in which the neural MPE baselines are also compared (ITSELF, Table 3). Best-of-KK is the sub-second option, warm-started SA and PT typically the highest-quality at 6060 s where composition helps, and Ours+TTT the amortized point in between.

Comments on the paper

5 comments
AuthorsOpenReview ↗

Response to Reviewer vE4R [Part 1/4]

We thank the reviewer for the constructive review. We answer each weakness and question with an experiment or a clarification, summarized here and detailed below. We label the reviewer's two weaknesses W1 (positioning relative to prior work) and W2 (baselines and cost accounting), and number the questions Q1 to Q3. All of the new experiments and analyses in this response will be incorporated into the revised paper and its appendix. Higher is better throughout, and LE450 values are negative log⁡P\log P.

Summary of the response. Detailed response follows

  1. W1. We credit the closest prior work (the VAN and VNA line, Sanokowski et al., and POMO) and state what is new (amortization over evidence on a fixed PGM, the factor-reading encoder, and reuse of the checkpoint ladder). The in-family comparison the reviewer asks for is already in the paper as the architecture ablation (Table 7).
  2. W2 and Q1. The three neural baselines follow Arya et al.'s protocol exactly, so they are not undertuned. Given the same per-query wall-clock as Ours and allowed to sample repeatedly, they draw thousands of samples per query and still fall short on all nine instances (Table A).
  3. Q2. We add simulated annealing and parallel tempering at the deployed β\beta, at 2020 and 6060 s/query (Table B), and disclose the hardware and thread counts. Both are samplers of the power distribution, so warm-starting them from our samples improves PT on all nine instances and SA on seven of nine (composition).
  4. W2, training cost and break-even. The per-query tables report inference cost, as standard for an amortized method, and the appendix folds the 9.59.5 to 1919 hours of training into a break-even of a few thousand queries against cold annealed SMC, with a cold parallel-tempering cross-check.
  5. Q3. We report training-seed variance on GLASS-400 and GRID-20 (Table C), where the seeds agree within 1.01.0 nat.

The central claim, that sampling a tempered target beats one-shot prediction for amortized MPE, stands across all nine instances.

W1: positioning relative to annealed autoregressive samplers

We do not claim the training recipe is new, and the submitted paper already attributes it to prior work on REINFORCE [1], GFlowNets [2], and annealed sampling [3, 4, 5]. The four works the reviewer names are closer still, and we will add them to the revised paper. Training an autoregressive model toward a Boltzmann or power target with a REINFORCE reverse-KL objective while annealing the temperature is the mechanism of variational autoregressive networks [6] and variational neural annealing [7]; annealed reverse-KL GNN samplers for graph combinatorial optimization are due to Sanokowski et al. [8]; and best-of-KK with a shared REINFORCE baseline is from POMO [9]. Our contribution is not the training rule but the combination that amortizes MPE over evidence on a fixed PGM.

This combination has three parts:

  1. Amortization over evidence. The single-system samplers [6, 7] train one model per target distribution, but others already amortize across problem instances: Sanokowski et al. [8] and POMO [9] train one model that generalizes across the instances of a combinatorial-optimization family. That amortization is over instances, for an unconditional objective such as a ground state or an optimal tour. Ours amortizes over a different axis, the evidence. It conditions on the observed variables and is reused across evidence configurations of a fixed PGM, so one trained model answers a stream of conditional MPE queries that differ by what is observed, rather than solving one optimization.
  2. The factor-reading encoder. The network reads the numerical factor tables (following SINE's factor encoding [10]), which is what lets the same parameters transfer across evidence patterns.
  3. Reuse of the power-indexed checkpoint ladder to warm-start annealed SMC and to order branch-and-bound.

The requested comparison, one such sampler as a baseline on the spin glasses, is already in the paper in controlled form. Our architecture ablation (Table 7) replaces the factor-reading encoder with a structure-blind MLP over raw variable tokens, trained with the identical annealed reverse-KL objective, and this 9.69.6M-parameter model loses badly to the 0.240.24M-parameter factor-reading GNN despite its far greater capacity, which the reviewer notes as a strength. VAN and VNA fall in the same family, annealed reverse-KL autoregressive samplers with no factor-reading encoder (their backbones are a masked-autoregressive MLP or PixelCNN for VAN and an RNN for VNA, none of which read the factor tables). The ablation thus isolates exactly what is new here, the factor-reading encoder, holding the objective fixed, so the gain is attributable to that encoder. The cited methods are not evidence-conditioned, whether they target a single distribution [6, 7] or amortize across a family of CO instances [8, 9], so a direct drop-in to our conditional MPE setting reduces to this ablation.

AuthorsOpenReview ↗

[Part 2/4]

W2 and Q1: neural baselines and matched-time budget

Q1, training and tuning. We did not undertune the baselines. All three follow Arya et al.'s protocol exactly: the same self-supervised, label-free multilinear-extension MPE loss, the same optimizer and training schedule, the same architectures (an MLP for SSMP, the hypergraph-attention encoder with a global readout for SINE, and the teacher-student scheme for GUIDE), and the same 2%2\% to 10%10\% evidence distribution we use. Each baseline's entropy-penalty weight, the tunable hyperparameter they share, is swept and selected on validation for each. Since the training matches the paper, the gap reflects the models themselves.

W2, the baselines are faster per query, so we spend the time they save on extra samples. We give each baseline the same per-query wall-clock as Ours best-of-3232 (sampling and scoring), let it draw as many samples as fit from its per-variable softmax, and keep the best of those and its one-shot prediction. Within this budget the baselines draw thousands of samples per query (a mean of 26002600 to 79007900 across instances), yet the extra samples barely lift them above their one-shot numbers, and they still fall short on all nine instances (Table A).

The cause is structural rather than a matter of tuning, and better tuning of the baselines is unlikely to close it. The baselines sample the query variables independently given the evidence, a mean-field proposal, so one forward pass fixes their per-variable marginals. A configuration whose probability comes from coordinated choices across coupled variables then has proposal probability equal to the product of those marginals, exponentially small in the number of coupled variables, so recovering it by independent draws would take exponentially many samples, far beyond a finite wall-clock budget. On the spin glasses the samples can even score below the one-shot argmax, which is why the table keeps the better of the two. Ours is an any-order autoregressive sampler that conditions each revealed variable on those already set, so it places mass on the coordinated configuration directly. The baselines' speed comes from the same independence assumption that makes these configurations exponentially rare under finite sampling, so matching wall-clock does not close the gap.

Table A. Matched-time baselines, per query the best of the one-shot prediction and as many samples as fit in the per-query wall-clock of Ours best-of-3232 (sampling and scoring). Same 100100 queries. LE450 values are negative log⁡P\log P.

InstanceOurs (best-of-3232)SSMPSINEGUIDE
GRID-20621.9539.1522.5537.7
GRID-402664.62407.52209.52341.6
GRID-80107289791.98600.39378.6
GLASS-400742.9535.1549.9588.7
GLASS-80014861165.91101.51210.9
GLASS-120022371785.01653.11825.3
LE450-2−18251-18251−20625-20625−21287-21287−20750-20750
LE450-3−8597-8597−11448-11448−11481-11481−11450-11450
LE450-4−4225-4225−6793-6793−6924-6924−5830-5830
AuthorsOpenReview ↗

[Part 3/4]

Q2: classical anytime baselines and hardware

Simulated annealing and parallel tempering at the deployed β\beta

We add both at the deployed β\beta, at 2020 and 6060 s/query (Table B), matching Table 3's two budgets. We compare against Ours+TTT because test-time training is the standard neural refinement, the form in which the neural MPE baselines are also compared (ITSELF, Table 3), so it is the matched neural operating point.

Table B. Anytime log⁡P\log P at 2020 and 6060 s/query over 100100 queries. Ours+TTT is best-of-KK with test-time training at the deployed β\beta. PT and SA are cold at each budget. ++ warm is the gain at 6060 s when the solver is seeded from our samples. LE450 values are negative log⁡P\log P.

InstanceTTT 20sTTT 60sPT 20sPT 60sPT ++ warmSA 20sSA 60sSA ++ warm
GRID-20624.6625.4615.2621.1+4.4+4.4617.8625.1−1.9-1.9
GRID-4026712673.125362591+78.9+78.923142566+102.6+102.6
GRID-80107311073292119963+778.1+778.178048800+1940.7+1940.7
GLASS-400751.8755.8742.2754.6+6.7+6.7681.2760.4−1.8-1.8
GLASS-8001500150714601494+27.5+27.512131447+70.1+70.1
GLASS-12002257226821642225+58.5+58.517362078+196.1+196.1
LE450-2−18222-18222−18214-18214−18183-18183−18182-18182−4.9-4.9−18182-18182−18182-18182−8.9-8.9
LE450-3−8494-8494−8469-8469−8359-8359−8330-8330−23.4-23.4−8350-8350−8329-8329−28.7-28.7
LE450-4−4033-4033−3967-3967−3806-3806−3717-3717−21.6-21.6−3786-3786−3718-3718−24.5-24.5

At 2020 s Ours+TTT leads on the six grid and glass instances, by a wide margin on the large grids (GRID-80 1073110731 vs PT 92119211 and SA 78047804), and already concedes the three LE450 coloring instances, where PT and SA score higher. By 6060 s the gap on the grids and glasses narrows, but Ours+TTT still leads on the grids and the larger glasses, is within a few nats of SA on GLASS-400, and continues to concede LE450, where its remaining advantage is amortized cost.

PT and SA are classical MCMC over the tempered landscape, replica-exchange sampling and annealed optimization respectively, so our amortized sampler composes with them rather than only competing. The ++ warm column seeds each solver from our samples at the same 6060 s budget, matched per query, changing only the initial population. Warm-starting improves PT on all the grids and spin glasses and SA on all but the two smallest (GRID-20, GLASS-400), where cold SA is already strong, with large gains on the bigger ones (up to +1941+1941 for SA on GRID-80). On the LE450 coloring instances it is negative, as cold SA and PT already reach near-optimal colorings, so refining our samples at the deployed power has little headroom. Warm-starting trades exploration for exploitation, a net gain where the proposal is already well-aligned with the optimum. This is the same role our checkpoints play warm-starting annealed SMC elsewhere in the paper.

Hardware and threads

Simulated annealing, parallel tempering, and the branch-and-bound baselines (toulbar2, daoopt) all ran on the same dual-socket Intel Xeon Silver 4208 (1616 physical cores, 3232 threads, 9393 GB RAM), each given its full core budget. Neural inference ran on one NVIDIA A40 (4646 GB). We will add this to the setup.

W2: break-even reference and training cost

We do account for the 9.59.5 to 1919 hours of training, not exclude it. The per-query tables report inference cost, as is standard for an amortized method, and the appendix amortization analysis (Table 11) folds training into a break-even query count Q⋆=Ttrain/(tSMC−tneural)Q^\star=T_{train}/(t_{SMC}-t_{neural}), the point beyond which the sampler is cheaper in total compute, training included, than answering each query with annealed SMC.

The reference is annealed SMC because SMC is the sampler of the power distribution that our method is built around. The same checkpoints warm-start annealed SMC elsewhere in the paper, so SMC is the procedure our sampler amortizes rather than an arbitrary baseline. We start it cold because the fair alternative to a trained model is to run the sampler from scratch. The break-even against it is approximately 14001400 queries on GLASS-400, 580580 on GLASS-800, and 375375 on GLASS-1200, far below the query volumes the amortized setting targets, after which the training cost is fully repaid. For completeness, we repeat the same analysis against a faster sampler of the power distribution, our cold parallel-tempering runs. The break-even rises to approximately 30503050, 20502050, and 12401240 queries, still in the thousands and still far below the amortized target. We will add this parallel-tempering cross-check to the appendix amortization analysis.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.