# Temporal Parallelization of Inference in Hidden Markov Models

arXiv: https://arxiv.org/abs/2102.05743 · HTML: https://mlsanity.com/paper/2102.05743/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 50 references that are in the map.
- First posted on arXiv 10 Feb 2021.

## Builds on (most cited first, 4 of 4)

- [In-Datacenter Performance Analysis of a Tensor Processing Unit](https://mlsanity.com/paper/1704.04760/) (2017)
- [Temporal Parallelization of Bayesian Smoothers](https://mlsanity.com/paper/1905.13002/) (2019)
- [Parallel Iterated Extended and Sigma-point Kalman Smoothers](https://mlsanity.com/paper/2102.00514/) (2021)
- [Fast Path Localization on Graphs via Multiscale Viterbi Decoding](https://mlsanity.com/paper/1711.01329/) (2017)

## Built on by (most cited first, 5 of 5)

- [SING: SDE Inference via Natural Gradients](https://mlsanity.com/paper/2506.17796/) (2025)
- [A Unifying Framework for Parallelizing Sequential Models with Linear Dynamical Systems](https://mlsanity.com/paper/2509.21716/) (2025)
- [De-Sequentialized Monte Carlo: a parallel-in-time particle smoother](https://mlsanity.com/paper/2202.02264/) (2022)
- [Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models](https://mlsanity.com/paper/2305.18578/) (2023)
- [High-Performance Tensor Formulation of the Viterbi Algorithm for Hidden Semi-Markov Models](https://mlsanity.com/paper/2609.16500/) (2026)

## Abstract (arXiv)

This paper presents algorithms for parallelization of inference in hidden Markov models (HMMs). In particular, we propose parallel backward-forward type of filtering and smoothing algorithm as well as parallel Viterbi-type maximum-a-posteriori (MAP) algorithm. We define associative elements and operators to pose these inference problems as parallel-prefix-sum computations in sum-product and max-product algorithms and parallelize them using parallel-scan algorithms. The advantage of the proposed algorithms is that they are computationally efficient in HMM inference problems with long time horizons. We empirically compare the performance of the proposed methods to classical methods on a highly parallel graphical processing unit (GPU).