# Controller-Augmented Hidden Markov Models: A Computational Framework for Constrained Sequential Inference

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 63 references that are in the map.
- First posted on arXiv 11 Jun 2026.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Neural Architectures for Named Entity Recognition](https://mlsanity.com/paper/1603.01360/) (2016)
- [Structured Inference Networks for Nonlinear State Space Models](https://mlsanity.com/paper/1609.09869/) (2016)
- [A Survey of Constraint Formulations in Safe Reinforcement Learning](https://mlsanity.com/paper/2402.02025/) (2024)
- [A Survey of Safe Reinforcement Learning and Constrained MDPs: A Technical Survey on Single-Agent and Multi-Agent Safety](https://mlsanity.com/paper/2505.17342/) (2025)
- [Probabilistic Model Checking and Autonomy](https://mlsanity.com/paper/2111.10630/) (2021)
- [Variational inference based on a subclass of closed skew normals](https://mlsanity.com/paper/2306.02813/) (2023)
- [State-Space Abstractions for Probabilistic Inference: A Systematic Review](https://mlsanity.com/paper/1804.06748/) (2018)
- [Statistical Inference in Hidden Markov Models using k-segment Constraints](https://mlsanity.com/paper/1311.1189/) (2013)
- [hmmTMB: hidden Markov models with flexible covariate effects in R](https://mlsanity.com/paper/2211.14139/) (2022)
- [Hierarchical Semi-Markov Models with Duration-Aware Dynamics for Activity Sequences](https://mlsanity.com/paper/2509.18414/) (2025)

## Abstract (arXiv)

Hidden Markov models are foundational for sequential inference, but their Markovian assumption fails under pathwise constraints such as precedence requirements, visitation cardinalities, or monotonic state progression, which induce long-range dependencies that invalidate standard dynamic programming algorithms. To deal with this, we present Controller-Augmented Hidden Markov Models (CHMMs), a framework that compiles each constraint into a finite-state controller tracking the minimal sufficient history, after which standard forward--backward and Viterbi recursions on the augmented chain compute exact constrained posteriors and maximum a posteriori paths in both discrete and continuous time, the latter through uniformization. We establish four theoretical guarantees: exactness of constrained inference, monotone ascent of constrained EM, inference complexity linear in the controller cardinality, and a total-variation bound under constraint misspecification. A catalog of controller encodings covering 11 constraint families across the ordering, visitation, path, and temporal categories operationalizes the framework. Empirically, we evaluate CHMMs against 6 alternative decoders on 3 real-world sequence-labeling tasks of substantively different character: gene-structure decoding in Drosophila melanogaster, free-living activity recognition in CASAS smart-home environments, and protocol-defined human activity recognition from wearable sensors. The results reveal a clean local-versus-cumulative dichotomy in which controller augmentation is uniquely able to recover globally feasible trajectories on cumulative-constraint regimes, whilst simpler decoders are matched in validity on locally-dominated regimes. Together, theory and experiment characterize when exact controller augmentation is necessary and when simpler approaches suffice.