Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Viterbi Algorithm › Constrained Decoding

Michael BrenndoerferUpdated April 28, 20254 min read

Language AI HandbookAll chapters

Part 6 of 67Sequence Labeling

Chapter 41Viterbi Algorithm › Constrained Decoding

Reading section 9 of 12 · Constrained Decoding · 4 minSection 9 of 12 · 4 min

Section 9 of 12 · 4 min read

Viterbi Algorithm › Constrained DecodingOne section · Sections in this chapter9 / 12 ↓

Sections in this chapter12

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

In sequence labeling, certain tag transitions are invalid. An I-LOC tag cannot follow a B-PER tag. Rather than learning these constraints from data, we can enforce them during decoding by setting invalid transition probabilities to zero (or negative infinity in log space).

In[24]:

Code

def get_bio_constraints(entity_types):
    """
    Generate valid transition constraints for BIO tagging.

    Returns a set of valid (prev_tag, curr_tag) pairs.
    """
    tags = ["O"]
    for etype in entity_types:
        tags.extend([f"B-{etype}", f"I-{etype}"])

    valid_transitions = set()

    for prev_tag in tags + ["<START>"]:
        for curr_tag in tags:
            # O can follow anything
            if curr_tag == "O":
                valid_transitions.add((prev_tag, curr_tag))
                continue

            # B-X can follow anything (starts new entity)
            if curr_tag.startswith("B-"):
                valid_transitions.add((prev_tag, curr_tag))
                continue

            # I-X can only follow B-X or I-X
            if curr_tag.startswith("I-"):
                curr_type = curr_tag[2:]
                if prev_tag == f"B-{curr_type}" or prev_tag == f"I-{curr_type}":
                    valid_transitions.add((prev_tag, curr_tag))

    return valid_transitions


# Generate constraints
entity_types = ["PER", "LOC", "ORG"]
valid = get_bio_constraints(entity_types)

Out[25]:

Console

BIO Tagging Constraints
=======================================================

Entity types: ['PER', 'LOC', 'ORG']
Tags: O, B-PER, I-PER, B-LOC, I-LOC, B-ORG, I-ORG

Sample valid transitions:
  O        → B-PER    ✓
  B-PER    → I-PER    ✓
  I-PER    → I-PER    ✓
  I-PER    → B-LOC    ✓
  B-LOC    → O        ✓

Sample invalid transitions:
  O        → I-PER    ✗
  B-PER    → I-LOC    ✗
  I-LOC    → I-PER    ✗

Constraint summary: 38 valid transitions out of 49 possible

The constraints follow BIO semantics: I-tags can only continue entities of the same type, while B-tags and O can follow any tag. Invalid transitions like O → I-PER (starting an entity with a continuation tag) or B-PER → I-LOC (continuing a PER entity as LOC) are explicitly forbidden. By setting these transition probabilities to negative infinity during Viterbi decoding, we guarantee the output is always a well-formed BIO sequence.

Out[26]:

Visualization

Heatmap showing 7x7 matrix of BIO tag transitions. Valid transitions are green, invalid are red. Clear diagonal pattern visible for I-tags. — BIO transition constraint matrix as a heatmap. Green cells indicate valid transitions, red cells indicate forbidden transitions. Notice the diagonal pattern in the I-tag region: I-PER can only follow B-PER or I-PER, never tags of different entity types. This sparse structure enables significant computational optimization.

The heatmap reveals the structure of BIO constraints at a glance. The first row and column (O tag) show that O can follow anything and anything can precede O. The B-tags (columns 2, 4, 6) are fully green because they can follow any tag since they start new entities. The distinctive pattern appears in the I-tag columns: each I-tag has exactly two green cells, corresponding to its matching B and I tags. This sparsity (25 valid out of 49 possible transitions) enables significant optimization during Viterbi decoding.

Constrained decoding ensures the output is always a valid BIO sequence, even if the model's raw scores would suggest otherwise. This is particularly important for neural models that don't explicitly model transition constraints.