Mathematical Justification for Greedy Search

Construction of the Optimal Sequence in Greedy Search

Candidate Set in Greedy Search

A language model is generating a two-token sequence. At the first step, it calculates the probability for the next token: 'Token A' has a probability of 0.6, and 'Token B' has a probability of 0.4. If the model chooses 'Token A', the most probable subsequent token is 'Token C' (with a conditional probability of 0.5). If the model had chosen 'Token B', the most probable subsequent token would be 'Token D' (with a conditional probability of 0.9). A text generation algorithm is used that, at every step, commits to the single token with the highest immediate probability. Based on this process, which sequence will be generated and why?

Algorithm Suitability for Text Generation Tasks

When generating a sequence of text, an algorithm that selects the single most probable token at each step is guaranteed to produce the overall most probable sequence.

Analyzing Suboptimal Outcomes in Text Generation

Selecting and Justifying a Decoding Policy for Two Production Use Cases

Debugging Decoding: Balancing Determinism, Diversity, and Length in a Regulated Product

Post-incident analysis: fixing repetition and truncation by tuning decoding

Choosing a Decoding Configuration Under Latency, Diversity, and Length Constraints

Release-readiness decision: decoding configuration for a customer-facing summarization feature

Decoding policy decision for a multilingual support assistant under safety, latency, and verbosity constraints

You are tuning decoding for an internal "meeting-n...

You’re implementing an LLM feature that generates ...

You’re building an internal “RFP response drafter”...

You’re deploying an LLM to draft customer-facing i...

Beam search

Construction of the Optimal Sequence in Greedy Search

When generating text one token at a time, a greedy algorithm aims to select the token y_i at step i that maximizes the log-probability of the entire sequence up to that point, log Pr(y_1...y_i | x). This optimization problem can be simplified to choosing the token that maximizes only the conditional log-probability of the current token, log Pr(y_i | x, y_{<i}). Why is this simplification mathematically valid for finding the best current token y_i?

The simplification of the greedy search objective relies on a specific mathematical derivation. Arrange the following steps to correctly represent the logical flow of this derivation, which shows how maximizing the log-probability of the entire sequence up to the current step (log Pr(y_1...y_i | x)) is equivalent to maximizing the log-probability of just the current token (log Pr(y_i | x, y_{<i})).

Explaining Greedy Search Optimization

Construction of the Optimal Sequence in Greedy Search

An autoregressive model generates the token sequence $y = (\text{'The'}, \text{'quick'}, \text{'brown'}, \text{'fox'})$, where $y_1 = \text{'The'}$, $y_2 = \text{'quick'}$, and so on. What does the notation $y_{<3}$ represent in this specific sequence?

True or False: For an autoregressive model generating the output sequence $y = (y_1, y_2, y_3, y_4)$, the notation $y_{<4}$ represents the complete subsequence $(y_1, y_2, y_3, y_4)$.

Formula for Constructing Top-K Candidate Sequences

An autoregressive language model is generating a sequence of tokens, one at a time. To predict the fifth token in the sequence, denoted as $y_5$, the model uses all the previously generated tokens as context. The standard notation for this preceding subsequence of tokens is ____.