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

A new theoretical study identifies a sharp computational boundary for learning-to-sample from Ising models, a foundational task in generative modeling. The work proves the problem becomes computationally hard once a specific spectral threshold is crossed, even with full access to model parameters and training data [1]. The paper, submitted in 2026, examines learning-to-sample, where an algorithm must produce new configurations that mimic an unknown target distribution after seeing independent samples [1]. Ising models serve as the testbed. Originally devised in 1920 by Wilhelm Lenz and given to student Ernst Ising, these models represent magnetic spins on a graph that interact with neighbors; the two-dimensional version was famously solved by Lars Onsager in 1944 and is one of the simplest systems to exhibit a phase transition [3]. The models remain a standard benchmark for algorithmic ideas in theoretical computer science and machine learning [2]. The authors construct a family of constantly bounded-width Ising models positioned just beyond the spectral threshold defined by the difference between the maximum and minimum eigenvalues of the interaction matrix equaling 1 [1]. Below this threshold, prior work by AJKPV24 and KLV25 established that learning-to-sample is tractable [2]. The new result demonstrates that crossing the threshold renders the task computationally hard under standard cryptographic assumptions, establishing a sharp computational phase transition [1]. The hardness holds even when the learner receives polynomially many independent samples and explicit access to the model’s parameters [2]. This finding also separates learning-to-sample from the related problem of parameter learning. Earlier results by KM17, WSD19, and VML20 showed that parameter learning for bounded-width Ising models is achievable [2]. The new work reveals that learning-to-sample can be strictly more difficult, as the hard instances are drawn from a regime where parameters are known but efficient sampling remains out of reach [1]. The study further characterizes the failure modes of any efficient learner on these hard instances through a memorization-hallucination dichotomy. The learner must either produce configurations that, after a simple transformation, match the transformed training data, or place substantial probability mass on configurations that have negligible probability under the true target distribution [1]. This behavior echoes challenges seen in broader generative modeling, where models can memorize training examples or generate implausible outputs. Ising models also connect to spin glasses, disordered magnetic systems with frustrated interactions that are widely studied for their complex metastable structures and applications to neural networks [5]. The computational phase transition identified here adds a rigorous layer to understanding when efficient generation is possible and when it fundamentally breaks down.