Climbing the WOL: Training for Cheaper Inference

Zichang Liu, Zhaozhuo Xu, Alan Baonan Ji, Jonathan Li, Beidi Chen, Anshumali Shrivastava

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:

  1. 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).
  2. 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.
Figure 1: The LSS pipeline in two stages: 1) During preprocessing, we incorporate label information from training data in LSH hash functions and rebuild hash tables accordingly. 2) During the actual inference, the softmax computation of the WOL is based on a subset of neurons retrieved by the input embeddings from hash tables rather than the full set of neurons.

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.
Figure 2: Blue line plots the collision probability between positive pairs. Green line plots the colli- sion probability between negative pairs. For all the experiment, hashing function training batch is 256. The starting point represents the probabilities of random simhash.

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

Abstract

Efficient inference for wide output layers (WOLs) is an essential yet challenging task in large scale machine learning. Most approaches reduce this problem to approximate maximum inner product search (MIPS), which relies heavily on the observation that for a given model, ground truth labels correspond to logits of highest value during full model inference. However, such an assumption is restrictive in practice. In this paper, we argue that approximate MIPS subroutines, despite having sub-linear computation time, are sub-optimal because they are tailored for retrieving large inner products with high recall instead of retrieving the correct labels. With WOL, the labels often have moderate inner products, which makes approximate MIPS more challenging. We propose an alternative problem formulation, called Label Superior Sampling (LSS), where the objective is to tailor the system to ensure retrieval of the correct label. Accordingly, we propose a novel learned hash approach, which is significantly more efficient and sufficient for high inference accuracy than MIPS baselines. Our extensive evaluation indicates that LSS can match or even outperform full inference accuracy with around 5x speed up and 87% energy reduction.
BibTeX
@misc{liu2020climbing,
  author = {Zichang Liu and Zhaozhuo Xu and Alan Baonan Ji and Jonathan Li and Beidi Chen and Anshumali Shrivastava},
  title = {{Climbing the WOL: Training for Cheaper Inference}},
  year = {2020},
  eprint = {2007.01230},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2007.01230},
}
Figure