1Cademy - Formula for the Expansion of the Search Space at Each Step

Learn Before

Search Space in LLM Inference

Formula

Formula for the Expansion of the Search Space at Each Step

In sequence generation, the set of sequences generated at step $i$ , denoted $Y_i$ , can be obtained by expanding each sequence in the previous set $Y_{i-1}$ with all possible next tokens from the vocabulary $V$ . This is expressed recursively as the Cartesian product: $Y_i = Y_{i-1} \times V$ . This operation denotes that each sequence in $Y_{i-1}$ is concatenated with each token in $V$ . However, if a sequence in $Y_{i-1}$ is already complete (for instance, ending with an $\langle \mathrm{EOS} \rangle$ token), it will not be expanded any further.