CRF Sequence Labeling

Every sentence is a sequence of words, and understanding language often means sticking a label on each one: this is a Person, that is an Organization, and the rest are Other. The task is called sequence labeling, and it sits at the heart of named-entity recognition, part-of-speech tagging, and dozens of other language problems.

The naive approach labels each word independently — look at the word, maybe its neighbors, and pick the most likely tag. But language rarely works that way. "Washington" is a person, a city, or a state depending entirely on what surrounds it. A model that ignores those dependencies will make avoidable mistakes.

Conditional Random Fields (CRFs), introduced by Lafferty, McCallum and Pereira in 2001, solve this by scoring the entire label sequence jointly. Instead of asking "what is the best label for word $i$?", a CRF asks "what is the best sequence of labels for the whole sentence?" That global view lets it enforce consistency across positions — if the model commits to B-ORG here, it will naturally prefer I-ORG next rather than an incoherent jump.

CRFs are a solved model: training by maximum-likelihood gradient descent and decoding by the Viterbi algorithm (dynamic programming in $O(n \cdot k^2)$ time, where $n$ is the sequence length and $k$ is the number of labels) are both well understood and efficient.

Below is a short sentence with a hidden gold annotation. Click any word to cycle its label through O (Other), B-PER (person start), I-PER (person continuation), B-ORG (organization start), and I-ORG (organization continuation). The score panel shows how well your labeling agrees with typical CRF transition and emission features.

<!-- {{c_intro}} -->
<p class="hint">{{hint_para}}</p>
<div id="sentence" class="sentence" role="group" aria-label="{{aria_sentence}}"></div>
<div class="score-panel">
  <div class="score-row">
    <span class="score-label">{{label_score}}</span>
    <span id="score-value" class="score-value">0</span>
    <span class="score-bar-wrap"><span id="score-bar" class="score-bar"></span></span>
  </div>
  <div id="violations" class="violations"></div>
</div>
<div class="btns">
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <button id="btn-reveal" type="button">{{btn_reveal}}</button>
</div>
<div id="legend" class="legend">
  <span class="tag-O">O</span> {{legend_o}}
  &nbsp;&nbsp;
  <span class="tag-B-PER">B-PER</span> <span class="tag-I-PER">I-PER</span> {{legend_per}}
  &nbsp;&nbsp;
  <span class="tag-B-ORG">B-ORG</span> <span class="tag-I-ORG">I-ORG</span> {{legend_org}}
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px 4px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.sentence { display: flex; flex-wrap: wrap; gap: 6px; margin-bottom: .8rem; }
.token { display: inline-flex; flex-direction: column; align-items: center; cursor: pointer;
         border-radius: 8px; padding: 6px 10px 5px; border: 2px solid #cdd9e3;
         background: #f0f4f8; transition: all .12s; user-select: none; }
.token:hover { border-color: #5a87c0; }
.token .word { font: 700 15px ui-monospace, monospace; }
.token .tag { font-size: .7rem; font-weight: 600; margin-top: 3px; padding: 1px 5px;
              border-radius: 4px; letter-spacing: .03em; }
/* {{c_css_colors}} */
.token[data-tag="O"] .tag { background: #e8eef3; color: #5a7088; }
.token[data-tag="B-PER"] .tag, .token[data-tag="I-PER"] .tag { background: #d4f0e0; color: #1a6e3c; }
.token[data-tag="B-ORG"] .tag, .token[data-tag="I-ORG"] .tag { background: #dde7fb; color: #1d3a8a; }
.token.violation { border-color: #e63946; }
.score-panel { display: flex; flex-direction: column; gap: 4px; margin-bottom: .7rem; }
.score-row { display: flex; align-items: center; gap: 8px; }
.score-label { font-size: .85rem; color: #555; min-width: 80px; }
.score-value { font: 700 15px system-ui; min-width: 28px; text-align: right; }
.score-bar-wrap { flex: 1; height: 10px; background: #e0e7ef; border-radius: 5px; overflow: hidden; }
.score-bar { height: 100%; background: #1d8a4e; border-radius: 5px; width: 0; transition: width .3s; }
.violations { font-size: .8rem; color: #c0392b; min-height: 1.2em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.legend { font-size: .78rem; color: #555; display: flex; flex-wrap: wrap; align-items: center; gap: 4px; }
.legend .tag-O { background: #e8eef3; color: #5a7088; padding: 1px 6px; border-radius: 4px; font-weight: 600; }
.legend .tag-B-PER, .legend .tag-I-PER { background: #d4f0e0; color: #1a6e3c; padding: 1px 6px; border-radius: 4px; font-weight: 600; }
.legend .tag-B-ORG, .legend .tag-I-ORG { background: #dde7fb; color: #1d8a4e; padding: 1px 6px; border-radius: 4px; font-weight: 600; }
.tag-I-PER { background: #d4f0e0; color: #1a6e3c; }
.tag-B-ORG { background: #dde7fb; color: #1d3a8a; }
.tag-I-ORG { background: #dde7fb; color: #1d3a8a; }

// Code not found

Notice that some transitions feel "wrong" even before checking the score — I-ORG right after O is a red flag, because the BIO convention says a continuation tag must follow a matching begin tag. A CRF learns exactly these cross-position constraints from data, encoding them as transition features in the model's log-linear score.

Unlike many learning problems that hide NP-hard inference inside them, CRFs are remarkably tractable:

• Decoding (finding the best label sequence given the model) runs in $O(n \cdot k^2)$ time via the Viterbi algorithm — dynamic programming that sweeps left to right, keeping only the best partial path to each state. With $n$ words and $k$ labels, you fill a table of size $n \times k$ in time proportional to $k^2$ per step.
• Training optimizes a convex log-likelihood objective. Gradient descent with L-BFGS converges to the global optimum; there are no local minima to worry about.
• Marginals (the probability of each label at each position, summed over all consistent sequences) come from the forward–backward algorithm, also $O(n \cdot k^2)$, and are needed for the gradient.

The real difficulty is not computational but representational: the model is only as good as its features. Traditional CRFs rely on handcrafted indicator functions — is the current word capitalized? Does it end in -ing? What is the previous predicted label? Getting these right is an art.

Modern systems layer a CRF on top of a deep neural network (a BiLSTM-CRF or Transformer-CRF) that learns features automatically, combining the expressive power of neural representations with the global consistency guarantee of the CRF output layer. This combination — tractable exact decoding on top of learned representations — is why CRFs remain relevant in the era of large language models. Compare this to the unconstrained sampling in Bayesian inference, where exact inference is often intractable.

Sequence labeling appears wherever meaning is distributed across positions, and CRFs have been deployed across a wide range:

• Named-entity recognition (NER): tagging people, places, organizations, and dates in news articles, contracts, and medical records — the classic CRF application since Lafferty et al. (2001).
• Part-of-speech tagging: assigning grammatical roles (noun, verb, adjective, …) to every token; the context-sensitive transitions give CRFs an edge over per-word classifiers.
• Chunking and shallow parsing: identifying noun phrases, verb phrases, and other syntactic chunks without building a full parse tree.
• Biomedical NLP: finding gene names, protein mentions, and clinical entities in scientific literature, where domain-specific capitalization and compound words make feature design critical.
• OCR post-correction: fixing errors in scanned text by treating the sequence of recognized characters as a sequence-labeling problem with spelling constraints as features.
• Computer vision: CRFs model spatial label dependencies in image segmentation and scene labeling, extending the sequential model to two-dimensional grids.

The common thread: whenever the correct label at position $i$ depends on what comes before and after, a model that scores the full sequence will outperform one that labels positions independently. Related ideas appear in pattern matching, where finding structure in sequences is also the central challenge.

Conditional Random Fields occupy a special place in machine learning: they are one of the few models where you can score an exponential number of possible outputs — all $k^n$ label sequences — and still find the best one exactly, in polynomial time, via Viterbi. That is not obvious, and it is not free; it relies on the chain structure of the model.

The lesson generalizes. Whenever a problem has sequential structure and you need globally consistent predictions, the right tool is a model that scores sequences, not positions. CRFs made that lesson concrete for language, and their influence echoes in every modern neural sequence model that terminates with a structured output layer.

Whether you are tagging entities in a legal brief or segmenting proteins in a genome, you are solving the same problem Lafferty, McCallum and Pereira formalized in 2001: given a sequence of observations, find the label sequence that is most consistent with everything you know — not just locally, but globally.