Conditional Random Field

A conditional random field (CRF) is a discriminative probabilistic model for structured prediction, used most often to assign a label to every position in an input sequence. Instead of modeling how inputs and labels were jointly generated, a CRF defines a single conditional distribution over the entire label sequence given the entire observation sequence, and normalizes that distribution once over whole sequences rather than separately at each position ^[1]. John Lafferty, Andrew McCallum and Fernando Pereira introduced the model at the Eighteenth International Conference on Machine Learning in 2001. All three authors were then at WhizBang! Labs Research in Pittsburgh; Lafferty and McCallum also listed Carnegie Mellon University, and Pereira the University of Pennsylvania ^[1].

The original paper framed CRFs as a fix for two separate problems. Compared with hidden Markov models and other generative models, a conditional model does not have to account for the distribution of the observations, so it can use arbitrary, overlapping and non-independent features of the input without the inference problem becoming intractable. Compared with maximum entropy Markov models (MEMMs) and other locally normalized classifiers chained together, the global normalization removes a systematic distortion the authors named the label bias problem ^[1].

CRFs became the standard tool for sequence labeling in natural language processing through the 2000s and remained a component of the best neural taggers well into the deep learning era. The OpenAlex bibliographic index records more than 13,000 citations of the 2001 paper ^[22]. The model is still in active use, both as an output layer on top of neural encoders and as a structured smoothing step in computer vision.

Background: sequence labeling before CRFs

Many language and biology tasks map an input sequence to a sequence of labels: part-of-speech tagging, named-entity recognition and shallow parsing in text ^[3], or segmenting genes in a strand of DNA ^[2]. Two families of methods dominated before 2001 ^[3].

The first used generative sequence models, typically HMMs. An HMM factorizes the joint probability of states and observations into a transition distribution and an observation distribution, which keeps training and decoding simple but forces strong independence assumptions ^[2]. Features that clearly help with unseen words, such as capitalization, suffixes and surrounding words, are awkward to add because the model must explain how they were produced ^[1][3].

The second family applied a classifier at each position, conditioning on the input window and on the previous few decisions. Maximum entropy taggers and MEMMs work this way. They accept correlated features freely, but because each position is trained and normalized independently, they cannot trade a decision at one position against a decision made later in the sequence ^[3].

The label bias problem

The 2001 paper identified a structural weakness shared by MEMMs and other next-state classifiers. In such a model the transitions leaving a given state compete only against each other, not against all transitions in the model. Because the score mass arriving at a state must be distributed among that state's successors, an observation can influence which successor receives the mass, but not how much mass is passed on at all. The result is a bias toward states with few outgoing transitions, and in the limit a state with a single outgoing transition ignores its observation entirely ^[1].

Lafferty and colleagues illustrated the effect with a small finite-state model that distinguishes the words rib and rob. Given the input r i b, the first symbol splits probability mass roughly evenly between the two branches. Both branch states then have exactly one outgoing transition, so neither can react to the i that follows, and whichever word was slightly more frequent in training wins regardless of the observation ^[1]. The authors credited Yoshua Bengio, Léon Bottou, Michael Collins and Yann LeCun with alerting them to the phenomenon, and coined the name in this paper ^[1].

A CRF avoids the problem because it has one exponential model for the whole label sequence rather than one per state. Transition weights are no longer constrained to be locally normalized probabilities, so individual transitions can amplify or dampen the mass they receive, and evidence observed after a branch point can still overturn the branch ^[1].

Definition

Let G = (V, E) be a graph whose vertices index the output variables Y. The pair (X, Y) is a conditional random field if, conditioned on X, the variables Y obey the Markov property with respect to G: each Y_v is independent of the rest of Y given its graph neighbors ^[1]. By the Hammersley-Clifford theorem, a strictly positive distribution is Markov with respect to a graph exactly when it factorizes over that graph, which gives the exponential form used in practice ^[2].

Note what is not assumed. The model says nothing about the structure of X and never represents p(x). That is the source of the modeling freedom: features may inspect any part of the input, at any distance, in any combination, without the model needing to explain their statistical dependence ^[1][2].

Linear-chain CRFs

The case used for sequence labeling is the linear chain, where the output variables form a chain and each factor couples one label, its predecessor, and the observations. Sutton and McCallum state it as follows: given a parameter vector and a set of real-valued feature functions f_k(y_t, y_{t-1}, x_t), a linear-chain CRF is the distribution

p(y|x) = (1 / Z(x)) * prod_t exp( sum_k theta_k * f_k(y_t, y_{t-1}, x_t) )

where Z(x) is an instance-specific normalization function summing over all label sequences ^[2]. Writing an HMM in this exponential form and then conditioning on the observations yields exactly a linear-chain CRF with features restricted to word identity, which is why the pair is described as a generative-discriminative pair in the same sense as naive Bayes and logistic regression ^[2].

Feature functions

A feature function returns a real number for a candidate label pair at a position. In classical NLP systems they are almost all binary indicators built by feature engineering: tests on the current word, capitalization, digit patterns, prefixes and suffixes, membership in a gazetteer, the part-of-speech tags at nearby positions, and conjunctions of those tests with label pairs ^[3][4]. Feature sets were large. The shallow parsing CRF of Sha and Pereira used about 3.8 million features on the CoNLL-2000 training set ^[3]. Because a CRF can also assign a weight of negative infinity, hard constraints on label sequences (for example, forbidding a continuation tag that does not follow a begin tag) are expressed directly in the model ^[3].

Inference

Two quantities are needed. Training requires the marginal probability of each label and label pair, computed with a forward-backward recursion; prediction requires the single highest-scoring label sequence, computed with the Viterbi algorithm. Both are dynamic programming procedures over the chain, and each forward or backward update costs time quadratic in the number of labels, giving O(T M^2) for a sequence of length T with M labels ^[2]. Because Z(x) does not depend on the labels, decoding can maximize the unnormalized score directly ^[3].

Practical implementations either rescale the forward and backward vectors at each step or work in the logarithmic domain to avoid numerical underflow ^[2].

For graphs that are not trees, exact inference is intractable and approximations are used, including loopy belief propagation, mean field, and other variational inference methods ^[2].

Training

CRFs are trained by penalized maximum likelihood: the parameters are chosen to maximize the conditional log-likelihood of the labeled training sequences, usually with an L2 penalty from a Gaussian prior ^[2][3]. The objective is concave in the parameters, so every local optimum is also a global optimum, and for tree-structured models (of which the chain is the simplest case) a numerical optimizer provably converges to the optimal solution ^[2]. The gradient has a simple form: for each feature, the empirical count minus the model's expected count under the current parameters, with the expectation supplied by forward-backward ^[3].

The 2001 paper used two iterative scaling algorithms, Algorithm S and Algorithm T, both derived from improved iterative scaling ^[1]. These converged slowly, and the paper listed that slowness as the method's main limitation ^[1]. Within two years the field had moved to general-purpose convex optimizers. Sha and Pereira compared training methods on noun-phrase chunking and found that limited-memory BFGS reached their target penalized log-likelihood in 84 minutes and preconditioned conjugate gradient in 130 minutes, while generalized iterative scaling never reached it at all ^[3]. McCallum and Li's named-entity system likewise used L-BFGS ^[4]. Later toolkits added stochastic gradient descent and online methods such as averaged perceptron, passive-aggressive and AROW ^[13].

Results reported in the original paper

The 2001 paper evaluated CRFs against HMMs and MEMMs with matched state structures. On synthetic data generated to reproduce the label bias example, using 2,000 training and 500 test sequences, the CRF reached 4.6% error while the MEMM reached 42%, confirming that the MEMM could not discriminate between the two branches ^[1]. On part-of-speech tagging over the Penn treebank, using first-order models trained on half of the 1.1 million word corpus with an out-of-vocabulary rate of 5.45%:

Scroll sideways for more →

Adding orthographic features (capitalization, digits, hyphens and a list of suffixes) cut the overall error by around 25% and the out-of-vocabulary error by around 50% for both conditional models, which the HMM could not match ^[1].

Applications in natural language processing

Shallow parsing was one of the first large-scale applications of CRFs ^[2]. On the CoNLL-2000 noun-phrase chunking data, Sha and Pereira reported an F score of 94.38% for a single CRF, statistically indistinguishable from a combination of 24 forward- and backward-looking support vector machine classifiers at 94.39% and better than any previously reported single model ^[3].

Scroll sideways for more →

A McNemar test on labeling disagreements put the CRF-versus-MEMM difference at p = 0.00109, while the CRF-versus-SVM difference was not significant at p = 0.469 ^[3].

McCallum and Li applied CRFs to the CoNLL-2003 named-entity shared task, adding automatic feature induction and lexicons harvested from web pages by a method they called WebListing. Their system reached an overall F1 of 84.04% on the English test set and 68.11% on German, training in about 12 hours on a 1 GHz Pentium; substituting fixed conjunction patterns for feature induction dropped English F1 to 73.34% while using about a million features ^[4]. Peng, Feng and McCallum extended the approach to Chinese word segmentation and new word detection ^[5]. CRFs were also applied to citation extraction from research papers, identifying protein names in biology abstracts, RNA structural alignment and protein structure prediction, among many other tasks in information extraction and bioinformatics ^[2].

The BiLSTM-CRF era

Neural encoders removed the need for hand-built features but did not remove the need for structured output. Huang, Xu and Yu published the BI-LSTM-CRF architecture in 2015: a bidirectional long short-term memory network produces a score for each label at each position, and a CRF layer on top models the transitions between adjacent labels and decodes the whole sequence with Viterbi. They reported accuracy at or near the state of the art on part-of-speech tagging, chunking and named-entity recognition, with less dependence on pretrained word embeddings than earlier systems ^[6].

Two 2016 papers made the design canonical. Lample and colleagues combined a bidirectional LSTM with a CRF and with character-level representations, and reported state-of-the-art named-entity results in four languages without language-specific resources or gazetteers ^[7]. Ma and Hovy added a character-level convolutional neural network to the same stack, reporting 97.55% accuracy on Penn Treebank WSJ part-of-speech tagging and 91.21% F1 on CoNLL-2003 named-entity recognition with no feature engineering or preprocessing ^[8]. A 2025 reproducibility study of that architecture obtained 91.18% F1 on CoNLL-2003 and released a PyTorch implementation ^[18].

The pattern carried over to pretrained transformers, where a CRF layer is commonly placed on top of a BERT-style encoder for token classification ^[23]. The tradeoff is no longer automatic: the Flair library, for example, switches the CRF on by default in its sequence tagger and keeps it in the stacked-embedding recipe, but deactivates the CRF (along with the recurrent layer and the reprojection) when fine-tuning a transformer, on the grounds that the transformer is powerful enough not to need those components ^[17].

Computer vision

CRFs entered vision as a way to enforce spatial consistency in semantic segmentation, where a per-pixel classifier produces noisy labels that ignore object boundaries. Basic models put pairwise potentials only on neighboring pixels or image patches, an adjacency structure that cannot capture long-range connections and generally oversmooths object boundaries ^[9].

Philipp Krähenbühl and Vladlen Koltun of Stanford University changed that in 2011 with a fully connected CRF defined over every pair of pixels in the image, a graph with tens of thousands of nodes and billions of edges. Their contribution was an approximate inference algorithm for the case where pairwise potentials are a linear combination of Gaussian kernels: mean field updates for all variables at once can be carried out by high-dimensional filtering in feature space, which reduces the cost of message passing from quadratic to linear in the number of variables and makes the algorithm sublinear in the number of edges ^[9]. On the same images, MCMC inference ran for 36 hours without fully converging and graph cut inference did not converge within 72 hours, while their single-threaded implementation produced a pixel-level labeling in 0.2 seconds. On MSRC-21 the method reached 86.0% global accuracy against 84.6% for a grid CRF and 84.0% for the unary classifiers alone, and on PASCAL VOC 2010 it reached 30.2% average accuracy against 28.3% and 27.6% ^[9].

This dense CRF became the standard post-processing step for the first generation of deep learning segmentation systems. DeepLab combined the responses of a deep convolutional network with a fully connected CRF and reported 79.7% mean intersection-over-union on the PASCAL VOC 2012 test set ^[11]. Zheng and colleagues went further and reformulated mean-field inference in a Gaussian-pairwise CRF as a recurrent neural network, so the CRF could be trained end to end with the convolutional network by backpropagation instead of being bolted on afterwards ^[10].

Implementations

Scroll sideways for more →

Limitations

The cost of exact inference grows quadratically with the label set, which becomes the bottleneck when labels are numerous, as in tagging schemes with many entity types or in second-order models ^[2][3]. Outside chains and trees, exact maximum likelihood training is intractable and practitioners fall back on approximate inference, which interacts awkwardly with learning ^[2].

Standard CRFs also assume a finite decision span, typically label bigrams, which limits how far label dependencies can reach ^[21]. The original slow-convergence complaint was real too: the 2001 paper reported that a CRF initialized from a uniform distribution had not converged after 2,000 iterations on the tagging task, while initializing from a trained MEMM converged in 1,000 ^[1]. Modern optimizers largely closed that gap, but a CRF layer still costs more than independent per-token softmax prediction, and strong pretrained encoders capture enough context that some libraries now recommend leaving it out ^[17].

Current status

CRFs are no longer the headline method for sequence labeling, but they have not left the toolkit. As an output layer, CRFs continue to appear on top of pretrained encoders for token classification in languages and domains where labeled data is scarce, including Bangla medical entity recognition, Urdu toxic span detection and nested entity extraction from plasma physics papers ^[23]. As a structured refinement step, CRFs are used to clean up predictions from large pretrained models: a January 2026 system called HistoCRF refines the zero-shot output of vision-language models on histopathology patches with a pairwise potential designed to promote label diversity, and its authors report average accuracy gains across five patch-level classification datasets of 16.0% over the zero-shot baseline with no annotations and 27.5% with only 100 annotations ^[19].

There is also continuing work on the algorithms themselves. Flash-SemiCRF, published in April 2026, targets semi-Markov CRFs, which label variable-length segments rather than individual positions; it replaces materialized edge-potential tensors with prefix-sum lookups and adds a streaming forward-backward pass with checkpoint-boundary normalization, keeping working memory sublinear in sequence length while preserving exact gradients. Packaged as a fused Triton kernel, it is claimed to enable exact semi-CRF inference at previously intractable problem sizes, including the genomic scales where sequences can exceed 100,000 positions ^[20]. A June 2026 paper trains a CRF conditioned on a noised version of the full label sequence using a diffusion process, sidestepping the finite-decision-span restriction and reporting, together with approximate CRF inference, a 16.5% error reduction on part-of-speech tagging ^[21]. Other 2025-2026 work applies CRFs to auditory attention decoding from EEG, pedestrian intention prediction, time series modeling and privacy-preserving video processing ^[23].

See also

• Hidden Markov model
• Named entity recognition
• Discriminative model
• Sequence model
• Semantic segmentation
• Maximum likelihood estimation

References

1. ^John Lafferty, Andrew McCallum and Fernando Pereira, "Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data," Proceedings of the Eighteenth International Conference on Machine Learning (ICML 2001), pages 282-289. cs.columbia.edu/...crf.pdf
2. ^Charles Sutton and Andrew McCallum, "An Introduction to Conditional Random Fields," arXiv:1011.4088, 17 November 2010; published in Foundations and Trends in Machine Learning, volume 4, issue 4 (2012), pages 267-373. arxiv.org/...1011.4088
3. ^Fei Sha and Fernando Pereira, "Shallow Parsing with Conditional Random Fields," Proceedings of HLT-NAACL 2003, pages 134-141. aclanthology.org/N03-1028
4. ^Andrew McCallum and Wei Li, "Early Results for Named Entity Recognition with Conditional Random Fields, Feature Induction and Web-Enhanced Lexicons," Proceedings of CoNLL 2003 at HLT-NAACL. aclanthology.org/W03-0430
5. ^Fuchun Peng, Fangfang Feng and Andrew McCallum, "Chinese Segmentation and New Word Detection using Conditional Random Fields," COLING 2004, pages 562-568. aclanthology.org/C04-1081
6. ^Zhiheng Huang, Wei Xu and Kai Yu, "Bidirectional LSTM-CRF Models for Sequence Tagging," arXiv:1508.01991, 9 August 2015. arxiv.org/...1508.01991
7. ^Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami and Chris Dyer, "Neural Architectures for Named Entity Recognition," arXiv:1603.01360, 4 March 2016. arxiv.org/...1603.01360
8. ^Xuezhe Ma and Eduard Hovy, "End-to-end Sequence Labeling via Bi-directional LSTM-CNNs-CRF," arXiv:1603.01354, 4 March 2016. arxiv.org/...1603.01354
9. ^Philipp Krähenbühl and Vladlen Koltun, "Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials," Advances in Neural Information Processing Systems 24 (2011), pages 109-117; arXiv:1210.5644. arxiv.org/...1210.5644
10. ^Shuai Zheng, Sadeep Jayasumana, Bernardino Romera-Paredes, Vibhav Vineet, Zhizhong Su, Dalong Du, Chang Huang and Philip H. S. Torr, "Conditional Random Fields as Recurrent Neural Networks," ICCV 2015; arXiv:1502.03240. arxiv.org/...1502.03240
11. ^Liang-Chieh Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy and Alan L. Yuille, "DeepLab: Semantic Image Segmentation with Deep Convolutional Nets, Atrous Convolution, and Fully Connected CRFs," arXiv:1606.00915, 2 June 2016. arxiv.org/...1606.00915
12. ^CRF++: Yet Another CRF toolkit, project page by Taku Kudo. taku910.github.io/crfpp
13. ^CRFsuite: a fast implementation of Conditional Random Fields, project page by Naoaki Okazaki. chokkan.org/...crfsuite
14. ^MALLET: MAchine Learning for LanguagE Toolkit, project page. mimno.github.io/Mallet
15. ^pytorch-crf documentation. pytorch-crf.readthedocs.io/...stable
16. ^sklearn-crfsuite documentation. sklearn-crfsuite.readthedocs.io/...latest
17. ^Flair documentation, "How to train a sequence tagger." flairnlp.github.io/...how-to-train-sequence-tagger
18. ^Anirudh Ganesh and Jayavardhan Reddy, "End-to-end Sequence Labeling via Bi-directional LSTM-CNNs-CRF: A Reproducibility Study," arXiv:2510.10936, 13 October 2025. arxiv.org/...2510.10936
19. ^Tiffanie Godelaine, Maxime Zanella, Karim El Khoury, Saïd Mahmoudi, Benoît Macq and Christophe De Vleeschouwer, "Conditional Random Fields for Interactive Refinement of Histopathological Predictions," arXiv:2601.12082, 17 January 2026. arxiv.org/...2601.12082
20. ^Benjamin K. Johnson, Thomas Goralski, Ayush Semwal, Hui Shen and H. Josh Jang, "Streaming Structured Inference with Flash-SemiCRF," arXiv:2604.18780, 20 April 2026. arxiv.org/...2604.18780
21. ^Nicolas Floquet, Joseph Le Roux and Nadi Tomeh, "Approximate Structured Diffusion for Sequence Labelling," arXiv:2606.18856, 17 June 2026. arxiv.org/...2606.18856
22. ^OpenAlex bibliographic record for the 2001 CRF paper (13,013 citations as retrieved 24 July 2026). api.openalex.org/works
23. ^arXiv listing of recent papers whose abstracts mention conditional random fields, retrieved 24 July 2026. export.arxiv.org/...query