# Certified partition-function reranking

- ID: 178
- Canonical URL: https://synthcore.org/idea/178/certified-partition-function-reranking
- API JSON: https://synthcore.org/api/idea/178.json
- API Markdown: https://synthcore.org/api/idea/178.md
- Verification status: unverified
- Source: [arXiv:2608.25545](https://arxiv.org/abs/2608.25545)
- Category: sampling
- Solves: accuracy, stability
- ML areas: sampling, loss
- Math tags: probability, statistics, stochastic-processes
- Ratings: usefulness 5/10; difficulty 6/10; novelty 6/10

## Idea description

Replace MAP scoring of discrete latent configurations by comparison of the total energy-model mass assigned to each candidate class. Estimate each class partition function with annealed importance sampling driven by identical random seeds, then return a prediction only when a paired bootstrap confidence interval certifies that its log-partition score exceeds every competitor.

## Mathematical statement

The paper defines a strictly positive Markov random field with clique potentials \(\psi_C\geq 0\), log-potentials \(\theta_C=\log\psi_C\), and global partition function \(\mathrm{Z}=\sum_{\bm{x}}\exp(\sum_{C\in\mathcal C}\theta_C(\bm{x}_C))\). For a neural energy model, let \(x\) be a discrete latent configuration, \(E_\phi(x;c)\) its energy conditioned on input \(c\), and \(\mathcal X_y\) the configurations corresponding to candidate class \(y\). The class probability is proportional to \(Z_y(c)=\sum_{x\in\mathcal X_y}\exp[-E_\phi(x;c)]\), rather than to the score of the single lowest-energy configuration. Use a temperature path \(0=\beta_0<\cdots<\beta_K=1\) and bridge densities \(f_k(x)=\exp[-\beta_kE_\phi(x;c)]\) restricted to \(\mathcal X_y\). If \(x_{k-1}^{(r)}\) is propagated through MCMC targeting the next bridge, annealed importance sampling uses \(w_y^{(r)}=\prod_{k=1}^{K}\exp[-(\beta_k-\beta_{k-1})E_\phi(x_{k-1}^{(r)};c)]\), and \(\widehat Z_y=|\mathcal X_y|R^{-1}\sum_r w_y^{(r)}\), where \(|\mathcal X_y|\) is the uniform base partition function. For candidates \(a,b\), use common random numbers to construct paired log-weight differences \(d_r=\log w_a^{(r)}-\log w_b^{(r)}\); bootstrap their mean and certify \(a\) only when its lower confidence bound is positive.

## Key formulas

- $$\mathrm{Z}=\sum_{\bm{x}}\prod_{C\in\mathcal{C}}\psi_C(\bm{x}_C)=\sum_{\bm{x}}\exp\!\Big(\sum_{C\in\mathcal{C}}\theta_C(\bm{x}_C)\Big).$$
- $$Z_y(c)=\sum_{x\in\mathcal X_y}\exp[-E_\phi(x;c)],\qquad \Pr(y\mid c)=\frac{Z_y(c)}{\sum_{y'}Z_{y'}(c)}.$$
- $$w_y^{(r)}=\prod_{k=1}^{K}\frac{f_k(x_{k-1}^{(r)})}{f_{k-1}(x_{k-1}^{(r)})}=\prod_{k=1}^{K}\exp\!\left[-(\beta_k-\beta_{k-1})E_\phi(x_{k-1}^{(r)};c)\right],\qquad \widehat Z_y=|\mathcal X_y|\frac{1}{R}\sum_{r=1}^{R}w_y^{(r)}.$$
- $$d_r=\log w_a^{(r)}-\log w_b^{(r)},\qquad \text{certify }a\text{ over }b\text{ if }\operatorname{LCB}_{1-\alpha}\!\left(\frac{1}{R}\sum_{r=1}^{R}d_r\right)>0.$$

## Implementation notes

(1) Integration point: add this as an optional inference-time reranker after a neural model proposes a small set of discrete candidates, such as beam outputs, VAE latent classes, or structured actions. The network supplies an energy \(E_\phi(x;c)\); do not change the forward pass initially. Each candidate class \(y\) must have an enumerable or MCMC-sampleable latent set \(\mathcal X_y\), and the base cardinality \(|\mathcal X_y|\) should be known. (2) Pseudocode: for each candidate pair \(a,b\), initialize \(R\) identical random latent states and identical random-number streams. Set \(\log w_y^{(r)}=0\). For \(k=1,\ldots,K\), evaluate \(E_\phi(x_{k-1}^{(r)};c)\), add \(-(\beta_k-\beta_{k-1})E_\phi(x_{k-1}^{(r)};c)\) to \(\log w_y^{(r)}\), then run several Metropolis or Gibbs transitions targeting \(\exp[-\beta_kE_\phi(x;c)]\). Form paired differences \(d_r\), resample the indices \(r\) with replacement for 1,000 bootstrap replicates, and return the best candidate only if the one-sided lower confidence bound is positive against all alternatives; otherwise abstain or retain the original model output. Use log-sum-exp for partition estimates. (3) The partition-function identity and AIS weight are fixed by the paper; proposal mixing, temperature spacing, transition count, confidence level, and bootstrap coverage are empirical. Adapt temperature spacing using effective sample size \(\mathrm{ESS}=(\sum_r w_r)^2/\sum_r w_r^2\), targeting an ESS fraction of 0.2--0.5. (4) First cheap experiment: train a small MNIST or CIFAR-10 energy-based classifier with a 4--16-state discrete latent variable and compare ordinary MAP scoring, independent AIS, and common-random-number AIS. Measure accuracy, calibration error, selective accuracy versus abstention rate, certification coverage, and wall-clock cost. Success means higher accuracy or better calibration at equal candidate count, with easy examples certified frequently and ambiguous examples producing abstentions rather than confident errors.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.