Google

The search space in Large Language Model (LLM) inference, denoted by $$\mathcal{Y}$$, is the complete set of all possible hypotheses that the model is capable of generating. Because a hypothesis in this context is simplified to mean an output sequence, the search space $$\mathcal{Y}$$ effectively consists of every possible output sequence.

Search Space in LLM Inference

The entire search space, denoted by $$\mathcal{Y}$$, is constructed by aggregating all complete sequences generated throughout the step-wise expansion process. It is formally defined as the union of the sets of complete sequences, $$\Psi(Y_i)$$, from each step $$i=1$$ up to a maximum sequence length, $$n_{\text{max}}$$. The formula is: $$\mathcal{Y} = \Psi(Y_1) \cup \Psi(Y_2) \cup \dots \cup \Psi(Y_{n_{\text{max}}})$$ This expression provides a constructive definition of the search space as the collection of all valid, terminated hypotheses.

Formula for the Search Space as a Union of Complete Sequences

In sequence generation, the set of sequences generated at step $$i$$, denoted $$Y_i$$, can be obtained by expanding each sequence in the previous set $$Y_{i-1}$$ with all possible next tokens from the vocabulary $$V$$. This is expressed recursively as the Cartesian product: $$Y_i = Y_{i-1} \times V$$. This operation denotes that each sequence in $$Y_{i-1}$$ is concatenated with each token in $$V$$. However, if a sequence in $$Y_{i-1}$$ is already complete (for instance, ending with an $$\langle \mathrm{EOS} \rangle$$ token), it will not be expanded any further.

Formula for the Expansion of the Search Space at Each Step

Consider two different tasks for a language model. Analyze the two scenarios below to determine which one involves a larger set of all possible unique output sequences (i.e., a larger search space). Justify your reasoning by explaining the relationship between the number of available tokens, the maximum output length, and the total size of the possibility space.

Analyzing Search Space Dimensions

A language model generates text by adding one token at a time from a fixed vocabulary. Explain how the total set of all possible output sequences changes in size as the length of the generated sequences increases. Describe the mathematical nature of this growth and its primary implication for the task of finding the 'best' possible sequence.

Growth of the Generative Search Space

The search problem for Large Language Model (LLM) inference can be mathematically re-expressed as finding the optimal output sequence, $$\hat{\mathbf{y}}$$, from the entire search space $$\mathcal{Y}$$ that maximizes the conditional probability given the input sequence $$\mathbf{x}$$. This is formally defined by the equation:
$$\hat{\mathbf{y}} = \argmax_{\mathbf{y} \in \mathcal{Y}} \Pr(\mathbf{y}|\mathbf{x})$$

Mathematical Formulation of the Search Problem in LLM Inference

A simplified language model has a vocabulary consisting of only three unique tokens: 'cat', 'sat', and 'on'. The model is configured to generate an output sequence with a fixed length of exactly two tokens. Which of the following options correctly represents the complete set of all possible output sequences the model can generate?

Learn Before

Related