1Cademy - Formula for Pruned Step-wise Expansion of the Hypothesis Set

Learn Before

Formula for Step-wise Expansion of the Hypothesis Set
Search Space Pruning in LLM Decoding

Formula

Formula for Pruned Step-wise Expansion of the Hypothesis Set

In practical decoding algorithms, the search space consists of an exponentially large number of sequences. To prevent the computational load from growing exponentially with sequence length, strategies are used to prune the space. At each decoding step, the set of candidate sequences $Y_i$ is formed by applying a pruning function to the full set of expanded hypotheses: $Y_i = \mathrm{Prune}(Y_{i-1} \times V)$ . The $\mathrm{Prune}(\cdot)$ function selectively removes sequences less likely to result in high-quality outcomes. Consequently, the number of sequences under consideration is drastically reduced, ensuring that $|Y_i| \ll |Y_{i-1}| \cdot |V|$ .