# Sampling from Discrete Energy-Based Models with Quality/Efficiency Trade-offs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 50 references that are in the map.
- First posted on arXiv 10 Dec 2021.

## Builds on (most cited first, 20 of 20)

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [Improved Techniques for Training Score-Based Generative Models](https://mlsanity.com/paper/2006.09011/) (2020)
- [Texygen: A Benchmarking Platform for Text Generation Models](https://mlsanity.com/paper/1802.01886/) (2018)
- [How to Train Your Energy-Based Models](https://mlsanity.com/paper/2101.03288/) (2021)
- [Facebook FAIR's WMT19 News Translation Task Submission](https://mlsanity.com/paper/1907.06616/) (2019)
- [Improved Contrastive Divergence Training of Energy Based Models](https://mlsanity.com/paper/2012.01316/) (2020)
- [A Distributional Approach to Controlled Text Generation](https://mlsanity.com/paper/2012.11635/) (2020)
- [Residual Energy-Based Models for Text Generation](https://mlsanity.com/paper/2004.11714/) (2020)
- [CGMH: Constrained Sentence Generation by Metropolis-Hastings Sampling](https://mlsanity.com/paper/1811.10996/) (2018)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [Limitations of Autoregressive Models and Their Alternatives](https://mlsanity.com/paper/2010.11939/) (2020)
- [Energy-Based Reranking: Improving Neural Machine Translation Using Energy-Based Models](https://mlsanity.com/paper/2009.13267/) (2020)
- [Exposing the Implicit Energy Networks behind Masked Language Models via Metropolis--Hastings](https://mlsanity.com/paper/2106.02736/) (2021)
- [Distributional Reinforcement Learning for Energy-Based Sequential Models](https://mlsanity.com/paper/1912.08517/) (2019)
- [Global Autoregressive Models for Data-Efficient Sequence Learning](https://mlsanity.com/paper/1909.07063/) (2019)
- [Joint Energy-based Model Training for Better Calibrated Natural Language Understanding Models](https://mlsanity.com/paper/2101.06829/) (2021)
- [Do You Have the Right Scissors? Tailoring Pre-trained Language Models via Monte-Carlo Methods](https://mlsanity.com/paper/2007.06162/) (2020)
- [Language Generation via Combinatorial Constraint Satisfaction: A Tree Search Enhanced Monte-Carlo Approach](https://mlsanity.com/paper/2011.12334/) (2020)

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

- [Cascade Reward Sampling for Efficient Decoding-Time Alignment](https://mlsanity.com/paper/2406.16306/) (2024)
- [Improving abstractive summarization with energy-based re-ranking](https://mlsanity.com/paper/2210.15553/) (2022)

## Abstract (arXiv)

Energy-Based Models (EBMs) allow for extremely flexible specifications of probability distributions. However, they do not provide a mechanism for obtaining exact samples from these distributions. Monte Carlo techniques can aid us in obtaining samples if some proposal distribution that we can easily sample from is available. For instance, rejection sampling can provide exact samples but is often difficult or impossible to apply due to the need to find a proposal distribution that upper-bounds the target distribution everywhere. Approximate Markov chain Monte Carlo sampling techniques like Metropolis-Hastings are usually easier to design, exploiting a local proposal distribution that performs local edits on an evolving sample. However, these techniques can be inefficient due to the local nature of the proposal distribution and do not provide an estimate of the quality of their samples. In this work, we propose a new approximate sampling technique, Quasi Rejection Sampling (QRS), that allows for a trade-off between sampling efficiency and sampling quality, while providing explicit convergence bounds and diagnostics. QRS capitalizes on the availability of high-quality global proposal distributions obtained from deep learning models. We demonstrate the effectiveness of QRS sampling for discrete EBMs over text for the tasks of controlled text generation with distributional constraints and paraphrase generation. We show that we can sample from such EBMs with arbitrary precision at the cost of sampling efficiency.