REVIEW 3 major objections 4 minor 23 references
Polynomial-time sampling despite disorder chaos
T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Transport disorder chaos does not preclude polynomial-time sampling: on $G(n,1/2)$, Glauber dynamics samples the hardcore model in Wasserstein distance in $O(n)$ steps.
desk verdict Genuinely new and mostly sound, but Theorem 1.3's stated stopping cap is off by an exponential and must be fixed before publication. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument rests on two combinatorial quantities. For an independent set $S$, the up-degree $\deg^\uparrow(S)$ counts the vertices outside $S$ that can be added while keeping the set independent, and the $\ell$-up-degree $\deg^\uparrow_\ell(S)$ counts the independent sets of size $\ell$ in the non-neighborhood of $S$. Concentration of up-degrees (Lemma 5.2) lets the authors couple Glauber dynamics to the RandomGreedy algorithm, which repeatedly adds a uniformly random available vertex. Concentration of $\ell$-up-degrees (Lemma 5.6) shows that every small independent set extends to nearly the same number of larger ones; this uniformity is what turns a greedy sample into a Wasserstein-close
What would settle it
Fix a graph from $G(n,1/2)$ and enumerate all independent sets of size $k^-=\log n-C\log\log n$; for each, count the independent sets of size $\log n-\log\log n$ containing it. Lemma 5.6 predicts these extension counts agree within a factor $1\pm 1/\log\log n$. Finding two small independent sets whose extension counts differ by a constant factor would break the Theorem 5.7 coupling and the sampling theorem. For the disorder-chaos half, compute the normalized $W_2$ distance between the hardcore measures on two graphs correlated by edge-resampling probability $s=1/\log n$; Theorem 1.2 predicts t
Extended reading notes
Core claim
On a random graph $\boldsymbol{G} \sim G(n,1/2)$ at fugacity $\lambda=1$, the hardcore model $\mu_{\boldsymbol{G}}$ — the uniform measure over independent sets — has two seemingly conflicting properties. Theorem 1.2 shows it exhibits transport disorder chaos: if $\boldsymbol{G}'$ is obtained by resampling each edge of $\boldsymbol{G}$ with probability $s \in (0,1)$, then the normalized 2-Wasserstein distance between $\mu_{\boldsymbol{G}}$ and $\mu_{\boldsymbol{G}'}$ tends to 2, the maximum possible value, even as $s \to 0$. Theorem 1.3 shows that Glauber dynamics, started at the empty set and stopped on first hitting an independent set of size $k = \log n - 30 \log \log n$ (or a polynomial t
Load-bearing premise
The load-bearing premise is Lemma 5.6: with high probability, every independent set of size $\log n - C\log\log n$ in $G(n,1/2)$ extends to the same number of slightly larger independent sets up to a $1/\log\log n$ factor; if that uniformity fails, the Wasserstein coupling collapses, and the lemma's stated proof uses a $d$-th moment with $d=\log^5 n/\ell$ even though $d$ must be even.
Editorial extensions
If this is right
- Disorder chaos is not a general barrier to canonical polynomial-time sampling: Glauber dynamics is not 'smooth' in the stability-based sense, so disorder-chaos lower bounds do not rule it out.
- The hardcore model on $G(n,1/2)$ at $\lambda=1$ is approximable in Wasserstein distance by $O(n)$ steps of Glauber dynamics, in a regime with no previously known polynomial-time sampler and where total-variation sampling remains open.
- Wasserstein sampling succeeds in a regime inaccessible to known total-variation samplers: the independent sets produced are within a factor $1/2$ of optimal size, whereas known total-variation algorithms on sparse random graphs reach only a factor $1/4$.
- Lemma 5.6 establishes strong concentration of extension counts for all small independent sets, a structural fact that can support further average-case sampling arguments.
Reading between the lines
- If the extension-count concentration extends to sparse $G(n,d/n)$ at the appropriate sizes, the same greedy-and-extend coupling could yield polynomial-time Wasserstein sampling there, potentially informing the open question of total-variation mixing up to the reconstruction threshold.
- The survival argument suggests a general recipe for disorder chaos: any measure concentrated on large structures that random noise destroys — large independent sets, large cuts, planted partitions — will exhibit transport disorder chaos; this could be tested in other dense random models.
- One might conjecture that Glauber dynamics at $\lambda=1$ on $G(n,1/2)$ actually samples in total variation as well; the Wasserstein result does not prove this, but it removes some of the motivation for believing total-variation mixing is needed for efficient sampling.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the hardcore model at fugacity 1 on G(n,1/2). It argues that the model exhibits transport disorder chaos (Theorem 1.2), yet a canonical Glauber-dynamics chain can approximately sample from the model in normalized 2-Wasserstein distance in polynomial time (Theorem 1.3). The proof strategy is self-contained: Section 3 proves concentration of the number of k-independent sets; Section 4 proves disorder chaos via a survival analysis of independent sets under edge resampling; Section 5 couples Glauber dynamics with a RandomGreedy algorithm, proves TV closeness to the uniform measure over independent sets of size k^- = log n - C log log n, and then uses concentration of ℓ-up-degrees to extend a k^- sample to a near-uniform sample of the larger independent sets that dominate the hardcore measure. The paper concludes that disorder chaos is not, by itself, a barrier to polynomial-time sampling by canonical algorithms.
Significance. If the main results are correct, this is an important conceptual contribution: it directly challenges the use of transport disorder chaos as evidence of average-case sampling hardness, and it shows that Glauber dynamics, a canonical non-smooth algorithm, succeeds in a regime where disorder chaos is present. The proofs are mostly elementary and avoid fitted parameters; the concentration arguments for independent-set counts and extension degrees are explicit and checkable. The paper is also cleanly written and the self-contained treatment makes the core ideas accessible. However, as discussed in the major comments, the main theorem as stated contains a quantitative stopping-time error and the algorithm pseudocode has a correctness bug; these must be fixed before the result can be accepted.
major comments (3)
- [§1.1, Theorem 1.3; §5.1, Theorem 5.3] The stopping time in Theorem 1.3 is printed as τ = min{100(log n)^2 k, τ_k}. For k = log n - 30 log log n this cap is ~100 log^3 n. On G(n,1/2), the up-degree of an independent set of size i is ≈ (n-i)2^{-i}, so the expected time to add a vertex at size i is Θ(2^i), and the expected hitting time to size k is Θ(2^k) = Θ(n/log^{30} n). Thus the chain almost surely hits the cap long before τ_k, and the output has size O(log log n), not k, so the stated Wasserstein guarantee fails. This is not a cosmetic issue: the proof in §5.1, Theorem 5.3, uses T ≥ 100·2^s·log n, which for s=k is Θ(n log n/log^{30} n), consistent with the abstract's O(n) claim but incompatible with the theorem statement. The theorem statement must be corrected to use the O(n) cap (or equivalently the cap from Theorem 5.3).
- [§5.1, Algorithm 1] The pseudocode for Glauber dynamics is incorrect as written. Lines 4–7 set S_t = S_{t-1} when S_{t-1} ∪ v is not independent, but then unconditionally execute `S_t ∼ Unif{S_{t-1}∪v, S_{t-1}\v}`. This allows a transition to S_{t-1}∪v even when that set is not independent, breaking the invariant that the chain stays on independent sets. The standard dynamics should be: if v∈S_t, remove v with probability 1/2; else if S_t∪v is independent, add v with probability 1/2; otherwise stay. The prose describes the correct chain, and the coupling in Theorem 5.3 relies on the correct chain, so this is a fixable but essential bug in the stated algorithm.
- [§5.3, Lemma 5.6] The proof of Lemma 5.6 uses a d-th moment argument and explicitly states 'For any even d', but then sets d = log^D n / ℓ without addressing integrality or parity. Since d need not be an even integer, the Markov bound and moment computation are not valid as written. This is fixable by taking, e.g., d = 2⌊log^D n/(2ℓ)⌋, which changes exponents by at most O(1), but the adjustment should be stated. Because Lemma 5.6 is the key concentration input for the extension-count coupling in Theorem 5.7, the proof is incomplete until this gap is closed.
minor comments (4)
- [§4, proof of Lemma 4.1] In the proof, the notation 'β n' appears in expressions such as 'k*−βn' and 'k*+βn' where β is a constant and the intended quantity is clearly β log n. Please correct these to β log n.
- [§5.2, Theorem 5.4] The statement says 'run for time k' but Algorithm 2 is an iterative procedure that runs for k iterations, not for a time parameter. Please rephrase to 'run for k steps' or 'run with size parameter k' to match the pseudocode.
- [§3, proof of Lemma 3.1] The expression 'O(2^{-a} Z*_k)' uses Z^*_k without definition; presumably this is Z_{k*}. Please define or correct the notation.
- [§1.1, Theorem 1.3] There is a typographical extra parenthesis in the definition of τ: 'min{100(log n)^2k), τ_k}' should read 'min{100(log n)^2 k, τ_k}'.
Circularity Check
No significant circularity: the main theorems are derived from in-paper concentration arguments; a minor self-citation and a stopping-time bug are noted but are not circular reductions.
full rationale
The paper's derivation chain is self-contained. Theorem 1.2 (disorder chaos) is proved from in-paper lemmas on the concentration of independent-set counts (Lemmas 3.1, 3.2, 3.3) and on the concentration of the second moment (Lemma 4.1), followed by a direct calculation of the normalized Wasserstein distance. Theorem 1.3 (sampling) is proved by coupling Glauber dynamics with RandomGreedy (Theorem 5.3), showing RandomGreedy samples near-uniformly in total variation over k^- cliques (Theorem 5.4), and then constructing a Wasserstein coupling using the concentration of extension counts (Lemma 5.6 and Theorem 5.7). No fitted parameter is renamed as a prediction, and no equation reduces by construction to the target statement. The only self-citation, [LS24] by Li and Schramm, appears in the introduction as related work and is not load-bearing for the main results. Two genuine non-circular issues exist. First, the stopping cap in Theorem 1.3 is printed as min{100(log n)^2 k, tau_k}; for k = log n - 30 log log n this is about 100 log^3 n, whereas the paper's own Theorem 5.3 requires T >= 100*2^s*log n, which is Theta(n/log^{29} n), and the expected time to reach size k is Theta(2^k) = Theta(n/log^{30} n). Thus the theorem statement appears quantitatively wrong as written, but this is a correctness bug, not a circular reduction. Second, Lemma 5.6 chooses d = log^5 n / ell without addressing the integrality/evenness of d, a technical gap that is also not circular. Overall, the central derivations are independent of their conclusions.
Assumptions & free parameters
assumptions (5)
- standard math Standard probabilistic inequalities: second moment method, Chernoff bounds, FKG inequality, Stirling's approximation.
- domain assumption The hardcore model at fugacity 1 is the uniform distribution over independent sets of the graph.
- domain assumption Glauber dynamics on the hardcore model has stationary distribution equal to the hardcore measure.
- domain assumption The noise operator T_{1-s} resamples each edge independently with probability s, preserving the marginal G(n,1/2) distribution.
- domain assumption Lemma 2.3 (time reversal preserves the measure) applies to the bipartite extension graph H in Section 5.3.
Cite this review
Pith. "Pith review of Polynomial-time sampling despite disorder chaos." pith.science (2026). https://pith.science/paper/FVHVSMV6
@misc{pith2026250804133,
author = {Pith},
title = {Pith review of: Polynomial-time sampling despite disorder chaos},
year = {2026},
howpublished = {\url{https://pith.science/paper/FVHVSMV6}},
note = {Machine review of arXiv:2508.04133}
}
abstract
A distribution over instances of a sampling problem is said to exhibit transport disorder chaos if perturbing the instance by a small amount of random noise dramatically changes the stationary distribution (in Wasserstein distance). Seeking to provide evidence that some sampling tasks are hard on average, a recent line of work has demonstrated that disorder chaos is sufficient to rule out "stable" sampling algorithms, such as gradient methods and some diffusion processes. We demonstrate that disorder chaos does not preclude polynomial-time sampling by canonical algorithms in canonical models. We show that with high probability over a random graph $\boldsymbol{G} \sim G(n,1/2)$: (1) the hardcore model (at fugacity $\lambda = 1$) on $\boldsymbol{G}$ exhibits disorder chaos, and (2) Glauber dynamics run for $O(n)$ time can approximately sample from the hardcore model on $\boldsymbol{G}$ (in Wasserstein distance).
Reference graph
Works this paper leans on
-
[1]
Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster
Emmanuel Abbe, Shuangping Li, and Allan Sly. Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 860--873, 2022
work page 2022
-
[2]
The probabilistic method
Noga Alon and Joel H Spencer. The probabilistic method . John Wiley & Sons, 2016
2016
-
[3]
Spectral gap estimates in mean field spin glasses
G \'e rard Ben Arous and Aukosh Jagannath. Spectral gap estimates in mean field spin glasses. Communications in Mathematical Physics , 361:1--52, 2018
work page 2018
-
[4]
Fast sampling via spectral independence beyond bounded-degree graphs
Ivona Bez \'a kov \'a , Andreas Galanis, Leslie Ann Goldberg, and Daniel S tefankovi c . Fast sampling via spectral independence beyond bounded-degree graphs. ACM Transactions on Algorithms , 20(1):1--26, 2024
work page 2024
-
[5]
On-line balancing of random inputs
Nikhil Bansal and Joel H Spencer. On-line balancing of random inputs. Random Structures & Algorithms , 57(4):879--891, 2020
work page 2020
-
[6]
Decay of correlations for the hardcore model on the d-regular random graph
Nayantara Bhatnagar, Allan Sly, and Prasad Tetali. Decay of correlations for the hardcore model on the d-regular random graph. Electronic Journal of Probability , 21, 2016
work page 2016
-
[7]
Rapid mixing on random regular graphs beyond uniqueness
Xiaoyu Chen, Zejia Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang. Rapid mixing on random regular graphs beyond uniqueness. arXiv preprint arXiv:2504.03406 , 2025
arXiv 2025
-
[8]
Sudakov-- F ernique post- AMP , and a new proof of the local convexity of the TAP free energy
Michael Celentano. Sudakov-- F ernique post- AMP , and a new proof of the local convexity of the TAP free energy. The Annals of Probability , 52(3):923--954, 2024
work page 2024
Show all 23 references
-
[9]
Hardness of sampling solutions from the symmetric binary perceptron
Ahmed El Alaoui and David Gamarnik. Hardness of sampling solutions from the symmetric binary perceptron. arXiv preprint arXiv:2407.16627 , 2024
2024 arXiv
-
[10]
Sampling from the S herrington- K irkpatrick G ibbs measure via algorithmic stochastic localization
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Sampling from the S herrington- K irkpatrick G ibbs measure via algorithmic stochastic localization. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science ( FOCS ) , pages 323--334. IEEE , 2022
2022
-
[11]
Sampling from mean-field G ibbs measures via diffusion processes
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Sampling from mean-field G ibbs measures via diffusion processes. arXiv preprint arXiv:2310.08912 , 2023
2023
-
[12]
Shattering in pure spherical spin glasses
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Shattering in pure spherical spin glasses. Communications in Mathematical Physics , 406(5):1--36, 2025
2025
-
[13]
On the mixing time of G lauber dynamics for the hard-core and related models on g(n, d/n)
Charilaos Efthymiou and Weiming Feng. On the mixing time of G lauber dynamics for the hard-core and related models on g(n, d/n) . In 50th International Colloquium on Automata, Languages, and Programming ( ICALP 2023) , pages 54--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Inf...
2023
-
[14]
The overlap gap property: A topological barrier to optimizing over random structures
David Gamarnik. The overlap gap property: A topological barrier to optimizing over random structures. Proceedings of the National Academy of Sciences , 118(41):e2108492118, 2021
2021
-
[15]
Sampling from spherical spin glasses in total variation via algorithmic stochastic localization
Brice Huang, Andrea Montanari, and Huy Tuan Pham. Sampling from spherical spin glasses in total variation via algorithmic stochastic localization. arXiv preprint arXiv:2404.15651 , 2024
2024 arXiv
-
[16]
Hardness of sampling for the anti-ferromagnetic I sing model on random graphs
Neng Huang, Will Perkins, and Aaron Potechin. Hardness of sampling for the anti-ferromagnetic I sing model on random graphs. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) , pages 61--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2025
2025
-
[17]
Fast mixing in sparse random ising models
Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman, and David X Wu. Fast mixing in sparse random ising models. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science ( FOCS ) , pages 120--128. IEEE , 2024
2024
-
[18]
Markov chains and mixing times , volume 107
David A Levin and Yuval Peres. Markov chains and mixing times , volume 107. American Mathematical Soc., 2017
2017
-
[19]
Some easy optimization problems have the overlap-gap property
Shuangping Li and Tselil Schramm. Some easy optimization problems have the overlap-gap property. arXiv preprint arXiv:2411.01836 , 2024
2024 arXiv
-
[20]
Optimization of the S herrington-- K irkpatrick H amiltonian
Andrea Montanari. Optimization of the S herrington-- K irkpatrick H amiltonian. SIAM Journal on Computing , (0): FOCS 19--1, 2021
2021
-
[21]
Combinatorics and graph theory 1 & 2
Irena Penev. Combinatorics and graph theory 1 & 2. 2022
2022
-
[22]
Phase transition for G lauber dynamics for independent sets on regular trees
Ricardo Restrepo, Daniel Stefankovic, Juan C Vera, Eric Vigoda, and Linji Yang. Phase transition for G lauber dynamics for independent sets on regular trees. SIAM Journal on Discrete Mathematics , 28(2):835--861, 2014
2014
-
[23]
Following the ground states of full- RSB spherical spin glasses
Eliran Subag. Following the ground states of full- RSB spherical spin glasses. Communications on Pure and Applied Mathematics , 74(5):1021--1044, 2021
2021
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.