Correct Locally, Swap Globally: Discrete Langevin Replica Exchange

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.