DISCS: ABenchmark for Discrete Sampling

Sampling in discrete spaces, with critical applications in simulation and opti-1 mization, has recently been boosted by significant advances in gradient-based2 approaches that exploit modern accelerators like GPUs. However, two key chal-3 lenges hinder the further research progress in discrete sampling. First, since there4 is no consensus on experimental settings, the empirical results in different research5 papers are often not comparable. Secondly, implementing samplers and target6 distributions often requires a nontrivial amount of effort in terms of calibration,7 parallelism, and evaluation. To tackle these challenges, we propose DISCS (DIS-8 Crete Sampling), a tailored package and benchmark that supports unified and9 efficient implementation and evaluations for discrete sampling in three types of10 tasks: sampling for classical graphical models, combinatorial optimization, and11 energy based generative models. Throughout the comprehensive evaluations in12 DISCS, we acquired new insights into scalability, design principles for proposal13 distributions, and lessons for adaptive sampling design.