1 Introduction↩︎

A recent book by Stephen Wolfram is titled

What Is ChatGPT Doing … and Why Does It Work?

Our essay is written as a response to the first of Wolfram’s two questions. Before doing so, we must clarify our interpretation of the meaning of these questions, while acknowledging that our understanding may differ from Wolfram’s own intentions¹.

1.0.0.1 1. What Is ChatGPT Doing?

A transformer is an algorithmic solution to a certain problem—that of predicting the next token. Our goal in this essay, which we view as a partial answer to Wolfram’s question, is to carefully define the token prediction problem, discuss its key difficulties, and speculate on the mathematical insights that a transformer solution reveals.

1.0.0.2 2. Why Does it Work?

This is a more difficult question that we do not attempt to address in this essay. In our view, the question highlights a central mystery: how does merely solving for next-token prediction problem lead to the coherent generation of words, sentences, and even entire paragraphs?

Our focus in this essay is on the problem related to Wolfram’s first question. While we discuss some of the details of a transformer solution, the essay is not intended as an explanation of the attention mechanism. In fact, part of our motivation comes from a concern that many explanations of attention focus narrowly on mechanistic details, while leaving the underlying problem unexamined.

Our goal in this essay is two-fold:

1. Formulation of the mathematical problem that a transformer solves. This is referred to as probabilistic modeling and formalized via a set of assumptions and hypotheses.

2. Enunciation of modeling and algorithmic insights that the transformer solution reveals. This is referred to as the transformer-inspired inference architecture.

1.1 The Transformer and its historical antecedents↩︎

Let \(\mathbb{O}=\{0,1,2,\ldots,m\}\) denote a finite set called the vocabulary. An element of \(\mathbb{O}\) is referred to as a token. A sequence of \(T\) tokens is an \(\mathbb{O}^T\)-valued random vector, denoted by \(\{Z_1,Z_2,\ldots,Z_T\}\). A decoder-only transformer is an algorithm to compute the conditional probability of the next token (see Fig. 1): \[p_T(z):={\sf P}(Z_{T+1}=z \mid Z_1,Z_{2},\ldots,Z_T),\quad z\in \mathbb{O}.\] During inference with a well-trained transformer, the conditional probability is often sparse—that is, only a small subset of tokens has non-negligible probability (see Fig. 2). This sparsity is useful for efficient sampling in generative AI applications [1].

There are two distinguishing features of the decoder-only transformer architecture:

1. Even though only the conditional probability at the terminal time \(t=T\) is of interest, conditional probabilities are also computed for intermediate times, \[p_t(z):={\sf P}(Z_{t+1}=z \mid Z_1,Z_2,\ldots,Z_t),\quad z\in \mathbb{O},\quad t=1,2,\ldots,T.\]

2. In all cases, the conditional probability of the next token is represented as a causal, nonlinear function of the past tokens, implemented through a procedure known as causal masking. In this essay, we refer to such a representation as a nonlinear predictor.

The second item is in contrast to a recurrent neural network (RNN) architecture, where a hidden state is stored and recursively updated [2], [3].

A transformer architecture is reminiscent of the classical Wiener filter. Recall that a Wiener filter computes the conditional expectation of a Gaussian process, also denoted (with slight abuse of notation) as \([Z_1,Z_2,\ldots,Z_T]\), in the following causal form: \[\text{(linear predictor)}\qquad {\sf E}(Z_{T+1} \mid Z_1,Z_{2},\ldots,Z_T) = \text{(constant)} + \sum_{t=0}^{T-1} u_t^{\rm\tiny T}Z_{t+1}. \label{eq:linear95predictor}\tag{1}\] The right-hand side is an example of a linear predictor where \(u:=\{u_t\in\mathbb{R}^{m\times m}:0\leq t\leq T-1\}\) are deterministic weights, to be designed or learned. The Wiener filtering theory is concerned with the synthesis of the optimal weights that yield the conditional expectation [4].

A generalization of the linear predictor representation 1 , now applicable to the \(\mathbb{O}\)-valued stochastic processes, is given in the following sub-section.

1.2 Representation formula for nonlinear predictor↩︎

Consider a vector-valued mapping \(e:\mathbb{O}\to \mathbb{R}^m\) as follows: \[e(1) = \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}_{m\times 1},\quad e(2) = \begin{bmatrix} 0 \\ 1\\ \vdots\\ 0 \end{bmatrix}_{m\times 1}, \quad \ldots \quad e(m) = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{bmatrix}_{m\times 1}, \quad e(0) = -e(1) -e(2) - \ldots -e(m).\] (Recall here that the cardinality \(|\mathbb{O}| = m+1\).)

In the nonlinear settings, the space of admissible weights (control inputs) is as follows: \[{\cal U}:=\{U:\Omega\times \{0,1,2,\ldots,T-1\} \to \mathbb{R}^m, \;\; U_t\in{\cal Z}_t, \;0\leq t\leq T-1\},\] where \({\cal Z}_t:=\sigma(\{Z_s:1\leq s\leq t\})\) (sigma-algebra of observations up to time \(t\)) and \({\cal Z}_0:=\{\phi,\Omega\}\). The definition is useful to obtain the following key representation (compare with 1 ): \[\label{eq:nonlin95predictor95rep} \text{(nonlinear predictor)}\qquad {\sf P}(Z_{T+1}=z \mid Z_1,Z_2,\ldots,Z_T) = \text{(const.)} - \sum_{t=0}^{T-1} U_t^{\rm\tiny T} e(Z_{t+1}),\;\; {\sf P}\text{-a.s.},\quad z\in\mathbb{O}\tag{2}\] where \(U=\{U_0,U_1,\ldots,U_{T-1}\}\in{\cal U}\). The right-hand side of 2 is referred to as a nonlinear predictor and \(U\) is referred to as the control input. The well-posedness result for the same is given in the following.

1.3 Outline↩︎

The outline of the remainder of this essay is as follows: In Sec. 2, a self-contained description of the transformer is presented together with insights for the probabilistic modeling. The modeling is used to motivate a fixed-point architecture for inference (formalized as Objective 1). For the special case of an HMM, the architecture is described in Sec. 3 (based on our prior work in [5]). The paper closes with some directions for future research in Sec. 4. All the proof appear in the Appendix 5.

2 Transformer and its probabilistic modeling↩︎

As noted in Sec. 1, a transformer is an algorithm to compute the conditional probability \(p_T\in {\cal P}(\mathbb{O})\) (the set of probability vectors on \(\mathbb{O}\)) for any given sequence of input \((z_1,z_2,\ldots,z_T)\in \mathbb{O}^T\). Therefore, \(p_T\) may be regarded as a nonlinear function, \[p_T : \mathbb{O}^T \to {\cal P}(\mathbb{O}).\]

A key difficulty is the size of the domain: the cardinality of \(\mathbb{O}^T\) is \((m+1)^T\), where note \(m+1 = |\mathbb{O}|\). Table 2 tabulates typical values of \(m\) and \(T\) used in open source models together with an estimate of \((m+1)^T\). These are very large numbers. It is therefore quite remarkable that a transformer is able to learn a (good enough) representation of this function!

That a transformer is able to learn a representation of \(p_T\) is because of the correlations that exist in human language. We have already defined the observation process \[\text{(observation process)} \qquad Z := [Z_1,Z_2,\ldots,Z_T,Z_{T+1}],\] which is a stochastic process takings values in \(\mathbb{O}\). A time honored approach to model the correlations is through the introduction of a hidden (latent) process, \[\text{(hidden state process)} \qquad X:=[X_0,X_1,\ldots,X_{T-1},X_T].\] The law of the joint process is expressed as \[{\sf P}(X,Z) = {\sf P}(Z\mid X) {\sf P}(X),\] so that modeling the joint behavior amounts to specifying \({\sf P}(Z \mid X)\) and \({\sf P}(X)\).

Concerning this model, the following questions are of interest:

1. What is the meaning of the state \(X\)?

2. How are the internal signals in a transformer related to \(X\)?

Towards constructing a probabilistic model for the transformer, we make the following assumptions concerning the state \(X\) and the factorization of the model \({\sf P}(Z\mid X)\) (a justification is given in the following sub-section):

Denote \[\pi_t(x) := {\sf P}(X_t=x \mid Z_1,Z_2,\ldots,Z_t),\quad x\in\mathbb{S},\quad t=1,2,\ldots,T.\] The definition is useful to describe the following formula, which relates \(\pi_t\) to \(p_t\).

It then remains to specify a model for \({\sf P}(X)\). A natural causal decomposition is given by, \[\begin{align} {\sf P}(X) &= {\sf P}(X_0,X_1,\ldots,X_{T-1},X_T) \\ &= {\sf P}(X_0) \; {\sf P}(X_1 \mid X_0) \; {\sf P}(X_2 \mid X_1,X_0) \; \cdots \; {\sf P}(X_T \mid X_{T-1},\ldots,X_1,X_0). \end{align}\]

The key hypothesis of this work is as follows:

The remainder of this section is divided into two subsections:

1. In Sec. 2.1, the input and the output signals in a transformer are described. The aim is to obtain some insights that are useful for probabilistic modeling. In particular,

   1. Justify Assumptions 1 and 2; and

   2. Describe a transformer surrogate of the conditional measure \(\pi\) and provide justification for the Hypothesis 1.

2. In Sec. 2.2, the key mathematical operations from the input to the output are described. The aim is to motivate a certain fixed-point representation for the solution being computed by the transformer.

The transformer descriptions are based upon [6] [7] and [8].

2.1 Transformer signals: Insights for probabilistic modeling↩︎

In a transformer, as a first step, a token is “embedded” using a \(d\times m\) embedding matrix denoted in this essay by \(C^{\text{\rm (xfer)}}\): \[z \mapsto C^{\text{\rm (xfer)}}(:,z) \in \mathbb{R}^d,\quad z\in\mathbb{O}.\] Using the embedding matrix, \[\begin{bmatrix} z_1 & \ldots & z_t & \ldots & z_T \end{bmatrix}_{1\times T} \mapsto \begin{bmatrix} C^{\text{\rm (xfer)}}(:,z_1) & \ldots & C^{\text{\rm (xfer)}}(:,z_t) & \ldots & C^{\text{\rm (xfer)}}(:,z_T) \end{bmatrix}_{d\times T}.\] The input \(C^{\text{\rm (xfer)}}(:,z_t)\) is augmented with the so-called positional encoding as follows: \[\sigma^{(0)}_t(x) := C^{\text{\rm (xfer)}}(x,z_t) + W_p(x,t),\quad x\in\mathbb{S}, \quad t=1,2,\ldots,T,\] where \(W_p \in \mathbb{R}^{d\times T}\) is referred to as the positional encoding matrix. In the original transformer paper [9], the rows of \(W_p\) are defined according to the sinusoidal-positional-encoding: \[\begin{align} W_p(2i-1,t) = \sin(\ell_{\text{max}}^{-\frac{2i}{d}} t),\quad W_p(2i,t) = \cos(\ell_{\text{max}}^{-\frac{2i}{d}} t), \quad i=1,2,\ldots,\frac{d}{2},\quad t=1,2,\ldots,T, \end{align}\] where \(\ell_{\text{max}} = 10,000\). The factor \(\ell_{\text{max}}^{-\frac{2i}{d}}\) determines the frequency of oscillations, ensuring a wide range of scales, as \(i\) varies from \(1,2,\ldots,\frac{d}{2}\). The positional encoding is the only mechanism through which information about the position (time) \(t\) is introduced into the transformer. Other types of positional encoding are also possible [10].

From an input-output perspective, a decoder-only transformer implements a causal nonlinear transformation that transforms a \(d\times T\) matrix at the input into a \(d\times T\) matrix at the output, \[[\sigma_1^{(0)}, \sigma_2^{(0)},\ldots, \sigma_T^{(0)} ]_{d\times T} \mapsto [\sigma_1^{(L)}, \sigma_2^{(L)},\ldots,\sigma_T^{(L)} ]_{d\times T}.\] Then the conditional probability of the next token is computed as follows: \[p_{t}(z)={\sf P}(Z_{t+1}=z \mid Z_1=z_1,\ldots,Z_t=z_t) = \frac{e^{((\sigma_t^{(L)})^{\rm\tiny T} C^{\text{\rm (xfer)}})(z)}}{\sum_{z'\in\mathbb{O}} e^{((\sigma_t^{(L)})^{\rm\tiny T}C^{\text{\rm (xfer)}})(z')}},\quad t=1,2,\ldots,T,\quad z\in\mathbb{O}.\] The operation on the right-hand side is referred to as softmax.

Internally, a transformer is arranged in \(L\) layers as follows (see Fig. 3): \[\begin{align} &\text{(input)} \quad [z_1,z_2,\ldots,z_T]_{1\times T} \mapsto [\sigma_1^{(0)} , \sigma_2^{(0)} ,\ldots, \sigma_T^{(0)} ]_{d\times T} \qquad \text{(embedding + positional-encoding)}\\[5pt] &\text{(first layer)} \quad [\sigma_1^{(0)} , \sigma_2^{(0)} ,\ldots, \sigma_T^{(0)} ]_{d\times T} \mapsto [\sigma_1^{(1)},\sigma_2^{(1)},\ldots,\sigma_T^{(1)}]_{d\times T}\\[5pt] &\text{(intermediate layer)} \quad [\sigma_1^{(\ell)},\sigma_2^{(\ell)},\ldots,\sigma_T^{(\ell)}]_{d\times T} \mapsto [\sigma_1^{(\ell+1)},\sigma_2^{(\ell+1)},\ldots,\sigma_T^{(\ell+1)}]_{d\times T},\quad \ell=1,2,\ldots,L-1 \\[5pt] &\text{(output)} \quad [\sigma_1^{(L)},\sigma_2^{(L)},\ldots,\sigma_T^{(L)}]_{d\times T} \mapsto [p_1,p_2,\ldots,p_T]_{m\times T} \qquad \text{(un-embedding)} \end{align}\]

Our task is to attach a meaning to a single layer operation in a transformer. Specifically,

1. What is the meaning of the input \(\sigma^{\ell}:=[\sigma_1^{(\ell)},\sigma_2^{(\ell)},\ldots,\sigma_T^{(\ell)}]\)?

2. What is the meaning of the output \(\sigma^{\ell+1}:=[\sigma_1^{(\ell+1)},\sigma_2^{(\ell+1)},\ldots,\sigma_T^{(\ell+1)}]\)?

3. What is the meaning of the transformer operation from the input \(\sigma^{\ell}\) to the output \(\sigma^{\ell+1}\)?

Recall that the output of the last layer is used to compute the conditional probability of interest: \[\begin{equation}\tag{4} \text{(transformer)}\qquad \ln p_t(z) = \sum_{x\in\mathbb{S}} \sigma_t^{(L)}(x) C^{\text{\rm (xfer)}}(x,z) + \text{(constant)},\quad t=1,2,\ldots,T, \quad z\in\mathbb{O}. \end{equation} This is compared with the formula~\eqref{eq:formula95pt95pit} for conditional measure in Prop.~\ref{prop:formula95for95ptz}, as repeated below, \begin{equation}\tag{5} \text{(probabilistic model)}\qquad p_t(z) = \sum_{x\in \mathbb{S}} \pi_t(x) C(x,z),\quad t=1,2,\ldots,T, \quad z\in\mathbb{O}. \end{equation}\] The above two equations provide the key correspondence that is used to motivate the following:

1. Interpretation of \(\sigma_t^{(L)}=\{\sigma_t^{(L)}(x):x\in\mathbb{S}\}\) as a surrogate of the conditional measure \(\pi_t=\{\pi_t(x):x\in\mathbb{S}\}\), for \(t=1,2,\ldots,T\), where \(\mathbb{S}\) has an interpretation of the state-space.

2. Justification of the conditional independence property ?? described as part of Assumption 2. Indeed, using the definitions of \(p_t\) and \(\pi_t\), an application of the total probability lemma shows that \[\begin{align} p_t(z) = {\sf P}(Z_{t+1}=z\mid Z_1,Z_2,\ldots, Z_t) = \sum_{x\in \mathbb{S}} \pi_t(x) \; {\sf P}(Z_{t+1}=z \mid & X_t=x,Z_1,Z_2,\ldots, Z_t),\\ &\qquad z\in\mathbb{O},\quad t=1,2,\ldots,T. \end{align}\] Based on the correspondence between \(\sigma_t\) and \(\pi_t\), formula 4 in the transformer provides a justification for assuming the conditional independence property ?? which in turn gives the formula 5 in terms of the conditional measure.

The correspondence is tabulated in the Table 3. While \(\pi_t\) is an element of the space of probability measures on \(\mathbb{S}\), its surrogate \(\sigma_t^{(L)}\) is an element of the space of signed measures on \(\mathbb{S}\). The two spaces are denoted by \({\cal P}(\mathbb{S})\) and \({\cal M}(\mathbb{S})\), respectively. Then \[\pi=[\pi_1,\pi_2,\ldots,\pi_T] \in {\cal P}(\mathbb{S})^T,\quad \sigma^{(L)} =[\sigma_1^{(L)},\sigma_2^{(L)},\ldots,\sigma_T^{(L)}] \in {\cal M}(\mathbb{S})^T.\]

2.2 Transformer operations: Insights for the solution architecture↩︎

Because each layer in a transformer is structurally identical, for the purposes of describing the mapping, it suffices to consider a generic layer whose input and output are denoted by, \[\sigma := [\sigma_1, \sigma_2,\ldots, \sigma_T]_{d\times T} \in {\cal M}(\mathbb{S})^T,\quad \sigma^+:= [\sigma^+_1, \sigma^+_2,\ldots, \sigma^+_T]_{d\times T} \in {\cal M}(\mathbb{S})^T,\] respectively, and the layer mapping is denoted by \[{\cal N}^{\text{\rm (xfer)}}:{\cal M}(\mathbb{S})^T \mapsto {\cal M}(\mathbb{S})^T\quad \text{s.t.}\quad \sigma^+ = {\cal N}^{\text{\rm (xfer)}}(\sigma).\] For the first layer, the input is given by the embedding plus positional encoding. For each subsequent layer, the input is defined by the output of the preceding layer.

Operationally, a layer is comprised of multiple attention heads. A single attention head is an input-output map of the form \[[\sigma_1, \sigma_2,\ldots, \sigma_T]_{d\times T} \mapsto [o_1^h,o_2^h,\ldots,o_T^h]_{d_V \times T}.\] where the output vector \(o_t^h \in\mathbb{R}^{d_V}\) whose dimension \(d_V = \frac{1}{n_{\text{head}}} d\), where \(n_{\text{head}}\) has the meaning of the number of heads. The operations in a single attention head are defined by three matrices \[W_V^h \in \mathbb{R}^{d_V \times d}, \;\;W_Q^h \in \mathbb{R}^{d_K \times d}, \;\;W_K^h \in \mathbb{R}^{d_K \times d},\] where typically \(d_K=d_V\). The matrices are constant (fixed) during the inference phase of the transformer operation.

The mathematical operation defining the causal self-attention is as follows: \[\label{eq:transf95output} o_t^h = W_V^h \left( \sum_{s=1}^t \alpha(s;t,h) \sigma_s\right),\quad t=1,2,\ldots, T,\tag{6}\] where \(\{\alpha(s;t,h):s=1,2,\ldots,t\}\) is referred to as the attention weight vector. For each fixed \((t,h)\in \{1,2,\ldots,T\}\times\{1,2,\ldots, {n_{\text{head}}}\}\), it is a probability vector. That is, \[\alpha(s;t,h)\geq 0,\quad s=1,2,\ldots,t,\quad \text{and}\quad \sum_{s=1}^t \alpha(s;t,h)= 1.\]

The attention weights are computed as follows: For each fixed \(1\leq t\leq T\), define \[\begin{align} \text{(query)} \qquad q_t &= W_Q^h \sigma_t, \\ \text{(key)} \qquad k_s &= W_K^h \sigma_s,\quad s=1,2,\ldots, t. \end{align}\] Then \[\text{(attention weight)} \qquad \alpha(s;t,h) = \frac{\exp({\frac{q_t^{\rm\tiny T}k_s}{\sqrt{d_K}}})}{\sum_{\tau=1}^t \exp({\frac{q_t^{\rm\tiny T}k_\tau}{\sqrt{d_K}}})},\quad s=1,2,\ldots, t.\] In the terminology adopted in this essay, the dependence of the weights upon the data (which varies between sample paths of observations), makes attention a nonlinear predictor. If the weights were deterministic (same for all sample paths), attention will be an example of linear predictor (see Remark [remark:connection95to95transformer]).

From 6 , the layer output is obtained as \[\sigma^+_t = W_O \; \text{concat}(o_t^1, \ldots, o_t^{n_{\text{head}}}),\quad t=1,2,\ldots,T,\] where \(W_O \in \mathbb{R}^{d\times d}\).

An issue that arises is that the output may ‘blow up’ during the training phase of a transformer. For this reason, additional miscellaneous operations are implemented. All of these operations are carried out independently for each fixed \(t\). Because these additional operations are not especially pertinent to probabilistic modeling, these are described in the Appendix 5.3.

Define \[L^h := W_O \; \text{concat}(0,\ldots,0,W_V^h,0,\ldots,0),\quad h=1,2,\ldots,n_{\text{head}}.\] For each fixed \(h\), \(L^h\) is a \(d\times d\) matrix. Fix \(f\in\mathbb{R}^d\) and define, \[y_s^{(t)} := \sum_{h=1}^{n_{\text{head}}} \alpha(s;t,h) ((L^h)^{\rm\tiny T}f),\quad s=1,2,\ldots,t.\] Then the mapping \({\cal N}:\sigma \mapsto \sigma^+\) is succinctly expressed as \[\label{eq:rep95attention95simplified} \sigma_t^+(f) = \sum_{s=1}^t \sigma_s(y_s^{(t)}),\quad t=1,2,\ldots,T,\quad f\in\mathbb{R}^d.\tag{7}\] (here \(\sigma_t^+(f) := (\sigma_t^+)^{\rm\tiny T}f\) and \(\sigma_s(y_s^{(t)}) :=\sigma_s^{\rm\tiny T}(y_s^{(t)})\)).

2.3 Numerical results for the example↩︎

In this sub-section, we revisit the example first introduced as part of Fig. 2 in Sec. 1. Even though the output of the last layer is used to compute the conditional probability of interest, one could do the same with the output of any intermediate layer. For this purpose, denote \[p_{t}^{(\ell)}(z):= \frac{e^{((\sigma_t^{(\ell)})^{\rm\tiny T} C^{\text{\rm (xfer)}})(z)}}{\sum_{z'\in\mathbb{O}} e^{((\sigma_t^{(\ell)})^{\rm\tiny T}C^{\text{\rm (xfer)}})(z')}},\quad z\in\mathbb{O}, \quad t=1,2,\ldots,T,\quad \ell=0,1,2,\ldots, L-1.\] Consider the following metric to compare predictions of the intermediate layer with those of the final layer: \[\overline{{\sf D}}(\ell) := \frac{1}{T} \sum_{t=1}^{T}\left(\sum_{z\in\mathbb{O}} p_t^{(L)} (z) \ln \frac{p_t^{(L)} (z) }{p_t^{(\ell)} (z)}\right),\quad \ell=0,1,2,\ldots,L-1.\] For the prompt described in Fig. 2, a numerical plot of \(\{\overline{{\sf D}}(\ell):\ell=0,1,,2,\ldots, L-1\}\) is depicted in Fig. 4. It is seen that the successive layer output provides a monotonically better approximation. It is also remarkable that the output of the first layer already assigns largest probability to “token”.

These numerical results suggest the following:

1. The layer output \(\sigma_t^{(\ell)}\in{\cal M}(\mathbb{S})\), for \(\ell=1,2,\ldots,L-1\), also has the meaning of an (approximate) surrogate of the conditional measure \(\pi_t\in {\cal P}(\mathbb{S})\).

2. The layer mapping \(\sigma^{(\ell)}\mapsto \sigma^{(\ell+1)}\) is an algorithm to iteratively compute (improve) \(\sigma^{(L)}\) starting from the initialization \(\sigma^{(0)}\).

All of this motivates the following hypothesis regarding the layer operation:

2.4 Objective: Fixed-point architecture for inference↩︎

Because the transformer layer output is interpretted as a surrogate of the conditional measure, our objective is to develop analogous representation (similar to 7 ) for \(\pi\). For this purpose, consider any fixed sample path of observations \(z :=[z_1,z_2,\ldots,z_T] \in \mathbb{O}^T\) such that \({\sf P}(Z=z)>0\). Denote \[\pi^{(z)} := \left[\pi_1^{(z)},\ldots, \pi_{T}^{(z)}\right]\quad \text{where}\quad \pi_t^{(z)}(x):={\sf P}(X_t = x \mid Z_1=z_1,\ldots,Z_t=z_t),\quad x\in\mathbb{S}, \quad 1\leq t\leq T.\] A mathematical formalization of the objective is as follows (see Fig. 5) :

3 Fixed-point inference architecture for an HMM↩︎

In this section, we describe the explicit form of \({\cal N}\) for the special case when the model is an HMM. The notation for the model is introduced next:

3.0.0.1 Mathematical model.

 Consider a finite time-horizon \(\mathbb{T}=\{0,1,2,\ldots,T\}\) with \(T<\infty\). An HMM is specified by a pair of discrete-time stochastic processes \((X,Z)\) defined as follows:

1. The state-space \(\mathbb{S}=\{1,2,\ldots,d\}\) and observation space \(\mathbb{O}=\{0,1,2,\ldots,m\}\) are finite.

2. The state process \(X=\{X_t:t\in\mathbb{T}\}=\text{Markov}(\mu,A)\) is a Markov chain taking values in \(\mathbb{S}\).

3. The observation process \(Z=\{Z_1,Z_2,\ldots,Z_T,Z_{T+1}\}\) takes values in \(\mathbb{O}\) and is modeled by \[{\sf P}(Z_{t+1} = z \mid X_t=x) = C(x,z),\quad z\in\mathbb{O},\quad x\in\mathbb{S}, \quad t\in\mathbb{T}.\]

The model is denoted by \((X,Z)=\text{HMM}(\mu,A,C)\) (see Fig. 6).

For the HMM, our goal is to describe an explicit form of the mapping \({\cal N}\). The algorithm in the following subsection is based on the theory for nonlinear predictor developed in our prior work [5]. A summary of the same is given in Appendix 5.4.

3.1 Fixed-point algorithm for inference↩︎

Let \(\rho =[\rho_1,\rho_2,\ldots,\rho_T]\in {\cal P}(\mathbb{S})^T\) and \(z=(z_1,z_2,\ldots,z_T)\in \mathbb{O}^T\). Our goal is to define a mapping \({\cal N}:\rho \mapsto \rho^+\) such that \(\pi^{(z)}\) is its fixed-point. Towards this goal,

1. Define \[c_t(x):=2 \, C(x, z_{t}) - 1,\quad x\in\mathbb{S}, \quad 1\leq t\leq T.\]

2. For \(\nu\in{\cal P}(\mathbb{S})\), \(f,c\in\mathbb{R}^d\), define \[\phi(f;\nu,c) = \begin{cases} \frac{-1}{(1-\nu(c)^2)} \left( \nu((Af)(c-\nu(c))) \right), & 1-\nu(c)^2 \neq 0, \\ 0 & \text{o.w.} \end{cases}\]

Based on these, consider a backward difference equation (B\(\Delta\)E) as follows: \[\tag{8} \begin{align} y_s(x) &= (Ay_{s+1})(x) + c_{s+1} (x) u_s,\quad x\in\mathbb{S},\quad s=0,1,2,\ldots,t-1, \tag{9} \\ u_s & = \begin{cases} \phi(y_{s+1};\rho_s,c_{s+1}) ,& s=1,2,\ldots,t-1, \\ \phi(y_{1};\mu,c_{1}), & t=0, \end{cases} \tag{10} \\ y_t(x) & = f(x),\quad x\in\mathbb{S}. \tag{11} \end{align} The solution y:=\{y_s(x)\in\mathbb{R}:x\in\mathbb{S},\;0\leq s\leq t-1\} of the B\DeltaE is used to define a mapping {\cal N}:{\cal D}\subset {\cal P}(\mathbb{S})^T\to {\cal P}(\mathbb{S})^T as follows: \begin{align} ({\cal N}\rho)_t := \rho_t^+\quad \text{s.t.} \quad \rho_t^+ (f) := \mu (y_0) - \sum_{s=0}^{t-1} u_s,\quad 1\leq t\leq T. \tag{12} \end{align}\] (compare with 7 ). The domain \({\cal D}\) is defined to be the largest subset in \({\cal P}(\mathbb{S})^T\) such that \({\cal N}\rho \in {\cal P}(\mathbb{S})^T\). That the domain is non-empty is because of the following proposition which also shows the significance of 8 to the computation of \(\pi^{(z)}\).

4 Directions for future work↩︎

In this paper, inspired by the decoder-only transformer, we introduced a probabilistic model together with an inference architecture, formalized as Objective 1. The architecture was described explicitly for the special case of a hidden Markov model (HMM), which serves as a useful starting point. A natural next step is to extend the framework to more general classes of hidden processes \(X\). In this regard, we note:

1. The positional encoding embodies a counterintuitive yet apparently effective approach to representing time in the causal processing of sequential data.

2. The attention operation 6 exhibits a symmetry: permuting the inputs \(\{\sigma_1,\sigma_2,\ldots,\sigma_{t-1}\}\) (while keeping \(\sigma_t\) fixed) yields the identical output \(o_t^h\) at time \(t\).

An understanding of these features, and their incorporation into probabilistic modeling, remains an important direction for future work.

5 Appendix↩︎

5.1 ChatGPT’s answer to the prompt: what do you think is the intended meaning of these two questions?↩︎

This title poses two layered questions, both inviting deeper reflection on the nature of large language models.

1. What Is ChatGPT Doing?

This question asks us to examine the behavior of ChatGPT at multiple levels:

• Functionally: What kind of tasks is ChatGPT performing—answering questions, generating coherent text, simulating dialogue?

• Mechanistically: What computations or internal representations underlie these responses?

• Linguistically or cognitively: Does it understand? Is it reasoning? Or is it merely imitating human-like language?

At its core, the question invites us to describe what is happening when we observe ChatGPT in action.

2. Why Does It Work?

This second question seeks a deeper explanation:

• Technically: Why do language models trained with simple objectives (e.g., next-token prediction) generalize so well?

• Conceptually: How can models built on pattern matching exhibit coherent reasoning and creativity?

• Philosophically: What does this success suggest about the nature of intelligence, understanding, and language?

This question acknowledges a puzzle: How does a model trained on statistical correlations manage to generate responses that appear meaningful and intelligent?

Together, these two questions capture a dual aim: to observe and to explain—to understand not just what language models do, but why they are so effective in doing it.

5.2 Proof of well-posedness↩︎

The existence theorems rely on the following proposition from linear algebra.

We now provide a proof of Prop. [prop:existence95nonlin95predictor95rep] leading to well-posedness of representation 2 .

5.3 Additional operations in a transformer↩︎

This section is based on [7]. Fix \(t\). The output \(y_t\) from concatenating the output of multiple heads is subject to the following operations:

1. Residual connection which means \[y_t\mapsto y_t + e_t.\]

2. Layer normalization which means \[y_t\mapsto \text{diag}(\gamma) \frac{y_t-\text{mean}(y_t)}{\text{std}(y_t)} + \beta.\] where \(\gamma\in\mathbb{R}^d\) and \(\beta\in\mathbb{R}^d\) are learnable parameters (referred to as gain and offset).

3. Feedforward neural network \[y_t\mapsto \text{FFN}(y_t).\]

Fix time \(t\). The following operations define a single layer in a transformer: \[\begin{align} y_t & = \text{MultiHeadAttention}(e_t,[e_1,e_2,\ldots,e_{t-1}])\\ y_t & = y_t + e_t \\ y_t &= \text{LayerNorm}(y_t) \\ y_t & = y_t + \text{FFN}(y_t) \\ y_t & = \text{LayerNorm}(y_t) \end{align}\] The learnable parameters in the MultiHeadAttention are the matrices \(W_V,W_K,W_Q,W_O\). For each of the two LayerNorm operations, the learnable parameters are the gains \(\gamma\) and the offset \(\beta\). Additionally, the weights of the FFN are also learned.

5.4 Theory for the nonlinear predictor↩︎

Recall the representation 2 . Our goal is to provide an interpretation of \(U\) as an optimal control input for a certain (dual) optimal control problem². The optimal control interpretation yields a formula for \(U\), from which an explicit form of the mapping \({\cal N}\) (described in Sec. 3.1) is derived.

The optimal control formulation is based on some recent advances in duality theory [13]: An HMM is an example of a state-output system (\(X\) is the state and \(Z\) is the output). In analogy with the classical duality in linear systems theory, we define an input-state system that is dual to an HMM. To this end, define \[c(x) := \begin{bmatrix} C(x,1) - C(x,0) \\ C(x,2) - C(x,0) \\ \vdots \\ C(x,m) - C(x,0) \end{bmatrix}_{m\times 1},\quad x\in\mathbb{S}.\] For each fixed \(x\in \mathbb{S}\), \(c(x)\) is a \(m\times 1\) vector.

 is a backward stochastic difference equation (BS\(\Delta\)E) \[\tag{14} \begin{align} Y_t(x) &= (AY_{t+1})(x) + c^{\rm\tiny T}(x) (U_t + V_t(x)) - V_t^{\rm\tiny T}(x) e(Z_{t+1}), \quad \;\; x\in\mathbb{S},\quad t=0,1,2,\ldots,T-1, \tag{15}\\ Y_T(x) & = F(x),\quad x\in\mathbb{S}, \tag{16} \end{align}\] where \(U\in{\cal U}\) is the control input and the terminal condition \(F \in {\cal Z}_T\) (which means \(F(x)\) is allowed to be \({\cal Z}_T\)-measurable for each \(x\in\mathbb{S}\)). For a given \(U\) and \(F\), the BS\(\Delta\)E 14 is solved to obtain the solution \((Y,V)=\{(Y_t(x),V_t(x))\in{\cal Z}_t :x\in\mathbb{S},\;t=0,1,2,\ldots,T-1\}\) (see [5] where the existence and uniqueness of the solution is shown).

Fix \(U\in {\cal U}\). For the solution \((Y,V)\) of the BS\(\Delta\)E 14 , define \[\begin{align} {\sf J}_T(U;F) := \operatorname{var}(Y_0(X_0)) + {\sf E}\Big( \sum_{t=0}^{T-1} l (Y_{t+1},V_t,U_t\,;X_t) \Big), \end{align}\] where \(\operatorname{var}(Y_0(X_0))={\sf E}(|Y_0(X_0) - \mu(Y_0)|^2) = \mu(Y_0^2) -\mu(Y_0)^2\) (note here \(Y_0\) is a deterministic function), and the running cost \(l:\mathbb{R}^d\times\mathbb{R}^{m\times d}\times\mathbb{R}^m\times\mathbb{S}\to\mathbb{R}\) is given by, \[l(y,v,u;x):= (\Gamma y)(x) + (u+v(x))^{\rm\tiny T}R(x) (u+v(x)), \quad y\in\mathbb{R}^d,\;v\in\mathbb{R}^{m\times d},\;u\in\mathbb{R}^m,\;x\in\mathbb{S},\] where \[\begin{align} (\Gamma f)(x) &:= \sum_{y\in\mathbb{S}} A(x,y) f^2(y) - (Af)^2(x),\quad x\in \mathbb{S}, \\ R(x) &:= \text{diag}(c(x)) + C(x,0) (I+{\sf 1}{\sf 1}^{\rm\tiny T}) - c(x) c^{\rm\tiny T}(x), \quad x\in\mathbb{S}. \end{align}\]

Now that the dual control system and the optimal control objective have been defined, the duality principle is given in the following theorem.

Noting that the right-hand side is the mean-squared error, the duality principle provides for an optimal control approach to compute the conditional expectation.

• Dual optimal control problem (OCP):

\[\label{eq:dual-optimal-control} \min_{U \in {\cal U}} \; {\sf J}_T(U;F) \quad \text{subject to} \quad \eqref{eq:dual95BSDE}\tag{17}\]

The relationship between the OCP 17 and the nonlinear filter is as follows:

The solution of the OCP 17 leading to an explicit formula for the optimal control \(U^{\text{\rm (opt)}}\) is described next.

Denote \[\phi(y,v;\rho) := - \rho(R)^{\dagger} \left( \rho ((c-\rho (c))y)- \rho (R v)\right), \quad y\in\mathbb{R}^d, \; v\in \mathbb{R}^{m\times d},\; \rho\in{\cal P}(\mathbb{S}).\] Here, \(\rho(R)^{\dagger}\) denotes the pseudo-inverse of the \(m\times m\) matrix \(\rho(R):=\sum_{x\in\mathbb{S}} \rho(x) R(x)\). The other two terms are \(\rho ((c-\rho (c))y) := \sum_{x\in\mathbb{S}} \rho(x) (c(x) - \rho(c)) y(x)\) and \(\rho (R v):= \sum_{x\in\mathbb{S}} \rho(x) R(x)v(x)\). Note that both of these terms are \(m\times 1\) vectors.

Denote \[\Pi :=\{\rho:\Omega\times \{1,2,\ldots,T\} \to {\cal P}(\mathbb{S}), \;\; \rho_t\in{\cal Z}_t, \;1\leq t\leq T\}.\] Note that the conditional measure \(\pi=\{\pi_t:1\leq t\leq T\}\) is an element of \(\Pi\). The subset of deterministic probability measures in \(\Pi\) is denoted by \(\Pi^{\text{\rm (det)}}\).

Pick \(\rho\in \Pi\) and consider the BS\(\Delta\)E control system, \[\tag{18} \begin{align} Y_t(x) &= (AY_{t+1})(x) + c^{\rm\tiny T}(x) (U_t + V_t(x)) - V_t^{\rm\tiny T}(x) e(Z_{t+1}),\quad x\in\mathbb{S},\quad t=0,1,2,\ldots,T-1, \tag{19} \\ U_t & = \phi(Y_t,V_t;\rho_t) ,\quad t=0,1,2,\ldots,T-1, \tag{20} \\ Y_T(x) & = F(x),\quad x\in\mathbb{S}.\tag{21} \end{align} Although the formula for the optimal control law is applied, the resulting control input is generally sub-optimal, since \rho may not coincide with the true conditional measure \pi. Because the terminal condition Y_T=F is arbitrary, the solution Y induces a mapping {\cal N}:{\cal D}\subset \Pi \to \Pi as follows: \begin{align} ({\cal N}\rho)_t(Y_t) := \mu (Y_0) - \sum_{s=0}^{t-1} U_s^{\rm\tiny T} e(Z_{s+1}),\quad 0\leq t\leq T,\tag{22} \end{align}\] where on the right-hand side, \(\{U_s:0\leq s\leq t-1\}\) is according to 20 and \(Y_0\) is the solution of 19 at time \(t=0\). It is clear that \({\cal N}\rho \in {\cal Y}^\dagger\) because the right-hand side of 22 is well-defined and \({\cal Z}_t\)-measurable for each \(0\leq t\leq T-1\). The domain \({\cal D}\) is defined to be the largest subset in \(\Pi\) such that \({\cal N}\rho \in \Pi\). That the domain is non-empty is because of the following corollary of Thm. 2.

References↩︎

---

1. We also asked ChatGPT to clarify the meaning of Wolfram’s questions. ChatGPT’s answer is reproduced verbatim in the Appendix 5.1.↩︎

2. The result is a generalization of the theory for linear predictor 1 for Gauss-Markov process. For such a process, \(u\) in the linear predictor 1 is an optimal control input for a deterministic linear quadratic (LQ) optimal control problem.↩︎