Google

After identifying the K most probable next tokens at step `i`, the set of top-K candidate sequences is formed by appending each of these tokens to the parent sequence, $y_1...y_{i-1}$. For each token $y_i^{\text{top k}}$ in the set of top K tokens (where $k$ ranges from 1 to K), a new candidate sequence $\mathbf{y}^{\text{top k}}$ is constructed as follows: $$\mathbf{y}^{\text{top k}} = y_1...y_{i-1}y_i^{\text{top k}}$$ This process expands a single parent hypothesis into K new, longer hypotheses to be considered in the next step of the beam search.

Construction of Top-K Candidate Sequences in Beam Search

In the expansion step of beam search, a set of candidate sequences for step `i`, denoted $Y_i$, is formed. This set consists of the K new hypotheses generated by extending the previous step's sequences. It is formally defined as the collection of the top K candidate sequences: $$Y_i = \{\mathbf{y}^{\text{top1}}, \dots, \mathbf{y}^{\text{topK}}\}$$ where each $\mathbf{y}^{\text{top k}}$ is a newly formed sequence.

Formula for the Candidate Set in Beam Search

In a text generation process, a single partial sequence is being expanded. The current sequence is 'The sun is shining', and the three most probable next words have been identified as 'brightly', 'today', and 'and'. Based on this information, what will be the new set of candidate sequences to consider for the next step?

A developer is implementing a text generation algorithm. When expanding the parent sequence 'The movie was incredibly' with the two most probable next tokens ('good', 'boring'), their code produces the following two new candidate sequences:
1. 'The movie was incredibly good'
2. 'The movie was incredibly good boring'

Identify the fundamental error in how the second candidate sequence was constructed and describe the correct procedure.

Error Analysis in Sequence Expansion

In a text generation process, several partial sequences (parent hypotheses) are being considered. For each parent hypothesis, the three most probable next tokens have been identified. Match each parent hypothesis to its correctly constructed set of new, longer candidate sequences.

Learn Before

Related