# Fast Amortized Inference and Learning in Log-linear Models with Randomly Perturbed Nearest Neighbor Search

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2017.

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

- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [Dialogue Without Limits: Constant-Sized KV Caches for Extended Responses in LLMs](https://mlsanity.com/paper/2503.00979/) (2025)
- [Scalable Cross-Entropy Loss for Sequential Recommendations with Large Item Catalogs](https://mlsanity.com/paper/2409.18721/) (2024)
- [Compression Barriers for Autoregressive Transformers](https://mlsanity.com/paper/2502.15955/) (2025)
- [Learning distributed representations with efficient SoftMax normalization](https://mlsanity.com/paper/2303.17475/) (2023)
- [kNN Attention Demystified: A Theoretical Exploration for Scalable Transformers](https://mlsanity.com/paper/2411.04013/) (2024)
- [Entropy-Aligned Decoding of LMs for Better Writing and Reasoning](https://mlsanity.com/paper/2601.01714/) (2026)
- [Fast-MWEM: Private Data Release in Sublinear Time](https://mlsanity.com/paper/2602.03732/) (2026)

## Abstract (arXiv)

Inference in log-linear models scales linearly in the size of output space in the worst-case. This is often a bottleneck in natural language processing and computer vision tasks when the output space is feasibly enumerable but very large. We propose a method to perform inference in log-linear models with sublinear amortized cost. Our idea hinges on using Gumbel random variable perturbations and a pre-computed Maximum Inner Product Search data structure to access the most-likely elements in sublinear amortized time. Our method yields provable runtime and accuracy guarantees. Further, we present empirical experiments on ImageNet and Word Embeddings showing significant speedups for sampling, inference, and learning in log-linear models.