Unverified 2026

Certified partition-function reranking

Implementation & benchmark of arXiv:2608.25545 — Certified decoding of quantum LDPC codes

Usefulness5/10

Difficulty6/10

Novelty6/10

Sampling Accuracy Stability Sampling Loss Probability Statistics Stochastic processes

Source paper: Certified decoding of quantum LDPC codes arXiv:2608.25545 ⓘ · analyzed Aug 29, 2026

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

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.

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.$$

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.

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.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.