In sequence labeling tasks—such as part-of-speech (POS) tagging, named entity recognition (NER), and syntactic supertagging—the goal is to assign a label to every token in a sequence. For years, the gold standard for this task has been structured prediction models like Conditional Random Fields (CRFs) paired with Viterbi decoding. These models are powerful because they don't just look at tokens in isolation; they model the transitions between consecutive labels.
However, this expressive power comes with a steep computational cost. If a task requires a label set of size $L$, modeling the transitions between every possible pair of labels requires evaluating an $L \times L$ matrix. As a result, both training (which requires calculating a global normalization factor) and inference (which requires finding the highest-scoring path) scale quadratically ($O(L^2)$) with the number of labels.
Standard CRF Transition Matrix (Dense):
L1 L2 L3 ... Ln
L1 [ X X X ... X ]
L2 [ X X X ... X ] --> O(L^2) computation at every step
L3 [ X X X ... X ]
...
Ln [ X X X ... X ]
When $L$ is small (e.g., a dozen core POS tags), $O(L^2)$ is trivial. But modern natural language processing tasks frequently push $L$ into the hundreds or thousands. For instance, predicting complex combinatoric "supertags" for high-precision grammars, analyzing fine-grained morphological features, or identifying thousands of ultra-fine-grained entity categories all cause standard architectures to hit a scalability wall. As noted by Andrew Smith et al. in their work on Logarithmic Opinion Pools for Conditional Random Fields, high-dimensional label spaces lead to prohibitive computational costs and memory requirements that severely limit real-time applications.
To scale sequence models to massive label sets, researchers have developed a variety of strategies to bypass or mitigate this quadratic bottleneck. These solutions broadly fall into three categories: pruning the transition space, structurally aggregating labels, and relaxing global normalization.
Pruning the Transition Space
The intuition behind pruning is simple: while the theoretical transition space is $L \times L$, the practically useful or linguistically permissible transition space is highly sparse. We can avoid computing the full matrix by filtering out impossible or highly unlikely transitions before running heavy computations.
Tag Dictionaries and Transition Masks
One of the most direct ways to prune the label space is to use a dictionary that restricts which labels are valid for a given token. Robert Moore demonstrated in An Improved Tag Dictionary for Faster Part-of-Speech Tagging that leveraging a massive, automatically labeled corpus to build a highly restrictive tag dictionary drastically reduces the number of candidate tags evaluated per token. This eliminates the need to compute transitions for irrelevant labels, speeding up inference without sacrificing accuracy.
In a similar vein, the authors of Constrained Decoding for Computationally Efficient Named Entity Recognition Taggers showed that the computationally expensive global CRF layer can be replaced entirely. By training a model with standard token-level cross-entropy and applying a rule-based transition mask during inference (e.g., forbidding an "Inside-Organization" tag from following a "Beginning-Person" tag), they achieved comparable accuracy while cutting training time in half.
Active vs. Inactive States
Instead of static rules, we can dynamically partition the label space during training and decoding. Minwoo Jeong et al. introduced a framework in Efficient Inference of CRFs for Large-Scale Natural Language Data that decomposes label states into "active" and "inactive" sets.
Dynamic Partitioning:
Active Labels (Frequent/Likely) --> Compute full transitions
Inactive Labels (Rare/Unlikely) --> Treat transitions as constants
By treating rare, inactive transitions as constants rather than calculating their exact probabilities at every step, the authors achieved up to a 50x speedup in training and a 12x speedup in decoding.
Structural Aggregation and Output Coding
Another way to beat quadratic complexity is to change how the label space is represented, compressing the $L \times L$ matrix into a more compact structural form.
Tied Potentials
If many labels behave similarly or occur rarely, we can group them together. In Efficient Inference in Large Conditional Random Fields, Trevor Cohn proposed tied potentials, a technique that clusters rare label configurations and processes them en masse. Instead of maintaining distinct parameters for every rare transition, the model shares parameters across the cluster, dramatically reducing the number of unique transition weights that must be calculated during inference.
Error-Correcting Output Codes (ECOC)
Alternatively, we can decompose a single large sequence labeling problem into multiple independent binary problems. Trevor Cohn et al. explored this in Scaling Conditional Random Fields Using Error-Correcting Codes, mapping large label sets to shorter binary strings.
While breaking the problem into independent binary tasks speeds up computation, it introduces a new flaw: it destroys the vital Markovian transition structure between labels. To fix this, Guohua Hao et al. proposed Cascaded SECOC (c-SECOC) in Revisiting Output Coding for Sequential Supervised Learning. Their approach re-couples the binary tasks in a cascaded fashion, allowing the model to retain sequential context and restore accuracy while preserving the speed advantages of output coding.
Relaxing Global Normalization
The core bottleneck during CRF training is calculating the partition function—the denominator that sums over all possible sequences to turn raw scores into probabilities. Several approaches avoid this by changing the optimization objective or using approximate inference.
Local Approximations: Piecewise Pseudolikelihood
Instead of normalizing over the entire sequence globally, we can normalize over local windows. In Piecewise pseudolikelihood for efficient training of conditional random fields, Charles Sutton et al. introduced Piecewise Pseudolikelihood (PWPL). PWPL splits the graphical model into independent factors (pieces) and trains them locally.
Global CRF: P(Y|X) = exp(∑ score) / Z(X) <-- Z(X) sums over all paths (O(L^2))
Piecewise PL: P(Y|X) ≈ ∏ exp(score_i) / Z_i(X) <-- Local normalization over small factors
This local normalization bypasses the global $O(L^2)$ sequence-wide summation, yielding a 5–10x training speedup while maintaining accuracy near that of maximum likelihood estimation. This strategy proved highly effective for scaling up complex tasks; for example, Phil Blunsom et al. successfully utilized a pseudo-likelihood approximation in Multilingual Deep Lexical Acquisition for HPSGs via Supertagging to predict hundreds of complex syntactic tags across different languages.
Inference Networks and Sampling
When exact decoding via the Viterbi algorithm is too slow, approximate inference can bridge the gap. Lifu Tu et al. investigated this trade-off in Benchmarking Approximate Inference Methods for Neural Structured Prediction. They demonstrated that Inference Networks—auxiliary models trained to directly predict the outputs of an expensive inference process—can be used to "warm-start" gradient descent, offering a much faster alternative to exact Viterbi search in massive label spaces.
For unsupervised scenarios where the label space expands combinatorially, the authors of Unsupervised Bayesian Part of Speech Inference with Particle Gibbs turned to advanced sampling. By using a Particle Gibbs approach, they successfully navigated tightly coupled probability landscapes without suffering from the cubic or quadratic scaling bottlenecks inherent to exact unsupervised inference algorithms.
Summary
The challenge of scaling sequence models to large label sets has forced a shift away from dense, global calculations toward sparsity, decomposition, and local approximations. Whether by pruning impossible paths with tag dictionaries, compressing the space via output codes, or relaxing the global partition function through piecewise training, these techniques share a common goal: ensuring that our models spend their computational budget only on the label transitions that truly matter.
Key Foundational Work
Logarithmic Opinion Pools for Conditional Random Fields (2005) — contributed 2 concept elements to this direction.
Scaling Conditional Random Fields Using Error-Correcting Codes (2005) — contributed 1 concept elements to this direction.
Efficient Hierarchical Entity Classifier Using Conditional Random Fields (2006) — contributed 1 concept elements to this direction.