# Sampling Binary Data by Denoising through Score Functions

arXiv: https://arxiv.org/abs/2502.00557 · HTML: https://mlsanity.com/paper/2502.00557/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- First posted on arXiv 1 Feb 2025.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Built on by (most cited first, 7 of 7)

- [Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees](https://mlsanity.com/paper/2602.15008/) (2026)
- [Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics](https://mlsanity.com/paper/2512.00580/) (2025)
- [Algorithm- and Data-Dependent Generalization Bounds for Diffusion Models](https://mlsanity.com/paper/2506.03849/) (2025)
- [Bit-Level Discrete Diffusion with Markov Probabilistic Models: An Improved Framework with Sharp Convergence Bounds under Minimal Assumptions](https://mlsanity.com/paper/2502.07939/) (2025)
- [Binomial flows: Denoising and flow matching for discrete ordinal data](https://mlsanity.com/paper/2605.00360/) (2026)
- [Discrete Flow Matching: Convergence Guarantees Under Minimal Assumptions](https://mlsanity.com/paper/2605.08882/) (2026)
- [Jumping up and down: Denoiser diffusion models for discrete ordinal data](https://mlsanity.com/paper/2610.02754/) (2026)

## Abstract (arXiv)

Gaussian smoothing combined with a probabilistic framework for denoising via the empirical Bayes formalism, i.e., the Tweedie-Miyasawa formula (TMF), are the two key ingredients in the success of score-based generative models in Euclidean spaces. Smoothing holds the key for easing the problem of learning and sampling in high dimensions, denoising is needed for recovering the original signal, and TMF ties these together via the score function of noisy data. In this work, we extend this paradigm to the problem of learning and sampling the distribution of binary data on the Boolean hypercube by adopting Bernoulli noise, instead of Gaussian noise, as a smoothing device. We first derive a TMF-like expression for the optimal denoiser for the Hamming loss, where a score function naturally appears. Sampling noisy binary data is then achieved using a Langevin-like sampler which we theoretically analyze for different noise levels. At high Bernoulli noise levels sampling becomes easy, akin to log-concave sampling in Euclidean spaces. In addition, we extend the sequential multi-measurement sampling of Saremi et al. (2024) to the binary setting where we can bring the "effective noise" down by sampling multiple noisy measurements at a fixed noise level, without the need for continuous-time stochastic processes. We validate our formalism and theoretical findings by experiments on synthetic data and binarized images.