Exact autoregressive sampling of planar Ising spin glasses via the Kac--Ward theory
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Condensed Matter. The day in condensed matter: materials, phases and the measurements under them.
Kai: I'm Kai.
Mira: And I'm Mira, here with Lev.
Kai: We're looking at the paper: "Exact autoregressive sampling of planar Ising spin glasses via the Kac--Ward theory".
Mira: Here's the gist of the paper. Exact autoregressive sampling of planar Ising spin glasses via the Kac–Ward theory provides an exact baseline for benchmarking neural autoregressive samplers by generating strictly independent and identically distributed samples with exact normalized likelihoods at a computational cost of O(N5/2) for N spins.
Kai: The Challenge in Sampling Spin Glasses Exact sampling from the Boltzmann distribution of spin glasses remains an outstanding challenge because Markov chain Monte Carlo methods suffer from critical slowing down and metastable trapping.
Mira: Modern neural autoregressive samplers are approximate and cannot be rigorously benchmarked in the absence of exact reference samples.
Kai: The Autoregressive Methodology The method decomposes the Boltzmann distribution into exact conditional probabilities via the chain rule and evaluates them by applying the Kac–Ward determinant formula to an extended planar graph.
Paper summary: Kai: So we're looking at this paper about "Exact autoregressive sampling of planar Ising spin glasses via the Kac--Ward theory". Basically, they're tackling a problem where standard methods like Markov chain Monte Carlo struggle with critical slowing down and getting stuck in these tricky metastable states <ref:2608.24382#pg1>.
Mira: That means we can't just use those usual sampling techniques reliably for complex spin glasses because they get bogged down, and this paper claims it gives us an exact baseline <ref:2608.24382#pg1>.
Lev: Exact is a big claim in this field, especially when you think about what it takes to run something like this on actual hardware later <ref:2608.24382#pg1>.
Kai: They do this by using the chain rule to break down the probability distribution into exact conditional probabilities for each spin sequentially <ref:2608.24382#pg1>.
Mira: But the main hurdle they address is that when you fix spins in a certain order, it naturally creates these effective fields on the boundary of what you haven't sampled yet <ref:2608.24382#pg2>.
Lev: That sounds like a real headache for an error correction scheme; dealing with those induced fields is where the overhead really lands for hardware <ref:2608.24382#pg1>.
Kai: The authors solve this by using a planarity-preserving auxiliary spin construction that maps the original model onto an enlarged planar graph without the external fields destroying the loop formulations <ref:2608.24382#pg2>.
Mira: So, they're essentially transforming the hard problem into one where you can use a known exact evaluation tool for partition functions <ref:2608.24382#pg3>.
Lev: If that mapping holds up under all the conditions, it means we might actually be able to get an unbiased estimate of the likelihoods <ref:2608.24382#pg1>.
Kai: And they evaluate these conditional partition functions exactly using the Kac–Ward determinant formula on this extended planar graph <ref:2608.24382#pg3>.
Mira: Which, according to the summary, results in strictly independent and identically distributed samples with exact normalized likelihoods summary.
Lev: That exactness is key because neural samplers are approximations; having an exact reference means we have something rigorous to check them against summary.
Kai: The computational cost they state for generating these samples is O of N to the power of five over two, or O of N to the five over two summary.
Mira: That scaling is quite high, so it limits practical application right now, but it's still a massive step forward in terms of rigor summary.
Lev: If we had GPU-accelerated sparse linear algebra packages later on, maybe we could bring that complexity down for systems of N around one thousand spins summary.
Kai: They show this works on the two dimensional Edwards–Anderson spin glass where the autocorrelation function satisfies gamma t equals delta t zero, which confirms they are strictly independent and identically distributed samples validation.
Mira: That’s a strong validation because it shows the algorithm produces what it claims—the i.i.d. samples—on a system that is known to have that property validation.
Lev: Being able to get direct entropy estimation as an unbiased expectation value over N spins is something we need for training better models, regardless of the sampling cost appendix C.
Kai: They also provide direct access to the exact normalized likelihood and conditional probabilities for every generated configuration, which is a big deal appendix C.
Mira: That exact likelihood information allows us to validate neural autoregressive samplers against these planar instances used in variational benchmarks without any approximation errors from the sampling process appendix C.
Lev: One limitation they state is that the condition number of the matrix A diverges exponentially under quenched disorder or geometric frustration, meaning you need arbitrary precision arithmetic to keep things numerically stable appendix B.
Kai: That divergence in condition number is a serious issue for any numerical method; it shows the difficulty when disorder gets really bad appendix B.
Mira: So, while the theory is exact, we have this practical constraint on how big a system we can handle before the computation becomes totally intractable appendix B.
Lev: And they also note that this O of N to the five over two cost per sample restricts applications to systems of moderate size, like N around one thousand spins appendix C.
Kai: They also mention that future work could involve using GPU-accelerated sparse linear algebra packages to improve efficiency and using those exact conditional probabilities as per-step teacher signals for training via knowledge distillation appendix C.
Mira: That idea of using the exact conditional probabilities as a teacher signal for on policy training sounds promising because it bypasses some of the approximation steps in the neural network itself appendix C.
Lev: If we can distill that exact information efficiently, maybe we can get better results for running these complex simulations on real quantum hardware someday appendix C.
Kai: So, to wrap up this paper about "Exact autoregressive sampling of planar Ising spin glasses via the Kac--Ward theory", it gives us a rigorous way to generate exactly what's needed for benchmarking other AI samplers summary.
Mira: It proves that we can get exact samples from these hard problems, but we still have those scaling issues and the need for high precision arithmetic appendix B.
Lev: The implication is that it sets a very high bar for any neural sampler trying to learn how to sample these complex physical systems accurately summary.
Conclusion: Kai: So this paper, "Exact autoregressive sampling of planar Ising spin glasses via the Kac--Ward theory," it gives us a way to get perfectly accurate samples from these really hard physical systems, spin glasses.
Mira: The authors are using this Kac–Ward theory to map the problem onto a zero-field Ising model on an enlarged planar graph, which lets them use an exact math formula to find the conditional probabilities.
Lev: And what they achieve is generating strictly independent and identically distributed samples with exact normalized likelihoods for every step.
Kai: So, for someone listening who just cares about getting reliable data from a simulation, this means they have a rigorous baseline to test any approximate AI sampler against.
Mira: It’s about providing that exact likelihood information without needing to do any kind of thermodynamic integration beforehand. That lets you estimate entropy directly over the samples.
Lev: But we gotta be careful with the cost; generating these samples takes a big O of N to the five over two operations for N spins, which is not something you can run easily on very large systems right now.
Kai: Right, so it’s powerful for validation on smaller systems, like those around one thousand spins where we can actually measure things directly with our qubits.
Mira: The implication is that we finally have a solid reference point to see how well these newer neural autoregressive models are learning the true distribution of these complex disordered materials.
Lev: It sets a high bar for what any new sampling method needs to prove if it wants to be trusted for real hardware applications later on.
School of Physical Science and Technology, Beijing University of Posts and Telecommunications · Institute of Theoretical Physics, Chinese Academy of Sciences Institute for Advanced Study, University of Science and Technology of China, Hefei National Laboratory for Physical Sciences at the Microscale and Department of Modern Physics · Hefei National Laboratory, University of Science and Technology of China · School of Advanced Interdisciplinary Sciences, University Chinese Academy of Sciences · Beijing National Laboratory for Condensed Matter Physics and Institute of Physics, Chinese Academy of Sciences
cond-mat.stat-mech, cond-mat.dis-nn
Submitted: 2026-08-25
Updated: 2026-11-14
Comments: 10 pages, 4+1 figures
Code: https://github.com/bnuliujing/pykacward
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 92/100
The gist: Exact autoregressive sampling of planar Ising spin glasses via the Kac–Ward theory provides an exact baseline for benchmarking neural autoregressive samplers by generating strictly independent and…
Key concepts
- Kac–Ward Theory
- This theory is used to exactly evaluate the conditional probabilities of the spin glass distribution. It works by mapping the problem onto an extended planar graph and using a determinant formula to find these exact values, which is crucial for generating perfect samples.
- Planarity Preservation
- The method uses an auxiliary spin construction that ensures the resulting graph remains planar during sequential generation steps. This property is guaranteed by graph minor theory, ensuring the mathematical framework remains valid throughout the sampling process.
- Exact Likelihoods and Observables
- The algorithm calculates the exact normalized likelihood and unbiased observables for every generated configuration. This provides a rigorous, bias-free measure of probability distributions that can be used to validate other approximate sampling methods.
Terminology
Summary
Exact autoregressive sampling of planar Ising spin glasses via the Kac–Ward theory provides an exact baseline for benchmarking neural autoregressive samplers by generating strictly independent and identically distributed samples with exact normalized likelihoods at a computational cost of O(N5/2) for N spins. p. 0 By encoding these
fields with a planarity-preserving auxiliary spin construction, the conditional partition functions are
mapped to an extended zero-field Ising model and exactly evaluated using the Kac–Ward determinant formula. The method generates strictly independent and identically distributed samples with
exact normalized likelihoods at a computational cost of O(N
5/2
) for N spins, thereby providing an
exact baseline for benchmarking neural autoregressive samplers.Where the paper says it
The Challenge in Sampling Spin Glasses
Exact sampling from the Boltzmann distribution of spin glasses remains an outstanding challenge because Markov chain Monte Carlo methods suffer from critical slowing down and metastable trapping. Modern neural autoregressive samplers are approximate and cannot be rigorously benchmarked in the absence of exact reference samples. p. 0 Exact autoregressive sampling of planar Ising spin glasses via the Kac–Ward theory
Jing Liu,1, 2, ∗ Tao Chen,3, 4 Tianrui Che,5 Lei Wang,6 Youjin Deng,3, 4 and Pan Zhang2, 7, †
1School of Physical Science and Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
2
Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China
3Hefei National Laboratory for Physical Sciences at the Microscale and Department of Modern Physics,
University of Science and Technology of China, Hefei 230026, China
4Hefei National Laboratory, University of Science and Technology of China, Hefei 230088, China
5School of Advanced Interdisciplinary Sciences, University of Chinese Academy of Sciences
6Beijing National Laboratory for Condensed Matter Physics and Institute of Physics,
Chinese Academy of Sciences, Beijing 100190, China
7School of Fundamental Physics and Mathematical Sciences,
Hangzhou Institute for Advanced Study, UCAS, Hangzhou 310024, China
Exact sampling from the Boltzmann distribution of spin glasses remains an outstanding challenge:
Markov chain Monte Carlo methods suffer from critical slowing down and metastable trapping, while
modern neural autoregressive samplers such as variational autoregressive networks are approximate
and, in the absence of exact reference samples, cannot be rigorously benchmarked. Here we present
an exact autoregressive sampling algorithm for planar Ising spin glasses based on the Kac–Ward
theory.Where the paper says it
The Autoregressive Methodology
The method decomposes the Boltzmann distribution into exact conditional probabilities via the chain rule and evaluates them by applying the Kac–Ward determinant formula to an extended planar graph. Crucially, a planarity-preserving auxiliary spin construction is adopted to encode effective boundary fields induced during sequential generation. p. 1 The
method decomposes the Boltzmann distribution into exact conditional probabilities via the chain rule [25, 26]
and evaluates them by applying the Kac–Ward determinant formula [18] to an extended planar graph. Crucially,
we adopt a planarity-preserving auxiliary spin construction that was recently introduced for the exact maximum likelihood decoding of quantum error correction
codes [27, 28] to encode the effective boundary fields induced during the sequential generation (see Fig. We provide a rigorous proof of this planarity preservation in Appendix A. Consequently, the
auxiliary spin construction provides an exact mapping
from the original Ising model with boundary-localized
external fields to a zero-field Ising model on an enlarged
planar graph.Where the paper says it
Where the paper says it
Exact Evaluation via Kac–Ward Theory
The conditional partition functions are mapped to an extended zero-field Ising model and exactly evaluated using the Kac–Ward determinant formula. The method generates strictly i. p. 0 By encoding these
fields with a planarity-preserving auxiliary spin construction, the conditional partition functions are
mapped to an extended zero-field Ising model and exactly evaluated using the Kac–Ward determinant formula. The method generates strictly independent and identically distributed samples with
exact normalized likelihoods at a computational cost of O(N
5/2
) for N spins, thereby providing an
exact baseline for benchmarking neural autoregressive samplers. The
algorithm generates strictly i. samples with a computational complexity of O(N5/2
) for a system of N spins. Data are averaged over 100 independent
runs. The full determinant ratio thus collapses to an r × r determinant, requiring only a single LU factorization of A
per autoregressive step.Where the paper says it
Where the paper says it
Where the paper says it
Validation and Advantages
The algorithm demonstrates efficiency on the 2D Edwards–Anderson (EA) spin glass, where the autocorrelation function satisfies Γ(t) = δt,0, confirming strictly i.i.d. samples. Furthermore, the method allows for direct entropy estimation as an unbiased expectation value over Ns samples. p. 5 6
as an unbiased expectation value over Ns samples:
S = −⟨ln P(s)⟩ ≈ − 1
Ns
X
Ns
i=1
ln P(s
i
). (16)
Figure 4 presents the temperature dependence of the entropy per site for the triangular AFM Ising model with
system sizes L = 8 to 32. sampling, the method
provides direct access to the exact normalized likelihood
and conditional probabilities for every generated configuration. This capability enables unbiased entropy estimation without thermodynamic integration, and the exact likelihoods and unbiased observables provide a rigorous baseline for validating neural autoregressive samplers
on the same planar instances used in variational benchmarks [12, 24, 31]. sampling, the method
provides direct access to the exact normalized likelihood
and conditional probabilities for every generated configuration. This capability enables unbiased entropy estimation without thermodynamic integration, and the exact likelihoods and unbiased observables provide a rigorous baseline for validating neural autoregressive samplers
on the same planar instances used in variational benchmarks [12, 24, 31]. sampling, the method
provides direct access to the exact normalized likelihood
and conditional probabilities for every generated configuration. This capability enables unbiased entropy estimation without thermodynamic integration, and the exact likelihoods and unbiased observables provide a rigorous baseline for validating neural autoregressive samplers
on the same planar instances used in variational benchmarks [12, 24, 31].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Computational Cost and Future Directions
A current limitation is the O(N5/2) computational cost per sample, which restricts applications to systems of moderate size (N ≈ 10 cubed spins). Future directions include GPU-accelerated sparse linear algebra packages to improve efficiency and the use of exact conditional probabilities as per-step teacher signals for on-policy knowledge distillation training. p. 5 Looking forward, several directions can extend the utility of the approach. GPU-accelerated sparse linear algebra packages have the potential to improve the computational efficiency and extend the range of accessible system sizes.Where the paper says it
Appendix A: Proof of Planarity Preservation
The proof relies on the theory of graph minors, showing that the extended graph G′i is a minor of G if the frozen sets Fi are generated via a connected search ordering. This guarantees that G′i must be planar for all i. p. 0 Exact autoregressive sampling of planar Ising spin glasses via the Kac–Ward theory
Jing Liu,1, 2, ∗ Tao Chen,3, 4 Tianrui Che,5 Lei Wang,6 Youjin Deng,3, 4 and Pan Zhang2, 7, †
1School of Physical Science and Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
2
Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China
3Hefei National Laboratory for Physical Sciences at the Microscale and Department of Modern Physics,
University of Science and Technology of China, Hefei 230026, China
4Hefei National Laboratory, University of Science and Technology of China, Hefei 230088, China
5School of Advanced Interdisciplinary Sciences, University of Chinese Academy of Sciences
6Beijing National Laboratory for Condensed Matter Physics and Institute of Physics,
Chinese Academy of Sciences, Beijing 100190, China
7School of Fundamental Physics and Mathematical Sciences,
Hangzhou Institute for Advanced Study, UCAS, Hangzhou 310024, China
Exact sampling from the Boltzmann distribution of spin glasses remains an outstanding challenge:
Markov chain Monte Carlo methods suffer from critical slowing down and metastable trapping, while
modern neural autoregressive samplers such as variational autoregressive networks are approximate
and, in the absence of exact reference samples, cannot be rigorously benchmarked. Here we present
an exact autoregressive sampling algorithm for planar Ising spin glasses based on the Kac–Ward
theory. This condition is strictly satisfied provided that the autoregressive
generation follows a connected search ordering, where the
frozen spins always form a connected subgraph. Under
this condition, the auxiliary spin construction is topologically equivalent to progressively contracting the connected frozen region into a single vertex.Where the paper says it
Where the paper says it
Appendix B: Computational Complexity Analysis
The total sampling complexity is dominated by the early steps where M ∼ N, giving O(N5/2) overall. The condition number of the matrix A = I − BD− diverges exponentially under quenched disorder or geometric frustration. p. 6 S1(b), its condition number remains between 1
and 102
for non-frustrated models (the Ising model and
the triangular FM Ising model). The condition number diverges exponentially under quenched disorder (the
EA spin glass) or geometric frustration (the triangular
AFM Ising model). The condition number diverges exponentially under quenched disorder (the
EA spin glass) or geometric frustration (the triangular
AFM Ising model). The algorithm must therefore employ arbitrary-precision arithmetic to maintain numerical
stability.Where the paper says it
Where the paper says it
Appendix C: Exact Likelihood and Observables
The exact likelihoods and unbiased observables provide direct access to the exact normalized likelihood and conditional probabilities for every generated configuration. This capability enables unbiased entropy estimation without thermodynamic integration. p. 5 sampling, the method
provides direct access to the exact normalized likelihood
and conditional probabilities for every generated configuration. This capability enables unbiased entropy estimation without thermodynamic integration, and the exact likelihoods and unbiased observables provide a rigorous baseline for validating neural autoregressive samplers
on the same planar instances used in variational benchmarks [12, 24, 31].Where the paper says it
Appendix D: Efficient Evaluation of the Determinant Ratio
The full determinant ratio thus collapses to an r × r determinant, requiring only a single LU factorization of A per autoregressive step. This observation allows the full determinant ratio to collapse to an r × r determinant. p. 4 Data are averaged over 100 independent
runs. The full determinant ratio thus collapses to an r × r determinant, requiring only a single LU factorization of A
per autoregressive step. (9)
gives
log Qb+
i
Qb−
i
=
X
b
log
cosh K
+
gb
cosh K
−
gb
+
1
2
log det(I − BD+)
det(I − BD−)
, (13)
where the summation runs over the boundary sites coupled to the auxiliary spin. The key observation is that
h
+
m = h
−
m except on the auxiliary edges adjacent to the
i-th spin itself, so D+ −D− is nonzero only there. Data are averaged over 100 independent
runs. The full determinant ratio thus collapses to an r × r determinant, requiring only a single LU factorization of A
per autoregressive step.Where the paper says it
Where the paper says it
Where the paper says it
Appendix E: Physical Validation
The algorithm validates the method on the triangular ferromagnetic (FM) Ising model, where magnetization and specific heat curves are shown to be free from systematic biases. The exact likelihoods and unbiased observables provide a rigorous baseline for validating neural autoregressive samplers on the same planar instances used in variational benchmarks. The algorithm also provides direct access to the exact normalized likelihood and conditional probabilities for every generated configuration. p. 5 The principal computational advantage over conventional Monte Carlo methods
is the complete elimination of equilibration and autocorrelation overhead. sampling, the method
provides direct access to the exact normalized likelihood
and conditional probabilities for every generated configuration.Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved AI systems can generate strictly independent and identically distributed samples with exact normalized likelihoods at a computational cost of O(N 5/2) for N spins, providing an exact baseline for benchmarking neural autoregressive samplers. This allows for rigorous benchmarking of variational autoregressive networks (VANs) without relying on approximate reference samples.
-
The algorithm provides direct access to the exact normalized likelihood and conditional probabilities for every generated configuration, enabling unbiased entropy estimation without thermodynamic integration. This capability is crucial for accurately estimating residual entropy in systems with geometric frustration, such as the triangular antiferromagnetic Ising model.
-
AI systems can serve as per-step teacher signals for on-policy knowledge distillation training by deterministically computing the conditional probabilities Pi(sis<i) at every generation step. This provides a concrete route to improving variational autoregressive networks by minimizing the variational free energy through such signals, addressing the high gradient variance issue in standard REINFORCE algorithms.
Abstract
Independent samples from the Boltzmann distribution are valuable for estimating spin-glass observables and evaluating approximate sampling methods. Local Markov chain Monte Carlo methods typically generate temporally correlated samples and can encounter critical slowing down or metastable trapping, while neural autoregressive samplers such as variational autoregressive networks generate independent but approximate samples. Here we present an exact autoregressive sampling algorithm for planar Ising spin glasses based on the Kac--Ward theory. Under the chain-rule factorization, sequentially fixing spins induces boundary-localized external fields, which destroy the zero-field structure required for exact evaluation. By encoding these fields with a planarity-preserving auxiliary spin construction, the conditional partition functions are mapped to an extended zero-field Ising model and exactly evaluated using the Kac--Ward determinant formula. The method generates strictly independent and identically distributed samples with exact normalized likelihoods at a computational cost of O(N 5/2) for N spins, thereby providing an exact baseline for benchmarking neural autoregressive samplers.
Sources
- Tensor Network Markov Chain Monte Carlo: Efficient Sampling of Three-Dimensional Spin Glasses and Beyond
- Scalable Physics-Inspired Transformers for Spin Glasses
Related papers
- Emergent long-tail dynamics in driven magnets with dynamical frustration
- Statistical Mechanics of Dynamical System Identification
- Second law of thermodynamics in closed quantum many-body systems
- Chemical potentials from structure factors: II. Charged multi-component mixtures
- Genuine quantum scars in Floquet chaotic many-body systems
- Stochastic Thermodynamics for Autoregressive Generative Models: A Non-Markovian Perspective