Bridges: DSA to LLMs

Dynamic programming to Viterbi and edit distance

The same table, decoding sequences

~12 minLesson 38 of 57Written by Claude Opus 4.8

The same table you fill for edit distance decodes the most probable hidden path in a model - Viterbi is dynamic programming wearing a probability costume.

In Dynamic programming you learned dynamic programming as one move: fill a table so every cell reuses answers you already computed, and an exponential search collapses into a polynomial sweep. That exact table is the engine under two workhorses of pre-transformer language technology. Viterbi decoding finds the single most probable sequence of hidden states - the backbone of part-of-speech tagging, speech recognition, and gene finding. Edit distance measures how many single-character changes separate two strings, and the same table aligns and segments sequences inside modern tokenizers. Both are one idea in two costumes: a grid of subproblem answers, each cell a small local cost plus the best neighbour. This lesson makes that click - and shows why the greedy shortcut you might reach for first quietly returns the wrong answer.

The one-line idea

A DP table is a contract: solve each subproblem once, write it down, never redo it. Viterbi signs that contract for the question "what is the best path through a lattice of hidden states?" Every cell asks one small question - "cheapest way to arrive here?" - and answers it by reusing the column to its left. Fill left to right, then walk the winners backwards, and the best global path falls out.

What makes a table legal

Two properties, both from dynamic programming, license a DP table. Optimal substructure: the best whole answer is built from best sub-answers - so once a cell holds the best way to reach a state, you can trust it forever. Overlapping subproblems: the same sub-question recurs, so caching it pays. Viterbi has both. The best path to state $s$ at time $t$ must extend a best path to some state at time $t - 1$ (substructure), and every later cell reuses those same $t - 1$ answers (overlap). That is the whole justification for filling a grid instead of enumerating every path - of which there are $N^{T}$ , exponential in the length of the sequence.

Viterbi: the most probable hidden path

Set the scene with a : states you cannot see (today's weather), observations you can (ice-cream scoops eaten). Two knobs govern it - an emission distribution (how likely each state is to produce each observation) and a transition distribution (how likely one state follows another). Viterbi asks for the single most probable state sequence given the observations. Define the cell as a running cost:

C_{t} (s) = today’s emission e_{s} (o_{t}) + s^{'} min (C_{t - 1} (s^{'}) + switch cost τ_{s^{'} s}), C_{1} (s) = π_{s} + e_{s} (o_{1}) .

Everything is a cost in : $e_{s} (o) = - lo g_{2} b_{s} (o)$ turns an emission probability into a cost, $τ_{s^{'} s} = - lo g_{2} a_{s^{'} s}$ does the same for a transition, and $π_{s}$ is the start cost. Because $- lo g$ turns products into sums, minimising total cost is exactly maximising the path's probability. Alongside each cell store a backpointer $bp_{t} (s) = ar g min_{s^{'}} (C_{t - 1} (s^{'}) + τ_{s^{'} s})$ - the predecessor it chose. Notice the shape: a cell is one local cost plus the best of a few predecessors. That is the edit-distance recurrence too; "min over three neighbours" simply becomes "min over $N$ predecessors."

Below, the hidden states are Hot and Cold; you observe three days of ice-cream counts - 3, 1, 3. Hot explains a big-scoop day cheaply, Cold explains a single-scoop day cheaply, and the weather is sticky: switching states costs 3 bits while staying costs nothing. Step through each cell - it reaches back to both states of the previous day, keeps the cheaper arrival, and adds today's emission. When the grid is full, the cheapest final cell and its backpointers spell out the most probable week. Then flip on the greedy path and watch the shortcut fail.

Viterbi trellis - best hidden path (fill each cell · trace back · greedy vs DP)

current cellcandidate predecessorViterbi optimal pathgreedy myopic path

1emit +1

2emit +2

·emit +2

·emit +1

·emit +2

Base case: day 1 has no predecessor, so each start cell is just start cost (0) plus that day's emission. Hot explains 3 scoops for 1 bit; Cold needs 2.

Day 1 - nothing precedes it. Each start cell = start cost (0) + that state's emission.

☀ Hot : C[1][Hot] = 0 + emit(Hot, 3 scoops) = 1

❄ Cold : C[1][Cold] = 0 + emit(Cold, 3 scoops) = 2

Hot is the cheaper explanation of a big-scoop day.

Rows are the hidden weather states; columns are three observed days. Each cell is the cheapest cost to arrive in that state, in surprisal bits (lower = more probable). Costs are −log₂ probability, so summing costs multiplies probabilities.

The aha: the trellis is the DP table, and the arrows are the recurrence

Greedy reads each day in isolation and shouts "Cold!" on the single-scoop day - a locally perfect call that then forces two expensive weather-switches, costing 9 bits. Viterbi refuses to commit early: it keeps every state's best-so-far and only decides at the very end, discovering that staying Hot all week - a slightly worse fit on day 2 - is globally cheapest at 4 bits. That is the DP-vs-greedy lesson in one picture: a locally optimal choice can be globally wrong, and the fix is to remember every partial answer instead of gambling on the best-looking one right now.

One skeleton, many algorithms

Swap the words and the same table reappears. Edit distance takes the min over three neighbours - delete, insert, substitute - instead of $N$ predecessors, but a cell is still a local cost plus the best neighbour. Tokenizers that must find the single best way to cut a word into known subword pieces run Viterbi over character positions (that is exactly Unigram/WordPiece segmentation). Even the greedy cousin shows up honestly: BPE builds its vocabulary greedily, merging the most frequent adjacent pair over and over - fast, but with no promise of a globally optimal split, precisely the trade-off the demo just made visible. Here is Viterbi itself, in the cost form the trellis animates - $O (T N^{2})$ time, $O (T N)$ space because you keep the whole grid to trace back:

def viterbi(obs, start, emit, trans):        # costs = -log2 prob, so min cost = max probability
    T, N = len(obs), len(start)
    C    = [[0.0] * N for _ in range(T)]    # C[t][s] = cheapest cost to reach state s at time t
    back = [[0]   * N for _ in range(T)]    # backpointer: which predecessor each cell chose

    for s in range(N):                        # base case: start cost + first emission
        C[0][s] = start[s] + emit[0][s]

    for t in range(1, T):
        for s in range(N):                    # each cell reuses column t-1 only
            p = min(range(N), key=lambda q: C[t-1][q] + trans[q][s])
            back[t][s] = p
            C[t][s] = emit[t][s] + C[t-1][p] + trans[p][s]

    last = min(range(N), key=lambda s: C[T-1][s])   # cheapest final state
    path = [last]
    for t in range(T-1, 0, -1):               # walk the backpointers leftwards
        path.append(back[t][path[-1]])
    return path[::-1], C[T-1][last]           # O(T*N^2) time, O(T*N) space

emit  = [[1,2], [2,1], [1,2]]    # rows = days, cols = [Hot, Cold] surprisal
trans = [[0,3], [3,0]]            # stay = 0 bits, switch = 3 bits
viterbi([3,1,3], [0,0], emit, trans)           # -> ([0, 0, 0], 4)  =  Hot, Hot, Hot

Viterbi - cost form (min = most probable)

Why the grid beats brute force

A sequence of length

T

over

N

hidden states has

N^{T}

possible paths - checking each is hopeless. The trellis has only

T N

cells, and filling one cell costs

O (N)

(a min over

N

predecessors), so Viterbi runs in

O (T N^{2})

: for our toy

N = 2, T = 3

that is a dozen additions instead of

2^{3}

full paths, and for a 20-word sentence with 45 POS tags it is the difference between

1 0^{33}

paths and a few thousand cell updates. Space is

O (T N)

if you keep the whole grid - and you must, because the backpointers you trace for the answer live in those cells.

Check yourself

Greedy tags each day by its lowest-cost emission alone. Viterbi beats it because it also weighs:

To fill one Viterbi cell in column t, the recurrence reads only:

State the Viterbi recurrence (cost form), its base case, the backpointer, and its running time.

Nail down the recurrence and its cost. Try to state it, then check.

Lock it in

Viterbi decoding is dynamic programming: a trellis where each cell holds the cheapest cost to reach a hidden state, reusing only the previous column.
Working in surprisal costs ( $- lo g_{2} p$ ) turns products into sums, so minimizing total cost is exactly maximizing path probability.
Backpointers stored per cell let you trace the single most probable path backwards from the cheapest final state.
The grid runs in $O (T N^{2})$ instead of enumerating $N^{T}$ paths; edit distance and subword segmentation are the same recurrence, and greedy shortcuts can be globally wrong.

Primary source

For the DP mindset built from scratch - recurrences, memoization, tabulation, and worked table-filling - watch Abdul Bari's Dynamic Programming playlist. For Viterbi decoding treated rigorously - the HMM, the trellis, the backpointer, and the greedy-vs-optimal argument - read the Viterbi sections of Jurafsky & Martin, Speech and Language Processing (the appendix on HMMs and the sequence-labeling chapters).

Ask your teacher

The DP you learned earlier is the classical-NLP counterpart to attention: before transformers, Viterbi and edit distance were how machines aligned and decoded sequences - a hard table of best-path subproblems where attention now uses a soft, learned matrix of weights. Ask me how a transformer's greedy vs beam decoding echoes today's greedy-vs-Viterbi split, why softmax over paths (the forward algorithm) is the "sum" twin of Viterbi's "max," or how the backpointer here is the same bookkeeping as tracing an alignment out of an attention map.