When building systems that predict sequences—whether they are words in a sentence, notes in a melody, or genetic variations in a strand of DNA—we often face a fundamental choice: do we decide the next step based purely on what looks best right now, or do we look at the entire sequence as a whole?
The first approach, known as greedy decoding, is fast but myopic. If a model makes a high-confidence mistake early on, that error cascades down the line, ruining the coherence of the entire output. The second approach, global sequence optimization, avoids this trap. By treating sequence prediction as a pathfinding problem through a structured state space, it ensures that every local prediction is mathematically consistent with the global context.
At the heart of this paradigm is the Viterbi algorithm, a dynamic programming mechanism that efficiently finds the globally optimal sequence without evaluating an exponential number of possibilities.
The Myopia of Local Decisions
To understand why global optimization is necessary, consider the task of predicting grammatical tense in a language like Chinese, which lacks explicit verb conjugations. A sentence-level classifier might look at individual words and guess their tenses independently. However, human conversations possess structural continuity; we rarely flip randomly between past, present, and future from one clause to the next.
As Ge et al. demonstrate, a local classifier can easily be tripped up by noisy local features. To fix this, they introduce a cost function that balances the local classifier's confidence against a penalty for transitioning between different tenses. By using a finite-state automaton and Viterbi decoding, the system smooths out local errors, forcing the final sequence of labels to respect the broader conversational scene.
This tension between local ambiguity and global structure appears across many domains:
- Text Normalization: When cleaning up informal social media text (e.g., converting "bday" to "birthday"), Li et al. use Viterbi decoding to integrate n-gram language model probabilities across the full input string, ensuring the chosen words make sense together.
- Syntactic Parsing: Traditional dependency parsers often make greedy local choices to maintain speed. Duan et al. overcome this by using Viterbi decoding over transition probability distributions, allowing the parser to consider the "big picture" of sentence structure without losing efficiency.
- Speech Synthesis: In Chinese text-to-speech systems, predicting where a speaker should pause (prosodic boundaries) requires global consistency. Ding et al. append a Viterbi decoding layer to the output of a bidirectional LSTM, optimizing for the most probable sequence of transitions between boundary types rather than treating each character as an isolated prediction.
The Trellis: How Global Optimization Works
How do we find the single best sequence out of millions of possibilities without checking them all? We organize the search space into a trellis (or word lattice).
Imagine a grid where the horizontal axis represents time steps (or positions in a sequence) and the vertical axis represents all possible states (or labels) the system can occupy at that step. Every path from the left side of the grid to the right side represents one complete sequence configuration.
States
A ---- (A1) ---- (A2) ---- (A3)
\ / \ /
B ---- (B1) ---- (B2) ---- (B3)
\ / \ /
C ---- (C1) ---- (C2) ---- (C3)
Time: t=1 t=2 t=3
If we have $N$ possible states and a sequence of length $T$, there are $N^T$ possible paths—an exponentially large number that quickly becomes impossible to compute.
The Viterbi algorithm solves this by exploiting the Markov property: the optimal path to a specific state at time $t$ depends only on the optimal paths to the states at time $t-1$.
At each step in the trellis, the algorithm calculates two values:
- The Emission Score: How well does this state match the observed data at this specific moment?
- The Transition Score: How likely is it to move from a given state at $t-1$ to this state at $t$?
Instead of keeping track of every path, the algorithm only remembers the single highest-scoring path reaching each individual node. When it reaches the end of the sequence ($t=T$), it simply selects the node with the highest overall score and follows its pointers backward (a process called traceback) to reconstruct the optimal sequence.
Bridging Continuous Signals and Discrete Logic
One of the greatest strengths of global sequence optimization is its ability to act as a translator between continuous, noisy real-world signals and discrete, logical categories.
For instance, in genomics, Baldazzi et al. apply the Viterbi algorithm to decode underlying DNA sequences from the continuous, noisy physical force generated when unzipping a double helix. Similarly, Kamath et al. map the biological problem of haplotype assembly to the decoding of convolutional codes, using a state trellis to find the most probable sequence of genetic variations given a set of fragmented, error-prone sequencing reads.
This mechanism is equally powerful when tracking abstract lifecycles in text. Gupta et al. track how entities change over time in procedural documents (like recipes or scientific protocols). They combine continuous hidden representations from LSTMs with discrete logical constraints using a Conditional Random Field (CRF). By running Viterbi decoding over the entire document, they ensure that an entity's state transitions follow common-sense rules—preventing a model from, for example, "destroying" an ingredient before it has even been "created."
Scaling and Speed: Lattice Alternatives to Deep Learning
While deep autoregressive neural networks (like Transformers) have become dominant in sequence generation, they generate tokens one-by-one, requiring a full forward pass of a massive network for every single word. This makes them computationally expensive and slow.
Global sequence optimization over lattices offers a lightweight, high-speed alternative. The authors of Sequence-to-Lattice Models for Fast Translation demonstrate that you can replace a deep, autoregressive neural decoder with a lightweight search lattice. By using a simple statistical model to generate candidate tokens and a single-layer neural network to score the lattice, they use Viterbi decoding to find the optimal translation path. This approach achieves up to a 20x speedup while maintaining the translation accuracy of much heavier models.
A Universal Abstraction
Ultimately, global sequence optimization works because it treats coherence as a geometric property of a path through a graph. This abstraction is so robust that its applications extend far beyond language and biology:
- Neural Architecture Search: Zhou et al. use Viterbi decoding to find the optimal sequence of neural network operations across different stages of a vision model, proving that global path optimization yields more robust architectures than greedy, layer-by-layer selection strategies.
- Real-Time Audio Processing: To handle streaming audio without infinite delay, Schmalenstroeer et al. implement a partial traceback Viterbi decoder. By forcing the algorithm to output its finalized path at fixed intervals, they achieve low-latency speaker segmentation and identification in real time.
By shifting the optimization target from the immediate next step to the entire lifecycle of the sequence, trellis-based decoding provides a mathematical guarantee of global consistency that local classifiers simply cannot match.