Dual Filter: A Transformer-like Inference Architecture for Hidden Markov Models
Heng-Sheng Chang [email protected], Prashant G. Mehta [email protected] · 2025
Read Dual Filter: A Transformer-like Inference Architecture for Hidden Markov Models by Heng-Sheng Chang [email protected], Prashant G. Mehta [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00818.txt.
Introduction
Heng-Sheng Chang and Prashant Mehta present a 2025 paper deriving a transformer-like machine from first principles instead of copying one. The setting is prediction for hidden Markov models, where a hidden state generates a stream of observations and the goal is to forecast the next one. A decoder-only transformer solves a similar problem by mapping token sequences to the odds of the next token.
The authors recast best-possible prediction as an optimal control problem, which leads to a fixed-point equation over distributions. Solving it yields their dual filter, an iterative algorithm whose structure closely mirrors the transformer's layers. Experiments with research-scale settings illustrate the algorithm. The work offers mathematics for why transformer shapes suit sequence prediction.
Catalog record
| CREATOR | Heng-Sheng Chang [email protected], Prashant G. Mehta [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 116 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-00818
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Dual Filter: A Transformer-like Inference Architecture for Hidden Markov Models Heng-Sheng Chang [email protected], Prashant G. Mehta [email protected] Abstract This paper presents a mathematical framework for causal nonlinear prediction in settings where observations are generated from an underlying hidden Markov model (HMM). Both the problem formulation and the proposed solution are motivated by the decoder-only transformer architecture, in which a finite sequence of observations (tokens) is mapped to the conditional probability of the next token. Our objective is not to construct a mathematical model of a transformer. Rather, our interest lies in deriving, from first principles, transformer-like architectures that solve the prediction problem for which the transformer is designed. The proposed framework is based on an original optimal control approach, where the prediction objective (MMSE) is reformulated as an optimal control problem. An analysis of the optimal control problem is presented leading to a fixed-point equation on the space of probability measures. To solve the fixed-point equation, we introduce the dual filter, an iterative algorithm that closely parallels the architecture of decoder-only transformers. These parallels are discussed in detail along with the relationship to prior work on mathematical modeling of transformers as transport on the space of probability measures. Numerical experiments are provided to illustrate the performance of the algorithm using parameter values typical of research-scale transformer models. H.-S. Chang and P. G. Mehta † † heading: 23 2025 1- X/XX; Revised X/XX X/XX 25-0000 † † shortheadings: Dual Filter / Chang and Mehta † † firstpage: 1 † † editor: My editor keywords Nonlinear predictor, transformer, stochastic control, optimal control, hidden Markov model. 1 Introduction 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 Phuong and Hutter (2022) ): {\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. This sparsity is useful for efficient sampling in generative AI applications ( Wolfram, 2023 ) . 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, {\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 expressed as a causal, nonlinear function of the past tokens, implemented through a procedure known as causal masking. In this paper, we refer to such a function as a nonlinear predictor (a formal definition is given after the model has been introduced). The second item is in contrast to a recurrent neural network (RNN) architecture, where a hidden state is stored and recursively updated ( Graves, 2013 ; Dai et al., 2019 ) . 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: {\sf E}(Z_{T+1}\mid Z_{1},Z_{2},\ldots,Z_{T})=\text{(constant)}+\sum_{t=1}^{T}u_{t}^{\hbox{\rm\tiny T}}Z_{t}. The right-hand side is an example of a linear predictor where u:=\{u_{t}\in\mathbb{R}^{m\times m}:1\leq t\leq T\} 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 ( Kailath et al., 2000 , Ch. 7) . The objective of this paper is to develop both theory and algorithms for a nonlinear predictor, that computes the conditional probability of the next token, for a large but finite vocabulary. Our focus is exclusively on inference, not on learning. To this end, we adopt a model-based approach based on a hidden Markov model (HMM), where the observed tokens are generated from an underlying hidden stochastic process. This process evolves as a Markov chain, taking values in a finite state space of dimension d . We begin by describing the model and then introducing the problem. 1.1 Math Preliminaries: Hidden Markov model and the nonlinear filter Throughout this paper, we consider discrete-time stochastic processes on a finite time-horizon \mathbb{T}=\{0,1,2,\ldots,T\} with T<\infty . Fix the probability space (\Omega,{\cal F}_{T},{\sf P}) along with the filtration \{{\cal F}_{t}:t\in\mathbb{T}\} with respect to which all the stochastic processes are adapted. A hidden Markov model (HMM) is specified by a pair of stochastic processes (X,Z) defined as follows (see Elliott et al. (2008) ; Cappé et al. (2006) ): 1. The state-space \mathbb{S}=\{1,2,\ldots,d\} is finite. 2. The observation-space \mathbb{O}=\{0,1,2,\ldots,m\} is finite of cardinality |\mathbb{O}|=m+1 . (With m=1 , there are only two observations \mathbb{O}=\{0,1\} . Such an HMM is referred to as the binary-valued HMM.) 3. The state process X=\{X_{t}:t\in\mathbb{T}\} is a Markov chain taking values in the state-space \mathbb{S} . Its time-evolution is modeled as \displaystyle{\sf P}(X_{0}=x) \displaystyle=\mu(x),\quad x\in\mathbb{S}. \displaystyle{\sf P}(X_{t+1}=x^{\prime}\mid X_{t}=x) \displaystyle=A(x,x^{\prime}),\quad x,x^{\prime}\in\mathbb{S},\quad t=0,1,2\ldots,T-1. The matrix A is row stochastic, meaning that for each x\in\mathbb{S} , A(x,\cdot) is a probability vector. 4. The observation process Z=\{Z_{1},Z_{2},\ldots,Z_{T}\} takes values in \mathbb{O} . Its model is given by {\sf P}(Z_{t+1}=z\mid X_{t}=x)=C(x,z),\quad z\in\mathbb{O},\;x\in\mathbb{S},\quad t=0,1,2\ldots,T-1. The matrix C is row stochastic, meaning that for each x\in\mathbb{S} , C(x,\cdot) is a probability vector. The model is succinctly denoted by (X,Z)=\text{HMM}(\mu,A,C) . For the purposes of mathematical analysis, the filtrations are introduced as follows: \displaystyle{\cal F}_{t} \displaystyle:=\sigma(X_{0},Z_{1},X_{1},\ldots,Z_{t},X_{t}),\quad t\in\mathbb{T}, \displaystyle{\cal Z}_{t} \displaystyle:=\sigma(Z_{1},Z_{2},\ldots,Z_{t}),\quad t=1,2,\ldots,T, with {\cal Z}_{0}:=\{\phi,\Omega\} . {\cal F}=\{{\cal F}_{t}:t\in\mathbb{T}\} is referred to as the canonical filtration with respect to which all processes are adapted. The graphical model for the HMM is depicted in Fig. 1 . state observation (token) X_{0} X_{1} \cdots X_{T-1} X_{T} Z_{1} Z_{2} \cdots Z_{T} Z_{T+1} time 0 1 T-1 T Figure 1: Graphical model for the HMM. Notation: The spaces of signed measures on \mathbb{S} and \mathbb{O} are denoted by {\cal M}(\mathbb{S}) and {\cal M}(\mathbb{O}) , respectively, and the set of probability measures {\cal P}(\mathbb{S})\subset{\cal M}(\mathbb{S}) and {\cal P}(\mathbb{O})\subset{\cal M}(\mathbb{O}) . The space of signed-measures and functions on \mathbb{S} are both identified with \mathbb{R}^{d} : a real-valued function f (resp., a measure \mu ) is identified with a column vector in \mathbb{R}^{d} where the x^{\text{th}} element of the vector represents f(x) (resp., \mu(x) ), for x\in\mathbb{S} , and \mu(f):=\mu^{\hbox{\rm\tiny T}}f=\sum_{x}\mu(x)f(x) . Lower case symbol, e.g., f , is used to denote a deterministic function while an upper case symbol, e.g., F , is used to denote a random function. For such a function, the notation F\in{\cal Z}_{t} means F(x) is {\cal Z}_{t} -measurable for each x\in\mathbb{S} . A product of two functions f and g is denoted by fg ( (fg)(x)=f(x)g(x) for x\in\mathbb{S} ), and f^{2}=ff . The unity function is denoted by {\sf 1} (e.g., as a function on \mathbb{S} , {\sf 1}(x)=1 for all x\in\mathbb{S} ). For a vector f\in\mathbb{R}^{d} , \text{diag}(f) is d\times d diagonal matrix with entries given by the components of f . We follow the convention \frac{0}{0}=0 . Nonlinear filter: The objective of nonlinear (or stochastic) filtering is to compute the conditional measure, also called the posterior. It is defined as a conditional expectation, \pi_{t}(f):={\sf E}\big(f(X_{t})\mid{\cal Z}_{t}\big),\quad f\in\mathbb{R}^{d},\quad t\in\mathbb{T}. A recursive formula for the same is given by \pi_{t+1}(f)=\frac{\pi_{t}(\text{diag}(C(:,Z_{t+1}))Af)}{\pi_{t}(\text{diag}(C(:,Z_{t+1})){\sf 1})},\quad t=0,1,2\ldots,T-1,\quad\pi_{0}=\mu. The