Google

In beam search, given a parent node corresponding to the sequence prefix $$y_1...y_{i-1}$$, the algorithm identifies the top $$K$$ most probable next tokens from the vocabulary $$V$$. This selection is mathematically expressed as $$\left\{y_i^{\mathrm{top}1},...,y_i^{\mathrm{top}K}\right\} = \mathop{\mathrm{argTopK}}_{y_i \in V}\ \ \Pr(y_i|\mathbf{x},\mathbf{y}_{<i})$$, where $$K$$ represents the beam width and $$\mathrm{argTopK}$$ is a function that evaluates the conditional prediction probabilities of all possible next tokens and retrieves the top $$K$$ candidates.

Mathematical Definition of Top-K Token Selection

A researcher attempts to formalize the process of selecting the K most probable next tokens with the following expression: `S = argMax_{y_i ∈ V} Pr(y_i|x, y_{<i})`, where `S` is the set of selected tokens and `V` is the vocabulary. Identify the primary error in this formulation for a scenario where K > 1, and explain why it is incorrect.

Analyzing a Formalism for Token Selection

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 beam search algorithm, the top $$K$$ candidate sequences for step $$i$$ are generated by extending the previous step's prefixes with the newly selected tokens. Each new sequence is formed by appending a top token: $$\mathbf{y}^{\mathrm{top}k} = y_1...y_{i-1} y_i^{\mathrm{top}k}$$. The final candidate set, denoted $$Y_i$$, is then formally defined as $$Y_i = \{\mathbf{y}^{\mathrm{top}1},...,\mathbf{y}^{\mathrm{top}K}\}$$, where $$K$$ represents the beam width.

Formula for Constructing Top-K Candidate Sequences

Based on the described implementation, evaluate whether this two-step process (filtering then selecting) is a faithful implementation of the formal definition: $$\left\{y_i^{\text{top1}}, \dots, y_i^{\text{topK}}\right\} = \underset{y_i \in V}{\text{argTopK}} \, \text{Pr}(y_i|\mathbf{x}, \mathbf{y}_{<i})$$ Justify your conclusion.

Evaluating a Token Selection Implementation

At a certain step in a sequence generation process, the probabilities for the next token over a vocabulary V = {'A', 'B', 'C', 'D', 'E'} are as follows: Pr('A')=0.1, Pr('B')=0.4, Pr('C')=0.05, Pr('D')=0.3, Pr('E')=0.15. If the selection process is defined by the function `argTopK` with K=3, which set of tokens will be selected?

Learn Before

Related