A language model with a vocabulary of 50,000 tokens is generating a sequence. Explain why generating the 10th token in a sequence is computationally a much larger problem than generating the 2nd token, even though both involve selecting just one token. Base your explanation on the growth of the total number of possible sequences.

Google

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.

Formula for the Expansion of the Search Space at Each Step

A language model with a vocabulary of 5,000 unique tokens is generating text. If, at a certain stage, the model is considering 20 different unique sequences of tokens, each 4 tokens long, how many total unique sequences of 5 tokens can possibly be generated in the very next step?

Search Space Growth Analysis

Based on the principle of how the search space expands at each step of generation, which model described below would face a significantly greater computational challenge when performing an exhaustive search to generate a sequence of 10 tokens? Justify your answer by explaining how the size of the vocabulary influences the total number of sequences that must be evaluated.

Learn Before

Related