TL;DR
Standard methods for speeding up deep networks with massive output layers rely on Maximum Inner Product Search (MIPS), which often misses the correct label if its score is only moderate. This paper introduces Label Superior Sampling (LSS), a learned hashing approach that trains hash functions using ground-truth data to ensure the correct labels are retrieved. LSS achieves up to a 5x speedup and an 87% reduction in energy consumption while maintaining or even improving full-model accuracy.
What Problem Does This Paper Address?
In large-scale machine learning applications like language modeling and recommendation systems, the final layer of a neural network—the Wide Output Layer (WOL)—can contain millions of neurons (classes). Computing the full softmax over this layer during inference is incredibly expensive and acts as a major computational bottleneck.
To fix this, researchers usually turn to Approximate Maximum Inner Product Search (MIPS) to quickly find a few representative logits. However, the authors point out a critical flaw: MIPS assumes that the correct label always corresponds to one of the absolute highest inner products. In practice, due to imperfect model generalization, the correct label often has a moderate inner product, buried among many similar values. Standard MIPS algorithms focus on retrieving the largest mathematical inner products, not the correct labels, leading to a drop in accuracy unless a large, expensive subset is computed.
Methods
The authors propose Label Superior Sampling (LSS), which shifts the goal from finding the largest inner products to finding a "Perfect Retrieval Set" that guarantees the correct label is included.
LSS operates in two phases:
- Offline Preprocessing: Starting with a pre-trained model, neurons are indexed into $L$ hash tables using $K$ binary hash functions (based on SimHash hyperplanes). The hyperplanes are then iteratively optimized using a novel Index Update Loss (IUL). IUL uses a differentiable approximation ($\tanh$) of Hamming distance to adjust the hyperplanes, pushing correct labels into the same bucket as the query (positive pairs) and pushing non-essential, low-scoring neurons out (negative pairs).
- Online Inference: For a given input query, the optimized hash tables are queried to retrieve a small, "active" subset of neurons. The network then computes the softmax/logits only for this subset, drastically reducing the matrix multiplication cost.
Datasets
The method was evaluated on four large-scale benchmark datasets across two tasks:
- Extreme Classification: Wiki10-31K (30,938 classes) and Delicious-200K (205,443 classes) using a fully connected network with one hidden layer.
- Language Modeling: Text8 (1,355,336 classes) using a fully connected network, and Wiki-Text2 (50,000 classes) using a two-layer LSTM.
Key Insights and Ideas
- Better Retrieval Can Beat Full Softmax: In the Delicious-200K dataset, the average rank of the correct label neuron is 498 out of over 205,000. If an oracle can isolate a small subset containing the correct label while excluding the 497 higher-scoring incorrect neurons, the model will actually make a more accurate prediction than a full softmax computation.
- MIPS vs. Classification Goals: Traditional MIPS is data-agnostic regarding ground truth; it treats all high-inner-product vectors equally. LSS recognizes that we only care about retrieving the correct label, allowing it to ignore high-inner-product distractors.
- Collision Probability Convergence: During training, the collision probability for positive pairs quickly converges above 0.9, while negative pairs drop toward 0. This proves that the learned hyperplanes successfully segregate the data based on class relevance rather than raw vector similarity.
Key Results
- Massive Efficiency Gains: LSS achieved up to a 5.1× reduction in inference time and an 8.2× (87%) reduction in energy consumption compared to full PyTorch inference.
- Tiny Sample Sizes: LSS requires computing logits for at most 6% of the output neurons. For instance, on Delicious-200K, it only evaluated 424 neurons out of 205,443. On Text8, it evaluated 965 out of over 1.3 million.
- Accuracy Superiority: In datasets like Delicious-200K and Wiki-Text2, LSS actually outperformed full inference accuracy (e.g., P@1 of 0.4596 vs 0.4391 on Delicious-200K when optimized for accuracy).
- Outperforming Baselines: LSS consistently beat state-of-the-art MIPS solvers and graph-based methods (like ip-NSW and Graph Decoder) in both speed and accuracy. This is largely because hashing is highly parallelizable on multi-core CPUs, unlike graph walks which suffer from irregular memory accesses.
Limitations and Future Work
- Offline Overhead: LSS requires an offline preprocessing step to train the hash functions using the training dataset, which adds an initial computational cost before deployment.
- Hyperparameter Tuning: Performance depends on tuning thresholds ($t_1, t_2$) and hash table parameters ($K, L$), though the authors note LSS is relatively robust to variations in $K$ and $L$.
- Hardware Focus: The evaluation focuses heavily on multi-core CPU parallelization; extending or optimizing this learned hashing mechanism for GPU architectures during inference remains an open direction.
Summary updated