A computational phase transition for learning-to-sample from Ising models

Andrej Risteski; Thuy-Duong Vuong

arxiv: 2605.24752 · v1 · pith:BPL7MT5Unew · submitted 2026-05-23 · 💻 cs.LG · cs.CC· cs.DS· math.PR

A computational phase transition for learning-to-sample from Ising models

Andrej Risteski , Thuy-Duong Vuong This is my paper

Pith reviewed 2026-06-30 13:59 UTC · model grok-4.3

classification 💻 cs.LG cs.CCcs.DSmath.PR

keywords Ising modelslearning to samplecomputational hardnessspectral thresholdphase transitiongenerative modelingcryptographic assumptionsbounded width

0 comments

The pith

Ising models of constantly bounded width just beyond the spectral threshold make learning-to-sample computationally hard under cryptographic assumptions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a family of Ising models with constantly bounded width positioned just past the point where λ_max(J) minus λ_min(J) equals 1. It shows that learning to sample from these models remains computationally intractable even when the learner receives polynomially many i.i.d. samples and explicit access to the model parameters. This hardness rests on standard cryptographic assumptions. Prior tractability results below the threshold combine with this construction to establish a sharp phase transition exactly at the spectral threshold. The work also separates learning-to-sample from parameter learning by showing the former can be strictly harder, and proves that any efficient learner on these instances must follow a memorization-hallucination split.

Core claim

We construct a family of Ising models of constantly bounded-width which lie just beyond the spectral threshold λ_max(J)−λ_min(J)=1, and show that learning-to-sample for this family is computationally hard under standard cryptographic assumptions, even when the learner is given both polynomially many i.i.d. samples from the model and explicit access to its parameters.

What carries the argument

The family of constantly bounded-width Ising models lying just beyond the spectral threshold λ_max(J)−λ_min(J)=1, which serves as the target for a reduction from a cryptographic hard problem to the learning-to-sample task.

If this is right

Combined with tractability below the threshold, this pins a sharp computational phase transition for learning-to-sample exactly at λ_max(J)−λ_min(J)=1.
Learning-to-sample is strictly harder than parameter learning for bounded-width Ising models.
Any efficient learner must either output configurations that match the training data after a simple transformation or place substantial mass on configurations of negligible probability under the target.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Access to the explicit parameters does not remove the computational barrier above the threshold.
The memorization-hallucination split offers a precise way to diagnose whether an approximate sampler is succeeding on hard instances.

Load-bearing premise

The constructed family of constantly bounded-width Ising models lies just beyond the spectral threshold and the reduction from a cryptographic hard problem to the learning-to-sample task is valid.

What would settle it

An efficient algorithm that produces approximate samples from these specific Ising models while avoiding both exact matching of transformed training data and assignment of substantial mass to negligible-probability configurations.

read the original abstract

We study \emph{learning-to-sample} -- a basic algorithmic task underlying generative modeling -- for Ising models, a standard testbed for algorithmic ideas in both theoretical computer science and machine learning. Given i.i.d. samples of an unknown target distribution, the goal of learning-to-sample is to learn a computationally efficient generation procedure that produces new samples following approximately the same distribution. We construct a family of Ising models of constantly bounded-width which lie just beyond the spectral threshold $\lambda_{\max}(J)-\lambda_{\min}(J)=1$, and show that learning-to-sample for this family is computationally hard under standard cryptographic assumptions, even when the learner is given both polynomially many i.i.d. samples from the model and explicit access to its parameters. Combined with results of [AJKPV24,KLV25] showing tractability of learning-to-sample below the spectral threshold, this establishes a sharp computational phase transition at the spectral threshold. Moreover, combined with prior results on parameter learning for bounded-width Ising models [KM17,WSD19,VML20], this shows that learning-to-sample can be more difficult than parameter learning. Finally, we show that any efficient learner for these hard instances exhibits a natural memorization-hallucination dichotomy: the learner must either output configurations that, after a simple transformation, match the (transformed) training data or place substantial mass on configurations of negligible probability under the target distribution.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a clean crypto-based hardness result for learning-to-sample on constant-width Ising models just above the spectral threshold, matching known tractability below it and adding a memorization-hallucination split.

read the letter

The core contribution is a family of constantly bounded-width Ising models placed just past λ_max(J) - λ_min(J) = 1, where learning-to-sample remains hard even with both samples and explicit parameters, under standard cryptographic assumptions. This pairs with the tractability results from AJKPV24 and KLV25 to mark a sharp threshold. They also separate this task from parameter learning on the same models and show that any efficient learner must either reproduce transformed training data or put mass on negligible-probability states.

The construction and reduction appear new relative to the cited work on tractability and parameter estimation. The bounded-width property and the external crypto assumption keep the argument from being circular. The memorization-hallucination observation is a useful byproduct that clarifies what efficient learners can actually achieve on the hard side.

The main limitation is that the abstract and stress-test note give no explicit interaction matrix or reduction steps, so the constant-width claim and the precise gap in the reduction cannot be inspected directly. If the construction slips on the width bound or the reduction has a loose step, the threshold result weakens, but nothing in the given material indicates that has happened. The crypto assumption itself is standard and external.

This is aimed at researchers working on generative modeling primitives and on Ising models as algorithmic testbeds. It supplies a parameter-free computational cutoff that should affect both algorithm design and model selection. The work shows clear engagement with the literature and deserves referee time even if the proofs need tightening.

Referee Report

0 major / 2 minor

Summary. The paper claims a sharp computational phase transition for the learning-to-sample task on Ising models exactly at the spectral threshold λ_max(J)−λ_min(J)=1. It constructs a family of constantly bounded-width Ising models lying just beyond this threshold and proves that learning-to-sample remains computationally hard for this family under standard cryptographic assumptions, even when the learner receives polynomially many i.i.d. samples together with explicit access to the model parameters. The hardness result is paired with prior tractability theorems below the threshold and with a memorization-hallucination dichotomy that any efficient learner must satisfy on the hard instances.

Significance. If the stated construction and cryptographic reduction hold, the work supplies the first explicit computational separation between the tractable and intractable regimes for learning-to-sample on Ising models, demonstrates that the task can be strictly harder than parameter learning even for bounded-width models, and isolates a concrete behavioral dichotomy (memorization versus hallucination) forced on any efficient algorithm. The reduction to external cryptographic assumptions avoids circularity and the matching positive results from prior literature make the phase-transition claim sharp.

minor comments (2)

The abstract cites [AJKPV24,KLV25] and [KM17,WSD19,VML20] for the matching tractability and parameter-learning results; the manuscript should include a short self-contained paragraph in the introduction that recalls the precise statements of those theorems that are being invoked.
Notation for the interaction matrix J and the spectral gap λ_max(J)−λ_min(J) is introduced in the abstract but should be restated with a displayed equation in §2 before any hardness construction is presented.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary of the paper and for recognizing the significance of establishing a sharp computational phase transition for learning-to-sample on bounded-width Ising models. The report does not list any specific major comments requiring point-by-point responses.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The central claim constructs a new family of constantly bounded-width Ising models beyond the spectral threshold and reduces hardness of learning-to-sample to standard external cryptographic assumptions, with tractability below the threshold supported by independent prior results [AJKPV24,KLV25] and parameter-learning comparisons citing external works [KM17,WSD19,VML20]. No self-definitional relations, fitted parameters renamed as predictions, or load-bearing self-citations appear; the derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the validity of standard cryptographic hardness assumptions and on the existence of the stated family of bounded-width Ising models; no free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Standard cryptographic assumptions (e.g., existence of one-way functions or similar primitives sufficient for the reduction)
Hardness is stated to hold under these assumptions; the abstract does not specify which exact primitive is used.

pith-pipeline@v0.9.1-grok · 5793 in / 1404 out tokens · 46905 ms · 2026-06-30T13:59:43.914605+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

8 extracted references · 4 canonical work pages

[1]

ISBN 9783540853626

Springer-Verlag. ISBN 9783540853626. doi: 10.1007/978-3-540-85363-3 27. URL https: //doi.org/10.1007/978-3-540-85363-3_27 . Dan Boneh and Xavier Boyen. Short signatures without random oracles. In Christian Cachin and Jan L. Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004 , pages 56–73, Berlin, Heidelberg,

work page doi:10.1007/978-3-540-85363-3 2004
[2]

ISBN 978-3-540-24676-3

Springer Berlin Heidelberg. ISBN 978-3-540-24676-3. Dan Boneh and Matthew Franklin. Identity-based encryption from the Weil pairing. In Advances in Cryp- tology—CRYPTO 2001 , pages 213–229. Springer, 2001. doi: 10.1007/3-540-44647-8 13. Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the weil pairing. In Proceedings of the 7th International ...

work page doi:10.1007/3-540-44647-8 2001
[3]

45 Ankur Moitra, Elchanan Mossel, and Colin P Sandon

URL https://arxiv.org/abs/2411.09117. 45 Ankur Moitra, Elchanan Mossel, and Colin P Sandon. Learning to sample from censored markov random fields. In Conference on Learning Theory, pages 3419–3451. PMLR, 2021. Andrea Montanari and Viet Vu. Computational bottlenecks for denoising diffusions.ArXiv, abs/2503.08028,

work page arXiv 2021
[4]

David Pointcheval and Olivier Sanders

URL https://api.semanticscholar.org/CorpusID:276928563. David Pointcheval and Olivier Sanders. Short randomizable signatures. In Cryptographers’ Track at the RSA Conference, pages 111–126. Springer, 2016. David Pointcheval and Olivier Sanders. Reassessing security of randomizable signatures. In Nigel P. Smart, editor, Topics in Cryptology – CT-RSA 2018 , ...

work page doi:10.1016/0890-5401(89)90067-9 2016
[5]

The biases of i and j are increased by w
[6]

If there is no edge between i and j in G, this means add an edge of weight −w between i and j

Decrease the weight of the edge between i and j by w. If there is no edge between i and j in G, this means add an edge of weight −w between i and j
[7]

Finally, G′ has a new vertex k which has a bias of 2w, is connected to i and j by edges of weight −2w, and has no other edges. For a circuit C on n input bits consisting of r NAND gates, let GC,w be the weighted graph on n + r vertices constructed by applying the above procedure to each NAND gate, starting from the empty graph on n vertices. Proof of Lemm...
[8]

Note that f ′′ β (α) > 0 for α ∈ (α−, α+) and f ′′ β (α) < 0 for α ∈ (α+, 1) ∪ (0, α−)

where α+ + α− = 1. Note that f ′′ β (α) > 0 for α ∈ (α−, α+) and f ′′ β (α) < 0 for α ∈ (α+, 1) ∪ (0, α−). Note also that f ′ β(1/2) = 0 and f ′′ β (α) > 0 for α ∈ (α−, α+) hence f ′ β(α+) > 0 and f ′ β(α−) < 0. Next, since limα→1− f ′ β(α) = −∞ and f ′ β(α) is strictly decreasing in (α+, 1), the intermediate value theorem implies that there exists a uniq...

[1] [1]

ISBN 9783540853626

Springer-Verlag. ISBN 9783540853626. doi: 10.1007/978-3-540-85363-3 27. URL https: //doi.org/10.1007/978-3-540-85363-3_27 . Dan Boneh and Xavier Boyen. Short signatures without random oracles. In Christian Cachin and Jan L. Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004 , pages 56–73, Berlin, Heidelberg,

work page doi:10.1007/978-3-540-85363-3 2004

[2] [2]

ISBN 978-3-540-24676-3

Springer Berlin Heidelberg. ISBN 978-3-540-24676-3. Dan Boneh and Matthew Franklin. Identity-based encryption from the Weil pairing. In Advances in Cryp- tology—CRYPTO 2001 , pages 213–229. Springer, 2001. doi: 10.1007/3-540-44647-8 13. Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the weil pairing. In Proceedings of the 7th International ...

work page doi:10.1007/3-540-44647-8 2001

[3] [3]

45 Ankur Moitra, Elchanan Mossel, and Colin P Sandon

URL https://arxiv.org/abs/2411.09117. 45 Ankur Moitra, Elchanan Mossel, and Colin P Sandon. Learning to sample from censored markov random fields. In Conference on Learning Theory, pages 3419–3451. PMLR, 2021. Andrea Montanari and Viet Vu. Computational bottlenecks for denoising diffusions.ArXiv, abs/2503.08028,

work page arXiv 2021

[4] [4]

David Pointcheval and Olivier Sanders

URL https://api.semanticscholar.org/CorpusID:276928563. David Pointcheval and Olivier Sanders. Short randomizable signatures. In Cryptographers’ Track at the RSA Conference, pages 111–126. Springer, 2016. David Pointcheval and Olivier Sanders. Reassessing security of randomizable signatures. In Nigel P. Smart, editor, Topics in Cryptology – CT-RSA 2018 , ...

work page doi:10.1016/0890-5401(89)90067-9 2016

[5] [5]

The biases of i and j are increased by w

[6] [6]

If there is no edge between i and j in G, this means add an edge of weight −w between i and j

Decrease the weight of the edge between i and j by w. If there is no edge between i and j in G, this means add an edge of weight −w between i and j

[7] [7]

Finally, G′ has a new vertex k which has a bias of 2w, is connected to i and j by edges of weight −2w, and has no other edges. For a circuit C on n input bits consisting of r NAND gates, let GC,w be the weighted graph on n + r vertices constructed by applying the above procedure to each NAND gate, starting from the empty graph on n vertices. Proof of Lemm...

[8] [8]

Note that f ′′ β (α) > 0 for α ∈ (α−, α+) and f ′′ β (α) < 0 for α ∈ (α+, 1) ∪ (0, α−)

where α+ + α− = 1. Note that f ′′ β (α) > 0 for α ∈ (α−, α+) and f ′′ β (α) < 0 for α ∈ (α+, 1) ∪ (0, α−). Note also that f ′ β(1/2) = 0 and f ′′ β (α) > 0 for α ∈ (α−, α+) hence f ′ β(α+) > 0 and f ′ β(α−) < 0. Next, since limα→1− f ′ β(α) = −∞ and f ′ β(α) is strictly decreasing in (α+, 1), the intermediate value theorem implies that there exists a uniq...