Hierarchical Softmax › The Binary Tree Structure

The core of hierarchical softmax is an organizational insight: we place all $V$ vocabulary words as the leaves of a binary tree. Every internal node (non-leaf) holds a learned vector parameter. To predict a word, we trace the unique path from the root to that word's leaf, making a binary left-or-right decision at each internal node. The probability of the word is the product of probabilities assigned to each correct turn along that path.

The binary decomposition works because of a fundamental property of binary trees: exactly one path exists from the root to each leaf. This uniqueness guarantees that we define a valid probability distribution over all vocabulary words. The probabilities at each internal node form complementary pairs (left and right always sum to 1), so summing across all leaf paths always yields exactly 1. This is the hidden magic of the approach: you never have to compute the partition function because the partition function is implicitly built into the tree structure itself.

To see why this is the case, consider what happens at the root. The root assigns some probability $p$ to turning left and $1-p$ to turning right. The left subtree distributes its entire probability mass $p$ across all words in that subtree, and the right subtree distributes $1-p$ across all words in its subtree. At every subsequent level, the same splitting occurs. By the time probability mass reaches the leaves, it has been divided exactly once per word (since each word occupies exactly one leaf), and the total across all leaves is still exactly 1. No separate normalization step is ever needed.

Consider a vocabulary of eight words in a balanced tree of depth 3. Predicting "dog" requires three binary decisions. Compare this to standard softmax on 8 words, which requires 8 exponentials. For 100,000 words, the tree has depth $\log_2(100{,}000) \approx 17$, so we need only 17 operations instead of 100,000. The tree converts a global normalization problem into a sequence of local binary classification problems, each of which requires only a single sigmoid computation.

The path in red requires three decisions. Each decision has a learned vector and uses the sigmoid function to produce a probability. The final word probability is the product of all three sigmoid outputs. Every other word in the vocabulary can be reached by a different sequence of left-right choices from the same root, and their probabilities are computed in exactly the same way along their respective paths. The total probability distributed to all eight leaves always sums to 1, regardless of the current values of the node vectors.