acceptodds
Under review as a conference paper at ICLR 2027

Exactness, Criticality, and Memory in Mean-Field Sampling

Abstract

How much information must a sequential generator retain after it has emitted part of a sample? We answer this question for rank-one quadratic Gibbs distributions in a write-only, finite-state interface with a free clock and read-only transition kernels. For every nonzero coupling and arbitrary finite external fields, the minimum state count at a cut is the smaller number of attainable weighted sums on its two sides. A single stochastic generator simultaneously attains these cutwise lower bounds by switching from a prefix sum to a sampled suffix sum. In the homogeneous Curie–Weiss model, exact generation consequently needs states at every nonzero coupling. Allowing fixed total-variation error produces a different classification: the optimal width is at criticality and at each fixed positive noncritical coupling. The critical lower bound uses a robust near-diagonal mixture inequality, while the upper bound quantizes a Gaussian auxiliary field. Finally, arbitrarily small dyadic heterogeneity can raise exact memory to bits without changing the fixed-error classification. These results separate algebraic distinguishability from statistically necessary memory; they do not bound uniform implementation time or arithmetic workspace.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
sequential sampling, memory complexity, Curie-Weiss model, criticality, finite-state generators

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_7pQ6OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The authors study the memory required t generate a distribution P over n spins, focusing on the Curie-Weiss model. They define KϵK_\epsilon as the minimal number of hidden states of a time-inhomogeneous HMM that generates a distribution Q within total variation distance ϵ\epsilon of P. For exact generation (ϵ=0\epsilon = 0), they show that K0K_0 equals the maximal cut rank, and construct a generator attaining it. For fixed ϵ>0\epsilon > 0, they show that Kϵ=Θ(n1/4)K_\epsilon = \Theta(n^{1/4}) at the critical point β=1\beta = 1, whereas Kϵ=O(1)K_\epsilon = O(1) at any fixed noncritical β\beta.

Critical strengths

The fixed-ϵ\epsilon scaling Kϵ=Θ(n1/4)K_\epsilon = \Theta(n^{1/4}) at criticality, versus O(1)O(1) away from criticality, is an interesting and potentially novel result.

Critical weaknesses

The authors seem largely unaware of the large relevant literature on closely related problems, including minimal and positive realization of HMMs (e.g., Anderson 1999; Huang, Ge, Kakade & Dahleh 2014), computational mechanics (Shalizi & Crutchfield 2001), predictive state representations (Singh, James & Rudary 2004), and the memory required for approximate prediction (Sharan, Kakade, Liang & Valiant 2018). Many results recover standard ones: the cut-rank bound (Lemma 7) is the classical HMM realization bound, and Thm 2 is its specialization to this family; the observation in App. E that counting distinct conditional laws does not lower-bound non-unifilar generators is the distinction between statistical and generative complexity; and the discontinuity of exact complexity under small perturbations (Thm 5) is well known. Given lack of literature review in other areas, it is unclear to what extend the scaling result rediscover existing bounds on Curie-Weiss.

Finally, the paper is very hard to read. It seems written by AI and uses non-standard terminology (e.g., "retained-state generator with a free clock and read-only kernels" for a time-inhomogeneous HMM) and various disclaimers in place of explanation. The connection to ICLR topics is also thin.

Questions for authors

No questions that would change my assessment.

Suggestions for future work:

  • The authors may want to look into Bialek, Nemenman & Tishby 2001, I feel like the O(n^1/4) scaling is related to their analysis of scaling of mutual information.
  • Relating the results to learned autoregressive models (HMMs, RNNs/state-space models, etc.) would make the work more relevant to ICLR.
Reviewer_YaSiOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper considers a toy model for generative machine learning: a "sequential generator" that is designed to output a sequence of nn binary values (spins x=±1x = \pm 1), such that the probability of a particular sequence closely approximates a target probability distribution PP. At any given point in the sequence the generator has some internal state ss (chosen from some finite alphabet of states), and there is a transition kernel that describes the probability of producing the next spin x′x' while the internal state switches from s→s′s \to s'. To approximate a given PP, the generator may only end up visiting a subset of states at any point in the sequence (over the ensemble of all realizable state trajectories). One can define the "memory" size as the size of the largest such subset over the whole sequence. This is a measure of the complexity of the generator, and depends on whether the target distribution is mimicked perfectly, or whether there is some tolerance for errors. The paper solves this problem for a specific PP distribution: that corresponding to a mean-field (rank = 1) Ising model (essentially a model where the spin-spin coupling wijw_{ij} factors as wij=wiwjw_{ij} = w_i w_j). It finds the memory sizes for both the exact and error-tolerance cases, and tests these results with numerical examples.

Critical strengths

The paper may have interesting or novel contributions, but these are essentially impossible to discern because of the impenetrable, densely technical text (see details below). The summary above is a rough attempt at trying to translate the results into understandable terms, but this is just a best guess because the underlying ideas are difficult to salvage from a sea of jargon.

Critical weaknesses

From the first sentences of the abstract, the paper is extremely difficult to follow. The authors describe extensive use of LLMs in their AI Use Statement, and the prose displays all of the worst hallmarks of AI-generated technical write-ups, with little evidence of human intervention. There are no attempts to explain the concepts in broadly accessible terms, even though the underlying system is fairly interesting and could easily be explained to a wide audience (including computer scientists, physicists, and mathematicians, who have all considered analogous systems in different contexts).

Beyond the issues with presentation, there is very little motivation or explanation of significance: what is the point of calculating memory bounds for this particular sequential generator with this specific target distribution? Does it teach us anything interesting about the problem more generally (for wider families of targets), or does it have any practical significance in specific applications? The reader is left in the dark on all of these questions.

Questions for authors
  1. Can you revise your text in a way that makes it more accessible to a broad audience? Given the relentless impenetrability of the current version, this would require a total overhaul, not just minor cosmetic changes. I would recommend starting with a pedagogical description of the generator system (an illustration would be very helpful) with a small alphabet and small nn. Walk the reader through how this system operates, what the purpose is, and how one defines memory. The detailed technical aspects are fine for appendices, but the main text should be much more readable than the current version.

  2. Can you explain the significance of solving this version of the problem, with this particular form of the target distribution? What do we learn from this exercise?

Reviewer_YcFDOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes a theory of rank-one quadratic Gibbs distributions; the main result bounds the critical width as n^0.25.

Critical strengths

The theory seems to be sound.

Critical weaknesses

This paper seems clearly out of scope for ICLR. It's not clear what this has to do with machine learning or statistical inference. No machine learning papers are cited except for an Ising model reference at COLT (which is only referenced as "related transforms support efficient low-rank Ising sampling (Koehler et al., 2022)") : no ICLR papers are cited.

Questions for authors

How is this work connected to ICLR and to the machine learning community?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.