acceptodds
Under review as a conference paper at ICLR 2027

Correct Locally, Swap Globally: Discrete Langevin Replica Exchange

Abstract

Gradient-based discrete samplers enable efficient sampling from discrete distributions but struggle on multimodal targets, while parallel tempering complements their local exploitation with global exploration. Combining the two is nontrivial, however, as swapping cannot in general correct the discretization bias of unadjusted local dynamics. We characterize the small-step limits of discrete Langevin sampler as continuous-time Markov jump processes and identify an edge-balance condition ensuring reversibility w.r.t. the target distribution. Building on adjusted-score constructions, we develop A-DULA and AV-DULA, which rely only on discrete energy differences and require no continuous extension of the target. For the resulting limiting replica-exchange processes, we prove that swapping strictly reduces the asymptotic variance and increases the large-deviation rate governing deviations of the cold-chain empirical measure from its target. Under a multimodal decomposition, we further derive spectral-gap lower bounds that quantify the interplay among within-mode relaxation, hot-chain exploration, temperature overlap, and swap efficiency. Experiments on synthetic benchmarks, spin systems, combinatorial targets, and discrete energy-based models demonstrate improved mode exploration and sampling accuracy over the evaluated baselines.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
discrete MCMC, replica exchange

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_euzSOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper combines discrete Langevin samplers with parallel tempering. It shows that swap rules alone cannot correct the bias of unadjusted local updates, and it derives an edge-balance condition for reversibility in the small-step limit. Based on this condition, it proposes A-DULA and AV-DULA, which use only discrete energy differences and work with the classical Metropolis swap. It proves that swapping reduces the cold-chain asymptotic variance and gives a multimodal spectral-gap bound. Experiments cover synthetic mixtures, Ising and Potts models, RBMs, facility location, and MaxSAT EBMs.

Critical strengths

Critical Strengths

S1. The paper establishes a concrete limitation of swap-only correction. A log-quadratic counterexample shows that the history-dependent swap rule analyzed in prior work violates detailed balance with respect to both the intended product target and the claimed intermediate distribution. For the same local kernels, a symmetric-observable argument further shows that no post-proposal retain-or-swap rule can preserve the product target. This challenges the prior detailed-balance characterization and provides a clear justification for correcting the local dynamics.

S2. The edge-balance condition provides a precise diagnosis and a constructive remedy. By identifying the small-step limit of DLS as a continuous-time Markov jump process, the paper derives a necessary and sufficient condition for target reversibility along graph edges. This explains the vanishing-bias behavior in the log-quadratic setting and identifies why it need not extend to general energies. The condition directly motivates extension-free local updates based on discrete energy differences.

Critical weaknesses

Critical Weaknesses

W1. The computational benefit over gradient-based DLS remains unestablished. Gradient-based DLS constructs parallel coordinate proposals from one gradient evaluation, whereas the proposed FULL implementation requires O(d)O(d) to O(dS)O(dS) energy queries per score table, matching the neighborhood-query count of LB. Appendix B.1 discusses this overhead and lower-cost variants, but the reported wall-clock and ESS/s comparisons do not include gradient-based DLS baselines. Consequently, the iteration-based improvements over DLS do not establish better sampling accuracy at an equal computational budget. This matters because the additional energy evaluations could offset the gains per iteration.

W2. The evidence for gains beyond standard PT is limited and task-dependent. Appendix C.2 provides a relevant comparison with classical PT-DMALA and shows a substantial improvement on MNIST under highest-density initialization. However, many other RBM differences are small relative to the reported variability, and Table 4 shows very similar NLL values for PT-MANA and the proposed methods on MaxSAT, with more modest differences in gradient error and mode coverage. The synthetic benchmarks omit classical PT-DMALA. A broader comparison under matched computational budgets would clarify when replacing the original local kernels provides a meaningful benefit beyond adding standard PT.

Questions for authors

Q1 (experiment request). Could you compare the proposed methods with DMALA and DREAM at an equal number of energy evaluations or equal wall-clock time, at least on the Ising and RBM tasks? A neural EBM target would further show whether the O(d)O(d) energy evaluations per step remain practical.

Q2 (experiment request). Could you add Classical PT-DMALA to the synthetic and Ising/Potts experiments? This baseline would separate the effect of the corrected local dynamics from the effect of PT.

Q3 (clarification). On MaxSAT, PT-MANA stays within one standard deviation of the proposed methods in most settings. What do the corrected local dynamics add over classical PT in this task?

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

This paper generalizes existing adjusted-score and auxiliary-variable discrete Langevin samplers from the binary hypercube to finite product spaces and establishes time-uniform finite-step error bounds for sufficiently small step sizes without Dobrushin-type weak-dependence assumptions. For the limiting continuous-time replica-exchange processes, the authors also prove that every nonconstant cold-replica observable has strictly smaller asymptotic variance with a positive swap rate than without swapping. Experiments on synthetic distributions, spin systems, combinatorial targets, and energy-based models report improvements in sampling accuracy and exploration, with the extent of the gains varying across benchmarks.

Critical strengths

Convergence guarantees beyond Dobrushin-type weak-dependence conditions. Theorem 3 provides a finite-step error bound that separates mixing from discretization error and remains uniform over the number of iterations. Removing the weak-dependence requirement extends the theoretical coverage to finite targets with strong interactions, which is directly relevant to the multimodal setting motivating the paper. Although the constants remain target-dependent, this is a meaningful expansion of the applicability of the guarantees.

A rigorous strict improvement in cold-replica estimation variance. Theorem 5 establishes that a positive swap rate strictly reduces the asymptotic variance of every nonconstant cold-replica observable in the limiting continuous-time process. The proof goes beyond non-increasing variance by resolving the equality case through swap invariance and uniqueness of the Poisson solution. This directly addresses the statistical reliability of estimates obtained from the cold replica and provides a clear theoretical justification for replica exchange at a common continuous-time horizon.

Critical weaknesses

Computational efficiency on the higher-dimensional benchmarks is not sufficiently established. All primary experiments use FULL energy-difference tables, and A-DMALA generally requires an additional table for the reverse proposal (Appendices A–B.1). However, the spin-system comparisons are iteration-based, while the RBM protocols match update counts or local sampling rounds rather than measured computational cost. Consequently, it remains unclear whether the reported accuracy improvements persist under equal wall-clock budgets, including score construction and reverse-proposal evaluation. The facility-location ESS/s results and MaxSAT wall-time curves provide useful evidence, but do not resolve this issue for the higher-dimensional RBM experiments. This limits the empirical case for practical efficiency without undermining the stated theoretical results.

Questions for authors
  1. Equation (3) uses the sum of the current and previous inter-replica energy differences, whereas Eq. (8) in the published version of Zheng et al. (2026) uses their difference. Could you reconcile these expressions and specify which swap rule was implemented for the DREXEL and DREAM baselines? Please also clarify which rule the explicit detailed-balance calculation in Appendix D.2 addresses. This distinction matters for both the attribution of the counterexample and the fidelity of the empirical comparisons.

  2. For the spin-system and RBM experiments, could you clarify the computational budgets and implementation costs underlying the comparisons? In particular, how were FULL score-table construction, reverse-proposal evaluation, and the two replicas handled, including any caching or batching? Are per-update or total runtimes available from the existing runs? This would help determine whether the reported accuracy improvements also translate into gains at comparable computational cost.

Reviewer_pZdaOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1(−1)
Soundness
1(−1)
Read review
Paper summary

The paper introduces a framework for sampling from discrete distributions by combining discrete Langevin sampling (which allows efficient parallel coordinate updates) with parallel tempering. The authors modify the local proposal transition rates to satisfy detailed balance in the continuous time limit. Optionally, the paper proposes a Metropolis-Hastings correction to remove finite-step bias. The paper establishes theoretical guarantees showing that replica exchange reduces asymptotic variance, improve large-deviation rates, and can accelerate convergence to the equilibrium for multimodal distributions. Experiments across various problem settings are used to compare with existing methods.

Critical strengths
  • Among the theoretical guarantees, the strict improvement of the large-deviation rate for the empirical distribution is an interesting analysis.

  • The paper considers a relatively broad range of experiments and compares with several recent discrete sampling methods.

Critical weaknesses
  • The proposed A-DULA algorithm is closely related to a parallel or synchronous Glauber-type update, which is conceptually similar to Hogwild Gibbs sampling. Indeed, its continuous-time limit corresponds to Glauber dynamics. It is therefore unclear how much algorithmic novelty is provided by the proposed local dynamics compared to existing approached.

  • The extension with Metropolis-Hastings correction and replica exchange is also not new in itself. The paper should better clarify the novelty compared to existing parallel discrete sampling methods.

  • The theory gives several convergence guarantees for parallel tempering. However, some of these results follow from standard properties of reversible Markov chains. Moreover, they do not guarantee better sampling accuracy for the same computational budget. These results do not directly explain the empirical improvements with limited practical significance.

  • The presentation could be improved with some very small figures that are difficult to read and inconsistent font sizes in tables.

Questions for authors

Q1) It seems experimental comparison is missing standard sampling methods such as Gibbs with gradients and Hamming ball sampling. A comparison with standard Gibbs dynamics with parallel tempering would help isolating the contribution of the proposed dynamics.

Q2) The compute matching is unclear in the experiments. Could the authors clarify how the total computational cost is accounted for, including number of evaluations, additional cost of MH corrections, parallel hardware utilization ?

Q3) The comparison with classical PT-DMALA in C2 is useful, but limited to RBM sampling. Could the authors provide a more systematic ablation across other benchmarks ?

Q4) Could the authors clarify how informative the multimodal spectral-gap bound is for the experimental benchmarks?

Comments on the paper

1 comment

Thank you for the detailed rebuttal and additional experiments. The new compute-matched comparisons and classical PT-DMALA baselines address my concerns regarding W1 and W2. I appreciate the authors' efforts to strengthen the empirical evaluation, and I am inclined to raise my rating accordingly.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.