Google

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)

The mathematical basis for greedy search relies on simplifying its core objective. At step $$i$$, the goal is to select the best token $$y_i$$ that maximizes the log-probability of the entire sequence up to that point, $$\log \Pr(y_1...y_i|\mathbf{x})$$. Since this total log-probability decomposes into the accumulated log-probability of the preceding sequence $$\log \Pr(\mathbf{y}_{<i}|\mathbf{x})$$ (which is fixed with respect to $$y_i$$) and the conditional log-probability of the new token $$\log \Pr(y_i|\mathbf{x},\mathbf{y}_{<i})$$, maximizing the sum simplifies to maximizing only the newly computed token log-probability. The formal derivation is: $$y_i^{\mathrm{top}1} = \argmax_{y_i \in V} \log \Pr(y_1...y_i|\mathbf{x}) = \argmax_{y_i \in V} \big[ \log \Pr(\mathbf{y}_{<i}|\mathbf{x}) + \log \Pr(y_i|\mathbf{x},\mathbf{y}_{<i}) \big] = \argmax_{y_i \in V} \log \Pr(y_i|\mathbf{x},\mathbf{y}_{<i})$$.

Mathematical Justification for Greedy Search

In a greedy search algorithm, the single most optimal sequence at step `i`, denoted $\mathbf{y}^{\text{top1}}$, is constructed by taking the sequence generated up to the previous step, $y_1...y_{i-1}$, and appending the single most probable next token, $y_i^{\text{top1}}$. The formal representation of this construction is: $$\mathbf{y}^{\text{top1}} = y_1...y_{i-1}y_i^{\text{top1}}$$

Construction of the Optimal Sequence in Greedy Search

In the greedy search decoding algorithm, the set of candidate sequences at step `i`, denoted `Yi`, is reduced to contain only a single sequence. This sequence is the one formed by appending the highest-probability token from the current step to the optimal sequence generated in the previous steps.

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?

Evaluate the suitability of the proposed algorithm for *both* the 'PoemBot' and 'LegalBrief' applications. Justify your assessment by explaining how the algorithm's core mechanism would likely impact the output quality for each specific task.

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.

A language model is tasked with completing the phrase 'The weather today is...'. At the first step, it considers two options: 'very' (probability 0.5) and 'extremely' (probability 0.4). If it chooses 'very', the most likely next word is 'sunny' (conditional probability 0.6). If it chooses 'extremely', the most likely next word is 'hot' (conditional probability 0.9). An algorithm that always selects the single most probable token at each step is used. Identify the final two-word sequence this algorithm will generate and explain why this outcome is not the overall most probable sequence.

Analyzing Suboptimal Outcomes in Text Generation

You are deploying the same LLM behind two internal products:

1) A compliance assistant that drafts short, auditable policy answers where reproducibility is required (the same input should yield the same output), and answers must not become overly long.
2) A brainstorming assistant for product managers where novelty and variety are valued, but outputs must remain coherent and not drift into low-probability “nonsense.”

Write a recommendation memo that proposes a decoding configuration for each product. Your memo must:
- Choose between greedy decoding, beam search, top-k sampling, and top-p (nucleus) sampling for each product, and justify the choice in terms of determinism vs. diversity and how candidate-set pruning works.
- Specify how you would use temperature scaling in the sampling-based configuration(s) (e.g., higher/lower temperature) and explain the expected effect on the renormalized token probabilities.
- Explain whether and how you would apply a length penalty (or length normalization) in the deterministic configuration(s), including the failure mode it is intended to prevent.
- Explicitly discuss at least one tradeoff you are accepting in each product (e.g., quality vs. diversity, compute vs. optimality, brevity vs. completeness) and why it is appropriate for that product’s constraints.

Selecting and Justifying a Decoding Policy for Two Production Use Cases

You own the generation layer for an internal, regulated customer-support assistant. Two issues are reported after a model upgrade:

1) For short answers (target: 1–2 sentences), the assistant often produces overly long, meandering responses.
2) For longer answers (target: 6–10 sentences), the assistant is repetitive and sometimes “locks in” early to a suboptimal phrasing that later forces awkward continuations.

You are not allowed to change the model weights—only the decoding strategy and its parameters. Propose a single coherent decoding policy (you may use different settings by response-length tier, but keep the approach consistent) that addresses both issues. In your justification, explicitly explain how your choices combine: (a) a deterministic search method (greedy or beam search) versus a sampling method (top-k or top-p), (b) temperature scaling, and (c) a length penalty. Your answer must describe the tradeoffs you are making (e.g., predictability vs. diversity, local vs. global sequence quality, and how length controls interact with search/sampling) and why your policy would reduce both overlong short answers and repetitive long answers in production.

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

You own an internal LLM feature that drafts customer-facing incident updates. After a model upgrade, stakeholders report two issues: (1) outputs are often prematurely short (missing key details), and (2) when you try to increase “creativity,” some drafts become repetitive or slightly incoherent. You are not allowed to change the model weights—only the decoding configuration.

Write a post-incident proposal that recommends a single decoding strategy (you may combine methods) and a tuning plan that explicitly connects: (a) the choice between greedy decoding vs beam search vs sampling, (b) how you would set and justify either top-k or top-p (nucleus) sampling, (c) how you would use temperature-scaled softmax in combination with your sampling choice, and (d) how you would apply a length penalty (or length normalization) so that longer, more complete updates are not unfairly disfavored.

Your answer must explain the tradeoffs and interactions among these controls (e.g., how temperature changes the effective candidate distribution before top-k/top-p truncation, and how length penalty changes which sequences win under beam search), and it must end with a concrete “default” configuration plus a brief rollback/monitoring plan (what metrics or failure modes you would watch for).

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

You are deploying an internal LLM feature that drafts customer-facing email replies for account managers. Requirements: (1) average latency must stay under 250 ms, (2) outputs must not be overly “templated” across similar tickets (product wants noticeable variation), and (3) replies must be 90–130 words; current outputs are often ~50 words and sometimes end abruptly. You can change only decoding-time settings (no fine-tuning). 

Propose ONE concrete decoding configuration (algorithm + key parameters) that best meets all three requirements, and justify it by explaining how your choices jointly affect (a) determinism vs diversity, (b) search/compute cost, and (c) output length. Your answer must explicitly address why you did NOT choose at least one plausible alternative (e.g., greedy, beam search, top-k, or top-p) given the constraints.

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

You are the on-call ML lead for a B2B product that generates 1–2 sentence “Account Update” summaries from internal CRM notes. A pilot with 200 users shows two failure modes:

1) Some summaries are overly short (often 6–10 words) and omit key facts.
2) Other summaries are fluent but occasionally include a plausible-sounding detail that is not in the notes.

Constraints: p95 latency must stay under 250 ms; the product team wants consistent tone across runs for the same input, but they also want to avoid repetitive phrasing across different accounts. You can change only decoding-time settings (no retraining, no prompt changes).

You must choose ONE decoding approach to ship this week and specify concrete settings for: (a) the core decoding algorithm (greedy, beam search, top-k sampling, or top-p sampling), (b) whether/how you will use temperature scaling, and (c) whether/how you will apply a length penalty. In your answer, justify how your choices jointly address both failure modes and the stated constraints, including at least one tradeoff you are accepting.

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

You own the decoding configuration for an internal multilingual customer-support assistant that drafts replies agents can send with minimal edits. The business constraints are: (1) replies must be deterministic for the same ticket to support auditability, (2) average generation latency must stay under 250 ms, (3) replies must not be overly short (agents complain about missing key steps) but also must not ramble, and (4) the current model sometimes produces a safe but generic first sentence and then either ends too early or repeats itself.

You are given two candidate configurations to choose from for the next release:

Config A:
- Greedy decoding
- No length penalty

Config B:
- Beam search with beam width B=4
- Apply a length penalty that discourages very short completions

A third option is proposed by another team:

Config C:
- Top-p (nucleus) sampling with p=0.9
- Temperature-scaled softmax with β=1.3
- No length penalty

Case study task: Choose the single best configuration (A, B, or C) for this release and justify your choice by explicitly explaining how your selected approach handles (i) determinism vs diversity, (ii) the risk of premature stopping vs overly long outputs (including the role of length penalty), and (iii) latency/compute tradeoffs. Your justification must reference at least two concrete failure modes described above and explain why the other two configurations are less suitable under the stated constraints.

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, also referred to as beam decoding, is an algorithm that extends the greedy search approach by exploring multiple potential paths simultaneously. Rather than committing to the single most probable token at each generation step, beam search retains a predetermined number of the best candidate sequences, a parameter known as the beam width. This strategy helps mitigate the problem of high-quality sequences being discarded too early in the generation process.

Learn Before

Related