Google

In language model inference, the set of candidate sequences, or hypotheses, is expanded at each step. The set of sequences at step `i`, denoted as $$Y_i$$, is formed by taking every sequence from the previous step's set, $$Y_{i-1}$$, and appending each possible token from the entire vocabulary, $$V$$. This expansion process is formally expressed as the Cartesian product: $$Y_i = Y_{i-1} \times V$$

Formula for Step-wise Expansion of the Hypothesis Set

In the step-wise expansion of hypotheses during a search, a sequence is considered 'complete' if it terminates with a special end-of-sequence token, such as `⟨EOS⟩`. These complete sequences are not expanded further in subsequent steps of the search process.

Complete Sequences as a Stopping Condition for Expansion

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|$$.

Formula for Pruned Step-wise Expansion of the Hypothesis Set

Consider the formula for generating a new set of candidate sequences ($Y_i$) from a previous set ($Y_{i-1}$) and a vocabulary ($V$): $$Y_i = Y_{i-1} \times V$$ Analyze the primary computational challenge this method presents as the length of the generated sequences increases, especially when using a large vocabulary.

Computational Implications of Hypothesis Expansion

A language model is generating text. At a certain step, it has a set of candidate sequences. In the next step, it will expand this set by appending every possible token from its vocabulary to the end of each existing sequence. Based on the information below, list all the sequences that will be in the new, expanded set and explain the calculation used to determine the total number of new sequences.

Hypothesis Set Expansion in a Simplified Scenario

In a text generation process, the set of candidate sequences for the next step is created by appending every word from a fixed vocabulary to the end of each sequence in the current set. If the current set contains 5 candidate sequences and the vocabulary consists of 100 words, how many new candidate sequences will be generated for the next step?

Learn Before

Related