Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Conditional Random Fields › Inference Complexity and Practical Considerations

Michael BrenndoerferUpdated May 6, 20253 min read

Language AI HandbookAll chapters

Part 6 of 67Sequence Labeling

Chapter 42Conditional Random Fields › Inference Complexity and Practical Considerations

Reading section 9 of 13 · Inference Complexity and Practical Considerations · 3 minSection 9 of 13 · 3 min

Section 9 of 13 · 3 min read

Conditional Random Fields › Inference Complexity and Practical ConsiderationsOne section · Sections in this chapter9 / 13 ↓

Sections in this chapter13

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

CRF inference has specific computational characteristics worth understanding for practical applications.

Time ComplexityLink Copied

The key operations scale as follows:

Forward/Backward Algorithm: $O(nK^2)$ where $n$ is sequence length and $K$ is number of labels
Viterbi Decoding: $O(nK^2)$
Gradient Computation: $O(nK^2)$ per training example

The quadratic dependence on $K$ means that CRFs become expensive with many labels. For tasks with hundreds of possible labels (like fine-grained NER with many entity types), this can be a bottleneck.

Out[37]:

Visualization

Line plot showing CRF computational complexity growing linearly with sequence length for a fixed number of labels. — Linear scaling with sequence length (K=10 labels fixed). Operations grow proportionally with n.

Line plot showing CRF computational complexity growing quadratically with the number of labels for a fixed sequence length. — Quadratic scaling with label count (n=50 tokens fixed). Operations grow with K², becoming prohibitive for large label sets.

Beam Search AlternativeLink Copied

When exact Viterbi decoding is too slow, beam search provides an approximate alternative. Instead of tracking all $K$ labels at each position, beam search keeps only the top $B$ partial sequences:

In[38]:

Code

def beam_search_decode(emissions, transitions, beam_width=3, num_tags=5):
    """
    Approximate decoding using beam search.

    Keeps only top-k partial sequences at each step.
    """
    seq_len = emissions.shape[0]

    # Each beam entry: (score, path)
    beams = [(0.0, [])]

    for t in range(seq_len):
        candidates = []

        for score, path in beams:
            prev_tag = path[-1] if path else 0  # 0 for START

            for next_tag in range(num_tags):
                if t == 0:
                    trans_score = 0.0
                else:
                    trans_score = transitions[prev_tag, next_tag]

                emit_score = emissions[t, next_tag]
                new_score = score + trans_score + emit_score
                candidates.append((new_score, path + [next_tag]))

        # Keep top beam_width
        candidates.sort(reverse=True, key=lambda x: x[0])
        beams = candidates[:beam_width]

    return beams[0]  # Best sequence


# Compare beam search with different widths
emissions_np = emissions.detach().numpy()
transitions_np = crf_layer.transitions.detach().numpy()

Out[39]:

Console

Beam Search vs. Viterbi:
==================================================
Viterbi (exact):  path=[3, 3, 4, 3, 3, 3], score=-19989.8594
Beam width 1:     path=[1, 3, 4, 3, 3, 3], score=8.0399 ✗
Beam width 2:     path=[3, 3, 4, 3, 3, 3], score=9.3341 ✓
Beam width 3:     path=[3, 3, 4, 3, 3, 3], score=9.3341 ✓
Beam width 5:     path=[3, 3, 4, 3, 3, 3], score=9.3341 ✓

Beam search with width 1 is greedy decoding. As beam width increases, accuracy approaches Viterbi but with reduced computational cost for very long sequences or many labels.