# A* Sampling

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

## Key facts

- Cited by 151 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2014.

## Built on by (most cited first, 30 of 151)

- [Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions](https://mlsanity.com/paper/2102.05379/) (2021)
- [Chasing Sparsity in Vision Transformers: An End-to-End Exploration](https://mlsanity.com/paper/2106.04533/) (2021)
- [In Prospect and Retrospect: Reflective Memory Management for Long-term Personalized Dialogue Agents](https://mlsanity.com/paper/2503.08026/) (2025)
- [Learning Graph Structures with Transformer for Multivariate Time Series Anomaly Detection in IoT](https://mlsanity.com/paper/2104.03466/) (2021)
- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [Performance-Efficiency Trade-offs in Unsupervised Pre-training for Speech Recognition](https://mlsanity.com/paper/2109.06870/) (2021)
- [Wavelet Score-Based Generative Modeling](https://mlsanity.com/paper/2208.05003/) (2022)
- [Informed Correctors for Discrete Diffusion Models](https://mlsanity.com/paper/2407.21243/) (2024)
- [LightTS: Lightweight Time Series Classification with Adaptive Ensemble Distillation -- Extended Version](https://mlsanity.com/paper/2302.12721/) (2023)
- [Differentiable Subset Pruning of Transformer Heads](https://mlsanity.com/paper/2108.04657/) (2021)
- [Regularized Vector Quantization for Tokenized Image Synthesis](https://mlsanity.com/paper/2303.06424/) (2023)
- [D&D: Learning Human Dynamics from Dynamic Camera](https://mlsanity.com/paper/2209.08790/) (2022)
- [Physically Realizable Natural-Looking Clothing Textures Evade Person Detectors via 3D Modeling](https://mlsanity.com/paper/2307.01778/) (2023)
- [Concrete Subspace Learning based Interference Elimination for Multi-task Model Fusion](https://mlsanity.com/paper/2312.06173/) (2023)
- [Stochastic Batch Acquisition: A Simple Baseline for Deep Active Learning](https://mlsanity.com/paper/2106.12059/) (2021)
- [Algorithms for the Communication of Samples](https://mlsanity.com/paper/2110.12805/) (2021)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement](https://mlsanity.com/paper/2403.15180/) (2024)
- [Dynamic Resolution Network](https://mlsanity.com/paper/2106.02898/) (2021)
- [Bridging Discrete and Backpropagation: Straight-Through and Beyond](https://mlsanity.com/paper/2304.08612/) (2023)
- [Meta-Aggregator: Learning to Aggregate for 1-bit Graph Neural Networks](https://mlsanity.com/paper/2109.12872/) (2021)
- [Compression with Bayesian Implicit Neural Representations](https://mlsanity.com/paper/2305.19185/) (2023)
- [Generalizable Human Pose Triangulation](https://mlsanity.com/paper/2110.00280/) (2021)
- [Influencing Towards Stable Multi-Agent Interactions](https://mlsanity.com/paper/2110.08229/) (2021)
- [Parallel Attention Network with Sequence Matching for Video Grounding](https://mlsanity.com/paper/2105.08481/) (2021)
- [Classical Planning in Deep Latent Space](https://mlsanity.com/paper/2107.00110/) (2021)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Deep Graph Reprogramming](https://mlsanity.com/paper/2304.14593/) (2023)
- [Multiresolution Equivariant Graph Variational Autoencoder](https://mlsanity.com/paper/2106.00967/) (2021)
- [Counterfactual Temporal Point Processes](https://mlsanity.com/paper/2111.07603/) (2021)

## Abstract (arXiv)

The problem of drawing samples from a discrete distribution can be converted into a discrete optimization problem. In this work, we show how sampling from a continuous distribution can be converted into an optimization problem over continuous space. Central to the method is a stochastic process recently described in mathematical statistics that we call the Gumbel process. We present a new construction of the Gumbel process and A* sampling, a practical generic sampling algorithm that searches for the maximum of a Gumbel process using A* search. We analyze the correctness and convergence time of A* sampling and demonstrate empirically that it makes more efficient use of bound and likelihood evaluations than the most closely related adaptive rejection sampling-based algorithms.