Google

To manage the computationally infeasible size of the search space, practical decoding algorithms use pruning strategies. These methods work by identifying and discarding low-quality or unpromising sequences at each step of the generation process, thereby focusing computational effort on a smaller, more manageable set of high-potential candidates.

Search Space Pruning in LLM Decoding

Greedy search, also known as greedy decoding, is one of the most widely used decoding algorithms in natural language processing tasks, such as machine translation. The straightforward idea behind this method is to make locally optimal decisions at each generation step by selecting the next token that has the highest prediction probability. By continually picking the single most likely token, the process sequentially evaluates candidate sequences $$\mathbf{y} = y_1...y_i \in Y_{i-1} \times V$$ using their overall log-probability $$\log \Pr(\mathbf{y}|\mathbf{x})$$.

Greedy Search (Greedy Decoding)

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

Two text generation systems are built using the exact same underlying language model. However, they exhibit very different behaviors. Analyze the provided descriptions and explain the most probable reason for the difference in their performance, focusing on how they might be managing the set of potential output sequences.

Analyzing Text Generation System Performance

A language model is tasked with generating a 20-word summary. At each of the 20 steps, it could choose from a vocabulary of 50,000 words. Explain why it is impractical for the model to evaluate every single possible 20-word summary to find the absolute best one, and describe the general strategy used to make this task manageable.

Rationale for Decoding Heuristics

A language model is generating a sentence and must decide on the next word. It has identified 100 possible words, each with an associated probability. To manage computational resources, the model employs a strategy that discards all but the top 5 most probable words before considering the subsequent step. Which of the following statements best analyzes the primary trade-off inherent in this strategy?

Learn Before

Related