Dynamic Programming Inference

Finding the best label sequence looks like it needs checking every sequence, and there are exponentially many. It does not, because the sequences share their beginnings: once you know the best way to reach a given state at a given position, every sequence passing through it reuses that answer. Filling a table of those answers is the whole idea, and it is what made structured prediction tractable decades before anything was learned.

Two algorithms on the same table. Viterbi keeps the best score reaching each cell and recovers the single best sequence; the forward algorithm sums instead of maximising, giving the total probability of all sequences — which is what a CRF needs to normalise and what CTC uses to sum over every alignment consistent with a transcript. Same table, one operator different, two entirely different questions answered.

The table has one cell per position per state, and filling each cell looks at every state at the previous position, so the cost is the sequence length times the square of the state count. That replaces an exponential in the length with something linear in it — the exponential does not become large, it stops existing, because the shared prefixes were never enumerated separately in the first place.