DISCS: A Benchmark for Discrete Sampling
Authors: Katayoon Goshvadi
Haoran Sun
Xingchao Liu
Azade Nova
Ruqi Zhang
Will Sussman Grathwohl
Dale Schuurmans
Hanjun Dai
Venue: NeurIPS 2023 Datasets and Benchmarks Poster (2023)
Keywords: discrete
MCMC
sampling
benchmark
combinatorial optimization
language model
TL;DR: We provides a benchmark for discrete sampling for sampling from distributions in discrete space and solving combinatorial optimizations.

Abstract: Sampling in discrete spaces, with critical applications in simulation and optimization, has recently been boosted by significant advances in gradient-based approaches that exploit modern accelerators like GPUs. However, two key challenges are hindering further advancement in research on discrete sampling. First, since there is no consensus on experimental settings and evaluation setups, the empirical results in different research papers are often not comparable. Second, implementing samplers and target distributions often requires a nontrivial amount of effort in terms of calibration and parallelism. To tackle these challenges, we propose DISCS (DISCrete Sampling), a tailored package and benchmark that supports unified and efficient experiment implementation and evaluations for discrete sampling in three types of tasks: sampling from classical graphical models and energy based generative models, and sampling for solving combinatorial optimization. Throughout the comprehensive evaluations in DISCS, we gained new insights into scalability, design principles for proposal distributions, and lessons for adaptive sampling design. DISCS efficiently implements representative discrete samplers in existing research works as baselines and offers a simple interface that researchers can conveniently add new discrete samplers and directly compare their performance with the benchmark result in a calibrated setup.

consensus the experimental DISCS: A Benchmark for Discrete Sampling
Katayoon Goshvadi Google Deepmind
Haoran Sun Georgia Tech
Xingchao Liu UT Austin
Azade Nova Google Deepmind
Ruqi Zhang Purdue University
Will Grathwohl Google Deepmind
Dale Schuurmans Google Deepmind
Hanjun Dai Google Deepmind
Abstract
Sampling in discrete spaces, with critical applications in simulation and opti- mization, has recently been boosted by sigmificant advances in gradient- -based approaches that exploit modern accelerators like GPUs. However, two key chal- lenges are hindering further advancement in research on discrete sampling. First, since there is consensus experimental settings and evaluation setups, the empirical results in different research papers are often not comparable. Second, implementing samplers and target distributions often requires nontrivial amount of effort in terms of calibration and parallelism. To tackle these challenges, we pro- pose DISCS (DISCrete Sampling). tailored package and benchmark that supports unified and efficient experiment implementation and evaluations for discrete sam- pling three types of tasks: sampling from classical graphical models and energy based generative models, and sampling for solving combinatorial optimization. Throughout the comprehensive evaluations in DISCS, we gained new insights into scalability, design principles for proposal distributions, and lessons for adaptive sampling design. DISCS efficiently implements representative discrete samplers existing research works baselines and offers simple interface that researchers can conveniently add new discrete samplers and directly compare their performance with the benchmark result in calibrated setup.
1 Introduction
Sampling in discrete spaces has been an important problem for decades in physics (Edwards &
Anderson 1975. [Baumgärtner et al.] 2012), statistics (Robert & Casella 2013 Carpenter al. 2017), and computer science (LeCun et al. 2006 Wang & Cho 2019). Since sampling from a target discrete space X' is typically intractable, one usually resorts to Markov chain Monte Carlo (MCMC) methods (Metropolis et al. 1953 Hastings
probability distribution (<)) x expl--fc [x)) defined
1970). However, except for few algorithms such Swendsen-Wan
for the Ising model (S (Swendsen
& Wang 1987) and Hamze-Freitas for hierarchical models (Hamze & de Freitas 2012). which exploit the special structure of the underlying problem, sampling a general discrete space has primarily relied on Gibbs sampling, which exhibits notoriously poor efficiency in high dimensional spaces.
Recently, family of locally balanced MCMC samplers for discrete spaces (Zanella 2020 Grathwohl
al. 2021 Sun al. 2021 Zhang et al. 2022). using ratio informed proposal distributions,
*(3)
=(x)*
have Sagmificatlly improved sampling efficiency by exploiting modern accelerators like GPUs and TPUs. From the perspective of gradient flow on the Wasserstein manifold of distributions, Gibbs sampling is simply a coordinate descent algorithm, whereas locally balanced samplers perform full gradient descent (Sun al. 2022a Despite the advances in locally balanced samplers, quantitative benchmark is still missing. As result, the empirical results in different research papers may not be comparable. One important reason is that there
37th Conference on Neural Information Processing Systems (NeurIPS 2023) Track on Datasets and Benchmarks.

---

setting. Particularly, the initialization of energy based generative models, random seeds used in graphical models. and the protocol of hyper-parameter tuning all have a significant impact on samplers performance. Under this circumstance, there is critical need for unified benchmark to advance the research in discrete sampling.
There are two key challenges that seriously hinder the appearance of such benchmark. First, a sampler may perform well in one target distribution while poorly in another one. To thoroughly examine the performance of a sampler, a qualified benchmark needs to collect a set of representative distributions that covers the potential applications of discrete samplers. Second, the evaluation of discrete samplers is complicated. Although the commonly used metric Effective Sample Size (ESS) (Vehtari et al. 2021) can effectively reflect the efficiency of sampler in Monte Carlo integration or Bayesian inference, it is not very informative in scenarios when the sampler guides the search in combinatorial optimization problems or performs as a decoder in deep generative models.
To address the two challenges, we propose DISCS, a tailored benchmark for discrete sampling. In particular, DISCS consists of three groups of tasks: sampling from classical graphical models, sampling for solving combinatorial optimization problems, and sampling from deep energy based models (EBMs). These tasks cover both the topics of simulation and optimization, and also target distributions, ranging from hand-designed graphical models to learned deep EBMs, For each task, we collect the representative problems from both synthetic and real-world applications, for example, graph partitioning for distributed computing and language model for text generation. We carefully design the evaluation metrics in DISCS. In sampling from classical graphical models tasks, DISCS uses ESS as standard. In sampling for solving combinatorial optimization tasks, DISCS runs simulated annealing (Kirkpatrick et al. [983) with multiple chains and reports the average of the best results in each chain. In sampling from energy based generative models, DISCS employs domain specific scores to measure the sample quality.
DISCS offers a convenient interface for researchers to implement new discrete samplers, without worrying about parallelism, experiment loop, and evaluation. DISCS can efficiently sweep over different tasks and experiments configurations in parallel, making it easy to reproduce the benchmark results of this paper. Also, DISCS implements existing discrete samplers including random walk Metropolis (Metropolis et al. 1953). block Gibbs, Hamming Ball sampler (Titsias & Yau (017). Locally Balanced (Zanella 2020). Gibbs with Gradients (Grathwohl et al., 2021), Path Auxiliary Sampler (Sun et al. 2021). Discrete Metropolis Adjusted Langevin Algorithm (Zhang et al. 2022). Discrete Langevin Monte Carlo (Sun et al., 2022a). and is actively maintaining to add new samplers. Researchers can directly compare the results with state-of-the-art methods.
DISCS can also provide insights on the existing open questions in the space of discrete sampling. In our experiments, we observe an interesting phenomenon that the locally balanced weight function g(() = vi outperforms g(t) = т when Ising model has a temperature higher than the critical temperature and g(() प outperforms g()) vi when the temperature is lower than the critical temperature. We further observe similar phenomenon in our experiments with more complicated deep energy generative model where gt) т+T outperforms g(t) Vt on overparameterizee neural network with low temperature and sharp landscape. There have been numerous studies on how to select the locally balanced function for locally balanced sampler (Zanella 2020 Sansone (022), but the answer still remains open. We hope the observations in this paper can provide some insight on this question.
We wrap the DISCS package as a JAX library to facilitate the research in discrete sampling. The library is open sourced DISCS The dataset used in our benchmark experiments can be accessed at DISCS DATA The The paper is organized as follows:
In section we provide overview of related work on different tasks for discrete sampling and recent advances in discrete samplers.
In section we formulate the discrete sampling problem.
In section we introduce the discrete sampling tasks and evaluation metrics in DISCS. We also
present several results with interesting insights and observations.
In section 5
we discuss the contribution and limitations of DISCS.
1 'cdee base found at
2 set found at http::/:/chhoooeeeooooooooooooo/ buo30AnDx

---

We provide comprehensive results of our benchmark and studies with further details on the experi- mental setups, evaluation metries, mathematical formulations, and the data set used in the Appendix
A
2
Related Work
Discrete sampling has been widely used to study the physical picture of spin glasses (Hukushima & Nemoto| [196]] Katzgraber et al.) 2001). solve combinatorial optimization via simulated annealing (Kirkpatrick a 1983), and for training or decoding deep energy based generative models (Wang) & Chol 2019 Du et al. 2020 Dai ct al., 2020b). However, these tasks primarily depend on Gibbs sampling, which could be very slow in high dimensional space.
Since the seminal work Zanella (2020), the recent years have witnessed significant progresses for discrete sampling in both theory and practice. [Zanella 2020) introduces the locally balanced proposal
(xx,)) Xx g m(v)
), where y E (X) restricted within a small neighborhood of x: and g(-) I ->
(())
R. satisfying ga) ag( 1). and prove it is asymptotically optimal. In the following works, PAS (Sun et al,, )02T) and DMALA (Zhang et al.] 2022) generalize locally balanced proposal to large neighborhoods by introducing an auxiliary path and mimicking the diffusion process, respectively. Inspired by these locally balanced samplers, (Snn et al. (2022a) generalize the Langevin dynamics in continuous space to discrete Langevin dynamics (DLD) in discrete space continuous time
Markov chain an PX = X| = x) = I( a(v) ), and show that previous locally balanced x())
samplers are simulations DLD with different discretization strategies. In the view of Wasserstein gradient flow, the Gibbs sampling can be seen coordinate descent and DLD gives full gradient descent. Hence, locally balanced samplers induced from DLD provide a principled framework to utilize modern accelerators like GPUs and TPUs to accelerate discrete sampling. Besides the discretization of DLD, another crucial part to design a locally balanced sampler is estimating the probability ratio m(y)
F(a)) Grathwohl et al. (2021 proposes used gradient approximation त(z) R
m(y)
exp(=(V/(xz) y x>) and obtains good performance on various classical models and deep energy based models. When the Hessian is available, Rhodes & Gutmann (2022); ) [Sun et al. (2023a) use second order approximation via Gaussian integral trick (Hubbard, 1959) to further improve the sampling efficiency skewed target distributions. When the gradient is not available, Xiang et al. (2023) use zero order approximation via Newton's series.
Besides designing the sampler, Sun et al. 2022b) proves that when tuning path length in PAS (Sun al. 202T). the optimal efficiency is obtained when the average acceptance rate is 0.574, and design an adaptive tuning algorithm for PAS. Sansone (2022) learn locally balanced weight function for locally balanced proposal, but how to select the weight function in a principled manner still unclear.
3 Formulation for Sampling in Discrete Space
The sampling in discrete space can be formulated the following problem: in finite discrete space X' we have an energy function ʃ(.) X' - IR. We consider a target distribution
exp( (B)())
Z Σ exp(-3f(=)),
2
SEX
where 9 is the inverse temperature. When the normalizer Z is intractable, people usually resort to Markov chain Monte Carlo (MCMC) sample from the target distribution π. Metropolis-Hasting
(M-H) (Metropolis et al. 1953; Hastings 1970) is a commonly used general purpose MCMC algorithm. Specifically, given a current state (1)), the M-H algorithm proposes a candidate state from a proposal distribution q(x((1), 8). Then, with probability
min { (Vv)((, (00)
T (x(1))(x(1 y)
the proposed state is accepted and (+++1) = yt otherwise, (+++)) = z01) In this way, the detailed balance condition is satisfied and the M-H sampler generates a Markov chain (0()) (11). that has m as its stationary distribution.
3

---

4 Benchmark for Sampling in Discrete Space
The recent development of locally balanced samplers that use the ratio m(x) to guide the proposal distribution g(z, has significantly improved the sampling efficiency in discrete space. However, there is no consensus for many experimental settings, As a result, the empirical results in different research papers may not be directly comparable. Under this circumstance, we propose DISCS as benchmark for general purpose samplers in discrete space. In section [.1] we introduce implemented sampling methods as the basclines in DISCS and make some remarks on how present the results.
s(w)
DISCS implements both the classical discrete samplers and the recent developed locally balanced samplers. In the following sections, we introduce the tasks considered in DISCS follows: sampling from classical graphical models (section 4.2), sampling for solving combinatorial optimization problems (section 4.3). and sampling from deep energy based generative models (section 4.4). We also describe how the discrete samplers are evaluated on these tasks and report several results of them with some insights. We leave the remaining comprehensive results and experimentation and report them in detail in Appendix
4.1 Baselines
We include both classical discrete samplers and state-of-the-art locally balanced samplers in recent research papers as baselines our benchmark. Specifically, DISCS implements
1. random walk Metropolis (RWM) (Metropolis et al., 1953).
block Gibbs (BG), where BG-<a> denotes using block Gibbs with block size a.
3. Hamming Ball Sampler (HB) (Titsias & Yau 2017), where HB-<a><<b> denotes using block size
and Hamming ball size b.
4. Gibbs with Gradients (GWG) (Grathwohl et al. 2021). locally balanced sampler that uses gradient to approximate the probability ratio. For binary distribution, GWG has a scaling factor to determine how many sites to flip per step.
Path Auxiliary Sampler (PAS) (Sun al. 2021 locally balanced sampler that has scaling factor I, to determine the path length.
Discrete Metropolis Adjusted Langevin Algorithm (DMALA)(Zham)) et al. 2022). a locally balanced sampler that has scaling factor a to determine the step size.
Discrete Langevin Monte Carlo (DLMC) (Sun et al.) (022a)), a locally balanced sampler that has scaling factor 7 to determine the simulation time of DLD. DLMC has multiple choices for its numerical solver to approximate the transition matrix. DISCS considers the two versions used in the original paper, DLMC that uses an interpolation, and DLMCf that uses Euler's 's forward method.
Note that in the depicted plots in this paper, each of the previously described samplers is represented with a distinct and unique color of its own. We present samplers RWM, BG, HB, GWG, PAS, DMALA, DLMC, DLMCf as the colors green, yellow, blue, red, brown, purple, pink and grey.
Remark: weight function DISCS offers a range of locally balanced functions, including g = Vt. g(t) = - g() = 1 Lt and g(t) = 1 t. All the locally balanced samplers have the flexibility to select from these locally balanced functions. g(t) = vt and g(t) = .II are the two most commonly used weight functions which we also rely on for our experiments. We use <sampler>-<fune to refer to the type of the weight function for the locally balanced sampler. In cases that the weight function not reported, use vt by default.
Remark: scaling Since the scaling of the proposal distribution in RWM, PAS, DMALA, and DLMC are tunable, we consider two versions: one with adaptive tuning and another with binary search tuning to ensure fair comparison. [Sun et al. (2022b) 2023b) propose an adaptive tuning algorithm for PAS and DLMC when the target distribution is factorized In practice, we find that they also apply well to other locally balanced samplers and for more general target distributions. Hence, in this paper, we use the adaptive tuning algorithm by default to tune the scaling for locally balanced samplers. In the several exceptions where the adaptive algorithm does not apply, we will use caampplee-name-nnoe to indicate the results from binary search tuning.

---

4.2 Sampling from Classical Graphical Models
This section covers the classical graphical models frequently employed in physics and statisties, including Bermoulli Models. Ising Models ([sing) 1924). and Factorial Hidden Markov Models (Ghahramani & Jordan 1995). The graphical models have large configuration flexibility, for example, the number of discrete variables, the number of categories for each discrete variable, and the temperature of the model. The performances of different samplers can heavily depend on these configurations. DISCS provides tools to automatically sweep over hundreds of configurations with one click. Following the common practice Monte Carlo integration Bayesian inference, DISCS uses the Effective Sample Size (ESS) to evaluate the efficiency of each sampler and reports the ESS normalized by the number calling energy functions and by the running time. Below, we present several Ising Model results illustrative examples. We report more results and details of our experiments and ESS calculation in the Appendix [A. A.I. More specifically, we report the performance results of different samplers Bernoulli Model Categorical Model Ising Model 9, Potts Model TO and FHMM II We study the effect of number discrete variables (sample dimension), the number of categories for each discrete variable, weight function for locally balanced samplers, and the temperature of the models (smoothness/sarppnes)))
The Ising Model is defined on 2D grid, where the state space X' {-1,1]ex 1 represents the spins on all nodes. For each state x E X, the energy function defined as:
f(x) = Σ
Jijassy
Σ h5a;
where Jı, is the internal interaction and the h, is the external field. In the main text, we report the results using the configuration from Zanella (2020). Specifically, Jıy = 0.5, h2 = H4s + oi where o; Uniform(- 11.5, 1.5) and μ4 0.5 if node located in circle has the same center the 2D grid and radius P_ else - 0.5. We consider the target distribution <<x) x exp(-3f(x)) where B 2V2
is the inverse temperature. Using DISCS, one can easily investigate the influence of the number of
discrete variables (sample dimension). In Figure [ one can see that the classical samplers, RWM, BG, HB, have significant decrease in ESS when the model dimension increases, while the locally balanced samplers are less affected the ratio information
m(v) effectively guides the proposal
π(x)
distribution. The overall trends basically follows the prediction from Sun et al. (2022b) that the ESS Odt for RWM and (d à) for PAS.
Offect of sample dimendon l1hng
Effect dimersion
No
mot Cook
Figure 1: Results of Ising model with different dimensions.
Through DISCS, researchers can easily define various experiments, configure tasks, evaluate sampler performance and gain invalubale insights on open questions. As an example, we experiment with sampling from Ising Models with range temperatures and sample dimensions. In Figure 2 we experiment with sampling from Ising Models with inverse temperatures from 0.1607 to 0.7607 for both sample dimension of 50 x 50 and 100 x 100. We consider Ising Model without external field:
h, 0 and Jıy 1 as we know the critical temperature for this configuration is 2 log(1+v/}
This
gives us the critical point for inverse temperature as B = 0.4407. From the results in Figure that
we
The Ising model harder to sample from when the inverse temperature 3 is closer the critical point, which is consistent with the theory in statistical physics.
5

---

When the inverse temperature 3 is lower than the critical point, using weight function g(t) vt gives larger ESS: When the inverse temperature larger than the critical point, using weight function g(() I+I consistently obtains larger ESS.
The second observation implies that one should use ratio function सनं for target distributions with sharp landscapes. We will revisit this conclusion in Table 2 We report more results the effect of sample dimension in Appendix TOp.
0rale
1907
dndrt
#hoi
500
500
the Frversa lamperaure
Invatse temse dlars
Figure 2: Performance of locally balanced samplers with different types of weight functions temperature on: (left) 50 x 50 Ising model, (right) 100 x 100 Ising model.
The categorical version of Ising model is Potts model, where each site state æi has values in symmetry group, instead of {),, For simplicity, we denote the symmetry group set of one hot vectors {ei...., ec} with h4 CR, E RCxC
In this way, the energy function becomes:
f(x) - Σ r. Jijay f.j
Σ (hs,
In Figure 3 one can see the sampling efficiency very robust with respect to the number of categories, with the exception of the classical HB and BG samplers, which demonstrate decline in their sampling performance. The result for BG-2 on Potts model with 256 categories is omitted as it takes over 100 hours. We report more results on the effect of number of categories in Appendix X 10
of categuries
Effect
No-B:
ho-1p1
Ip2
par
Figure 3: Results of Potts models with different number of categories.
4.3 Sampling for Solving Combinatorial Optimiazation
Combinatorial optimization is core challenge in domains like logistics, supply chain management, and hardware design, and has been fundamental problem of study in computer science for decades. Combining with simulated annealing Kirkpatrick et al. (1883), the discrete sampling algorithm powerful tool to solve combinatorial optimization problems (Sun et al.) 2023b). In expectation, a sampler with a faster mixing rate can find better solutions. Hence, the second type of task is sampling for solving combinatorial optimization problems. Currently, DISCS covers four problems:

---

Maximum Independent Set (MIS), Max Clique, MaxCut, and Balanced Graph Partition. Without loss of generality, we consider combinatorial optimization that admits the following form:
min =EC= (c......... C-14
a(x),
S.L. b(x) =0
(5)
For ease of exposition, we assume b(x) 2 0, Va E C, but otherwise do not limit the form of a and b. To convert the optimization problem to sampling problem, we first rewrite the constrained optimization into a penalty form via penalty coefficient X, then treat this as an energy function for an EBM. In particular, the energy function takes the form:
f(z) a(x) + X b(x)
(6)
Then, we define the probability of x at inverse temperature 3 by:
(a(x) & exp(-3f(z))
A naive approach to this problem would be directly sampling from p0-+o(x)) , but such distribution highly nonsmooth and unsuitable for MCMC methods. Instead, following classical simulated an- nealing, we define a sequence of distributions parameterized by sequence of decaying temperatures:
p = lp% (z), Pa, (r),.... P3r (x)
where the sequence 30 < 81 < < BT + oC converges to a large enough value as 7 increases. Below, present the problem formulation and the energy functions used for MaxCut and MIS problems. We present several results of the samplers solution for these combinatorial optimization problems illustrative examples in the main text and report the remaining results in the Appendix
The objective of MaxCut problem is to find cut graph G EV) that partitions the graph nodes into two complementary sets V = V1 U V2, such that the number edges E between V1 and V2 is large possible. MaxCut is an unconstrained problem, which makes its formulation relatively simple. We can set C = {0. 1) such that I; = O represents i E Vi and x; = means 2; E V2. Then we can write a(x) = x Ar, b(x) = 0, where is the adjacency matrix of the graph G.
MaxCut
We apply the same simulated annealing temperature scheduling set up for all the samplers and compare the samplers performances against each other. In the MaxCut problem, we compute the ratio of our solution against the optimal solution found by Gurobi, running for one hour (Dai et al.) 2020a). The results presented at Figure 4 show the cut ratio throughout the chain generation over the number of M-H steps and the running time (s). The legends are sorted according to the most optimal solution each sampler finds. One can see that the PAS leads the results. Also, locally balanced samplers significantly outperform the traditional samplers, especially when the graph size increases.
[256-300]
ER-[512-600]
ER-[1024-1 1100]
3.5
3.0
099
0.1
134
2054
1.2
201
0.0
10
1.20
3.82
3.0
230
012
Figure 4: Results for MaxCut on ER graphs. The ratio is computed by dividing the optimal size obtained from running Gurobi for 1 hour. (top) ratio with respect to the number of M-H steps, (bottom) ratio with respect to running time.
7

---

MIS On graph G = (V, E), an independent set S C V means that for any Ł.j E S, (i,5) & E. We can set C {0, 1} such that Z; 0 means & S and x; = 1 means E S. Then we can write a(x) = Σ iev zi and b(x:) Σ (()))E T.zj. For the penalty coefficient X, we follow Sun et al. (202cc) to select À = 1.0001 being a value slightly larger than 1. We run all samplers on five groups of small ER graphs with 700 to 800 nodes, each group has 128 graphs with densities varying 0.05, 0.10, 0.15, 0.20, and 0.25. We also run all samplers on 16 large ER graphs with 9000 to I 11000 nodes. For each configuration, we run 32 chains with the same running time and report the average of the best results found by each chain in Table One can easily see that PAS obtains the best result.
Table 1: Results for MIS on ER graphs. The set found by the sampling algorithm is not necessarily an independent set, we report a lower bound: set size # pair of adjacent nodes in the set.
[R[700-800]
[R|9000-1 1000]
Sampler
0.05
0.10
0.15
0.20
0.25
0.15
HB-10-1
100.374
58.750
41.812
32.344
26.469
277.149
BG-2
102.468
60.000
42.820
32.250
27.312
316.170
RWM
97.186
56.249
40.429
31.219
25.594
-555.674
GWG-nA
104.812
62.125
44.383
34.812
28.187
367.310
DMALA
104.750
62.031
44.195
34.375
28.031
357.058
PAS
105.062
62.250
44.570
34.719
28.500
377.123
DLMCf
104.450
62.219
44.078
34.469
28.125
354.121
DLMC
104.844
62.187
44.273
34.500
28.281
355.058
4.4 Sampling from Energy Based Generative Models
The discrete samplers can also play the role of decoder in generative models. In particular, given a dataset 'D = { sampled from the target distribution æ, one can train an energy function fa (-). such that the energy based model (T) x exp(-fo(-)) fits the dataset D. DISCS provides multiple checkpoints for the energy function trained on real-world image or language datasets. Researchers can easily evaluate their samplers after loading the learned energy function. We provide further experimental details and mathematical formulations at Appendix A.3
For the models that are relatively simple, for example, Restricted Boltzmann Machine (RBM) trained on MNIST (LeCun 1998) and fashion-MNIST (Xiao et al.] (20176) one can continue using ESS as the metric. In Figure 5 we evaluate the samplers on RBMs trained on MNIST with 25 and 200 hidden variables. One can see that DLMC has the best performance. We further report the results of samplers on categorical RBM trained on Aishion-MNIS"" dataset at Appendix [66] For more complicated deep energy based models, sampler may fail to mix within reasonable steps. In this case, ESS is not good metric. To address this problem, DISCS provides multiple alternative measurements, including snapshots and domain specific scores.
Snapshots After loading the checkpoint of energy based generative models, DISCS can generate snapshots of the sampling chains. For example, in Figure 6 we display the snapshots of sampling on a deep residual network trained on MNIST data (Sun et al., 202T) and on pretrained language model BERT One can see that locally balanced samplers generate samples with higher qualities, and can typically visit multiple modalities in the distribution. We report further results on deep residual network trained on Omniglot and Caltech dataset at [7
Domain Specific Scores In many deep generative tasks, the goal is to efficiently sample high-quality samples, instead of mixing in the learned energy based models. In this scenario, domain specific scores that directly evaluate the sample qualities are better choices. For example, DISCS provides text filling task based on pre-trained language models like BERT (Wang & Cho 2019 Devlin et al.) 2018). Following the settings in prior work (Zhang al. 2022), we randomly samples 20 sentences from TBC (Zhu et al. 2013) and WiKiText- -03 (Merity et al. 2016) and mask four words in each sentence (Donahue et al. 2020) resulting in the dataset provided at DISCS DATA For each masked sentence, we sample 25 sentences by generating 25 chains with length of 50, following the target probability distribution provided by BERT, and then selecting the last sample of the chain. As a common practice
loading the checkpoint from https: co/bettee.co//beeeeeee. wwtp://bbbbbbbbuaaeeeeeeeeeeeeee uncased

---

Sivayy ApM with Nidden dimeriion 23
Sinaty w heleen direnies
10.00%
pvgft
200
Figure 5: Results on RBMs trained on MNIST dataset. (top) RBM with 25 binary hidden variables, (bottom) RBM with 200 binary hidden variables.
non-auto-regresssvve text generation, we select the top-5 sentences with the highest likelihood out of 25 sentences to avoid low-quality generation (Gu et al. 2017: Zhou et al. 2019).
We evaluate the generated samples in terms of diversity and quality. For diversity, we use self-BLEU (Zhu et al. 2018) and the number of unique n-grams (Wang & Cho 2019) to measure the difference between the generated sentences. For quality, we measure the BLEU score (Papineni et al.) 2002) between the generated texts and the original dataset, which is the combination of TBC and WikiText- 103. We report the quantitative results Table We do have the results for HB and BG as they are computationally infeasible for this task with 30k+ tokens. In this task, the locally balanced sampler still outperforms RWM. Also, one can notice that the weight function f significantly 2+I
outperforms vt on diversity metrics and reaches comparable results the quality. The reason is that the overparameterized neural network a low temperature system with sharp landscape. This phenomenon consistent with the results in Figure We provide further results for the non-adaptive cases with binary search fine tuming in Appendix A.3.3
5
5
3
8
3
3
+
4
(MASS)
D
3
8
8
3
3
X
3
9
9
5
3
3
5
8
S
6
3
8
g
DMA
Lacwing micosay aontenaaall peolle inehedine
ademaard
invinee hud olea des
vila
3
8
3
3
3
3
7
EMALAGA
Lacving (ni dralts sccenable andereed the pork inneinc how the
Lacviing
good undartad tu paple andraa snd boo day citra sarter
2
4
4
7
4
4
INAALA
PAA
evcn
to endornnd bhe poopl tocchd and hew thyy scar moteor
anderteed people iestrve
interred invileet wnthow
3
2
BUMEY
8
8
8
7
8
8
pag
undented you meremms
4.
X1k Stepe
MNIST
BERT
Figure 6: Snapshots of energy based generative models: (left) snapshots for every 1k steps on MNIST ResNet, (right) snapshots for text filling task on BERT in Table 2

---

Table 2: Quantative results text infilling. The reference text for computing the Corpus BLEU is the combination WT103 and TBC.
Unique R-grams (%)
Methods
Self-BLEU (L)
Self
WTT03
TBC
Corpus BLEU (t)
n
==3
ft
N
RWM
92.41
6.26
9.10
18.97
26.73
19.33
26.67
16.24
GWGVt
85.93
11.22
17.14
23.16
35.56
23.58
35.56
16.75
DMALAV
85.88
11,58
17.14
22.07
34.08
23.22
34.15
17.06
PASVZ
85.39
11.37
17.60
22.61
35.53
23.65
35.47
16.57
DIMCFV
88.39
9.53
14.06
21.00
31.85
22.27
31.98
16.70
DIMC
85.28
12.05
17.65
24.03
36.34
24.51
36.27
16.45
GWG
81.15
15.47
22.70
25.62
38.91
25.62
38.58
16.68
DMALA (41
80.21
16.36
23.71
25.60
39.39
26.75
39.72
16.53
PAS
81.02
15.62
22.65
25.59
39.28
26.08
39.48
16.69
DLMC
80.12
16.25
23.76
25.41
39.31
26.86
39.57
16.73
7
DLMC 2+1
84.55
12.62
18.47
24.27
37.28
24.94
37.14
16.69
Conclusion
DISCS is a tailored benchmark for discrete sampling. It implements a range of discrete sampling tasks and state-of-the-arr discrete samplers and enables fair comparison. From the results, we know that DLMC leads in sampling from classical graphical models, PAS leads in solving combinatorial optimization problems, DL.Mf and DMALA have the performance on language models. We believe more efficient discrete samplers can be obtained by designing better discretization of DLD (Sun et al. 2022a). DISCS a convenient tool during this process. The researcher can freely set configurations for tasks and samplers and DISCS will automatically compile the program and run the processes in parallel. Besides, we observe that the choice of the locally balanced weight function should depend on the critical temperature of the target distribution. We believe this observation is insightful and will lead to a deeper understanding of locally balanced samplers.
Of course, DISCS does not include all existing tasks or samplers in discrete sampling, for example, the zero order (Xiang et al. 2023) and second order (Sun al. 2023a) approximation methods. We will keep iterating DISCS and more features will be added in the future. We wrap DISCS to JAX library. Researchers can conveniently implement customer tasks or samplers to accelerate their study and, in the meanwhile, contribute the code to DISCS for further improvement. We believe DISCS will a powerful tool for researchers facilitate future research in discrete sampling.
Acknowledgments
The authors would like to thank Bo Dai, Bethany Wang, Emily Xue for providing helpful discussions, and Pengcheng Ying, Sherry Yang and anonymous reviewers for the helpful comments on the paper.
References
Baumgärtner, A., Burkitt, A., Ceperley, D., De Raedt, H., Ferrenberg, A., Heermann, D., Herrmann. H., Landau, D., Levesque, D., von der Linden, W., et al. The Monte Carlo method condensed matter physics, volume 71. Springer Science & Business Media, 2012.
Carpenter, B., Gelman, A., Hoffman, M. D., Lee, D., Goodrich, B., Betancourt, M., Brubaker, M., Guo, J., Li, P., and Riddell, Stan: A probabilistic programming language. Journal of statistical software, 76(1), 2017.
Dai, H., Chen, X., Li, Y., Gao, X., and Song, L. A framework for differentiable discovery of graph algorithms. 2020a.
Dai, H., Singh, R., Dai, B., Sutton, C., and Schuurmans, D. Learning discrete energy- based models via auxillary-variable local exploration. arXiv preprint arXiv:2011.0553 2020b.
Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for language understanding, arXiv preprint arXiv:1810.04880 2018.
10

---

Donahue, C., Lee, M., and Liang, P. Enabling language models to fill in the blanks. arXiv preprint 200:20005.05339, 2020.
Du, Y. Li, S., Tenenbaum, J., and Mordatch, I. Improved contrastive divergence training energy based models. arXiv preprint arXiv:2012.01116 2020.
Edwards, F. and Anderson, W. Theory of spin glasses. Journal of Physics F: Metal Physics, (5):965, 1975.
Ghahramani, Z. and Jordan, M. Factorial hidden markov models. Advances in Neural Information Processing Systems, 1995.
Grathwohl, W., Swersky, K., Hashemi, M., Duvenaud, D., and Maddison, C. J. Oops I took a gradient: Scalable sampling for discrete distributions. arXiv preprint arXiv:2/02.04509, 2021. 2021.
Gu, J., Bradbury, J., Xiong, C., Li, V. O., and Socher, R. Non-autoregressive neural machine translation. arXiv preprint Sidi::1711.228811 2017.
Hamze, F. and de Freitas, N. From fields to trees. arXiv preprint arXiv: 12X.v::207.41440 2012.
Hastings, W. K. Monte Carlo sampling methods using Markov chains and their applications. 1970.
Hinton, G. E. Training products experts by minimizing contrastive divergence, Neural computation. 1778):177 2002.
Hubbard, J. Calculation of partition functions. Physical Review Letters, 3(2):77, 1959.
Hukushima, K. and Nemoto, K. Exchange monte carlo method and application spin glass simulations. Journal of the Physical Society Japan, 65(6):1604-1608, 1996.
Ising, E. Beitrag zur theorie des ferro-und paramagnetismus. PhD thesis, Grefe & Tiedemann, 1924.
Katzgraber, H. G., Palassini, M., and Young. A. Monte carlo simulations of spin glasses low temperatures. Physical Review B, 63(18):184422, 2001.
Kirkpatrick, S., Gelatt Jr, C. D., and Vecchi, M. P. Optimization by simulated annealing, science, 220 (4598):671-680, 1983.
LeCun, Y. The mnist database of handwritten digits. http://yanm. lecun. com/exdb/nmist// 1998.
LeCun, Y., Chopra, S., Hadsell, R., Ranzato, M., and Huang, F, A tutorial on energy-based learning.
Predicting structured data, 1(0), 2006.
Merity, S., S., Xiong, C., Bradbury, J., and Socher, R. Pointer sentinel mixture models. arXiv preprint arXhv:1609.07843 2016.
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., and Teller, E. Equation of state calculations by fast computing machines. The journal of chemical physics, 1186:1087 1953.
Papineni, K., Roukos, S., Ward, T., and Zhu, W.J. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pp. 311-318, 2002.
Potts, R. B. Some generalized disorde transformations. Mathematical proceedings of the cumbridge philosophical society, volume 48, pp. 106-109. Cambridge University Press, 1952.
Rhodes, B. and Gutmann, M. Enhanced gradient-based meme in discrete spaces. arXiv preprint wrXiv:2208.00044 2022.
Robert, C. and Casella, G. Monte Carlo statistical methods. Springer Science & Business Media, 2013.
Sansone, Lsb: Local self-halancing meme in discrete spaces. International Conference on Machine Learning, pp. 19205-19220. PMLR, 2022.

---

Sun, H., Dai, H., Xia, W., and Ramamurthy, A. Path auxiliary proposal for MCMC in discrete space. In International Conference on Learning Representations. 2021.
Sun, H., Dai, H., Dai, B., Zhou, H., and Schuurmans, D. Discrete Langevin sampler via Wasserstein gradient flow. arXiv preprini arXiv:2206. 14897, 2022a.
Sun, H., Dai, H., and Schuurmans, D. Optimal scaling for locally balanced proposals in discrete spaces. arXiv preprint arXiv:2209.08/88, 2022b.
Sun, H., Guha E. K., and Dai, H. Annealed training for combinatorial optimization on graphs. arXiv preprint ar Xiv:: 220..1142. 2022c.
Sun. H., Dai, B., Sutton, C., Schuurmans, D., and Dai, H. Any-scale balanced samplers for discrete space. In The Eleventh International Conference on Learning Representations, 2023a.
Sun, H., Goshvadi, K., Nova, A., Schuurmans, D., and Dai, H. Revisiting sampling for combinatorial optimization. In International Conference on Machine Learning, pp. 19205-19220. PMLR, 2023b.
Swendsen, R. H. and Wang. J.-S. Nonuniversal critical dynamics in Monte Carlo simulations. Physical review letters, 58(2):86, 1987.
Titsias, M. K. and Yau, C. The Hamming ball sampler. Journal of the American Statistical Association, 1126520)1598-16111 2017.
Tran, T., Phung, D., and Venkatesh, S. Mixed-variate restricted boltzmann machines. In Asian conference on machine learning. pp. 213-229, PMLR, 2011.
Vehtari, A., Gelman, A., Simpson, D., Carpenter, B., and Bürkner, P.-C. Rank-normalization, folding, and localization: An improved for assessing convergence of meme (with discussion). Bayesian analysis, 16(2):667-78,, 2021.
Wang, A. and Cho, K. Bert has a mouth, and must speak: Bert as a markov random field language model. arXiv preprint arXiv:190..0000 04094, 2019.
Xiang, Y., Zhu, D., Lei, B., Xu, D., and Zhang, R. Efficient informed proposals for discrete distribu- tions via newton's 's series approximation. In International Conference on Artificial Intelligence and Statistics, pp. 7288-7310. PMLR, 2023.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: novel image dataset for henchmarking machine learning algorithms, 2017a
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint 1708:0770,.77777, 2017b.
Zanella, G. Informed proposals for local MCMC in discrete spaces. Journal of the American Statistical Association, 1 115(530):5228865 2020.
Zhang, R., Liu, X., and Liu, Q. A Langevin-like sampler for discrete distributions. In International Conference on Machine Learning, pp. 26375-26396. PMLR, 2022.
Zhou, C., Neubig, G., and Gu, J. Understanding knowledge distillation in non-autoregressive machine translation. arXiv preprint 1rXiv: 2019.
Zhu, Y., Kiros, R., Zemel, R., Salakhutdinov, R., Urtasun, R., Torralba, A., and Fidler, S. Aligning books and movies: Towards story-like visual explanations by watching movies and reading books. In Proceedings of the IEEE international conference on computer vision, pp. 19-27, 2015.
Zhu, Y., Lu, S., Zheng, L., Guo, J., Zhang, W., Wang, J., and Yu, Y. Texygen: A benchmarking platform for text generation models. In The 41st international ACM SIGIR conference on research & development in information retrieval, pp. 1097-1100, 2018. 8.
12

---

A Experiments Details
A.1 Classical Graphical Models
For all the experiments of classical graphical models, we run 100 chains. The chains run in parallel on 4 VI00 GPUs, with each GPU managing mini-batch of 25 chains. We report the performance of all the samplers on Bernoulli Model Categorical Model [8] Ising Model Potts Model [0 and FHMM IT] We study the effect of number of discrete variables (sample dimension), the number of categories for each discrete variable, weight function for locally balanced samplers, and the smoothness/sharpnes, of different models. Note that the result for BG-2 on Potts 10 and Categorical g model with 256 categories are omitted as takes over 100 hours. The chain length is set as million steps when studying the effect of the number of categories and sample dimension. In the other cases, we use 100k steps as the chain length. For each experiment, as we sample the chains, each sample from each chain at each step is mapped to lower dimension of 1. The samples mapped on the same arbitrary sample which we randomly initialize in the beginning the experiment. We calculate ESS the mapped samples after the burn-in phase i.e. after the generation of half of the chain. We explain more details on ESS computation in section A.6.1 The average and standard deviation of ESS is computed over all the chains and is reported over the running time and number of energy evaluation of each sampler.
In the following sections, we provide the energy function we used for each of the classical graphical models.
A.1.1 Factorized Models
Factorized models are the simplest distributions a discrete space, where each site is independent from the others. Consider the category set of one hot vectors C = fei...., ec) } and the state space X' = CN. We have C| = is the number of category and N is the number of variables. The energy function of factorized model is:
f(x)
(nn 0t)
where dd E RCC We denote the target distribution Bernoulli model when C' = 2 and Categorical model when C' > 2. We report the results on Bernoulli models and Categorical models Figure and X respectively.
A.1.2 Ising Models
The Ising model (Ising 1924) is a mathematical model of ferromagnetism in statistical mechanics.
It consists of binary random variables arranged in a lattice graph G = (V, E') and allows a node to interact with its neighbors. The Potts model (Potts 1952) a generalization of the Ising model where the random variables are categorical. The energy function for Ising model and Potts model can be described as:
((x)
Σ (n Ow)
Σ (19( (b,))E
(10)
where we set dd RR" and Jıy (Zi, VU) (a. my: For Ising model, use Ht ~ Uniform 1) for the outer part of the lattice graph, and 6t ~ Uniform( (1,2) for the inner part of the lattice graph. We report the results on Ising model and Potts model in Figure 10
A.1.3 Factorial Hidden Markov Model (FHMM)
FHMM (Ghahramani & Jordan 1995) uses latent variables to characterize time series data. In particular, assumes the continuous data y IR is generated by hidden state r Cl.ck The probability function is:
L
K
p(x) = p(x1) II 1(a"11x' p(y2)) II N Σ (We, + b²
(11)
1=2
13

---

In particular, for binary model, we consider P(11 = 0) 0.9, x - )-) 0 2.0.
We use L 200, K 50 for high temperature setting and L 1000, K 10 in low temperature setting. For categorical model, we use p(11 (2] * 0) and p(a"|='-1 xx * x²-1) as uniform distribution and we use 200, K 10 with category number C 4, We report the results in Figure 11
A.2
Combinatorial Optimization
Table 3: Synthetic data statistics.
MIS
Max Clique
Maxcut
Name
ER-[700-800]
ER ER- [9000-10 1000]
RB
ER
BA
Max nodes
800
10,915 1,190,799
475
1,100
1,100
Max edges
47,885
90,585
91,239
4,384
# Test instances
128
16
500
1.000
1,000
Table 4: Real-world data statistics.
MIS
Max Clique
Maxeut
Balanced Graph Partition
Name
SATLIB
Twitter
Optsicom
MNIST
VGG
ALEXNET
RESNET
INCEPTION
Max nodes
1,347
247
125
414
1,325
798
20,586
27,114
Max # edges
5.978
12,174
375
623
2,036
1,198
32,298
40,875
# Test instances
500
196
10
1
Here we first provide the experimental details for the combinatorial optimization problems, Maximum Independent Set (MIS), Max Clique, MaxCut and, Balanced Graph Partition. The statistics of the synthetic datasets, including the maximum number of nodes/cdges in graph, and the number of test instances are reported 3 Additionally the statisties of real- world graphs are in in For MaxCut-baa all Balanced Graph Partition and MIS graphs, we use 32 as the number of chains and for Max optsicom, MaxCut-er, and all Max Clique graphs we use 16. The data used for these experiments could be found at DISCS DATA
We all the experiments 8 V100 GPUs in parallel. For only MaxCut Optsicom graph, we use V100 GPUs The test instances are divided evenly between the GPUs and are run in parallel. For each experiment, we report the average and standard deviation of the best solution found over the number of test instances along with the end-to-end run time (in seconds) of each in tables. We report the results for all the samplers and plot their solution the chain is being generated over M-H step and the running time. Note that for reporting the standard deviation for the plots, for better visualization, we clip the found solutions by a minimum of zero (removing the penalty effect of the optimization objective). However, the tables include the accurate standard deviation of the best solution found over the instances.
In the following sections, we provide the energy function we use for each of the combinatorial optimization problems. For a graph G = (V, E)) label the nodes in V from d. The adjacency matrix is represented as A. For weighted graph, we simply let At denote the edge weight between follow Sun al. (022cc) to select penalty coefficient
node: and j. For constraint problems, as the minimum value of X such that x² := arg min f(x) is achieved at x* satisfying the original constraints. Such choice of the coefficient guarantees the target distribution converges the optimal solution of the original CO problems while keeping the target distribution as smooth as possible.
A.2.1 Maximum Independent Set (MIS)
The MIS has the integer programming formulation
min =E (0.14
C.T, s.t. T.. = 0. v(i E
(12)
We use the corresponding energy function in the following quadratic form:
f(x) == - x x Ax
(13)
2
14

---

In our experiments equals to 1 and we use À = 1.0001. In post processing, we iteratively go through all nodes x; for i ...,, d. If there exists 2; for (I,, 23) E E, we flip its value z;- 0. After post processing, the state x: is guaranteed to be feasible in the original MIS problem. We provide the average and standard deviation of the best solutions over all the number of instances along with their
corresponding running time (S) at 5 The plots of the experiments could be found at 12
Table 5: MIS.
Sampler
Dendity
Graphs
0.05
0.10
ERI 200 800)
0.15
0.20
0.25
ER|9000
0.15
SATLID
HR-10-1
Timets)
Size
100:374 20033
426
$8.750 = 1.12
390.810
4.812 0.344
684,500
2.344:0674
414,067
26,469
429.879
0.749
277.149 3.205
15139.425
122427 = T4CACO
$381.857
102.46 112.468-4 2.155
60,000
0.765
32,250
27.312
316.170
3.187
422
14,300
Timets)
13079.125
Size
97.186 =
56.249 0.968
40.429 0.777
31.219
0.599
25.594
-555/674 259 359.008
280
Time(s)
284,002
293.517
499.577
297.
281.772
12401.737
2855.73 729
GWG-nA
Timets)
Size
104.812-5 1.590
278.885
62. 125 0.739
308.873
44 44.381 +0.530 0.830
737,671
34812 + 0.583
303.435
28. 187 00463
310.551
367,310
24698, 296
583
422.971 + 14,407
3540,670
DMALA
Size
104.750
= 1,803
62.031 = 0.684
44,195 :: 0.781
34,375 0.599
28,031 0.467
5570058 9,A22
423.641 = 14,506
Timets)
291,271
292.133
714,614
297,848
298.732
24769,380
3465,343
PAS
Timets)
105.062 1,560
310.765
0.790
34,719
0.6222
28.500
25342.166
424 14,531
DLMCF
Timets)
291.366
1.561
62,219
301.554
44.078
726.257
0.746
34.469
302.667
0.558
125 0.414
300,413
354:121 10
24892.216
423.387
3679,125
DLMC
Time(s)
Size
104.844 1,760
293.235
187 = 0.882
294,973
44.275 + 0.788
725.306
34,500 + 0.707
294,688
28. 281 0.450
399.884
S55 355.059 + 10.128
24976.312
423 479 + 14.488
3523.33 520
We also conduct experiments justify the results are robust regarding the choice of the penalty coefficient. In Figure 13 we use penalty coefficient À E {1.001, 1.1, 2} on ER-[700-800 graphs with density {0.05, 0.10, 0.15, 0.20, 0.25J. We also use a dashed line represent the optimal value obtained by running Gurobi-10 for I hour. From the results, we can observe that 1) PAS consistently obtains the best results, 2) locally balanced samplers have results consistently better than traditional sampler and Gurobi.
A.2.2 Max Clique
The max clique problem is equivalent to MIS on the dual graph. In experiments equals 1.
min #e (0.1)
Ca s.t. 24æ = 0, v(i,)) $
(14)
The energy function is
:-)==-ch =-x
(1 J (1
1) 11) 1)- Ax)
(15)
In our experiments eequals to 1 and we use À = 1.0001. In post processing, we iteratively go through all nodes x; for i L.... d. If there exists 2, for (I,, & E. we flip its value zj- = 0. After post processing, the state is guaranteed to be feasible in the original Max Clique problem. We provide the average and the standard deviation of the best solutions over all number of instances along with their corresponding running time o The plots of the experiments could be found at 14
A.2.3 MaxCut
We optimize the following problem:
1 - T
min 1111
Aij
(16)
2
(KJ)EE
Note that for simplicity each dimension of x is selected from 1-, To represent the corresponding energy function for x E 10d, , we have
1 (2.r: 1) 1)
f(x)
Σ Aij
(17)
2
(NEE
In our experiments A.j equals to 1. Since the problem is always feasible, the post processing is an identity map. We provide the average and standard deviation of the best solutions over all number of instances along with their corresponding running time at The plots of the experiments could be found at [5]
15

---

Table 6: Max Clique.
Sampler
Results
RB
TWITTER
Ratio a
0.850 I 0.0620
0.966 0.056
HB-10-1
Time(s)
1724.893
6.817
Ratio
0.859 0.061
0.995 +: 0.030
BG-2
Time(s)
1592.808
6,327
Ratio
0.841 + 0.0633
0.584 = 0.484
RWM
Time(s)
1683,397
5.664
Ratio
0.878 0,062
0.999 + 0,010
GWG-nA
Time(s)
2525.801
6.032
Ratio a
0.876 = 0,0620
0.999 = 0.004
DMALA
Time(s)
2561.617
6,190
Ratio &
0.878 + 0.0618
0.999 + 0.011
PAS
Time(s)
2542.538
6.160
Ratio &
0.871 0.061
0,999 = 0.011
DLMCF
Time(s)
2532.835
5,988
Ratio
0.875 0.062
0.999 + 0.009
DLMC
Time(s)
2639.588
6.124
Table 7: Maxcut
Sampler
Reath
ER
OPTSICOM
100
142.88
251.63
34R.225
10001000
782.21
792.338
1131:302
1990.554
35..09
416.802
1488.362
75:347
Rase
1200L00000
10001110000
1000100000
101420004
10L30005
0.99 1000
LIMESC0000
Tindl
SUXUR3
335,258
390082
331220
578.991
1132.21
116
351.04
1295:19
1WM
534.15
$36.15
535.411
$55.506
$41.30
S76.75
1055222
207.01
40C
1266.630
$8 $1,960
GWG--A
1000050000
1.00000000 DO0
100000000 000
100000 D00
10000000000
100000000
017401004
001-00117
1002-00001
000 001-60001
10000000000
IMALA
Timel
1000-0000
531,433
1.000000000
S38.358
1006500000
568.354
100-0.000
SE0.26
SEL.66
100000
750.00
0026-00044
E290
101--0017
357
102:0 0001
461 179
1007--0000
1653.175
1,000-00000
$3 509
R
1000--02000
1.00000000 DOO
100+0 DOX
1:00-00000 DO0
1000000000
1000-000S
1003-0 004
101--0017
1002-00001
1007-60001
1.000-000000
DUMCF
Ralon
Timej
1000-00000
ST1 982
1.000-00000
S76-299
100-01000
S15,8T7
100--0.000
554-564
100-0000
535.19
1000-00005
7ESTI9
005--0004
1510 380
772.64
0117
452.200
0.01
[001 0011--6005
1639-570
1.000-00000
17 537
1,000-02200
1.000-00000
1000-10000
1000--00000
1.000-01015
1004-0094
101--0017
1817 0001
1007--/001
1.000-00000
A.2.4 Balanced Graph Partition
We find the following objective for balanced graph partition gives the hest result:
&
k
d
2
[(x)= = Σ Σ (x: * x,, s1,,, = x)) +
d/k Σ T(x =
(18)
(IJ)EE
where k is the number partitions. Since the problem is always feasible, the post processing identity map. We provide the edge cut ratio and balanceness of the best samples over all the chains at g Further details on the calculated metrics could be found A.6.2
A.3 Energy Based Generative Models
A.3.1 Restricted Boltzmann Machine
The RBM is an unnormalized latent variable model, with visible random variable CN and hidden random variable h E {0, 1]M When v is binary, we call a binary RBM (binRBM) and when is categorical, call it a categorical RBM (catRBM). The energy function of both binRBM
and catRBM (Tran et al. 2011) can be written as:
N (Uns On)
M Σ m=1
((v) = Σ
Bmh (lmommmd vn)
(19)
1=1
d.m.
Unlike the previous three models, where the parameters are hand designed, we train binary RBM on MNIST (LeCun 1998) and categorical RBM on Mushion-MNIST (Xiao et al., (017a) using contrastive divergence Hinton (2002). Across all settings, we have = 784. For binary models, we use M 25 for high temperature setting and M = 200 for low temperature setting. For categorical models, we use M = 100. We report the results in Figure 16 The experimental setup is similar to classical graphical models.
16

---

Table 8: Balanced graph partition.
Metric
Samplers
VGG
MNIST-conv
ResNet
AlexNet
Inception-v3
HB-10-3
0.050
0,046
0.050
0.037
0.065
BG-2
0.048
0.045
0.050
0.038
0.069
RWM
0.054
0.046
0.092
0.052
0.117
GWG
0.102
0.046
0.159
0.063
0.164
DMALA
0.084
0.058
0.178
0.063
0.176
DMALA-nA
0.059
0.045
0.048
0,039
0.054
Edge cut ratio J.
PAS
0.053
0.045
0.047
0.037
0.052
PAS-nA
0.084
0.050
0.138
0.053
0.144
DLMCF
0.086
0.063
0.178
0.053
0.176
DLMCF-nA
0.092
0.069
0.048
0.085
0.052
DLMC
0.105
0.056
0.183
0.097
0.182
DLMC-DA
0.113
0.048
0.082
0.091
0.086
HB-10-1
0.999
0.999
0.999
0.999
0,999
BG-2
0.999
0.997
0.999
0.999
0.999
RWM
0.999
0.998
0.999
0.999
0.999
GWG
0.999
0.997
0.999
0,999
0,999
DMALA
0.999
0.998
0.999
0,999
0,999
DMALA-nA
0.999
0.997
0.999
0.999
0.999
Balanceness
PAS
0.999
0.997
0.999
1.000
0.999
PAS-nA
0.999
0.998
0,999
0.999
0,999
DLMCF
0.999
0.997
0,999
0,999
0,999
DLMCF-DA
0.999
0.995
0.999
0.999
0,999
DLMC
0,999
0.994
0.999
0.999
0.999
DLMC-DA
0.999
0.993
0.999
0.999
0.999
A.3.2 Deep residual network
In this experiment, we train deep residual network on MNIST, Omniglot and Caltech dataset. The models checkpoints could be found at DISCS DATA We use all the samplers to sample from the trained energy based generative models. We use the chain length of 10k and number of chains of 100. We randomly selected one chain from the 100 chains and save sample after each 1k steps, giving us 10 images per each chain for each sampler 17] We can see that locally balanced samplers are able to generate higher quality images faster and visit more diverse modalities.
A.3.3 Text Infilling
The experimental set up is explained in detail at 4.4 Here we additionally provide the performance of the locally balanced samplers in their non adaptive condition observed a The data used for this experiment could be found at DISCS DATA
A.4
DISCS Code
The source code is open source DISCS with extensive documentation.
A.5 Data-Set
The data used in this paper is available at DISCS DATA Under the data set folder, you can find:
Restricted Boltzmann Machine (RBM) checkpoints, more specifically two binary RBM checkpoints trained MNIST dataset, one with 25 hidden dimensions and other with 200. Two categorical RBM checkpoints, trained on Fashion-MNIST data set with and categories. [6
Deep residual network checkpoints, more specifically three checkpoints trained on MNIST, Omniglot and Caltech dataset.
Graphs data used for combinatorial optimization experiments found at sco directory.
Text infilling data used for text infilling task experimentation.
17

---

Table 9: Quantative results text infilling. The reference text for computing the Corpus BLEU is the combination WT103 and TBC.
Unique n n-grams (%) (f)
Methods
Self-BLEU (L)
Self
WT103
TBC
Corpus BLEU (1)
2
3
RWM GWGVE
92.41
6.26
9.10
18.97
26.73
19.33
26.67
16.24
85.93
11.22
17.14
23.16
35.56
23.58
35.56
16.75
GWG FFT
81.15
15.47
22.70
25.62
38,91
25.62
38.58
16.68
DMALA-BAVE
83.99
13.26
19.52
24.33
36.40
25.30
36,40
16.37
DMALA-1A FF
80.44
15.86
23.58
25.79
39.88
26.57
40.20
16.64
DMALAVE
85.88
11.58
17.14
22.07
34.08
23.22
34.15
17.06
DMALA FI
80.21
16.36
23.71
25.60
39.39
26.75
39.72
16.53
PASVE
85.39
11.37
17.60
22.61
35.53
23.65
35.47
16.57
PAS
81.02
15.62
22.65
25.59
39.28
26.08
39.48
16.69
DIMCI-WAVE
91.57
7.25
10.42
19.53
28.31
20.13
28.18
16.56
DLMCI-DA
81.66
15.31
21.78
26.39
39.56
27.60
39.69
16.31
DLMCIVT
88.39
9.53
14.06
21.00
31.85
22.27
31.98
16.70
DLMC
80.12
16.25
23.76
25.41
39.31
26.86
39.57
16.73
DAVT
83.74
12.74
19.64
24.27
37.27
24.94
37.34
16.73
DLMC- EFT
82.26
14.18
21.41
25.51
39.10
26.18
39.29
16.55
D
85,28
12.05
17.65
24.03
36.34
24.51
36,27
16.45
DLMC, 111
84.55
12.62
18.47
24.27
37,28
24.94
37.14
16.69
A.6 Metrics and Evaluation Methods
Depending on the task we are solving, we use different metrics and evaluation methods to measure the quality of the generated samples. Below explain in detail the process of evaluation for different tasks in the benchmark. Additionally, referring to an example provided in 4.4) DISCS is structured in way that researchers easily plug in evaluation methods and define their domain specific scores. For further code implementation details, you can refer to DISCS-Evaluato
A.6.1 Classical Graphical Models
For each of the experiments of classical graphical models, we run multiple chains in parallel. We rely on Effective Sample Size (ESS) measure the efficiency of different samplers. We compute the ESS using tfp.substrates jam.mmc..a..mmm...feeeet.e second half of the chain after the burn-in phase. The average and the standard deviation of the ESS is computed and reported over the chains.
sample_sizz size from Python TensorFlow library on the
A.6.2 Combinatorial Optimization
For the combinatorial optimization problems, for each of the test instances, we run multiple chains in parallel. Throughout the chain generation, we keep track of the best solution over all the chains for each of the instances. We report the average and standard deviation of the best solutions found over test instances for each problem.
For balanced graph partition problem, we additionally store the sample resulting in the best solution of the optimization problem and do further post processing on Let n be the number of nodes and the g number of disjoint sets. For each of the instances, we load the corresponding graph and the best solution and compute the edge cut ratio as the ratio of the balanceness as one minus the MSE of number of nodes in every partition and balances partition n/g
the total number of edges and the
A.6.3 Energy Based Generative Models
For the text infilling task, we evaluate the generated text from two perspectives, diversity, and quality. For diversity, we use self-BLEU (Zhu et al., 2018) and the number of unique n-grams (Wang & Cho 2019) to measure the difference between the generated sentences. For quality, we measure the BLEU score (Papineni et al. 2002) between the generated texts and the original dataset, which is
18

---

the combination of TBC and WikiText- 103. We rely on Natural Language Toolkir (NLTK) Python library, more specifically takk.translate.ble score and uggaas to compute the metrics above.
To gain insights into the performance and the quality of the generated samples we also rely on visual representation 17 As the chains are generated, the samples are saved images different time intervals. The images could provide insights on the performance of the sampler in terms of the quality and diversity of generated samples.
19

---

Effect dimension
sample dimension
N0301
307
pepit
oraisi7
E35
Effect balancing function
balancing
5410 crnaka
Otrels
B5
High temperature Bernoulli
High temperatiure Bernoull
16-011
bp2
perpll
smalutt
smale.
pax-7
diranit
strdtey
ESS
diriffic
Low tern pempenuuure Bemoulli
1bo0-1
1b-0-1
1p1
num
swo/7
smalitt
pas-T
106.
divdi
direci dirs.
Figure 7: Results of Bernoulli Models
20

---

sample Categorical
sample Categorical
10-10-1
gesif
onabii
ES
Effect of ballancing function Categorical
Effect of lancing function type Categarical
(94)
strala
diive
dimnc
Effect categories on Categorical
categories Categorical
Stals/T
smeak?
ESS wr..lock
Figure 8: Results of Categorical model
21

---

sample lsig
ho-101
by
E55 WrE
balancing type
Effect
Chrg Otrela
emalla
BS
High temperature tsing
High temperahire liiing
smalatt
diralant
smale,
dinefFF
strdley
Low temperature
tomperature tsing
1bo0-3
1b-0-1
bp3
prrp
swo/7
smalitt
pas-T
ateoF
atmeck
Figure 9: Results of Ising model
22

---

Effect of sample dimersion on Potts
16-10
SAm
655
Effect function type
Effect function type
cirals
para
Effect of number of categories an Potts
Effect of number categories on Potts
Savill
mivi
Figure 10: Results of Potts model
23

---

Binary
Smooth Binary RHMM
16:011
1o2
pwg.7
pmg.t
dinefii direffiz
ESS
Binary
Sharp Birwry raww
1b-0-1
tga
lo2
swo/f
envate
peayis diount
BSS
dtreit
Categorical FHMM with categorics
Categorical FHMM with 4 categories
emalact
Orrllart
smallay
direfeir
Categotical FHMM with categaries
Categorical categories
1o-0-3
1o20-1
1y2
hp3
num
peg/t
pwg.T
mmaluct
1M67
pan-i
ESS
droo
atrici direyii
Figure 11: Results of FHMMs
24

---

HR| (800088888 100--000-0005
100
Size Independeen ndeent Set
Size Independent Siet
sampler-
smppee-ppsss)
sampler-dmd8)
sam pler-clmmts)
samplerrggg-MM
-25
sampte--mmallss)
-25
zompler-omalltt
dmmdle--dmdja)
sam ampler=cimccttll
-30
sampler-gg2
-30
sampler:
1b-1011
smmatersbb119
sampler-
sam pmmper--mm
10000
20000
30000
40000
50000
100
200
300
400
Steps
60
60
ER 8-0-000-00.
40
40-
Size Indeppendett Seet
Size Indequndent
20
20
samplers
sampler-pasla)
daddter-dmdiss
sa daniokr-dncctii
sampler-dmdde
samplersdmnct)
Sampler-ggg-nA//
sampter-owgnMMa)
compler-dmalarse
sampkr-dmaaas)
sampler- bo
-60
samplembgg2
sampler=Mb-104
-60
sampber-h-1001
samplers rmm
sampkr-ram
-100
-100
HR 18000---0 800-0000-0000 J
40
40
Size of independent Set
Size of Independentt Set
samplers
sampler-
plor-paols)
-00
sampler-dmmed
-40
sam Sameee-ddmdde
samplers dimef(s) dimplersdime(())
pler cfmcffs)
60
sampler-dmallse
600
dmalaa)
sampler- bo-2
samper-
sampler- 1b-10-1
Samper-Nb1100
sampler-rwm
-100
-100
10000
20000
30000
40000
50000
400
Steps
Time
BR (108800-0 1300-800-0.25 25
Size of Indepindent Sett
Size of independent Set
-20
sampler: sests)
-20
som pamper-passs)
sampler- dimdssssss
sampler-cimmte
-00
sampler-gug-nA9
-40
Campler:dmmciis
sampler: simpfersoimmftee
-60
zampler-dmalaoe
-60
sample--mmsaath
sampler-bo-3 bg-2
-80
hampler=té-10- 10-1
sampee 1011
sampler-awm
sampler-rem
-100
-100
0
10000
20000
30000
40000
50000
0
100
200
300
400
Staps
Time (s)
440
440
420
Site Indequndentt Set
400
diddopandent
SATLIB
380
samplerw
samplerspast
380
sampler past
sampler=dmalass)
360
sampler-
samploradimcist
360
sampler=ddme(s)
samplermdimmcts)
340
gamplerngwg-AAis)
340
sampler=gwg nAts
zamplenwha-1o..
sampler=hb- 10-10-11
320
samplecebg.2.
sampler=bg
samplerarwm
sampler=nwm
300
500000
300
25

---

ER| (000-800) |
Size Indepenndent Set
Size independent Set
-100
-100
samplerspast pasts)
sam plmp---passs)
200
sampler= nAts
200
sample-gggg-nk
didiss)
sampler-dmake
3300
samptermsimllali
Compler-dmdffy
sempler-dimcffed som
sampler-bg22
4400
sampler-
-400
sampler-bb
sampler: nm
sampler
-500
10000
200000
50000
Stops
ER 9900- 11000]
400
Saye of Inddepemtent: Set
Size of independem:: Set
-200
samparrpasii
-200
samplermpatei
samplerngug-nAi
sampeerggwgg
complar-dmalals
se smmter=dmal alssss
samp sampli-dimccs)
so dimeerddmmmod
-800
dimpitr-dimctis
-800
sampar=boe2
samplermbg-2
-800
sbmpler-hbijf
-800
sampler=hb-10
10000
20000
30000
40000
50000
5000
10000
15000
20000
25000
Steps
Time (5)
Figure 12: Solving progress MIS
26

---

Set
140
ER (200700-80 000-800-0.05)
Hb-10-1
Eg
20
omalaisi
pasis)
cliicfss
Size
dlimcts)
1.001
1.01
1.1
2.0
ER 7700 111-800000100 1O]
hb-10-3
bg-2
rwm
pastst
dimettet
dimmls)
1.001
1.01
2.0
ER 700 111-800-0.111
hb 10
bg-2
garenAls)
dmalals!
paslst
dimmlij
Size
dlimass)
1.001
1.01
2.0
345
240
ER| (RR70-8000-0-0 ]
bg.
rwm
Size of Indepenn
dmallass)
pasts)
23.5
1.01
27

---

BR (RR700--80-0-.0 25]
hb-10-3
Size Independent
by-2 rwm
NAG dmalols)
dimmcs)
1.001
1.01
1.1
Figure 13: Reuslts on MIS: effect of penalty coefficient. The dashed line represents the best result obtained by running Gurobi for hour.
1.0
1.0
0.8
0.8
Ratio
(
Ratio
sampler-gwa
samplerspas(s)
sampler-pasio
RB
sampleerddalladt)
sampler- dmmala))ddmala(s
sampleredimets
sampler:
sampleredimdSs)
sampler-dinctts
samplar-bgg22
sampler=bg-22
samplermmb-10-11
sampler=hb- 10-1 sampler-ram
samplere-rwm
0.0
2500
5000
7500
10000
12500
15000
17500
20000
0.0
500
1000
1500
2000
2500
Steps
Time
1.0
1.0
0.8
0.8
Twitter
Ratio
0.6
sampler-geg pA(s)
Rato
0.6
sampler=dmaladss
samglef- qwa nAlsi
sampler=pas())
sampler-pasis
samplerydimctis)
Kampler dimeed) camplar-dimatsi samplermbg-2
tamokfredincts)
samplermbg-2
hbmpler-hb-10-11
samplar-hb-10-
fampler-nym
sampler-rem
0.0
200
400
600
800
0.0
Steps
Time (5]
Figure 14: Solving progress on Max Clique
28

---

1.01
sampler bg-2
1.01
1.00
samplem 10-1
23mpbr-ho-101
sampler=dmaleess
0.99
samplerm posts]
sampl/-pan(s]
BA- 14-16-20
0.98
sampler-
0.98
samplar-
53 mppor-cmmmss
0.97
dmm
0.97
sampkr-cincfts)
0.96
0.96
58 mpperrrm
0.95
0.94
0.93
0.93
10a
Steps
(4)
1.00
sampler-bp- by-2
samplem=bg-2
sampler-tb-10-
sampler-ho 10-1
0.98
samplir-dmall10
sampler-
0.98
sampler=dmakk(2
sample-pasls)
BA-32-40
0.96
gampllrrg
samplerndmett)
0.96
sampler-dimcds
sampler-gwg-oMt)
sampler=dmet dimett)
2300
0.94
sampler=-em
sampler-num
0.92
0.92
10a
10
10a
10
10
10c
10
10
10
Steps
Time (5)
1.00
samplermbbp 2
2ampler-bo2
0.98
sampleri dmall
1mmpler-t-10-..
sampler-ho-10:1
samplermdmale(s)
BA-64-75
sampler- pasts)
sampler=dmtts)
0.96
sampler-dindsi
samoler-paiis
0.94
skmple)mdime(())
sampler-am
sampler-nmm
0.92
(amplar=gwa-nAke
0.92
sampler-@wa
0.90
0.88
10a
10
10
10'
10
107
10
1.000
sampier=dimets
samplere dimcss)
sampler-pasis)
0.975
sampler-dimmfss
samplers (imcft)
BA-128-11 10-128-115 150
0.950
sampler--malaal dmalatss
0.950
sampler- dmalatst
Sampler-gug-nAik
sampler- gwg-nAls)
0.925
sampler=hb-1os.
0.925
samplers tb- 1--1
sampler-bgi
sampler ago?
0.900
sampler-rem
0.900
samplera
0.875
0.875
0.850
0.050
0.825
0.825
10a
10
107
107
10
10"
10"
10
10
10
Steps
Time 1st
1.00
simplerdmmalal sampleri dimcts)
sampleri pests)
mapperspas((s) 4a smpler-dmalats)
dimcts) samplerddmictte
BA-512-600
0.95
camplanwdmatte
0.95
samplers gvg nAts)
$3 gwp niis)
0..90
bg-2 sampler- Nb-10-1
0.90
mmpler=bb222
Patio
Patio
samplar nwm
43 mppterrym
0.80
0.80
0.75
0.75
107
10:
10
107
10a
107
Time
29

---

sampleripasts)
semplermpestsi
sampler-dmal
samplor-dmalat
BA- BA-1024-11M 100
dampler-dimctss
samplor-dimdt)
dimpier-
samplor=dimctt
sampler-gug-nAky
samplirguggnAn
0.90
samplermig-2
0.90
bampler=bg-2
Balln
sampler-hb-104
Samplemmhb-1t
0.85
samplerisem
0.85
0.50
0.80
0.75
0.75
10
10P
10
10
10-
10
Steps
1.04
1.04
1.02
1.02
ER-256-300 300
1.00
1.00
sampler-dmelate
sampler-dmalats)
sampler=dimcfsi
sampkir-dimerta
0.94
sampleredimx(s)
0.94
sampeeedime (8)
sampler-pasis)
sampkir-pasti
0.92
samplermgwg-nnkk
0.92
sampkrmgug-nnk
sampler=bo
samper=bg
samplermhb-10. 10-1
samplershb-10-1
samplerwnem.
samplerenmm
10a
10
10a
10
10a
10a
10a
Steps
Time (s)
0.98
0.98
ER-512-600
0.96
0.96
sampler-pests) samplerndimcis)
sampler-pastsl
(mmplermdimcts)
samplor=dmelate
samplerudmalajal
sampler=dimcfsi
sample-ddlmeteo
0.92
sampler-guo
0.92
sampler=bg-2
sampker=bg32
0.90
samplerwhb-100 10-1
0.90
samplerwho-100
sampler-rwm
samplewwwms
10f
10
10a
10a
10a
10a
10
10
Steps
Time (6)
1.00
1.00
ER- 1024-1 100
0.98
0.98
samplerndimc(s)
smpler-pasis))
Hatle
sam sampkeree pken-pasts
samplermdimcol
sampler=dmslatd
sampkrmdmalazs)
sampleragug-nnae
samplermgwg nAls)
sampler=dimxfss)
sampler-dime(t)
samplersibg-2
samplerabg
0.92
zampler=hb-100
0.92
samplerahb
sampler-nwm
sampler-rwm
10:
10a
10a
10:
Steps
samplereram
sampler-nwm
Sampler-hb-16-1
hb-101
samplerndmalats)
samplerrddmallts)
sampler-pasit)
sampler=pasts)
Optsicom
sampler=dimefis)
samplermdimees)
0.95
sampler=
dempleredimcte))
samplermbg-2
0.90
sampler-gwo nA(s)
0.90
sampleregagaate
0.85
10
107
10a
10
10'
Steps
Time (s)
Figure 15: Solving progress MaxCut
30

---

Binary dimension
1b-04
ho-10-1
102
pwgit
peggrt
pas-t
pan!t
dincfie
dreet
dnc.f
Binary with hidden dimension
Birary RBM with hrodenn dimension 2000
16:01
twm
pvp/i
emalt!?
smallai
posyly
abech
dinunt
ESS
direfii
Gategorical RSM with rategories
Categorical RBM with categaries
16:0-1
smalitt
diaaliit dmala
smalkay
ESS Oock
pondyy
Gategorical RBM with catepories
Categarical RBM with
1bo0a1
1o-0-1
bpa
prrg77
smabu?
diaisii
su
Punn
drsd,
drooF
drc.f
dmsi
Figure 16: Results of RBMs
31

---

[
5
22
dmahs
111
-77
dimc
VZ
P
01
X
X
Samplers
Omniglot
22
<13
314
P
7-5
2.55
522
PI-10-3
3
J
TAA
X1k Steps
5
3
8
3
3
1
+
4
8
8
3
3
X
3
9
9
3
5
8
S
3
8
8
dinc
5
2
3
3
3
3
7
Semplers
MNIST
4
7
4
4
4
4
4
4
8
8
8
8
8
8
8
8
1o-10-1
x1k Steps
Samplers dimc
Caltech
h92
NB-10-3
xlkc
Figure 17: Resnet EBM trained on different data set with snapshots for every 1k sampling steps
32


Reviews:
[{"review_id": "O1bKoMX050", "reviewer": "Reviewer_2XnF", "summary": "", "questions": "", "limitations": "I felt that the limitations were discussed reasonably well -- there are always more baselines to include and other tasks to consider.  The proposed tasks cover a broad range of possible use cases for samplers.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "Systematic frameworks are useful for head-to-head comparisons, especially when there are a number of different design choices. The benchmark is well-motivated and contains a number of existing techniques.", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "fcgBwDyYvr", "reviewer": "Reviewer_q6pU", "summary": "", "questions": "", "limitations": "The paper briefly acknowledges that DISCS does not encompass all existing discrete sampling tasks or samplers. However, it would be appreciated if more detail could be provided on which tasks, samplers, and metrics are omitted and why.\n\n", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "1. DISCS covers a wide range of tasks, including sampling from graphical models, solving combinatorial optimization problems, and sampling from deep energy-based generative models, and provides a simple interface that allows researchers to implement further discrete samplers.\n\n2. The paper introduces evaluation metrics tailored to each task type, allowing a fair comparison between different samplers.\n\n3. Interesting observations were made through the benchmarking process, such as the difference in the performance of locally balanced weight functions as a function of the critical temperature of the target distribution. ", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "H5KBaMwb5J", "reviewer": "Reviewer_Edfj", "summary": "", "questions": "", "limitations": "- Building on JAX, the benchmark DISC can be extended with more samplers and benchmarks. \n\n- No negative societal impact is expected.", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "- Discrete sampling is an important problem that is receiving more attention recently. A library was missing to quickly test various discrete samples against each other and against potentially new samplers. Thus, this is a timely and important contribution.\n\n- The authors include a range of different discrete samples.\n\n- It is important to note that also the methods are implemented and provided, in contrast to just providing a data set or benchmark problems. ", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "7dgSFrsaiI", "reviewer": "Reviewer_GKfw", "summary": "", "questions": "", "limitations": "No.", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "1. The discrete sampling is an important and general tool. A new convenient package and fair benchmarks would be highly valuable.\n2. The new phenomenon about the local balanced weight function would provide more insights into how to select the locally balanced function.\n3. The baselines are comprehensive.\n4. The provided examples are comprehensive, including Classical Graphical Models, Solving Combinatorial Optimiazation and Energy Based Generative Models.\n", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}]

Author rebuttal:

Meta-review: Paper proposes a unified framework for assessment of discrete sampling under three different paraadigms.
The reviews imply that, given the objectives, the paper could be more comprehensive. 
Overall, the concept and idea apper sufficiently novel to accept the paper, given that the authors intend to
further extend the framework in the future.
Decision: Accept (Poster)