While exhaustive search guarantees finding the optimal sequence, it incurs a prohibitive computational cost of $$\mathcal{O}(|\mathcal{Y}|^{T'})$$, where $$|\mathcal{Y}|$$ is the vocabulary size and $$T'$$ is the sequence length. This exponential growth makes it practically infeasible; for instance, evaluating a sequence of length $$T'=10$$ with a vocabulary of $$|\mathcal{Y}|=10000$$ would require assessing $$10000^{10} = 10^{40}$$ sequences, which is beyond the capabilities of foreseeable computers.

Computational Cost of Exhaustive Search in Sequence-to-Sequence Models

Beam search is a sequence decoding strategy that strikes a compromise between the computational efficiency of greedy search and the optimality of exhaustive search. Instead of greedily picking the single most likely token or exploring all possible paths, beam search evaluates and retains a predetermined number of the most promising candidate sequences at each step of the generation process.

Beam Search Strategy in Sequence-to-Sequence Models

In sequence-to-sequence generation tasks, if the goal is to obtain the single most likely output sequence, one might consider using an exhaustive search strategy. This theoretical approach involves enumerating all possible output sequences from the vocabulary, calculating the conditional probability for each complete sequence, and ultimately outputting the sequence that scores the highest predicted probability.

Claude

In sequence generation tasks, the ultimate objective is typically to find the single most likely output sequence, which can differ from a sequence formed by simply selecting the most likely token at each individual step. If a sequence-to-sequence decoder accurately reflects the underlying generative process, the most likely translation is the complete sequence that maximizes the product of conditional probabilities over all time steps: $$\prod_{t'=1}^{T'} P(y_{t'} \mid y_1, \ldots, y_{t'-1}, \mathbf{c})$$ where $$\mathbf{c}$$ is the context vector. This expression represents the global optimal sequence based on the model's learned probability distribution.

Learn Before

Related

Learn After