Choosing how many hidden states a sequence model should have is still mostly done by brute force. A hidden Markov model (HMM) explains a time series as jumps between a small number of unobserved regimes. To decide how many regimes $K$ there are, practitioners fit one model per candidate $K$ and score each fit. The score with the best theoretical footing is the marginal likelihood, also called the evidence: the probability of the data under a model order after averaging over all parameter values. It picks the true $K$ consistently as data grows, and it avoids the failures of information criteria. It is also expensive, because each $K$ needs its own Monte Carlo estimate, and the usual practice gives every $K$ the same large budget even when most of them are clearly wrong after a few hundred samples.
We propose to treat the choice of $K$ as a race between candidates, run by two-sided bounds. For every candidate $K$ we maintain a lower bound and an upper bound on its log evidence. Both bounds come from cheap Monte Carlo estimators and both tighten as more samples are spent. A candidate is dropped as soon as its upper bound falls below another candidate's lower bound. Compute then flows only to orders that are still in contention. The race ends with a winning $K$ and an explicit gap. It can also end with an honest "undecided between 3 and 4". A single-number criterion never gives that answer.
Core Claim
The contribution is the pairing of two ideas. The first is a stochastic sandwich on the log evidence of each fixed-$K$ HMM. The second is a dual-bound stopping and allocation rule borrowed from sequential experimental design. Together they should reach the same model-order decision as a full evidence sweep for a fraction of the compute, and the width of the final interval should be calibrated.
The sandwich is built as follows. Because the forward algorithm computes $p(y \mid \theta, K)$ exactly, the hidden path can be summed out, and only the parameters $\theta$ need to be integrated. An importance-sampling estimate $\hat Z_K$ built from $M$ draws from a proposal $q$ is unbiased for the evidence $Z_K = p(y \mid K)$. By Jensen's inequality, its logarithm is a lower bound in expectation.
A reverse (harmonic-type) estimate $\hat R_K$ averages $q(\theta)/[p(y\mid\theta,K)\,p(\theta\mid K)]$ over posterior draws of $\theta$. It is unbiased for $1/Z_K$, so its negative logarithm is an upper bound in expectation:
$$ \mathbb{E}\,[\log \hat Z_K] \;\le\; \log Z_K \;\le\; \mathbb{E}\,[-\log \hat R_K]. $$
We run independent batches of each estimator and wrap the batch means in empirical-Bernstein or bootstrap confidence limits. This gives an interval $[L_K, U_K]$ that holds with probability at least $1-\delta$. Candidate $K'$ is eliminated when
$$ U_{K'} < \max_{K} L_K , $$
and the next batch of samples goes to the surviving candidates whose intervals most overlap the leader's.
The reverse estimator only has finite variance if $q$ has lighter tails than the posterior. The locally restricted proposals of Determine the Number of States in Hidden Markov Models via Marginal Likelihood provide this. That paper estimates evidence by MCMC plus restricted importance sampling, proves the evidence is consistent for $K$, and shows that the likelihood blows up in heterogeneous Gaussian HMMs. It supplies our estimator and our main benchmark. We change how its compute is spent across candidates and what it reports at the end.
Relation to Prior Work
The stopping rule is taken directly from Sequential Bayesian Experimental Design with Variable Cost Structure. That paper (BOEDIR) keeps two-sided bounds on the mutual information of candidate experiments, stops once one candidate's lower bound beats every rival's upper bound, and treats bound tightening as a budgeted knapsack problem. Its candidates are sensor designs; ours are model orders, and our bounds are on evidence rather than information. The same "sandwich" logic explains the large speedups in exact search of Tightening Bounds for Bayesian Network Structure Learning and Integrating Sample-Based Planning and Model-Based Reinforcement Learning. Both papers motivate the design. Both work on fully specified search spaces, and neither estimates latent cardinality.
The closest existing work is Scalable Adaptation of State Complexity for Nonparametric Hidden Markov Models. It grows and shrinks a sticky nonparametric HMM with birth, merge and delete moves, and prunes candidate merges using a lower bound on the change in its variational objective. That bound is one-sided, and the objective is itself only a lower bound on evidence. The method therefore cannot say how far its final $K$ might be from the evidence-optimal one. We keep both sides and target the evidence itself.
Nonparametric samplers take a different route to choosing $K$. Beam sampling for the infinite hidden Markov model truncates an unbounded state space with random slice thresholds, and A sticky HDP-HMM with application to speaker diarization adds a self-transition bias to stop spurious switching. These methods give a posterior over $K$ that depends on concentration hyperparameters, and they do not stop with a stated error level.
We deliberately do not pursue semidefinite relaxations of the kind used in Learning of Linear Dynamical Systems as a Noncommutative Polynomial Optimization Problem or Low-Rank Semidefinite Programming for the MAX2SAT Problem.. The first targets continuous linear systems, and its relaxation grows quickly with window length. Deterministic bounds on discrete-HMM evidence would be far looser than a Monte Carlo sandwich.
Research Program
The build has three parts.
The first is the per-$K$ sandwich estimator. The forward-pass likelihood is shared between the two directions. Posterior draws come from a Gibbs or Hamiltonian sampler. To handle the $K!$ relabelings of states, the proposal $q$ is symmetrized over permutations, or restricted to one ordered labeling with the matching combinatorial correction.
The second is the racing controller. It maintains confidence limits and eliminates dominated orders. It allocates new batches by expected reduction in the overlap between each surviving interval and the leader, which is the knapsack view from BOEDIR.
The third is an analysis of when the sandwich is valid. The upper bound is exact in expectation only if the posterior draws are exact. On simulated data we get exact draws by the bidirectional trick: we simulate $(\theta, y)$ from the prior, so the generating $\theta$ is an exact posterior draw. On real data, MCMC draws are approximate, so we treat the upper limit as a diagnostic and measure how much chain length it takes to become trustworthy.
We also state one limit up front. The race works over a user-supplied range $K \le K_{\max}$. We do not yet have a valid bound that covers every larger $K$ at once, and we report this as open rather than hide it.
Baselines
The naive reference is a BIC sweep. It fits Baum-Welch with several restarts for each $K$ up to $K_{\max}$ and picks the minimum. It is what most practitioners run. Determine the Number of States in Hidden Markov Models via Marginal Likelihood reports that at $n=200$, in noisy settings, BIC chooses correctly about 16% of the time.
The strongest competitor on accuracy is the uniform-allocation evidence sweep of that same paper. It is correct about 80% of the time at $n=200$ in the same simulations, and it is the method our race must match. No reported result found on Lacuna for its compute cost.
We re-run it with the identical estimator code, spending the same total number of forward-pass evaluations that our race uses, split evenly across all $K$. We also run it at a large reference budget, which defines the "true" evidence ordering. Beating it means one of two things. Either the race matches its accuracy (within one standard error over replicates) with at least three times fewer forward evaluations, or it is more accurate at equal budget.
For the nonparametric side we run the adaptive memoized variational method of Scalable Adaptation of State Complexity for Nonparametric Hidden Markov Models and the sticky HDP-HMM sampler of A sticky HDP-HMM with application to speaker diarization. Each gets its published default hyperparameters plus a small grid of concentration values at matched wall-clock time. We take the variational method's final $K$ and the sampler's posterior mode of $K$.
Two ablations isolate the key ingredient. The first is a lower-bound-only race: it drops candidates when their estimated lower bound trails the leader by a margin, mirroring the one-sided pruning in the adaptive variational method. The second is successive halving on a single importance-sampling estimate with symmetric confidence intervals. Both use the same total budget as our race.
Why not just…?
Why not just use BIC, as everyone does? The file already contains the answer. BIC's regularity conditions fail in HMMs when $K$ is overestimated, and the likelihood is unbounded in heterogeneous Gaussian HMMs. BIC finds about 16% of true orders at $n=200$, versus about 80% for evidence. On real single-molecule FRET data it misses a rare third conformation that was later confirmed biologically (Determine the Number of States in Hidden Markov Models via Marginal Likelihood). The question is not whether to use evidence but how to afford it.
Why not just run a nonparametric model and read off $K$? Its answer depends on concentration and stickiness settings. The non-sticky and sticky versions differ from 23.91% to 17.84% diarization error on the NIST meetings (A sticky HDP-HMM with application to speaker diarization), which shows how much these settings matter. It also gives no calibrated stopping statement. For long sequences with many states, however, the adaptive variational method may simply be the better tool; we expect our race to pay off at moderate $n$ where evidence is computable. The chromatin-scale regime is outside our claim.
Why not just race with one estimator and standard confidence intervals? This is the real threat. The log of an importance-sampling estimate is biased downward, and the bias shrinks with $M$ at a rate that differs across $K$. Symmetric intervals around it can therefore systematically favor small $K$. Larger $K$ has a harder posterior, so its lower bound is looser at equal cost. If the successive-halving ablation matches our accuracy and calibration, then the upper bound is unnecessary and we will say so. The experiments measure exactly this, with extra weight on cases where the true $K$ has a rare state.
Why not spectral learning, which gives an order from a rank? Spectral learning estimates order from the numerical rank of observable moment matrices (A Spectral Algorithm for Learning Hidden Markov Models). That rank is fragile under noise, and the method is stated for discrete observations. We include a singular-value-gap rule on the discretized synthetic data as a cheap reference, not as a main competitor.
Proposed Experiments
The primary benchmark reproduces the synthetic Gaussian HMM simulations of Determine the Number of States in Hidden Markov Models via Marginal Likelihood. It uses $n=200$ and $n=2000$, several noise levels, and flat, diagonal and off-diagonal transition structures. We simulate from the prior so that the upper bound is exactly valid. Metrics are the fraction of correct $K$, forward-pass evaluations to decision, the fraction of runs ending undecided, and calibration. For calibration, among runs that declare a winner at confidence $1-\delta$, the empirical error rate should not exceed $\delta$.
We then move to real sequences where the upper bound is only approximate. These are the FRET trajectories, where the target is recovering three states rather than BIC's two, and the 4,050-point well-log series from Beam sampling for the infinite hidden Markov model, where we report the selected $K$, its interval, and agreement with a long-budget reference sweep. The last real-data test is a subset of NIST Rich Transcription meetings with known speaker counts. There, $K$-selection accuracy and diarization error of the resulting segmentation are compared with the sticky HDP-HMM figure of 17.84%.
The decisive checks are three. At equal accuracy, the race should use substantially less compute than the uniform sweep. Its stated confidence should be honest on simulated data. And the lower-bound-only and single-estimator ablations should be measurably worse at picking larger true $K$. If the third check fails, the two-sided construction adds nothing, and the contribution reduces to budget-adaptive evidence sweeping.
References
- Determine the Number of States in Hidden Markov Models via Marginal Likelihood
- Sequential Bayesian Experimental Design with Variable Cost Structure
- Tightening Bounds for Bayesian Network Structure Learning
- Integrating Sample-Based Planning and Model-Based Reinforcement Learning
- Scalable Adaptation of State Complexity for Nonparametric Hidden Markov Models
- Beam sampling for the infinite hidden Markov model
- A sticky HDP-HMM with application to speaker diarization
- Learning of Linear Dynamical Systems as a Noncommutative Polynomial Optimization Problem
- Low-Rank Semidefinite Programming for the MAX2SAT Problem.
- A Spectral Algorithm for Learning Hidden Markov Models