# A New Unbiased and Efficient Class of LSH-Based Samplers and Estimators for Partition Function Computation in Log-Linear Models

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Mar 2017.

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

- [MagicPIG: LSH Sampling for Efficient LLM Generation](https://mlsanity.com/paper/2410.16179/) (2024)
- [Training Overparametrized Neural Networks in Sublinear Time](https://mlsanity.com/paper/2208.04508/) (2022)
- [You Only Sample (Almost) Once: Linear Cost Self-Attention Via Bernoulli Sampling](https://mlsanity.com/paper/2111.09714/) (2021)
- [Memory Mosaics](https://mlsanity.com/paper/2405.06394/) (2024)
- [Scalable Cross-Entropy Loss for Sequential Recommendations with Large Item Catalogs](https://mlsanity.com/paper/2409.18721/) (2024)
- [Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations](https://mlsanity.com/paper/2212.11408/) (2022)
- [RECE: Reduced Cross-Entropy Loss for Large-Catalogue Sequential Recommenders](https://mlsanity.com/paper/2408.02354/) (2024)
- [Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering](https://mlsanity.com/paper/2109.05773/) (2021)
- [LookupFFN: Making Transformers Compute-lite for CPU inference](https://mlsanity.com/paper/2403.07221/) (2024)
- [Cooperative Retriever and Ranker in Deep Recommenders](https://mlsanity.com/paper/2206.14649/) (2022)
- [Kernel approximation on algebraic varieties](https://mlsanity.com/paper/2106.02755/) (2021)
- [Improved Stochastic Optimization of LogSumExp](https://mlsanity.com/paper/2509.24894/) (2025)
- [Efficient Inference via Universal LSH Kernel](https://mlsanity.com/paper/2106.11426/) (2021)
- [Distributed SLIDE: Enabling Training Large Neural Networks on Low Bandwidth and Simple CPU-Clusters via Model Parallelism and Sparsity](https://mlsanity.com/paper/2201.12667/) (2022)
- [Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation](https://mlsanity.com/paper/2610.05174/) (2026)
- [Attention via Black-Box Vector Search](https://mlsanity.com/paper/2610.10135/) (2026)

## Abstract (arXiv)

Log-linear models are arguably the most successful class of graphical models for large-scale applications because of their simplicity and tractability. Learning and inference with these models require calculating the partition function, which is a major bottleneck and intractable for large state spaces. Importance Sampling (IS) and MCMC-based approaches are lucrative. However, the condition of having a "good" proposal distribution is often not satisfied in practice. In this paper, we add a new dimension to efficient estimation via sampling. We propose a new sampling scheme and an unbiased estimator that estimates the partition function accurately in sub-linear time. Our samples are generated in near-constant time using locality sensitive hashing (LSH), and so are correlated and unnormalized. We demonstrate the effectiveness of our proposed approach by comparing the accuracy and speed of estimating the partition function against other state-of-the-art estimation techniques including IS and the efficient variant of Gumbel-Max sampling. With our efficient sampling scheme, we accurately train real-world language models using only 1-2% of computations.