# Adaptive Sampled Softmax with Kernel Based Sampling

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2017.

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

- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Choose a Transformer: Fourier or Galerkin](https://mlsanity.com/paper/2105.14995/) (2021)
- [EGformer: Equirectangular Geometry-biased Transformer for 360 Depth Estimation](https://mlsanity.com/paper/2304.07803/) (2023)
- [Sparse Spiking Gradient Descent](https://mlsanity.com/paper/2105.08810/) (2021)
- [FMMformer: Efficient and Flexible Transformer via Decomposed Near-field and Far-field Attention](https://mlsanity.com/paper/2108.02347/) (2021)
- [Hybrid Random Features](https://mlsanity.com/paper/2110.04367/) (2021)
- [Item Recommendation from Implicit Feedback](https://mlsanity.com/paper/2101.08769/) (2021)
- [On the Theories Behind Hard Negative Sampling for Recommendation](https://mlsanity.com/paper/2302.03472/) (2023)
- [Accelerating SLIDE Deep Learning on Modern CPUs: Vectorization, Quantizations, Memory Optimizations, and More](https://mlsanity.com/paper/2103.10891/) (2021)
- [How Does Momentum Benefit Deep Neural Networks Architecture Design? A Few Case Studies](https://mlsanity.com/paper/2110.07034/) (2021)
- [Disentangling Sampling and Labeling Bias for Learning in Large-Output Spaces](https://mlsanity.com/paper/2105.05736/) (2021)
- [Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering](https://mlsanity.com/paper/2109.05773/) (2021)
- [Dual-Encoders for Extreme Multi-Label Classification](https://mlsanity.com/paper/2310.10636/) (2023)
- [Exact Conversion of In-Context Learning to Model Weights in Linearized-Attention Transformers](https://mlsanity.com/paper/2406.02847/) (2024)
- [Cooperative Retriever and Ranker in Deep Recommenders](https://mlsanity.com/paper/2206.14649/) (2022)
- [Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining](https://mlsanity.com/paper/2303.15311/) (2023)
- [Momentum Transformer: Closing the Performance Gap Between Self-attention and Its Linearization](https://mlsanity.com/paper/2208.00579/) (2022)
- [Fast Offline Policy Optimization for Large Scale Recommendation](https://mlsanity.com/paper/2208.05327/) (2022)
- [Prototype Memory for Large-scale Face Representation Learning](https://mlsanity.com/paper/2105.02103/) (2021)
- [Generating Negative Samples for Sequential Recommendation](https://mlsanity.com/paper/2208.03645/) (2022)
- [Hierarchical Attention Encoder Decoder](https://mlsanity.com/paper/2306.01070/) (2023)
- [Efficient and Programmable Exploration of Synthesizable Chemical Space](https://mlsanity.com/paper/2512.00384/) (2025)
- [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)
- [Efficient Image Representation Learning with Federated Sampled Softmax](https://mlsanity.com/paper/2203.04888/) (2022)
- [Adapting Triplet Importance of Implicit Feedback for Personalized Recommendation](https://mlsanity.com/paper/2208.01709/) (2022)
- [Learning distributed representations with efficient SoftMax normalization](https://mlsanity.com/paper/2303.17475/) (2023)
- [EMC2: Efficient MCMC Negative Sampling for Contrastive Learning with Global Convergence](https://mlsanity.com/paper/2404.10575/) (2024)
- [From Algorithm to Hardware: A Survey on Efficient and Safe Deployment of Deep Neural Networks](https://mlsanity.com/paper/2405.06038/) (2024)
- [Beyond Nystr"omformer -- Approximation of self-attention by Spectral Shifting](https://mlsanity.com/paper/2103.05638/) (2021)
- [GBSK: Skeleton Clustering via Granular-ball Computing and Multi-Sampling for Large-Scale Data](https://mlsanity.com/paper/2509.23742/) (2025)

## Abstract (arXiv)

Softmax is the most commonly used output function for multiclass problems and is widely used in areas such as vision, natural language processing, and recommendation. A softmax model has linear costs in the number of classes which makes it too expensive for many real-world problems. A common approach to speed up training involves sampling only some of the classes at each training step. It is known that this method is biased and that the bias increases the more the sampling distribution deviates from the output distribution. Nevertheless, almost any recent work uses simple sampling distributions that require a large sample size to mitigate the bias. In this work, we propose a new class of kernel based sampling methods and develop an efficient sampling algorithm. Kernel based sampling adapts to the model as it is trained, thus resulting in low bias. Kernel based sampling can be easily applied to many models because it relies only on the model's last hidden layer. We empirically study the trade-off of bias, sampling distribution and sample size and show that kernel based sampling results in low bias with few samples.