Question: Consider a system that assigns a score to every candidate output sequence for a given input, such as a captioning model that ranks possible word sequences for an image. Explain why checking every possible output is not realistic, and describe the main drawback of relying on an approximate search method.

Sample answer: A complete search is not practical because the number of possible output sequences grows extremely quickly as the sequence length increases. If the system uses a vocabulary of 30,000 words and the output length is N, the number of possible sequences is on the order of (30,000)^N, which becomes far too large to evaluate exactly. For that reason, the system must use an approximate search procedure to find a high-scoring candidate. The limitation is that approximate search can miss the true best sequence, so it may return a good answer without guaranteeing the highest possible score.

Key points:

• The candidate space expands exponentially with sequence length.
• Exact enumeration becomes computationally impossible very quickly.
• Approximate search makes the problem manageable.
• Approximate search does not guarantee the top-scoring sequence.

Rubric: A strong response should explain both why exhaustive evaluation is infeasible and why approximate search is used, while also stating that the approximate method may fail to find the actual score-maximizing output.