{"id":"f836604f-c96b-4a50-ab9b-f5e910bc4e46","arxiv_id":"2505.05185","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"Provides the first RNC-class parallel samplers for ferromagnetic Ising models with fields and for Ising models with interaction norm below 1, using localization schemes.","lead":"This paper designs parallel algorithms for sampling from Ising model distributions and estimating their partition functions in polylogarithmic parallel time. If correct, it would make these sampling tasks feasible on many processors at once, a step beyond existing sequential methods.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Appendix D's universal ratio bound is false; Theorem 1.3's polylog mixing proof is incomplete, though the claim appears repairable via sign(h) initialization.","rationale":"The reader's weakest_assumption identifies the main gap in the written proof: the universal ratio bound in Appendix D is false, and the displayed TRGD calculation depends on it. I agree with this assessment. I do not escalate to REJECT because (i) the random-cluster portion is independent and appears technically sound, and (ii) the Gaussian theorem can likely be repaired by initializing at sign(h): for ±1 vectors under ||J||≤1, |x^T Jx − s^T Js|≤2n, so log(1/µ(sign h))≤n log2 + n, and the entropy-decay bound still gives TRGD=O_η(log(n/ϵ)). Thus the counterexample does not refute the asymptotic claim; it refutes the proof as written. The original CONDITIONAL verdict remains appropriate: the authors need to correct Appendix D and the initialization in Algorithm 3 before Theorem 1.3 is accepted. No other concern in the ferromagnetic/random-cluster half changes the assessment.","tokens_in":18968,"tokens_out":29107,"duration_ms":293065,"concrete_test":"Verify the counterexample directly: for η=0.2, n=100, u=1_V/√n, J=0.5I+0.4uu^T, h=0, x=all +1, y=half +1/half −1, compute log(µ(x)/µ(y)) = 0.2n = 20 > 10 = 2/η using only the definition of µ. This settles that the Appendix D bound is false. Then check the proposed repair: replace the initialization by x0=sign(h) and re-derive 1/µ(x0)≤2^n e^n via |s^T Js − x^T Jx|≤2n; if this bound holds and TRGD is set to (1/δ)[log(4/ϵ²)+log(n log2 + n)], the mixing argument of Item 3 goes through.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix D asserts: 'Since 0≺η/2I⪯J⪯(1−η/2)I, it follows that for all x,y, µ(x)/µ(y) ≤ exp(2/η).' This assertion is false. Take η=0.2, u=1_V/√n, J=0.5I+0.4uu^T (eigenvalues 0.5 and 0.9, so 0.1I≤J≤0.9I), h=0. For x=all +1 and y with half +1/half −1, u^T x=√n and u^T y=0, so log(µ(x)/µ(y)) = (1/2)(x^T Jx − y^T Jy) = (1/2)(0.9n − 0.5n) = 0.2n, which exceeds 2/η=10 once n>50. The proof of Item 3 uses the false bound to conclude 1/µ(x0)≤2^n exp(2/η) and then sets TRGD=O_η(log(n/ϵ)). For a permitted initial state such as y, log(1/µ(x0))=0.2n, so the displayed TRGD formula in Appendix D does not follow. Consequently Theorem 1.3 is not proven as written. Note that this is likely repairable: initializing x0=sign(h) and using |x^T Jx − s^T Js|≤2n gives 1/µ(x0)≤2^n e^n, which would still yield TRGD=O_η(log(n/ϵ)); hence the concern is a proof gap rather than a demonstrated falsity of the theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two parallel Ising samplers. The first targets ferromagnetic Ising models with external fields by sampling from the associated random cluster model: it simulates field dynamics (negative-field localization) and uses a new 'coupling with the stationary distribution' criterion to parallelize the Glauber dynamics used in each denoising step. The second targets Ising models whose interaction matrix J satisfies ηI/2 ⪯ J ⪯ (1−η/2)I with arbitrary external fields, by simulating restricted Gaussian dynamics (stochastic localization); the Gaussian noising step is implemented by a parallel Langevin algorithm and the denoising step by product-form sampling. Theorems 1.1 and 1.2 state polylogarithmic-depth samplers for the ferromagnetic/random-cluster regimes, and Theorem 1.3 states an O_η(log^4(n/ε))-depth sampler for the contracting-matrix regime. The random-cluster result is also used to approximate the partition function via parallel annealing.","tokens_in":19285,"tokens_out":23337,"duration_ms":234995,"significance":"If the theorems are correct, the random-cluster/ferromagnetic part would be the first RNC sampler for ferromagnetic Ising models outside the high-temperature uniqueness region, and the contracting-matrix result would match the spectral threshold ||J||_2<1 for which sequential Glauber dynamics is rapidly mixing. The paper's main technical novelty, Condition 1, is a genuinely useful relaxation of the Dobrushin condition used in earlier parallel single-site dynamics, and the random-cluster half is presented with detailed proofs, explicit parameter choices, and a nontrivial good event taken from prior work; this part appears internally consistent. The restricted-Gaussian part is less complete: one inequality used in the proof of Item 3 in Appendix D is false, so Theorem 1.3 is not justified as written, although the gap appears repairable rather than fatal.","major_comments":[{"comment":"The assertion 'Since 0≺η/2 I ⪯ J ⪯ (1−η/2) I, it follows that for all x,y ∈ {±1}^n, μ(x)/μ(y) ≤ exp(2/η)' is false. A concrete counterexample is η=0.2, u=1_V/√n, J=0.5I+0.4uu^T, h=0, x=all-plus, and y any configuration with u^T y=0 (e.g., half plus and half minus). Then η/2 I ⪯ J ⪯ (1−η/2) I holds, but log(μ(x)/μ(y)) = (1/2)(0.9n − 0.5n) = 0.2n, which exceeds 2/η = 10 for n>50. The proof of Item 3 uses this false bound to conclude 1/μ(x0) ≤ 2^n exp(2/η) and then sets T_RGD = O_η(log(n/ε)), so the proof of Theorem 1.3 is incomplete as written. The theorem may still be true; for instance, initializing x0 = sign(h) gives |x^T Jx − x0^T Jx0| ≤ 4n and h^T(x − x0) ≤ 0 for all x, hence 1/μ(x0) ≤ 2^n e^{2n}, and the same T_RGD = O_η(log(n/ε)) follows. Please repair Item 3 accordingly.","section":"Appendix D, verification of Item 3"}],"minor_comments":[{"comment":"The stated parallel-time bounds (ε^{-1} log n · log n)^{O_δ(1)} are polynomial in 1/ε, which is weaker than what the analysis in Table 1 and Appendix C.1 appears to give for polynomially small ε; please state the sharpest bound that follows from the parameter choices, or clarify explicitly that RNC is understood with ε treated as a constant.","section":"Theorems 1.1 and 1.2"},{"comment":"The Edwards-Sokal coupling is stated for λ ∈ (0,1), while Theorem 1.1 allows λ_v = 0; please state the boundary case explicitly or justify it by a limiting argument, since the random-cluster component inclusion probability is 0 when a component contains a vertex with λ_v = 0.","section":"Lemma 3.2"},{"comment":"The algorithm samples from N(x_{i−1}, J^{-1}), but the Langevin implementation is described for N(0, J^{-1}); please state explicitly that one samples Z from the latter and returns x_{i−1}+Z.","section":"Appendix D, Item 1"},{"comment":"In the expansion of the denoising distribution, 'h⊺σ' should read 'h⊺x'; also, the factor exp(−(1/2)y_i^T J y_i) is independent of x and cancels in the conditional distribution, which is worth stating explicitly.","section":"Appendix D, denoising step"},{"comment":"There is a typo, 'teriminates' for 'terminates' in Proposition C.1.","section":"Appendix C.1"}],"recommendation":"major_revision","confidential_remarks":"The paper relies on prior results by overlapping authors ([CZ23] for field-dynamics mixing and low-temperature random-cluster bounds, [CCYZ24] for entropy decay of restricted Gaussian dynamics). This is legitimate black-box use, but Theorem 1.3 depends on an unpublished preprint and also contains the Appendix D gap identified above; the authors should either include a self-contained proof of the entropy decay statement or verify that [CCYZ24] is published. The random-cluster half of the paper appears to be the more solid and complete contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the random-cluster/ferromagnetic side is strong and, as far as I can tell, correct: it gives the first RNC samplers for ferromagnetic Ising models with fields and for the random-cluster model in that regime, with a genuine new coupling-with-stationarity criterion that relaxes Dobrushin. Second, the restricted Gaussian side has a real proof gap in Appendix D: the universal ratio bound mu(x)/mu(y) <= exp(2/eta) is false, and the mixing-time proof for Theorem 1.3 leans on it.\n\nThe new contribution is real. Prior parallel samplers required Dobrushin-type conditions or only got sqrt(n) depth; this paper gets polylog depth for the full ferromagnetic regime with fields, matching the sequential Jerrum-Sinclair result. The random cluster part is worked out in detail — the parameter choices, the low-temperature Glauber simulation, and the stability argument all hang together. I have no reason to doubt Theorems 1.1 and 1.2.\n\nThe soft spot is exactly where the reader put it. In Appendix D, the claim that for all x,y, mu(x)/mu(y) <= exp(2/eta) under the spectral condition does not follow. Take J = 0.5I + 0.4uu^T with u the normalized all-ones vector, eta=0.2, x all-plus, y half-plus: the log-ratio is 0.2n, so the bound is false for n>50. That bound is what yields 1/mu(x0) <= 2^n exp(2/eta) and hence T_RGD = O_eta(log(n/epsilon)); without it, the arbitrary-h mixing claim is unproven. To be fair, the stress-test note is right that this looks repairable — initializing at sign(h) and using |x^T Jx - s^T Js| <= 2n would restore a polylog bound. So this is a proof gap, not a demonstrated false theorem. The rest of the Gaussian part (the Langevin oracle, the product-form denoising) is fine.\n\nSelf-citations do not bother me here; the paper uses CZ23 and CCYZ24 as black-box theorems with separate proofs, and the new part is the parallel simulation and the coupling criterion.\n\nWho is this for? People working on parallel sampling, Ising models, and localization schemes. It deserves a serious referee, but the referee should be told to focus on Appendix D. My recommendation: accept for review, with the expectation that the Gaussian part be revised or split off. If the authors fix the ratio bound, the paper is a clear accept.","headline":"The random-cluster/ferromagnetic sampler is strong and likely correct, but the restricted Gaussian proof in Appendix D has a false universal ratio bound that needs repair before Theorem 1.3 stands.","tokens_in":19901,"tokens_out":2542,"would_cite":true,"duration_ms":23199,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W10","68Q25","82B20","60J22"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that ferromagnetic Ising models with external fields and Ising models with contracting interaction matrices admit the first RNC Gibbs samplers, running in polylogarithmic parallel time with polynomial work.","keywords":["Ising model","parallel sampling","RNC","field dynamics","random cluster model","stochastic localization","restricted Gaussian dynamics","Gibbs sampling"],"falsifier":"Set $n > 10/\\eta$, take $J = 0.5I + 0.4 uu^\\top$ with $u$ a unit vector, and compare $x$ with $u^\\top x = \\sqrt{n}$ against $y$ with $u^\\top y = 0$. Then $\\mu(x)/\\mu(y) = \\exp(0.2n) > \\exp(2/\\eta)$, contradicting the Appendix D bound used in the mixing proof; checking whether the algorithm's argument survives such a $J$ would settle the matter.","tokens_in":18722,"feed_emoji":"🧲","tokens_out":8581,"duration_ms":79513,"temperature":0.7,"pith_summary":"This paper claims that two regimes of the Ising model that were previously only known to be sequentially samplable are in fact samplable in randomized polylogarithmic parallel time (RNC). The first regime is ferromagnetic Ising with inverse temperature at least $1+\\delta$ and external fields at most $1-\\delta$; the second is any Ising model whose interaction matrix satisfies $\\tfrac{\\eta}{2}I \\preceq J \\preceq (1-\\tfrac{\\eta}{2})I$ with arbitrary external fields. For both, the proposed algorithms use polylogarithmic depth and polynomial total work, and the first regime also yields an RNC approximation of the partition function via annealing. The significance is that these are claimed to be the first RNC samplers in either regime, connecting a classically tractable sampling problem to the broader question of which sequential sampling tasks admit fast parallel algorithms.","feed_headline":"Two Ising regimes now sample in polylog parallel time","feed_subtitle":"Ferromagnetic models with fields and contracting interactions get RNC samplers; partition functions follow by annealing.","key_machinery":"Negative-field localization and its induced field dynamics: a global Markov chain on edge subsets whose update adds each element to a random set with probability $\\theta$ and then resamples from a tilted posterior, mixing in polylogarithmically many steps because the tilt drives the model into a low-temperature regime. Stochastic localization and its induced restricted Gaussian dynamics: a two-step chain on spin configurations alternating $y_i \\sim \\mathcal{N}(x_{i-1}, J^{-1})$ with resampling from a posterior that becomes a product distribution. Two further mechanisms carry the parallel efficiency: the coupling-with-stationarity criterion, which relaxes the Dobrushin condition needed for the parallel Glauber simulation, and parallel Langevin Monte Carlo, which supplies the Gaussian noising samples.","core_discovery":"The central discovery is that localization schemes, originally developed as tools for proving rapid mixing, can be turned into efficient parallel samplers. For ferromagnetic models, the paper simulates the field dynamics of the random-cluster model: each step adds edges to a random set with probability $\\theta$ and then resamples from a tilted low-temperature random-cluster distribution. The resampling step is implemented by Glauber dynamics, and a new “coupling with stationarity” criterion replaces the Dobrushin condition, allowing the parallel Glauber simulation to remain faithful in this low-temperature regime. For contracting interactions, the paper simulates restricted Gaussian dynamics, alternating Gaussian noise with covariance $J^{-1}$ and a product-form posterior resampling, with the Gaussian step handled by a parallel log-concave sampler. The two theorems state $\\bigl(\\epsilon^{-1}\\log n \\cdot \\log n\\bigr)^{O_\\delta(1)}$ parallel time for ferromagnetic models and $O_\\eta(\\log^4(n/\\epsilon))$ parallel time for contracting interactions, both with polynomial processors.","pith_inferences":["Editorial inference: the contracting-interaction theorem is only as strong as the Appendix D assertion that $\\mu(x)/\\mu(y) \\le \\exp(2/\\eta)$ for all $x,y$; this bound is directly checkable, and its failure would force a different treatment of the external field in the mixing argument.","Editorial inference: a natural test is to push the field-dynamics sampler closer to critical temperature by replacing the denoising subroutine with another rapidly mixing chain, since the localization tilt only needs to make that subroutine fast.","Editorial inference: the same two-phase template—noise through a log-concave channel, denoise from a product posterior—may yield RNC samplers for other Gibbs distributions with log-concave interaction structure, such as bounded continuous spin systems.","Editorial inference: because Theorem 1.2 is the engine behind Theorem 1.1, the edge cases $p\\to 1$ and $\\lambda\\to 1$ are the bottlenecks; eliminating them would extend the ferromagnetic sampler to the full ferromagnetic region."],"forward_implications":["A ferromagnetic Ising partition function can be approximated to $(1\\pm\\epsilon)$ in RNC by running the work-efficient parallel annealing algorithm of [LYZ24] on top of the Theorem 1.1 sampler.","The random-cluster sampler of Theorem 1.2 inherits the same polylogarithmic depth and polynomial work, so improvements for one model transfer to the other through the Edwards–Sokal coupling.","Under $\\|J\\|_2 \\le 1-\\eta$, adding a constant diagonal shift $J' = J + CI$ produces an instance satisfying Theorem 1.3, so the sampler covers every contracting interaction matrix for which Glauber dynamics is known to mix rapidly.","The coupling-with-stationarity criterion is stated for arbitrary Boolean-domain Glauber dynamics, making the parallel simulation theorem a general tool rather than a random-cluster-specific result.","The Gaussian noising step is the only component of the contracting-interaction sampler using expensive parallel sampling, so a faster parallel Gaussian oracle would speed up the entire sampler proportionally."],"supporting_citations":[{"why":"Establishes the sequential polynomial-time ferromagnetic Ising sampler whose parallel counterpart Theorem 1.1 claims to be.","marker":"[JS93]"},{"why":"Introduces field dynamics and proves its stationary distribution; Algorithm 1 simulates this global chain.","marker":"[CFYZ21]"},{"why":"Supplies the field-dynamics mixing time bound and the near-linear sequential sampler structure that Algorithm 1 follows.","marker":"[CZ23]"},{"why":"Provides the universal-coupling parallel simulation of Glauber dynamics that Algorithm 2 adapts.","marker":"[LY25]"},{"why":"Gives the concrete Edwards–Sokal coupling variant used in Lemma 3.2 to convert random-cluster samples into Ising samples.","marker":"[FGW22]"},{"why":"Introduces the localization-scheme framework and the entropy-decay theory used for restricted Gaussian dynamics.","marker":"[CE22]"},{"why":"Proves the entropy decay of restricted Gaussian dynamics that controls the outer-loop iteration count in Theorem 1.3.","marker":"[CCYZ24]"},{"why":"Supplies the parallel log-concave sampler used to approximate the Gaussian noising step $\\mathcal{N}(x_{i-1}, J^{-1})$.","marker":"[ACV24]"},{"why":"Introduces the restricted Gaussian oracle and proximal sampler that Algorithm 3 implements.","marker":"[LST21]"},{"why":"Provides the work-efficient parallel annealing reduction that turns the Ising sampler into a partition-function approximator.","marker":"[LYZ24]"}],"fun_headline_variants":["Localization schemes unlock parallel Ising sampling","Parallel Ising samplers hit polylog depth via localization","Ising models go parallel: polylog time with localization tricks","Field dynamics and Gaussian steps: parallel Ising in polylog","From mixing proofs to parallel samplers: Ising in polylog"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For Theorem 1.3, the load-bearing premise is the Appendix D assertion that, whenever $\\tfrac{\\eta}{2}I \\preceq J \\preceq (1-\\tfrac{\\eta}{2})I$, every configuration is at most $\\exp(2/\\eta)$ times as likely as any other, since that is what turns entropy decay into an $O_\\eta(\\log(n/\\epsilon))$ iteration count for arbitrary external fields.","fun_headline_variants_meta":{"raw":{"variants":["Localization schemes unlock parallel Ising sampling","Parallel Ising samplers hit polylog depth via localization","Ising models go parallel: polylog time with localization tricks","Field dynamics and Gaussian steps: parallel Ising in polylog","From mixing proofs to parallel samplers: Ising in polylog"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000266,"raw_usage":{"total_tokens":1601,"prompt_tokens":928,"completion_tokens":673,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":544,"completion_tokens_details":{"reasoning_tokens":585}},"tokens_in":544,"tokens_out":673,"duration_ms":6340,"temperature":1.0,"reasoning_tokens":585,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:13:41.420728+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set $n > 10/\\eta$, take $J = 0.5I + 0.4 uu^\\top$ with $u$ a unit vector, and compare $x$ with $u^\\top x = \\sqrt{n}$ against $y$ with $u^\\top y = 0$. Then $\\mu(x)/\\mu(y) = \\exp(0.2n) > \\exp(2/\\eta)$, contradicting the Appendix D bound used in the mixing proof; checking whether the algorithm's argument survives such a $J$ would settle the matter.","supporting_citations":[],"review_version":1}