Hierarchical Softmax › Hierarchical Softmax vs Negative Sampling

Hierarchical softmax and negative sampling are both approximations that solve the same problem: making softmax tractable at large vocabulary sizes. They take fundamentally different approaches, and each has situations where it performs better.

The two approaches differ in what they approximate and how they update parameters.

Hierarchical softmax retains the full probabilistic structure. It still defines a valid probability distribution over all vocabulary words, just computed more efficiently via path products. Every training step updates only the parameters along the target word's path (roughly $\log_2 V$ node vectors plus the center embedding). No other words receive gradient signal during that step.

Negative sampling abandons the normalization requirement entirely and instead frames training as binary classification. For each positive (center, context) pair, we sample $k$ negative words and train a sigmoid classifier to distinguish real pairs from noise. Each training step updates the $k + 1$ word embeddings directly, and the model never computes a full probability distribution over all words. The resulting embeddings are useful for semantic tasks even though the model does not define a proper probability distribution.

Hierarchical softmax works better when:

• The vocabulary has a very skewed frequency distribution and Huffman coding provides significant speedup. The more extreme the Zipf distribution, the greater the benefit of shorter paths for frequent words.
• You need a true probability distribution over words, for tasks like language modeling perplexity evaluation, beam search decoding, or any application where you need to rank or compare probabilities across words.
• You have a small number of training examples and cannot rely on stochastic negative sampling to converge reliably. Hierarchical softmax provides a more principled objective with lower variance per update.

Negative sampling works better when:

• You want to learn high-quality embeddings for frequent words specifically. The $k$ negative samples and the sampling distribution can be tuned to emphasize certain word pairs, giving you control over what the model focuses on.
• The vocabulary is large but frequencies are relatively flat, reducing Huffman coding's advantage. When all words have similar frequencies, a Huffman tree offers little benefit over a balanced tree.
• Simplicity of implementation matters, and the probabilistic interpretation of the output is not needed downstream.
• You are training with very large minibatches where the sampling randomness of negative sampling averages out and the approximation quality approaches that of full softmax.

In practice, negative sampling has become the dominant approach for training word2vec because it tends to produce slightly better embeddings for semantic tasks and is simpler to implement. Hierarchical softmax remains relevant when the probability distribution interpretation matters or when vocabulary frequency is highly skewed.