Exact Constrained Decoding for Sequence Models: Controller-Augmented Hidden Markov Models and Beyond
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Statistics. The day in statistics: methods, theory and the inference under them.
Tom: We're looking at the paper: "Exact Constrained Decoding for Sequence Models".
Jane: Here's the gist of the paper. Hidden Markov models are fundamental for sequential inference, yet their standard Markovian assumption breaks down when confronted with pathwise constraints such as precedence requirements, visitation cardinalities, or monotonic state progression.
Tom: These constraints introduce long-range dependencies that invalidate conventional dynamic programming algorithms.
Jane: To address this limitation, the paper introduces Controller-Augmented Hidden Markov Models (CHMMs), a novel framework designed to handle structured sequence labeling under finite-memory path constraints.
Tom: CHMMs operate by compiling each constraint into a finite-state controller that tracks the minimal sufficient history.
Paper summary: Tom: So wrapping up "Exact Constrained Decoding for Sequence Models: Controller-Augmented Hidden Markov Models and Beyond," the main point is that we have a new computational framework, CHMMs, that lets us solve sequence labeling problems with pathwise constraints exactly.
Jane: It’s about taking those hard rules—like needing an order or visiting states a certain number of times—and turning them into a finite state controller that tracks the history needed to enforce those rules locally and globally (<ref:2606.13850#pg1>).
Lu: The paper proves that this augmentation keeps the model Markovian in a way, so we can still use standard algorithms like forward backward to get exact answers instead of relying on approximations like beam search that might fail to accumulate the required structure (<ref:2606.13850#pg3>).
Meng: For deployment, it suggests that if you have cumulative constraints, this approach is much safer for getting a guaranteed feasible path compared to simpler decoders that might only check things locally (<ref:2606.13850#pg2>).
Lalam: In simple terms, we can now compute the exact probability of a sequence given these structural rules, and the paper gives us concrete ways to design those controllers for various types of constraints (<ref:2606.13850#pg2>).
Tom: The authors are giving us a systematic catalog of eleven constraint families—like ordering, visitation, and temporal requirements—and showing exactly how to encode them into these controllers (<ref:2606.13850#pg2>).
Jane: So what this means for the world is that any application relying on long-range dependencies in sequences can now potentially get an exact solution instead of an approximation, provided you can define those dependencies as a controller constraint (<ref:2606.13850#pg1>).
Lu: It’s a principled way to handle these structured sequence labeling problems that we’ve seen popping up everywhere in AI applications (<ref:2606.13850#pg2>).
Meng: The limitation they mention is the size of that controller state space, so you still have to design controllers that are computationally feasible for the hardware you're using on real traffic (<ref:2606.13850#pg1>).
Lalam: Overall, this paper provides a solid tool for when exactness is required and you need to enforce complex path constraints in sequence models (<ref:2606.13850#pg2>).
Conclusion: Tom: So, we're wrapping up on "Exact Constrained Decoding for Sequence Models: Controller-Augmented Hidden Markov Models and Beyond." Basically, these authors took Hidden Markov models and added a controller to handle those tricky path rules—like needing an order or visiting states a certain number of times—and made them solvable exactly.
Jane: That's the main idea, Tom. They used this controller concept to turn a problem that was way too complex into one that standard algorithms, like forward backward, could actually solve for the exact probability and path.
Lu: The paper focuses on how you design these controllers—they give us eleven different families of constraints across ordering and visitation—and they prove that this augmentation keeps the model Markovian while enforcing those finite-memory rules.
Meng: From an engineering standpoint, what’s impressive is the guarantee they provide: inference complexity is linear in the size of that controller, which means it scales nicely to production systems if you can design a manageable controller space.
Lalam: And for the learning part, they show that this constrained expectation maximization procedure actually climbs toward the correct parameter settings in a monotone way, which means we can learn those sequence models more reliably under these rules.
Tom: So it’s about making sure that when you have complex path constraints, you don't just get an approximation; you get the exact answer because of this controller trick.
Jane: Exactly. It gives us a principled way to handle things that aren't simple Markovian transitions anymore, which is where a lot of real-world sequence data lives.
Lu: The paper lays out a solid methodology for constraint design, which is useful for anyone trying to build these kinds of specialized sequence models that need to respect specific structural requirements.
Meng: But I do see the bottleneck they flag—the size of that controller state space—so if you’re building this, you still have to worry about how big that controller gets before it becomes too slow on real traffic.
Lalam: And the authors also prove that even if your constraints are slightly off, the inference stays stable because it's bounded by how much those constraint sets actually differ from each other.
Tom: It sounds like this framework moves us past just getting good approximations to actually guaranteeing exactness when sequence structure matters.
Jane: Right. So, this opens up the door for AI applications where sequence constraints are non-negotiable, not just nice to have, and we need to know the precise probability of a valid path.
Lekha Patel, Luis Damiano
Sandia National Laboratories
stat.ME, stat.ML
Submitted: 2026-06-11
Updated: 2026-11-13
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 91/100
The gist: Hidden Markov models are fundamental for sequential inference, yet their standard Markovian assumption breaks down when confronted with pathwise constraints such as precedence requirements…
Key concepts
- Controller Augmentation
- This technique transforms a constrained problem into an unconstrained one. A finite-state controller is designed to track only the minimal history required to satisfy path constraints like precedence or visitation rules. This augmented state space allows standard Markovian algorithms to solve the complex, constrained sequence labeling problem exactly.
- Gating Function
- A function used locally within the CHMM framework that checks if a potential transition violates a path-dependent rule. If the gating function outputs 0, it blocks that specific transition from occurring. This enforces local path constraints step-by-step during inference.
- Finite-Memory Path Constraints
- These are structured rules governing sequences, such as requiring an item to appear before another (precedence) or limiting how many times a state can be visited (visitation cardinality). CHMMs handle these by encoding the necessary history into the controller, ensuring that only trajectories satisfying these specific path rules are considered valid.
- Monotone Ascent of EM
- This guarantee ensures that when training models using Expectation-Maximization (EM), the likelihood function will always increase or stay the same. This property is crucial for finding exact parameter learning solutions in constrained sequence labeling problems.
Terminology
Summary
Hidden Markov models are fundamental for sequential inference, yet their standard Markovian assumption breaks down when confronted with pathwise constraints such as precedence requirements, visitation cardinalities, or monotonic state progression. p. 0 gov
Luis Damiano
Optimization & Uncertainty Quantification
Sandia National Laboratories
Albuquerque, NM 87123
ladamia@sandia. gov
June 15, 2026
ABSTRACT
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. gov
Luis Damiano
Optimization & Uncertainty Quantification
Sandia National Laboratories
Albuquerque, NM 87123
ladamia@sandia. gov
June 15, 2026
ABSTRACT
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. These diverse applications share a fundamental requirement for
exact probabilistic inference over trajectories that satisfy pathwise constraints transcending first-order Markovian
dependencies, whilst differing crucially in whether the dominant constraint is purely local (a forbidden transition or a
no-reentry rule) or genuinely cumulative (a precedence chain or an exactly-k-visit cardinality), a distinction that turns
out to govern which inference strategies succeed and which fail in practice. This paper introduces Controller-Augmented Hidden Markov Models (CHMMs), a principled framework for exact
inference under structured sequence labeling subject to finite-memory path constraints, namely those constraints that
admit encoding by a deterministic finite controller. gov
June 15, 2026
ABSTRACT
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. gov
June 15, 2026
ABSTRACT
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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The framework is formally defined by a controller specification (C, c 0, tau, F, F T), where the constraint set chi is satisfied if and only if a trajectory x maintains the gating function F(c t, x t, x t+1) = 1 for all steps and ends in a terminal controller state c T in F T. p. 6 logic (Pnueli, 1977) have been extensively formalized, and our framework compiles these logical specifications into a
probabilistic inference-ready format. Table 1 provides the catalog, in which each constraint is specified by its controller
space C, update function τ , gating condition F, and terminal acceptance set FT . In this paper, all inference and learning are performed under the conditional distribution given Acc, denoted p(· | Acc),
where the constrained path law equivalently satisfies p(x | Acc) ∝ p(x) 1{x ∈ χ}. The controller therefore enforces
the constraint through two complementary mechanisms: local gating via F(c, i, j) blocks transitions that would violate
path-dependent requirements given the current controller state, whilst terminal acceptance via FT restricts the inference
normalization to trajectories whose terminal controller state lies in FT , thereby ensuring that cumulative requirements
are satisfied.Where the paper says it
Where the paper says it
The main contributions of this work include proving that the controller augmentation preserves the Markov property while enforcing finite-memory pathwise constraints. p. 1 1 Main Contributions
Our work makes 4 contributions to the field of constrained sequential inference. First, we prove that the controlleraugmentation construction preserves the Markov property whilst enforcing finite-memory pathwise constraints, enabling
direct application of standard HMM algorithms on the augmented state space. First, we prove that the controlleraugmentation construction preserves the Markov property whilst enforcing finite-memory pathwise constraints, enabling
direct application of standard HMM algorithms on the augmented state space. Second, we provide a systematic
methodology for controller design, with a catalog of eleven constraint families spanning the ordering, visitation, path,
and temporal categories, each with an off-the-shelf encoding. This linear scaling ensures computational tractability even for complex constraint combinations,
and the systematic nature of the encoding further enables practitioners to compose multiple constraints through controller
products, with overall complexity scaling as the product of the individual controller sizes. To illustrate how these encodings are realized in practice, and to exhibit the two enforcement mechanisms in their
canonical forms, we now present two worked examples: a precedence constraint whose enforcement is purely local
(gating only), and a visitation constraint whose enforcement is purely cumulative (terminal acceptance only). 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Empirically, the results reveal a clean local-versus-cumulative dichotomy. p. 0 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. 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. We additionally develop a unified evaluation framework
comprising 4 headline metrics (position-wise accuracy, macro-averaged F1, sequence-level trajectory validity rate,
and segment-F1) that operationalize structural fidelity alongside the standard classification metrics. The framework is
subsequently exercised on 3 real-world sequence-labeling tasks demonstrating that protocol-defined domain knowledge
can be incorporated into CHMMs to deliver categorical empirical gains over locally-pruning alternatives in the
cumulative-constraint regime. 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. This paper introduces Controller-Augmented Hidden Markov Models (CHMMs), a principled framework for exact
inference under structured sequence labeling subject to finite-memory path constraints, namely those constraints that
admit encoding by a deterministic finite controller. Our approach transforms constrained non-Markovian problems
into unconstrained Markovian problems on an augmented state space through systematic controller design, with the
controller maintaining precisely the minimal information necessary to determine constraint satisfaction at each step of
the sequential process.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved inference capability for models with pathwise constraints, specifically those involving precedence requirements, visitation cardinalities, or monotonic state progression. This allows AI systems to compute exact constrained posteriors and maximum a posteriori paths in both discrete and continuous time without relying on standard dynamic programming algorithms that fail under these dependencies.
-
Enhanced parameter learning capabilities by enabling the standard expectation maximization (EM) machinery to be applied directly on the augmented state space, where
the gating annihilates infeasible counts and thus enters the updates only as a support restriction.
This leads to a constrained EM procedure with amonotone-ascent property,
ensuring that the sequence of constrained marginal log-likelihoods is non-decreasing. -
A robust mechanism for assessing constraint misspecification by providing an interpretable bound on the deviation between constrained and true posterior distributions, stating that
the trajectory-level identity (34) states that the constrained posteriors under chi and chi star differ in total variation by precisely the fraction of the larger constraint set that is not shared with the smaller one.
This allows developers to quantify exactly how much inference error results from using incomplete domain knowledge. -
Increased computational tractability for complex path constraints by transforming non-Markovian problems into unconstrained Markovian problems on an augmented state space. The complexity is characterized as
polynomial in |C|
and scales linearly with the controller cardinality for many constraint families, such as those requiring visitation counts or temporal windows. -
A unified evaluation framework that includes metrics beyond standard classification accuracy, such as
Sequence-level trajectory validity rate,
which is defined as the binary indicator thatthe entire decoded path lies in the feasibility set,
allowing for a direct measure of structural fidelity. -
Superior performance on tasks dominated by cumulative constraints (like gene-structure decoding) where controller augmentation delivers a categorical advantage over locally pruning alternatives, achieving
TVRseq = 1 for any constraint encodable in the catalog.
Conversely, it is shown that in locally-dominated regimes (like CASAS activity recognition), simpler decoders are matched in validity.
Abstract
Hidden Markov models are foundational for sequential inference, yet conditioning on pathwise constraints such as precedence requirements, visitation cardinalities, or monotonic state progression can introduce long-range dependencies that require additional memory for dynamic programming. To deal with this, we present Controller-Augmented Hidden Markov Models (CHMMs), a framework that compiles each constraint into a finite-state controller tracking a sufficient finite history, after which standard forward--backward and Viterbi recursions on the augmented chain compute exact constrained posteriors and maximum a posteriori paths in discrete time and, through uniformization, maximum a posteriori augmented-state sequences at observation times in continuous time. While we establish several theoretical guarantees, a catalog of controller encodings for 11 constraint families operationalizes our framework. Empirically, we evaluate classical and neural decoders with and without controller augmentation on 3 real-world sequence-labeling tasks: gene-structure decoding in Drosophila melanogaster, free-living activity recognition in CASAS smart homes, and protocol-defined activity recognition from wearable sensors. Together, theory and experiment characterize when exact controller augmentation is useful and when simpler approaches suffice.
Related papers
- Learning Robust Treatment Rules for Censored Data
- Neural Estimation of Summary Statistics for Simulation-Based Inference with Non-Asymptotic Guarantees
- Spectral divide-and-conquer MCMC for long stationary time series
- Improving the Efficiency of Subgroup Analysis in Randomized Controlled Trials with TMLE
- Personalized Federated Vector Autoregression with Personalization Diversity
- Doubly Robust and Efficient Calibration of Prediction Sets for Right-Censored Time-to-Event Outcomes