Google

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

In large language model inference, the optimal output sequence $$\hat{\mathbf{y}}$$ is the one that maximizes the conditional log-probability given the input $$\mathbf{x}$$. This objective, expressed as finding the argument that maximizes $$\log \text{Pr}(\mathbf{y}|\mathbf{x})$$, can be decomposed using the chain rule of probability. The total log-probability of the output sequence is equivalent to the sum of the conditional log-probabilities of each individual token $$y_i$$. This is expressed as: $$ \hat{\mathbf{y}} = \underset{\mathbf{y}}{\text{arg max}} \log \text{Pr}(\mathbf{y}|\mathbf{x}) = \underset{\mathbf{y}}{\text{arg max}} \sum_{i=1}^{n} \log \text{Pr}(y_i|\mathbf{x}, \mathbf{y}_{<i}) $$ In this formula, $$\mathbf{x}$$ represents the entire input sequence and $$\mathbf{y}_{<i}$$ represents all previously generated output tokens. A more explicit representation of the conditional probability term is $$\text{Pr}(y_i|x_0, ..., x_m, y_1, ..., y_{i-1})$$, where the input sequence is $$(x_0, ..., x_m)$$ and the preceding output is $$(y_1, ..., y_{i-1})$$. This formulation is the mathematical basis for autoregressive generation.

Autoregressive Decomposition of the LLM Inference Objective

A language model is given the input sequence, x = 'The weather today is'. The model must determine the most appropriate complete sentence to generate. It calculates the total probability for several potential output sequences (y) given the input. Based on the fundamental mathematical objective for this task, which sequence should the model select as its final output, and why?

Optimal Sequence Selection

The search process in language model inference aims to identify an output sequence `y` that is either optimal or sub-optimal based on its conditional log-probability, `log Pr(y|x)`, given an input `x`. The objective is to find a sequence that maximizes this metric.

Search for Optimal Output Sequence in LLMs

In the context of generating text, a language model's objective is often expressed as: $$\hat{\mathbf{y}} = \underset{\mathbf{y}}{\arg\max}\, \text{Pr}(\mathbf{y}|\mathbf{x})$$ Explain what each component of this mathematical expression represents and what the expression as a whole instructs the model to do.

Interpreting the LLM Search Objective

A language model is generating a response based on a user's input. For this input, the model can generate many different possible sequences of words. The model's core task is to select the single best sequence from all these possibilities. According to the mathematical objective that governs this selection, which principle should the model follow?

Learn Before

Related