Hierarchical softmax computes vocabulary probabilities by replacing a flat choice among every word with a walk through a binary tree. Instead of scoring roughly one million vocabulary items, training makes about twenty binary decisions along a path. section 2.1.2
The technique addresses the normalization bottleneck in Word2Vec: probabilities must sum to one across the entire vocabulary, making each training step expensive for large word-level vocabularies. It is an alternative to negative sampling, which avoids probabilities and asks a small number of yes-or-no classification questions instead. section 2.1.2 section 2.1.5
From dictionary scan to tree walk
A vocabulary of 692,000 words would require summing across all words under the flat formulation. Hierarchical softmax follows a binary-tree path of roughly twenty decisions, like playing “20 Questions” instead of reading the dictionary line by line. section 2.1.2
