Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Viterbi Algorithm › Log-Space Computation

Michael BrenndoerferUpdated April 28, 20255 min read

Language AI HandbookAll chapters

Part 6 of 67Sequence Labeling

Chapter 41Viterbi Algorithm › Log-Space Computation

Reading section 5 of 12 · Log-Space Computation · 5 minSection 5 of 12 · 5 min

Section 5 of 12 · 5 min read

Viterbi Algorithm › Log-Space ComputationOne section · Sections in this chapter5 / 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

Multiplying many small probabilities causes numerical underflow. For a sequence of 100 tokens with probabilities around 0.01, the path probability would be approximately $0.01^{100} = 10^{-200}$ , far below the smallest representable floating-point number (approximately $10^{-308}$ for 64-bit floats).

The solution is to work in log space. The logarithm function has a useful property: it converts products into sums. Since $\log(ab) = \log(a) + \log(b)$ , we can rewrite the Viterbi recurrence entirely in terms of log probabilities:

\log V_i(s) = \max_{s'} \left[ \log V_{i-1}(s') + \log P(s | s') + \log P(w_i | s) \right]

where:

$\log V_i(s)$ : the log probability of the best path ending at state $s$ at position $i$
$\log V_{i-1}(s')$ : the log probability of the best path to predecessor state $s'$ (already computed)
$\log P(s | s')$ : the log transition probability from $s'$ to $s$
$\log P(w_i | s)$ : the log emission probability of word $w_i$ from state $s$

Log probabilities are negative since probabilities are between 0 and 1, and $\log(x) < 0$ when $x < 1$ . The best path has the highest (least negative) log probability. The $\max$ operation is unchanged because log is monotonic: if $a > b$ , then $\log(a) > \log(b)$ . This means finding the maximum log probability gives the same answer as finding the maximum probability.

In[12]:

Code

import math


def viterbi_log_space(observations, states, start_prob, trans_prob, emit_prob):
    """
    Viterbi algorithm in log space for numerical stability.
    """
    n = len(observations)

    # Convert to log probabilities
    def safe_log(p):
        return math.log(p) if p > 0 else float("-inf")

    log_start = {s: safe_log(p) for s, p in start_prob.items()}
    log_trans = {k: safe_log(p) for k, p in trans_prob.items()}
    log_emit = {k: safe_log(p) for k, p in emit_prob.items()}

    # Viterbi in log space
    V = [{} for _ in range(n)]
    backpointer = [{} for _ in range(n)]

    # Base case
    for s in states:
        emit = log_emit.get((s, observations[0]), float("-inf"))
        V[0][s] = log_start.get(s, float("-inf")) + emit
        backpointer[0][s] = None

    # Recursive case
    for i in range(1, n):
        for s in states:
            best_prev = None
            best_score = float("-inf")

            emit = log_emit.get((s, observations[i]), float("-inf"))

            for s_prev in states:
                trans = log_trans.get((s_prev, s), float("-inf"))
                score = V[i - 1][s_prev] + trans + emit

                if score > best_score:
                    best_score = score
                    best_prev = s_prev

            V[i][s] = best_score
            backpointer[i][s] = best_prev

    # Find best final state
    best_final = max(states, key=lambda s: V[n - 1][s])
    best_log_prob = V[n - 1][best_final]

    # Backtrack
    path = [best_final]
    current = best_final
    for i in range(n - 1, 0, -1):
        current = backpointer[i][current]
        path.append(current)

    path.reverse()
    return path, best_log_prob


# Compare probability space vs log space
path_log, log_prob = viterbi_log_space(
    observations, states, start_prob, trans_prob, emit_prob
)

Out[13]:

Console

Log-Space vs Probability-Space Computation
=======================================================

Optimal path (both methods): Sunny → Rainy → Rainy

Probability space: P = 0.012960
Log space: log(P) = -4.345888
Converted back: exp(log(P)) = 0.012960

For long sequences, probability space would underflow:

  Sequence length: 400
  Per-step probability: 0.1
  Probability space: 0.0 (underflow to 0)
  Log space: -921.03 (computable)

Both methods find the identical optimal path, confirming that log-space computation preserves correctness. The probability-space result (best_prob) and the exponentiated log-space result match to numerical precision. For the 400-token demonstration, probability space underflows to exactly zero while log space produces a meaningful value near -921. This is why all production Viterbi implementations work in log space.

Out[14]:

Visualization

Two line plots. Left shows probability decaying exponentially to zero. Right shows log probability decreasing linearly and remaining stable. — Path probability decay in probability space versus log space as sequence length increases. Left: with a per-step factor of 0.1, values reach the smallest normal float64 magnitude near length 308, then enter the subnormal range before underflowing to zero. The gray dashed horizontal line marks the normal-range limit and the coral dotted vertical line marks the corresponding sequence length. Right: log-space values remain computationally stable and decrease linearly.

The visualization makes the underflow problem concrete. With a typical per-step probability of 0.1, probability-space values reach the smallest normal float64 magnitude around sequence length 308, enter the narrow subnormal range, and then underflow to zero. Log-space values, in contrast, decrease linearly and remain perfectly representable regardless of sequence length. Even a 1000-word document produces a log probability around -2300, large in magnitude but entirely computable.

Log-space computation is essential for practical implementations. The algorithm produces identical paths but with stable numerics.