Exact Constrained Decoding for Sequence Models: Controller-Augmented Hidden Markov Models and Beyond

arXiv:2606.13850 · stat.ME, stat.ML · Submitted 2026-06-11 · Read on arXiv

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

Where the paper says it

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 constraints introduce long-range dependencies that invalidate conventional dynamic programming algorithms. p. 0
Where the paper says it

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.

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. p. 1
Where the paper says it

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.

CHMMs operate by compiling each constraint into a finite-state controller that tracks the minimal sufficient history. p. 0
Where the paper says it

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.

This augmented state space transforms the constrained non-Markovian problem into an unconstrained Markovian problem, allowing standard forward–backward and Viterbi recursions to compute exact constrained posteriors and maximum a posteriori paths in both discrete and continuous time. p. 0
Where the paper says it

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.

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

Where the paper says it

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 .

Constraints are enforced locally through gating functions that block transitions violating path-dependent rules, and globally via terminal acceptance based on F T. p. 5
Where the paper says it

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.

The main contributions of this work include proving that the controller augmentation preserves the Markov property while enforcing finite-memory pathwise constraints. p. 1

Where the paper says it

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.

The paper provides a systematic methodology for controller design, presenting a catalog of eleven constraint families across ordering, visitation, path, and temporal categories with corresponding systematic encodings (e. p. 1
Where the paper says it

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.

g., precedence constraints via binary flags, visitation constraints via terminal acceptance). p. 6
Where the paper says it

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).

Crucially, the framework establishes four theoretical guarantees: exactness of constrained inference, monotone ascent of constrained Expectation–Maximization (EM), inference complexity linear in the controller cardinality C, and a total-variation bound under constraint misspecification. p. 0
Where the paper says it

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.

Empirically, the results reveal a clean local-versus-cumulative dichotomy. p. 0

Where the paper says it

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.

Controller augmentation is uniquely capable of recovering globally feasible trajectories when constraints are cumulative, whereas simpler decoders maintain validity when constraints are locally dominated. p. 0
Where the paper says it

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.

CHMMs demonstrate superior performance across real-world sequence labeling tasks, achieving a sequence-level trajectory validity rate of 1 for any constraint encodable in the catalog. p. 3
Where the paper says it

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.

Furthermore, the constrained EM procedure enables exact parameter learning through monotone ascent guarantees on the marginal log-likelihood. p. 0
Where the paper says it

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.

The framework's robustness is confirmed by proving that inference remains stable under constraint mismatch, bounded by the symmetric difference of constraint sets. While its principal limitation lies in controller state space size C and novel constraint design bottlenecks, CHMMs offer a principled solution for exact inference under structured sequence labeling. p. 1
Where the paper says it

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.

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

  1. 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.

  2. 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 a monotone-ascent property, ensuring that the sequence of constrained marginal log-likelihoods is non-decreasing.

  3. 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.

  4. 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.

  5. 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 that the entire decoded path lies in the feasibility set, allowing for a direct measure of structural fidelity.

  6. 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