Chapter 36 · Section 36.2 · 80 min

Connectionist temporal classification

Connectionist temporal classification, or CTC, is a way to train a speech recognizer on audio paired with nothing but its transcript (Graves et al. 2006). The recognizer reads the audio as a sequence of short frames and makes a guess at every frame. The training data says that the whole clip reads "hello". It never says which frames are the "h". CTC adds up the probability of every way the frames could spell "hello", and it computes that sum exactly and fast.

Here is the idea in four steps, before any symbols. Add one extra symbol, the blank, which means "no new letter here". Let every frame emit either a letter or the blank. To read the text off the frames, merge each run of repeated symbols into one and then delete the blanks. The probability of a transcript is the total probability of all the frame-by-frame strings that read as it.

Not knowing which frames go with which label is the central problem of speech recognition, as §36.1 showed. An encoder network turns a clip into $T$ frames. The transcript has $U$ labels, far fewer. Even without any extra symbol, cutting the $T$ frames into $U$ consecutive pieces, one per label, can be done in $\binom{T-1}{U-1}$ ways, about $1.35\times10^{18}$ for 300 frames and 11 words. The classical recognizer handled this with hidden Markov models, a pronunciation dictionary, and frame labels bootstrapped from an older recognizer. CTC needs none of that. It is why you can fine-tune a pretrained speech encoder with one linear layer and a list of transcripts, and it still powers some of the fastest recognizers on the 2026 leaderboards.

This section builds CTC from the ground up. We define the blank and the collapsing rule, count the alignments, and derive the forward algorithm that sums them in $O(TU)$ time. We derive the gradient, implement both in log space, and check them against brute force and against PyTorch. Then we find how many frames a transcript needs, see why trained models put the blank on almost every frame, decode with greedy search and prefix beam search, and align words to time. We end with what CTC achieves at scale and the one assumption that limits it. The transducer of §36.3 removes that assumption by adding a small network that reads the labels already written.

Why we cannot just label the frames

An encoder is the network that reads the audio features and outputs one vector per frame. A linear layer turns each vector into logits, one score per symbol, and a softmax turns the scores into probabilities. Write $\mathbf p_t$ for that distribution at frame $t$ , for $t = 1,\dots,T$ , and $p_t(k)$ for its entry for symbol $k$ . It is called a posterior, because it is the model's probability of each symbol after seeing the audio.

The frames here are encoder frames, not feature frames. The encoder starts by subsampling, merging several 10 ms feature frames into one (§36.1). So an encoder frame lasts $\Delta_{\text{enc}} = 40$ ms with 4x subsampling and 80 ms with 8x.

If we knew the label of every frame, training would be ordinary classification. Each frame would get a cross-entropy loss. Its gradient with respect to the logits is $\mathbf p_t - \mathbf e_{y}$ , the predicted distribution minus the one-hot vector of the frame's target label $y$ (§0.2).

The naive fix is to invent the frame labels. Stretch the transcript evenly over the frames, so that "hello" in 20 frames gives each letter 4 frames. Real speech does not cooperate. Vowels last longer than stops. A speaker pauses before one word and rushes through the next. The clip starts and ends in silence. An evenly stretched target tells the network that silence is "h" and that the middle of the "e" is "l", and the network learns those mistakes.

The classical answer was a loop (§36.1). Estimate the frame labels with a hidden Markov model, train on them, realign with the better model, and repeat. That loop needs a working recognizer before it can train one.

CTC does not pick one labeling at all. It treats the frame labels as hidden, gives every frame labeling that fits the transcript its probability under the model, and maximizes the total. Two things make this work. Frames must be allowed to carry no label, since most frames are silence or a transition between sounds. And the sum over labelings must be computed without listing them.

A blank symbol and a collapsing rule

Add a symbol $\varnothing$ , the blank, to the vocabulary. A frame-level path is a string of $T$ symbols, one per frame. For 10 frames, one path is

\texttt{h h}\ \varnothing\ \texttt{e}\ \varnothing\ \texttt{l l}\ \varnothing\ \texttt{l o}.

To read off the transcript, first merge each run of identical symbols into one. That gives $\texttt{h}\ \varnothing\ \texttt{e}\ \varnothing\ \texttt{l}\ \varnothing\ \texttt{l o}$ . Then delete the blanks. That gives "hello".

The blank does two jobs.

Frames with nothing to say. Silence, breaths, and the transitions between sounds belong to no letter. The blank absorbs them, so a letter only has to claim the frames where the model is confident it is there.
Repeated letters. Without a blank, "ll" on two frames would merge into one "l", and no path could ever spell "hello". With the blank, $\texttt{l}\ \varnothing\ \texttt{l}$ keeps two copies apart, while $\texttt{l l}$ is still one "l" that lasts two frames.

The order of the two steps matters. Deleting blanks first would turn $\texttt{l}\ \varnothing\ \texttt{l}$ into $\texttt{l l}$ , which then merges into one "l". Merging first is what lets the blank separate repeats.

📐 Blank, alignments, and the collapse map

Let $\mathcal V$ be the label vocabulary, of size $V$ , and $\bar{\mathcal V} = \mathcal V\cup\{\varnothing\}$ the extended vocabulary of size $V+1$ , where $\varnothing$ is the blank. For $T$ frames, an alignment (or path) is a sequence $\mathbf a = (a_1,\dots,a_T)\in\bar{\mathcal V}^T$ . The collapse map $\mathcal B : \bar{\mathcal V}^T\to\bigcup_{U\ge0}\mathcal V^U$ first merges each maximal run of identical consecutive symbols into a single symbol, then deletes every $\varnothing$ . For a transcript $\mathbf y = (y_1,\dots,y_U)\in\mathcal V^U$ , the set of its alignments is

\mathcal B^{-1}(\mathbf y) = \{\mathbf a\in\bar{\mathcal V}^T : \mathcal B(\mathbf a) = \mathbf y\}.

In plain words, an alignment says what each frame emits, and the collapse map turns it into the text it spells. Many alignments spell the same text, and $\mathcal B^{-1}(\mathbf y)$ collects all of them.

Warm-up

The collapse map

Write ctc_collapse(path, blank=0), the collapse map $\mathcal B$ . The input is a sequence of integer symbols, as a list or a NumPy array. Merge each run of equal symbols into one, then drop the blanks, and return the result as a tuple of plain Python ints. The blank is the symbol blank, which need not be 0.

def ctc_collapse(path, blank=0):
    raise NotImplementedError

Tests, verified solutions, and AI help, open once you add your API key.

The probability of a transcript is a sum over its alignments

The network's job is now to give a distribution over $\bar{\mathcal V}$ at every frame. CTC makes one modeling assumption, and it is the one to remember. Once the audio is fixed, the symbol emitted at each frame is drawn independently of the symbols at the other frames. So a path's probability is a product of one softmax entry per frame.

📐 The CTC model and loss

Let $\mathbf X$ be the input features and let the encoder produce logits $\mathbf z_t\in\R^{V+1}$ for $t = 1,\dots,T$ , with $p_t(k) = \operatorname{softmax}(\mathbf z_t)_k$ for $k\in\bar{\mathcal V}$ . CTC assumes that the symbols of an alignment are conditionally independent given $\mathbf X$ ,

p(\mathbf a\mid\mathbf X) = \prod_{t=1}^{T}p_t(a_t),

and defines the probability of a transcript as the total probability of its alignments, and the loss as its negative log,

p_{\text{CTC}}(\mathbf y\mid\mathbf X) = \sum_{\mathbf a\in\mathcal B^{-1}(\mathbf y)}\ \prod_{t=1}^{T}p_t(a_t), \qquad \mathcal L_{\text{CTC}} = -\log p_{\text{CTC}}(\mathbf y\mid\mathbf X).

In plain words, the probability of "hello" is the probability that the frames spell "hello" in any of the ways frames can spell it. Each way's probability is a product of one softmax entry per frame.

Conditional independence does not mean the frames ignore each other. The encoder is usually a Conformer, a stack of attention and convolution layers (§36.1), or a Transformer, and it reads the whole clip. So $\mathbf p_t$ depends on all of $\mathbf X$ . What the assumption says is narrower. Once $\mathbf X$ is fixed, what frame $t$ emits tells you nothing more about what frame $t+1$ emits. The model cannot reason "I wrote 'q' a moment ago, so 'u' is likely now" except through the sound itself. This is why CTC leans on external language models. An interviewer who asks "what does CTC assume?" wants this answer.

The sum also changes what decoding means. The most probable transcript is not always the transcript of the most probable path. The smallest possible example shows it.

The cell checks the collapse map and this example. It lists every path of a slightly bigger problem, three frames over $\{\varnothing, \texttt a, \texttt b\}$ , and groups the paths by the transcript they spell.

Python · cell 1

"ab" has five alignments in three frames, $\texttt{ab}\varnothing$ , $\texttt a\varnothing\texttt b$ , $\varnothing\texttt{ab}$ , $\texttt{aab}$ , and $\texttt{abb}$ . "aa" has exactly one, $\texttt a\varnothing\texttt a$ , because the two copies must be kept apart by a blank.

Here is the same model at the size of a real recognizer. Everything CTC touches is one table of log-probabilities, one row per encoder frame.

✏️ One clip through a CTC recognizer

Take a 10-second clip from LibriSpeech, a standard benchmark of read audiobooks. Run it through a FastConformer Large, an encoder of width 512 that subsamples by 8 (Rekesh et al. 2023). For LibriSpeech its authors trained the CTC version with 128 subword tokens.

The log-mel front end of §35.3 gives 1,000 feature frames of 80 numbers, one every 10 ms.
Three stride-2 convolutions shorten them to 500, 250, and then $T = 125$ encoder frames. The encoder outputs 125 vectors of 512 numbers, one every 80 ms.
The CTC head is one linear layer from 512 numbers to $V+1 = 129$ logits, the 128 tokens plus the blank. It has $512\times129 + 129 = 66{,}177$ parameters, about 0.06 percent of the 120 million the paper lists for its Large model.
A log-softmax turns the logits into a $125\times129$ table of $\log p_t(k)$ . The CTC loss reads only this table and the transcript's token ids.

A 10-second clip of fluent reading holds about 25 to 30 words, roughly 150 characters with spaces. CTC needs at least one frame per label, so 125 frames cannot hold 150 characters, and that is why this model writes subword tokens. The section on lengths below makes the condition exact.

The cell repeats the shape arithmetic with a random stand-in for the encoder output.

Python · cell 2

How many alignments there are

In §36.1 an alignment of $U$ labels to $T$ frames was a cut into $U$ nonempty pieces, and there were $\binom{T-1}{U-1}$ of them. Blanks add many more. A run of blanks can sit before, between, or after the labels, and it can have any length, including zero. Counting the run lengths gives an exact formula.

∂ Proof of the count

An alignment of $\mathbf y$ consists of $U$ runs of labels, the $u$ -th of length $\ell_u\ge1$ and made of $y_u$ . They are interleaved with $U+1$ runs of blanks of lengths $b_0,\dots,b_U\ge0$ , before the first label, between labels, and after the last. Where $y_u = y_{u-1}$ , the blank run between them must have $b_{u-1}\ge1$ , or the two label runs would merge. Conversely, any such run lengths summing to $T$ give one alignment, and different run lengths give different alignments, since the runs are maximal. So we count the solutions of $\sum_u\ell_u + \sum_u b_u = T$ under these constraints.

Substitute $\ell_u' = \ell_u - 1\ge0$ for every label run and $b_u' = b_u - 1\ge0$ for the $R$ constrained blank runs. That leaves $2U+1$ nonnegative integers summing to $T - U - R$ . By stars and bars there are $\binom{(T-U-R) + 2U}{2U}$ solutions. ∎

Check it on the lists from the first cell. For "ab" in three frames, $U = 2$ , $R = 0$ , and $\binom{5}{4} = 5$ , the five paths we listed. For "aa", $R = 1$ and $\binom{4}{4} = 1$ . The cell checks the formula against brute force and then evaluates it for a real clip.

Python · cell 3

Three seconds of speech, 75 encoder frames and 26 characters, already has about $10^{29}$ alignments. Nobody will sum them one by one. We need structure that a dynamic program can exploit, and the next section finds it.

The forward algorithm adds up every alignment

Every alignment of $\mathbf y$ walks through the same skeleton, the transcript with a blank slot before, between, and after its labels. This is the blank-extended label sequence

\mathbf y' = (\varnothing, y_1, \varnothing, y_2, \varnothing, \dots, \varnothing, y_U, \varnothing),

of length $2U+1$ , indexed by $s = 1,\dots,2U+1$ . So $y'_{2u} = y_u$ and every odd position is a blank. For "ab", $\mathbf y' = (\varnothing, \texttt a, \varnothing, \texttt b, \varnothing)$ .

An alignment is a walk through $\mathbf y'$ , one position per frame. At frame $t$ the walk sits at some position $s$ and emits $y'_s$ . From one frame to the next it makes one of three moves.

Stay at $s$ . The symbol repeats, which the collapse merges.
Advance by one, from a blank to the next label or from a label to the following blank.
Skip by two, from a label straight to the next label, over the blank between them.

The skip is the only subtle move, and the two jobs of the blank decide when it is allowed. It is forbidden into a blank, because a jump from one blank slot to the next would pass over the label between them and drop it. It is also forbidden between equal labels, $y'_s = y'_{s-2}$ , because $\texttt a$ followed directly by $\texttt a$ merges into one $\texttt a$ . Between two equal labels the walk must pass through the blank.

Picture the walks on a grid called the trellis. Frames run along the horizontal axis and the $2U+1$ positions of $\mathbf y'$ run down the vertical axis. A valid walk starts in one of the first two rows (the leading blank or the first label). It moves right one column per frame and never moves up. It ends in one of the last two rows (the last label or the trailing blank).

The forward variable $\alpha_t(s)$ is the total probability of all partial walks over frames 1 to $t$ that are at position $s$ at frame $t$ ,

\alpha_t(s) = \sum_{\substack{\text{walks over frames } 1..t\\ \text{that are at position } s \text{ at frame } t}}\ \prod_{\tau=1}^{t}p_\tau(y'_{s_\tau}),

where $s_\tau$ is the walk's position at frame $\tau$ . It includes the emission at frame $t$ . The same kind of forward variable summed the ways to cut a word into tokens in §2.4 and the state paths of a hidden Markov model in §36.1. Here it runs on a new grid.

∴ The CTC forward algorithm

With $\mathbf y'$ as above and $\alpha$ including the emission at frame $t$ ,

\alpha_1(1) = p_1(\varnothing),\qquad \alpha_1(2) = p_1(y_1),\qquad \alpha_1(s) = 0\ \text{ for } s \gt 2,

and for $t = 2,\dots,T$ ,

\alpha_t(s) = p_t(y'_s)\Big[\alpha_{t-1}(s) + \alpha_{t-1}(s-1) + \mathbb 1[\text{skip}_s]\,\alpha_{t-1}(s-2)\Big], \qquad \text{skip}_s \iff y'_s\ne\varnothing \text{ and } y'_s\ne y'_{s-2},

with $\alpha_{t-1}(0) = \alpha_{t-1}(-1) = 0$ . The transcript probability is

p_{\text{CTC}}(\mathbf y\mid\mathbf X) = \alpha_T(2U+1) + \alpha_T(2U).

It costs $O(TU)$ time, and $O(U)$ memory if only the loss is needed. For $U = 0$ , $\mathbf y' = (\varnothing)$ and $p_{\text{CTC}} = \prod_tp_t(\varnothing)$ .

In plain words, the probability of reaching position $s$ at frame $t$ is this frame's probability of the symbol at $s$ , times the total probability of having been at one of the two or three places you can arrive from.

∂ Proof of the forward recursion

Every alignment in $\mathcal B^{-1}(\mathbf y)$ corresponds to exactly one walk through $\mathbf y'$ that starts at position 1 or 2, ends at position $2U$ or $2U+1$ , and moves by 0, 1, or 2 per frame under the skip rule.

In one direction, read the alignment's runs in order. Each label run sits at its even position $2u$ . Each blank run between labels $u$ and $u+1$ sits at the odd position $2u+1$ , a leading blank run at position 1, and a trailing one at $2U+1$ . A label run followed directly by the next label's run is a move of 2. The alignment can only do that when the two labels differ, since equal labels with no blank between them would merge, contradicting $\mathcal B(\mathbf a) = \mathbf y$ .

In the other direction, any such walk emits a sequence that collapses back to $\mathbf y$ . It visits every even position in order, stays on each label for one contiguous run, and separates equal neighbors by a blank. So the sum over alignments is a sum over walks.

Now fix $t\ge2$ and a position $s$ , and split the walks that are at $s$ at frame $t$ by where they were at frame $t-1$ . The allowed predecessors are $s$ (stay), $s-1$ (advance by one), and $s-2$ (skip, only when $\text{skip}_s$ holds). These sets of walks are disjoint and together contain every walk at $s$ at frame $t$ . A walk's probability is a product over frames, so the walks through predecessor $r$ contribute $\alpha_{t-1}(r)\,p_t(y'_s)$ . Adding the three cases gives the recursion.

At $t = 1$ a walk must start at position 1 or 2, which gives the initialization. At $t = T$ the walk must have reached the last label or the trailing blank, and those two sets are disjoint, so $p_{\text{CTC}}$ is the sum of the last two entries. Each of the $T$ columns costs $O(1)$ per position, $O(U)$ in all, and each column only needs the previous one. ∎

✏️ CTC by hand

Take $\mathbf y$ = "ab", so $\mathbf y' = (\varnothing, \texttt a, \varnothing, \texttt b, \varnothing)$ , and three frames with $(p_t(\varnothing), p_t(\texttt a), p_t(\texttt b))$ equal to $(0.2, 0.7, 0.1)$ , $(0.5, 0.2, 0.3)$ , and $(0.3, 0.1, 0.6)$ . The skip is allowed into $s = 4$ (since $\texttt b \ne \texttt a$ ) and nowhere else.

$s$	$y'_s$	$\alpha_1$	$\alpha_2$	$\alpha_3$
1	$\varnothing$	0.2	$0.5\times0.2 = 0.1$	$0.3\times0.1 = 0.03$
2	a	0.7	$0.2\times(0.7+0.2) = 0.18$	$0.1\times(0.18+0.1) = 0.028$
3	$\varnothing$	0	$0.5\times(0+0.7) = 0.35$	$0.3\times(0.35+0.18) = 0.159$
4	b	0	$0.3\times(0+0+0.7) = 0.21$	$0.6\times(0.21+0.35+0.18) = 0.444$
5	$\varnothing$	0	$0.5\times(0+0) = 0$	$0.3\times(0+0.21) = 0.063$

The answer is $\alpha_3(5) + \alpha_3(4) = 0.063 + 0.444 = 0.507$ . Listing the five alignments gives the same total, $\texttt{ab}\varnothing = 0.063$ , $\texttt a\varnothing\texttt b = 0.21$ , $\varnothing\texttt{ab} = 0.024$ , $\texttt{aab} = 0.084$ , and $\texttt{abb} = 0.126$ . The entry $\alpha_2(4) = 0.21$ comes entirely through the skip, the path $\texttt{ab}$ in two frames. Without the skip, "ab" would need three frames.

The cell runs the same recursion, written for clarity rather than speed, and checks it against enumeration.

Python · cell 4

The last line shows the problem with this version. A product of a thousand probabilities is far below the smallest positive float64, about $5\times10^{-324}$ , so it rounds to exactly zero. A 40-second clip at 40 ms per frame has a thousand frames, so this version fails on ordinary audio. The log-space version below fixes it.

The widget draws the trellis for a short word. With "sum over walks" each cell's shade is its occupancy, the share of $p_{\text{CTC}}$ carried by the walks through that cell, and a dashed cell is one that no walk can reach. With "best walk" it draws the single most likely walk, which we use for timestamps later in the section. The sharpness slider makes the synthetic frame posteriors flatter or more confident, and Sharpen sweeps it from 0 to 8, the way a model grows more confident as it trains.

In three frames "aa" has a single alignment, $\texttt a\varnothing\texttt a$ , so only its three cells are live and each carries all of $p_{\text{CTC}}$ . "hello" in five frames has no walk at all, so its loss is infinite, and the section on lengths below explains why. As Sharpen runs on "cat" in nine frames, the best walk's share climbs from under 2 percent to over 99 percent. That spiky picture, each letter on one frame and blanks everywhere else, is what a trained CTC model looks like, and the section on peaky outputs below shows where it comes from.

CTC is a hidden Markov model with a blank

A hidden Markov model (HMM) moves through hidden states one frame at a time and emits one frame from each state it visits (§36.1). Its forward algorithm is $\alpha_t(j) = b_j(\mathbf x_t)\sum_i\alpha_{t-1}(i)\,P_{ij}$ , where $P_{ij}$ is the probability of moving from state $i$ to state $j$ and $b_j(\mathbf x_t)$ is how likely state $j$ makes frame $\mathbf x_t$ . Read the $2U+1$ positions of $\mathbf y'$ as states and the three moves as transitions, and the CTC forward algorithm is this recursion with three changes. The two starting states, positions 1 and 2, each get initial weight 1. Every allowed transition weight $P_{ij}$ is 1. And the emission $b_j(\mathbf x_t)$ is replaced by the network's posterior $p_t(y'_j)$ .

📌 CTC is an HMM with a blank

For a transcript $\mathbf y$ , CTC is a left-to-right HMM with $2U+1$ states, the positions of $\mathbf y'$ . Every state has a self-loop, so a label or a pause can last any number of frames. Each state may move to the next one, and a label may jump to the next label over the blank between them when the two labels differ. So the blank between different labels is optional and the blank between equal labels is compulsory. Over the frames, the alignments of $\mathbf y$ are exactly the strings that match

\varnothing^{*}\ y_1^{+}\ \varnothing^{*}\ y_2^{+}\ \cdots\ \varnothing^{*}\ y_U^{+}\ \varnothing^{*},

where $k^{*}$ means zero or more consecutive frames of $k$ and $k^{+}$ one or more, and $\varnothing^{*}$ becomes $\varnothing^{+}$ between two equal labels. Two things set it apart from the hybrid recognizer of §36.1, which put a network's posteriors inside an HMM. Nothing in the topology is learned, since every allowed transition has weight 1, so durations are left entirely to the network. And the emission score is the posterior $p_t(y'_s)$ itself. The hybrid divided its posteriors by how common each state is, its scaled likelihood, and CTC never does.

Working in log space

The fix for underflow is the one §0.4 gives for every likelihood. Store $\hat\alpha_t(s) = \log\alpha_t(s)$ . Add log-probabilities where the recursion multiplies probabilities. Combine the two or three incoming terms with a stable log-sum-exp, the log of a sum of exponentials computed without overflow, $\operatorname{LSE}(u, v) = \max(u, v) + \log\big(1 + e^{-|u - v|}\big)$ . Zero probability becomes $-\infty$ , which LSE handles, since $\operatorname{LSE}(-\infty, v) = v$ and $\operatorname{LSE}(-\infty, -\infty) = -\infty$ . The recursion becomes

\hat\alpha_t(s) = \log p_t(y'_s) + \operatorname{LSE}\big(\hat\alpha_{t-1}(s),\ \hat\alpha_{t-1}(s-1),\ \hat\alpha_{t-1}(s-2)\ \text{if skip}_s\big), \qquad \mathcal L_{\text{CTC}} = -\operatorname{LSE}\big(\hat\alpha_T(2U+1), \hat\alpha_T(2U)\big).

Each frame updates all $2U+1$ positions with a few vectorized operations, so the only Python loop is over $t$ . The network's output layer is already a log-softmax, so log-probabilities are what you are given anyway. Writing this loss from scratch is a common interview coding question.

Interview

The CTC loss in log space

Write ctc_loss(log_probs, y, blank=0), the CTC loss computed by the forward algorithm in log space.

log_probs has shape (T, V+1) and holds $\log p_t(k)$ . Each row is already log-softmaxed.
y is a list of $U$ label indices, none equal to blank.
Return $-\log p_{\text{CTC}}(\mathbf y\mid\mathbf X)$ as a float, or np.inf when no alignment exists.

Handle $U = 0$ , repeated labels, and any blank index. It must run $T = 1000$ with $U = 120$ in well under a second, so loop over frames only and vectorize over the $2U+1$ positions.

import numpy as np

def ctc_loss(log_probs, y, blank=0):
    # log_probs: (T, V+1) log-softmax outputs. y: labels, none equal to blank.
    raise NotImplementedError

Tests, verified solutions, and AI help, open once you add your API key.

The gradient is the prediction minus a soft target

Training needs $\partial\mathcal L_{\text{CTC}}/\partial z_t(k)$ for every frame and symbol. The answer has a simple shape. At each frame, the gradient is the model's prediction minus a soft target. The soft target is the model's own belief about what that frame emits, averaged over all the alignments of the transcript.

To compute that belief we run the same recursion backward. The backward variable $\beta_t(s)$ is the total probability of the partial walks over frames $t,\dots,T$ that are at position $s$ at frame $t$ and end at position $2U$ or $2U+1$ . Like $\alpha$ , it includes the emission at frame $t$ , which is the convention of Graves et al. (2006). Mirroring the forward argument,

\beta_T(2U+1) = p_T(\varnothing),\qquad \beta_T(2U) = p_T(y_U),\qquad \beta_t(s) = p_t(y'_s)\Big[\beta_{t+1}(s) + \beta_{t+1}(s+1) + \mathbb 1[\text{skip}_{s+2}]\,\beta_{t+1}(s+2)\Big],

where $\beta_T(s) = 0$ for $s \lt 2U$ , entries beyond $2U+1$ are zero, and $\text{skip}_{s+2}$ is the skip rule applied to the move from $s$ to $s+2$ .

A complete walk that is at position $s$ at frame $t$ splits into a part over frames $1..t$ and a part over frames $t..T$ . The two parts share frame $t$ . So $\alpha_t(s)\beta_t(s)$ counts the emission $p_t(y'_s)$ twice, and dividing once by it gives the total probability of the complete walks through $(t, s)$ . Every walk is at exactly one position at frame $t$ , so for every $t$ ,

\sum_{s=1}^{2U+1}\frac{\alpha_t(s)\,\beta_t(s)}{p_t(y'_s)} = p_{\text{CTC}}(\mathbf y\mid\mathbf X).

Dividing one term by $p_{\text{CTC}}$ gives the probability that the walk is at $(t, s)$ . Several positions carry the same symbol. All the odd ones are blanks, and a label that occurs twice in $\mathbf y$ has two positions. So we gather the positions by symbol.

∴ The CTC gradient

Define the occupancy of symbol $k\in\bar{\mathcal V}$ at frame $t$ ,

\gamma_t(k) = \frac{1}{p_{\text{CTC}}(\mathbf y\mid\mathbf X)}\sum_{s\,:\,y'_s = k}\frac{\alpha_t(s)\,\beta_t(s)}{p_t(k)},

the probability, under the model and given that the alignment spells $\mathbf y$ , that frame $t$ emits $k$ . Then $\gamma_t(k)\ge0$ , $\sum_k\gamma_t(k) = 1$ for every $t$ , and with $p_t = \operatorname{softmax}(\mathbf z_t)$ ,

\frac{\partial\mathcal L_{\text{CTC}}}{\partial z_t(k)} = p_t(k) - \gamma_t(k).

The derivative with respect to the log-probability $\log p_t(k)$ , treated as a free input, is $-\gamma_t(k)$ .

∂ Proof of the gradient

Fix a frame $t$ . Write $P = p_{\text{CTC}}(\mathbf y\mid\mathbf X)$ and, for each position $s$ , $\alpha_t(s) = p_t(y'_s)\,A_t(s)$ and $\beta_t(s) = p_t(y'_s)\,B_t(s)$ , where $A_t(s)$ and $B_t(s)$ collect the factors of the other frames only. By the identity above,

P = \sum_s p_t(y'_s)\,A_t(s)\,B_t(s) = \sum_{k}p_t(k)\sum_{s\,:\,y'_s = k}A_t(s)\,B_t(s).

So $P$ is linear in the numbers $p_t(k)$ , with coefficients that do not involve frame $t$ . Treat the $\log p_t(k)$ as free inputs. Then

\frac{\partial(-\log P)}{\partial\log p_t(k)} = -\frac{p_t(k)}{P}\,\frac{\partial P}{\partial p_t(k)} = -\frac{p_t(k)}{P}\sum_{s\,:\,y'_s = k}A_t(s)B_t(s) = -\frac1P\sum_{s\,:\,y'_s = k}\frac{\alpha_t(s)\beta_t(s)}{p_t(k)} = -\gamma_t(k).

Summing over $k$ and using the identity gives $\sum_k\gamma_t(k) = 1$ , and nonnegativity is clear. Now chain through the log-softmax, $\log p_t(j) = z_t(j) - \operatorname{LSE}(\mathbf z_t)$ , whose derivative is $\partial\log p_t(j)/\partial z_t(k) = \mathbb 1[j = k] - p_t(k)$ . The logits of frame $t$ affect only the log-probabilities of frame $t$ , so

\frac{\partial\mathcal L}{\partial z_t(k)} = \sum_j\big(-\gamma_t(j)\big)\big(\mathbb 1[j = k] - p_t(k)\big) = -\gamma_t(k) + p_t(k)\sum_j\gamma_t(j) = p_t(k) - \gamma_t(k). \qquad ∎

In plain words, the gradient at each frame is what the model predicts minus what its own alignment posterior says the frame should emit. It has exactly the shape of the softmax cross-entropy gradient $\mathbf p - \mathbf y$ of §0.2, with the one-hot target replaced by a soft target $\boldsymbol\gamma_t$ that the model computes for itself. The word2vec gradient of §1.5 had the same "expected minus observed" form.

This makes CTC training a gradual version of the classical recognizer's training loop, which guessed the frame labels with the current model and then retrained on the guess (§36.1). Here the forward-backward pass guesses where the labels are, as a soft distribution, and each gradient step moves the frame predictions a little toward that guess. The gradient vanishes when $\mathbf p_t = \boldsymbol\gamma_t$ at every frame, which makes it a stationary point of the loss.

✏️ The gradient by hand

In the three-frame "ab" example the occupancies over $(\varnothing, \texttt a, \texttt b)$ are $\boldsymbol\gamma_1 = (0.047, 0.953, 0)$ , $\boldsymbol\gamma_2 = (0.414, 0.213, 0.373)$ , and $\boldsymbol\gamma_3 = (0.124, 0, 0.876)$ . Check one. Frame 1 emits $\texttt a$ in every alignment except $\varnothing\texttt{ab}$ , so $\gamma_1(\texttt a) = (0.507 - 0.024)/0.507 = 0.953$ .

The logit gradient at frame 1 is $\mathbf p_1 - \boldsymbol\gamma_1 = (0.2 - 0.047,\ 0.7 - 0.953,\ 0.1 - 0) = (0.153, -0.253, 0.1)$ . Gradient descent raises the logit of $\texttt a$ and lowers the other two. The row sums to zero, as every softmax gradient does.

Core

The CTC gradient by forward-backward

Write ctc_grad(logits, y, blank=0), the gradient of the CTC loss with respect to the logits. The input logits holds the pre-softmax scores, shape (T, V+1), and the output has the same shape. Assume the pair is feasible.

Compute $\log\alpha$ and $\log\beta$ in log space, form the occupancies $\boldsymbol\gamma_t$ , and return $\mathbf p_t - \boldsymbol\gamma_t$ for every frame. The tests compare against central differences, check that every row sums to zero, and run $T = 800$ .

import numpy as np

def ctc_grad(logits, y, blank=0):
    # logits: (T, V+1) pre-softmax scores z_t. Return dL/dz, shape (T, V+1).
    raise NotImplementedError

Tests, verified solutions, and AI help, open once you add your API key.

From here on the section's cells use one reference implementation of the loss and the gradient. The cell checks the identity $\sum_s\alpha_t(s)\beta_t(s)/p_t(y'_s) = p_{\text{CTC}}$ at every frame of a long random problem, and the gradient against central differences on a small one.

Python · cell 5

The spread of $\log P$ across the 400 frames is about $10^{-12}$ , rounding error, and the analytic gradient matches the numeric one to about $10^{-10}$ . Every row of the gradient sums to zero.

CTC in PyTorch

torch.nn.functional.ctc_loss implements exactly this loss. Its interface has four details that trip people up.

The log-probabilities are laid out as (T, N, C) by default, time first, or (T, C) for one clip. Here $N$ is the batch size and $C = V + 1$ the number of symbols.
The blank is index 0 by default.
The default reduction="mean" divides each clip's loss by its target length and then averages over the batch. So each label of a short transcript weighs more than each label of a long one. For comparisons use reduction="sum" or "none".
A clip with no possible alignment gives $+\infty$ . The flag zero_infinity=True replaces it by zero, with a zero gradient.

The block below writes the forward recursion in torch, lets autograd differentiate it, and compares the loss and the logit gradient with the built-in. It also checks the reductions, the infeasible case, and a quirk of the built-in's backward pass that the pitfall after it explains.

🔥 In PyTorchfor a machine with PyTorch

The finite stand-in for $-\infty$ in ctc_nll is deliberate. torch.logsumexp of a vector that is entirely $-\infty$ returns $-\infty$ but has an undefined gradient, so a literal $-\infty$ in unreachable cells puts NaN into the backward pass.

Training runs on batches. Clips of different lengths are padded to a common $T$ , transcripts are padded to a common length, and length arrays tell the loss which frames and labels are real. Most of the interface pitfalls above live here, so it is worth writing the batched loss once yourself.

Interview

Batched CTC loss over padded inputs

Write ctc_loss_batched(log_probs, targets, input_lengths, target_lengths, blank=0, reduction="mean"). It must behave like F.ctc_loss.

log_probs has shape (T, N, C), time first. It holds log-softmax outputs for $N$ clips padded to $T$ frames. Clip $n$ uses only its first input_lengths[n] frames, at least 1.
targets has shape (N, S). Clip $n$ uses only its first target_lengths[n] entries, none equal to blank. The padding after them can hold any integer.
With reduction="none" return the array of the $N$ losses $-\log p_{\text{CTC}}$ , with np.inf for an infeasible clip. With "sum" return their sum. With "mean" divide each loss by its target length (by 1 when that length is 0) and then average over the batch.

Loop over frames only, vectorizing over both the batch and the $2S+1$ positions.

import numpy as np

def ctc_loss_batched(log_probs, targets, input_lengths, target_lengths, blank=0, reduction="mean"):
    # log_probs: (T, N, C) log-softmax outputs, time first. targets: (N, S), padded.
    raise NotImplementedError

Tests, verified solutions, and AI help, open once you add your API key.

How many frames a transcript needs

The last line of the torch block returned infinity. "hello" has five letters and got five frames, so why is there no alignment? The two l's need a blank between them, and that blank needs a frame of its own. So "hello" needs six frames.

In plain words, every label needs a frame of its own, and every adjacent repeat needs one more frame for the blank that keeps its two copies apart. The proof shows that this count is both necessary and enough.

∂ Proof of the length condition

Suppose an alignment of $\mathbf y$ exists. It has at least one frame for each of the $U$ labels. For each of the $R$ adjacent repeats it also has at least one blank frame between the two copies, or they would merge. These $U + R$ frames are distinct, so $T\ge U+R$ .

Conversely, suppose $T\ge U+R$ . Take the path that writes $y_1$ , then for each $u\ge2$ writes a blank if $y_u = y_{u-1}$ followed by $y_u$ , and then $T - U - R$ trailing blanks. It has length $T$ , collapses to $\mathbf y$ , and its probability is a product of positive numbers. ∎

The same condition is where the count $\binom{T+U-R}{2U}$ of the counting theorem becomes zero.

The rule gives the minimum length at a glance. "hello" needs $5 + 1 = 6$ frames, as we found. "book" has $U = 4$ and one repeat ("oo"), so it needs 5. "aaa" has $U = 3$ and two repeats, so it also needs 5, and the only path that fits in 5 frames is $\texttt a\varnothing\texttt a\varnothing\texttt a$ .

The condition ties a CTC model's frame rate to its vocabulary. A frame lasts $\Delta_{\text{enc}}$ , so a CTC model can emit at most $1/\Delta_{\text{enc}}$ labels per second. That is 25 per second at 40 ms and 12.5 at 80 ms, and fewer when labels repeat. Fluent speech runs at about 15 characters per second, spaces included, and fast speech runs faster. So 80 ms frames are too coarse for characters.

This is what happened to the 10-second clip earlier, and to FastConformer as a whole. The encoder subsamples 8x, to 80 ms frames, to cut the cost of attention (Rekesh et al. 2023). Its authors found that with a character vocabulary most LibriSpeech training samples no longer met the condition. So they switched their CTC models to subword vocabularies of 128 to 1,024 tokens, learned with the SentencePiece tool, each covering one or more characters (§2.2 and §2.4 build such vocabularies). The transducer of §36.3 has no such constraint, because it can emit several labels on one frame.

Two practical rules follow. First, filter or fix the pairs of long transcript and short audio in a training set before CTC training. One infinite loss makes the batch loss infinite and the gradient NaN, and zero_infinity=True only hides such a pair from the gradient. Second, when you design a recognizer, choose the subsampling factor and the token vocabulary together, and check the condition on the fastest clips in the training data. Interviewers like this question because it connects the loss to a design decision.

Why trained CTC models are peaky

Look at the frame posteriors of any trained CTC model and you see the same picture. The blank has probability close to one on almost every frame. Each label appears as a sharp spike one or two frames wide, even when its sound lasts ten frames. Figure 1 of Graves et al. (2006) shows a trained network's outputs as such spikes separated by blanks, and their Figure 4 shows the spikes forming during training. The loss does not ask for this. Any alignment would do, including one in which every label holds all its frames. So why does training pick the spikes?

Start at the beginning of training. If the logits are all equal, then $p_t(k) = 1/(V+1)$ for every frame and symbol, and every alignment has the same probability $(V+1)^{-T}$ . The occupancy is then a pure count that does not depend on the audio,

\gamma_t(k) = \frac{\big|\{\mathbf a\in\mathcal B^{-1}(\mathbf y) : a_t = k\}\big|}{\big|\mathcal B^{-1}(\mathbf y)\big|},

the fraction of alignments that put $k$ at frame $t$ . Blanks fill all the frames the labels do not need. So most alignments put a blank at most frames, and the blank is the most common symbol.

∂ Proof of the one-label occupancy

An alignment is fixed by the first and last frames of its $\texttt a$ run, $1\le f\le l\le T$ , so there are $T(T+1)/2$ of them. Frame $t$ is inside the run when $f\le t\le l$ , which happens for $t$ choices of $f$ and $T-t+1$ choices of $l$ . Summing, $\sum_t t(T-t+1) = T(T+1)(T+2)/6$ . So the average label share is $(T+2)/(3T)$ and the blank share is $1 - (T+2)/(3T) = 2(T-1)/(3T)$ . ∎

Now follow the first gradient step. The gradient is $\mathbf p_t - \boldsymbol\gamma_t$ with $p_t(\varnothing) = 1/(V+1)$ . So gradient descent raises the blank's logit at every frame where $\gamma_t(\varnothing) \gt 1/(V+1)$ . With a real vocabulary $1/(V+1)$ is tiny, so when the clip has frames to spare that is every frame.

Then a feedback loop starts. A path's probability is a product over frames, so a higher blank probability everywhere makes the paths with many blank frames more probable than those with long label runs. The occupancy shifts further toward the blank, and the next step raises it again. Each label keeps only the frames where it is needed most and ends up firing on one or two of them. Zeyer et al. (2021) prove that for a simple model trained from a uniform start, gradient descent converges toward such peaky solutions.

Python · cell 6

At the start the blank's occupancy is between 0.45 and 0.82 at every frame, far above its probability of 0.25, so the first steps push the blank up everywhere. By step 10 the blank is the most probable symbol at all 30 frames, and the loss has fallen from 27.7 to 4.3. Only then do the labels claim frames, and they claim as few as they can. At step 300 each label holds two frames and the other 24 frames, 80 percent of them, are blank.

🔬 A label prior that removes the peaks

Zeyer et al. (2021) also show that a variant of the loss with a label prior does not become peaky. It divides each frame's posterior by a prior over the symbols,

\mathcal L_{\text{prior}} = -\log\sum_{\mathbf a\in\mathcal B^{-1}(\mathbf y)}\ \prod_{t=1}^{T}\frac{p_t(a_t)}{P(a_t)}, \qquad P(k) = \frac1T\sum_{t=1}^{T}p_t(k),

where the prior $P(k)$ is the model's own average posterior over the frames. In a stable recipe it is averaged over the whole training set and held fixed while the network updates. They note that a prior learned as free parameters of its own, or estimated badly, can instead reinforce the peaks or let a different label dominate.

This is the hybrid scaled likelihood of §36.1, posterior over prior, the step the HMM view above showed CTC leaves out. A large prior on the blank discounts it, the way the hybrid's priors discounted silence, so the blank no longer wins frames merely by being common. If you build this loss on F.ctc_loss, remember the gradient pitfall of the PyTorch section, since log-probabilities minus a log prior no longer come straight from a log_softmax.

The research exercise below makes the counting argument exact at real scale, where the counts no longer fit in a float.

Research

Why CTC gets peaky, from counts

At a uniform start every alignment of $\mathbf y$ has the same probability. So $\gamma_t(\varnothing)$ is the fraction of alignments with a blank at frame $t$ , whatever $V$ is. Write two functions, with labels as positive ints and the blank as 0. Assume $T \ge U + R(\mathbf y)$ , so that at least one alignment exists.

uniform_blank_occupancy(T, y) returns the array of $\gamma_t(\varnothing)$ for $t = 1,\dots,T$ , of shape (T,).
first_step_blank_frames(T, y, V) returns the number of frames at which the first gradient step from uniform logits raises $p_t(\varnothing)$ .

The tests check the first function against the closed form for one label, against brute-force counting with repeated labels, and at $T = 3000$ with $U = 150$ , where there are about $10^{428}$ alignments.

import numpy as np

def uniform_blank_occupancy(T, y):
    # Return gamma_t(blank) for t = 1..T, shape (T,), when every p_t is uniform.
    raise NotImplementedError

def first_step_blank_frames(T, y, V):
    raise NotImplementedError

Tests, verified solutions, and AI help, open once you add your API key.

Decoding a transcript

At test time we want the most probable transcript, $\hat{\mathbf y} = \arg\max_{\mathbf y}p_{\text{CTC}}(\mathbf y\mid\mathbf X)$ . The sum inside $p_{\text{CTC}}$ is what makes this hard. The number of candidate transcripts grows exponentially with $T$ , and each candidate's probability is a sum over its own alignments. So neither listing the candidates nor a single best-path search gives the answer.

Greedy decoding and where it fails

The cheapest decoder takes the best symbol at every frame and collapses the result.

How often does this matter? The cell draws random posteriors over $\{\varnothing, \texttt a, \texttt b\}$ for seven frames. It finds the exact most probable transcript by summing all $3^7$ paths, and counts how often greedy decoding misses it, at three levels of sharpness.

Python · cell 7

Greedy decoding misses about half the time on flat posteriors and about a tenth of the time on sharp ones. A trained CTC model is very sharp, because it is peaky. That is why greedy decoding is common for CTC in practice, and the FastConformer paper reports greedy WER throughout. The errors that remain sit exactly on the uncertain frames, where the sum over paths matters.

Prefix beam search

To compare transcripts we must score prefixes, not paths, and merge every path that spells the same prefix. A prefix is the start of a transcript, the labels written so far. The forward recursion over a prefix does the merging, if we split its probability by how its paths end. For a label prefix $\ell = (\ell_1,\dots,\ell_n)$ and a frame $t$ , let

p_b(\ell, t) = \sum_{\substack{\mathbf a_{1:t}\,:\,\mathcal B(\mathbf a_{1:t}) = \ell\\ a_t = \varnothing}}\ \prod_{\tau\le t}p_\tau(a_\tau), \qquad p_{nb}(\ell, t) = \sum_{\substack{\mathbf a_{1:t}\,:\,\mathcal B(\mathbf a_{1:t}) = \ell\\ a_t \ne \varnothing}}\ \prod_{\tau\le t}p_\tau(a_\tau).

In plain words, $p_b$ is the probability of the partial paths that spell $\ell$ by frame $t$ and end in a blank, and $p_{nb}$ of those that end in a label, necessarily $\ell_n$ . We need the split because the next symbol behaves differently in the two cases. A copy of $\ell_n$ after a label merges into it, while after a blank it starts a new label.

∴ Prefix probabilities obey a forward recursion

Start from $p_b((), 0) = 1$ and $p_{nb}((), 0) = 0$ for the empty prefix, and $p_b(\ell, 0) = p_{nb}(\ell, 0) = 0$ for every nonempty $\ell$ . The empty prefix never ends in a label, so $p_{nb}((), t) = 0$ for all $t$ . Writing $\ell^-$ for a nonempty $\ell$ without its last label,

p_b(\ell, t) = p_t(\varnothing)\big[p_b(\ell, t-1) + p_{nb}(\ell, t-1)\big],

p_{nb}(\ell, t) = p_t(\ell_n)\Big[p_{nb}(\ell, t-1) + p_b(\ell^-, t-1) + \mathbb 1\big[\ell^-_{\text{last}} \ne \ell_n\big]\,p_{nb}(\ell^-, t-1)\Big],

where the indicator is 1 when $\ell^-$ is empty. At the last frame, $p_{\text{CTC}}(\ell\mid\mathbf X) = p_b(\ell, T) + p_{nb}(\ell, T)$ for every label sequence $\ell$ .

∂ Proof of the prefix recursion

Split the partial paths by their last symbol. A path ending in a blank at frame $t$ spells $\ell$ exactly when its first $t-1$ symbols spell $\ell$ , ending either way, which gives the first line.

A path ending in a label at frame $t$ must end in $\ell_n$ . Its first $t-1$ symbols fall into one of three cases.

They spell $\ell$ and end in $\ell_n$ . The new frame extends that run, which merges.
They spell $\ell^-$ and end in a blank. The new frame starts the label $\ell_n$ .
They spell $\ell^-$ and end in a different label. The new frame starts $\ell_n$ directly, which is allowed only when that label differs from $\ell_n$ , or the two would merge.

A path that spells $\ell$ but ends in a blank cannot be extended by $\ell_n$ into $\ell$ , because that would spell $\ell$ followed by another $\ell_n$ . The three cases are disjoint and exhaustive. At $t = T$ the two endings together are all the alignments of $\ell$ . ∎

Run this recursion for every prefix at once and you have exact decoding, but the number of prefixes grows exponentially. Prefix beam search keeps only the $b$ most probable prefixes after each frame. Graves et al. (2006) introduced a related best-first prefix search, and Hannun et al. (2014) gave the beam form used today.

📐 CTC prefix beam search

Input posteriors $p_t(k)$ for $t = 1,\dots,T$ and a beam width $b$ . Keep a set of prefixes, each with $(p_b, p_{nb})$ .

Start with the empty prefix, $p_b = 1$ and $p_{nb} = 0$ .
At each frame $t$ $t$ , start an empty table of candidates. For every prefix $\ell$ $ℓ$ in the beam, with $q = p_b(\ell) + p_{nb}(\ell)$ $q = p_{b} (ℓ) + p_{nb} (ℓ)$ , add to the candidates
1. the blank, $p_b(\ell)\mathrel{+}= p_t(\varnothing)\,q$ (the prefix is unchanged and now ends in a blank),
2. the repeat, if $\ell$ is nonempty, $p_{nb}(\ell)\mathrel{+}= p_t(\ell_n)\,p_{nb}^{\text{old}}(\ell)$ (the last label continues and merges),
3. every label $k$ , extending to $\ell k$ , with $p_{nb}(\ell k)\mathrel{+}= p_t(k)\,p_b^{\text{old}}(\ell)$ if $k = \ell_n$ (a second copy needs the blank in between) and $p_{nb}(\ell k)\mathrel{+}= p_t(k)\,q$ otherwise.
Candidates reached in several ways, for example $\ell k$ extended from $\ell$ and $\ell k$ already in the beam, are one entry, and their contributions add.
Keep the $b$ candidates with the largest $p_b + p_{nb}$ , and continue with the next frame.
After frame $T$ , return the prefix with the largest $p_b + p_{nb}$ .

All probabilities are kept as logs and added with LSE. Each frame examines $b(V+1)$ extensions, so the search costs $O(T\,b\,V)$ score updates plus the selection of the $b$ best.

With an unbounded beam no prefix is ever pruned. The steps then compute the recursion of the theorem exactly, and the search returns the true $\arg\max_{\mathbf y}p_{\text{CTC}}(\mathbf y\mid\mathbf X)$ . With a finite beam it is an approximation, because a pruned prefix's paths are lost to all its extensions. A beam of 1 is not greedy decoding, since it still sums the paths of its prefix.

✏️ Prefix beam search by hand

Run the two-frame example, $p_t(\varnothing) = 0.6$ and $p_t(\texttt a) = 0.4$ , with a beam of 2. After frame 1 the beam holds the empty prefix with $p_b = 0.6$ and "a" with $p_{nb} = 0.4$ .

At frame 2 the empty prefix gets $p_b = 0.6\times0.6 = 0.36$ . The prefix "a" collects three contributions.

From its own blank, $p_b = 0.6\times0.4 = 0.24$ .
From its repeat, which merges, $p_{nb} = 0.4\times0.4 = 0.16$ .
From extending the empty prefix by $\texttt a$ , $p_{nb}\mathrel{+}= 0.4\times0.6 = 0.24$ .

The total for "a" is $0.24 + 0.16 + 0.24 = 0.64$ , which beats 0.36. Prefix beam search returns "a", where greedy returned the empty transcript.

The widget runs prefix beam search on four frames over $\{\varnothing, \texttt a, \texttt b\}$ , with presets chosen to show where greedy decoding and narrow beams fail. Under each frame it lists the candidate prefixes with their $p_b$ and $p_{nb}$ , and Run fills in the beam one frame at a time.

This is also where a language model enters. A language model gives a probability to every word sequence and is trained on text alone. Hannun et al. (2014) multiply in an $n$ -gram language model's probability, raised to a weight, whenever a prefix is extended by a space. They also multiply by the number of words raised to a second weight, a bonus that keeps the search from favoring short transcripts. That is the decoder behind most CTC systems with a language model, and §36.5 derives the fused score and builds it. Prefix beam search is a classic speech coding interview question.

Interview

CTC prefix beam search

Write ctc_prefix_beam_search(probs, beam, blank=0). The input probs has shape (T, V+1), with strictly positive rows that sum to one. Return (labels, score), where labels is the best prefix as a tuple of ints and score is $\log(p_b + p_{nb})$ of that prefix after the last frame.

Keep $p_b$ and $p_{nb}$ in log space, merge every way of reaching the same prefix, and after each frame keep the beam prefixes with the largest $p_b + p_{nb}$ . The tests check the two-frame example, compare a very wide beam with the exact answer found by enumeration, check narrow beams against a reference search, and include a case where a beam of 1 and greedy decoding disagree. Ties do not occur in the tests.

import numpy as np

def ctc_prefix_beam_search(probs, beam, blank=0):
    # probs: (T, V+1) per-frame probabilities. Return (best label tuple, log(p_b + p_nb)).
    raise NotImplementedError

Tests, verified solutions, and AI help, open once you add your API key.

Which decoder to use

Decoder	What it maximizes	Cost per clip	Language model	When to use it
Greedy (best path)	the single most probable alignment	$O(TV)$ , one argmax per frame	none	the default for a well-trained model, and for throughput
Prefix beam search	$p_{\text{CTC}}(\mathbf y\mid\mathbf X)$ over prefixes, approximately	$O(T\,b\,V)$	none	when frames are uncertain, or to produce a list of the best few transcripts
Prefix beam search with an LM	the fused score of §36.5	$O(T\,b\,V)$ plus LM queries	an n-gram or neural LM	domain text, rare words, low-resource models
WFST decoding	CTC scores composed with a lexicon and grammar	depends on the graph	compiled into the graph	production systems with a lexicon, biasing, or strict grammars

🔬 CTC inside a WFST search graph

A weighted finite-state transducer (WFST) is a graph whose edges read one symbol, write another, and carry a weight. The classical recognizer of §36.1 composes several of them into one search graph, $H\circ C\circ L\circ G$ , for HMM states, phonetic context, the lexicon, and the grammar. CTC reuses that graph with one substitution.

The CTC topology of the HMM box is written as a token transducer $\mathcal T$ , which reads frame-level symbols and writes one label per run, absorbing blanks and repeats. (This $\mathcal T$ is EESEN's $T$ , not the frame count.) It takes the place of $H\circ C$ , since CTC labels are context-independent units with no HMM states of their own. The EESEN recognizer (Miao et al. 2015) builds the graph as $\mathcal T\circ\min(\det(L\circ G))$ , the token transducer composed with the determinized and minimized lexicon and grammar. It searches the graph frame by frame with a pruned beam, as a hybrid decoder searches its graph. The open-source toolkits WeNet, k2, and icefall build the same graph, which WeNet calls TLG and k2 calls HLG, with $H$ there denoting the CTC topology.

EESEN also divides the frame posteriors by label priors before decoding, the scaled likelihood of §36.1 once more. It counts the priors on the blank-extended training transcripts, because priors counted on peaky frame alignments are dominated by the blank.

Forced alignment and timestamps

Sometimes the transcript is known and the question is where each word is. Subtitles need this, cutting long recordings into training segments needs it, and so do word timestamps on a recognizer's output. Finding the times is called forced alignment. Replace the sum in the forward recursion by a max and keep a pointer to the winning predecessor. You get the single most probable alignment of the known transcript, the Viterbi path on the same trellis. It is the max version of the forward algorithm, as Viterbi was in §2.4 and §36.1.

📐 CTC forced alignment

With $\mathbf y'$ , the skip rule, and the log-probabilities as before, let

\delta_1(s) = \log p_1(y'_s)\ \text{ for } s\le 2,\quad \delta_1(s) = -\infty\ \text{ for } s \gt 2,\qquad \delta_t(s) = \log p_t(y'_s) + \max\big(\delta_{t-1}(s),\ \delta_{t-1}(s-1),\ \delta_{t-1}(s-2)\ \text{if skip}_s\big),

record which predecessor won at every $(t, s)$ , end at whichever of positions $2U$ and $2U+1$ has the larger $\delta_T$ , and follow the backpointers to frame 1. The resulting positions $s_1,\dots,s_T$ form the best alignment, with log-probability $\max(\delta_T(2U), \delta_T(2U+1))$ . Label $u$ occupies the frames where $s_t = 2u$ , a contiguous span, and the spans of different labels are ordered and disjoint. The cost is $O(TU)$ time and $O(TU)$ memory for the backpointers.

The frame spans become times by multiplying by the encoder frame duration. Frame $t$ covers the interval $[(t-1)\Delta_{\text{enc}}, t\Delta_{\text{enc}})$ . A word's span runs from its first token's first frame to its last token's last frame. The trellis widget above shows the Viterbi path when set to "best walk".

This is how NVIDIA's NeMo Forced Aligner produces token, word, and segment timestamps from CTC models. WhisperX (Bain et al. 2023) puts word times on Whisper's text the same way. It aligns the text against the frame posteriors of a wav2vec 2.0 model fine-tuned with CTC, and takes each word's start and end from its first and last unit.

The peaky caveat applies with full force. The Viterbi path of a peaky model puts each label on one or two frames, somewhere inside its sound. So a word's span is where the model fired, not where the word was spoken, and the blanks between words absorb the real word edges. Aligners therefore treat CTC spans as anchors and pad or post-process them. Models trained for timing sometimes add a label prior or use a different topology to reduce peakiness.

Core

CTC forced alignment

Write ctc_force_align(log_probs, y, blank=0). It takes log-probabilities of shape (T, V+1) and a transcript y, and returns (spans, score).

score is the log-probability of the best alignment in $\mathcal B^{-1}(\mathbf y)$ .
spans[u] = (first, last) are the 0-indexed first and last frames of label $u$ on that alignment.
Return (None, float("-inf")) when no alignment exists.

Vectorize over positions, since the tests align 300 labels to 2,000 frames.

import numpy as np

def ctc_force_align(log_probs, y, blank=0):
    # Return (spans, score): spans[u] = (first_frame, last_frame) of label u on the best path.
    raise NotImplementedError

Tests, verified solutions, and AI help, open once you add your API key.

CTC at real scale, and what it cannot do

CTC has been at the frontier twice, a decade apart. Two measures recur below. Word error rate (WER) is the share of reference words a recognizer gets wrong, counting substitutions, deletions, and insertions (§36.1). RTFx is the number of seconds of audio transcribed per second of compute, so higher is faster.

✏️ CTC at real scale

On TIMIT, a corpus of read English with phone labels, Graves et al. (2006) trained a bidirectional LSTM with 114,662 weights and a 62-way softmax (61 phones plus the blank). They used CTC and no frame labels. Its phone error rate was 30.51 percent with prefix search and 31.47 percent with best-path decoding. A context-dependent HMM scored 35.21 percent, and an HMM hybrid built on the same kind of network 33.84 percent (Table 1).

Baidu's Deep Speech 2 (Amodei et al. 2015) trained CTC models on 11,940 hours of English speech. wav2vec 2.0, the self-supervised encoder of §35.4, is fine-tuned with a CTC head. Pretrained on 53,000 hours of unlabeled audio and fine-tuned on ten minutes of labels, its large model reaches 4.8 and 8.2 percent WER on the LibriSpeech test-clean and test-other sets when decoded with a Transformer language model (Baevski et al. 2020).

The Open ASR Leaderboard paper (Srivastav et al. 2025) reports average WER over its short-form English test sets and RTFx on one A100 GPU, with numbers as of 27 March 2026. NVIDIA's Parakeet CTC 1.1B, a 1.1-billion-parameter FastConformer with a CTC head, scores 7.40 percent at an RTFx of 2,730. OpenAI's Whisper large-v3, an attention encoder-decoder (§36.4), scores 7.44 percent at 146, about 19 times slower. The smaller FastConformer CTC Large scores 8.96 percent at an RTFx of 6,400.

The speed is structural. CTC is non-autoregressive, meaning it does not produce one token at a time with each conditioned on the last. One encoder pass gives every frame's distribution, the frames are decoded independently, and greedy decoding is an argmax and a collapse. There is no decoder network to run once per token. The leaderboard paper's summary is that Conformer encoders with Transformer decoders give the best average WER, while CTC and token-and-duration transducers give far higher RTFx. That makes them the choice for batch and long-form transcription.

The price is the assumption in the definition box. Given $\mathbf X$ , CTC's outputs are conditionally independent, so no output can depend on another. Everything a language model would know, such as spelling, grammar, and which of two words that sound alike fits, must come from the encoder or from outside.

📌 What a language model is worth to CTC

The same wav2vec 2.0 large model fine-tuned on 10 minutes of labels scores 40.2 and 38.7 percent WER on test-clean and test-other without any language model, against 4.8 and 8.2 percent with one (Baevski et al. 2020, Table 9). Its most common errors without one are spellings such as "all" written "al" and "will" written "wil" (Table 11). Each of these words has one l sound but two l letters. Spelling it needs the path $\texttt l\varnothing\texttt l$ , and only knowledge of the word, which a language model supplies, says the second l is there. With all 960 hours of labels it scores 2.2 and 4.5 percent without a language model (Table 10), because a large encoder trained on enough data learns much of the missing dependence itself. On the leaderboard the gap remains. The best CTC model, at 7.40 percent, is two points behind the best system, at 5.42 percent with a Transformer decoder.

There are three families of fixes.

Add a language model at decoding time, through prefix beam search with fusion (§36.5).
Strengthen CTC inside the encoder. Intermediate CTC (Lee and Watanabe 2021) attaches extra CTC losses to intermediate encoder layers as a regularizer. It improves every model they test. Combined with stochastic depth, which randomly skips whole layers during training, a Conformer reaches 9.9 percent WER on the Wall Street Journal read-speech corpus (WSJ) with greedy decoding and no language model. Self-conditioned CTC (Nozaki and Komatsu 2021) also feeds each intermediate layer's predictions back into the next layer's input. So the final layer's output is conditioned on earlier guesses of the whole transcript. It reports more than 20 percent relative WER reduction over plain CTC on WSJ. On TED talks (TEDLIUM2) and Mandarin (AISHELL-1) it matches a strong autoregressive model with beam search while decoding at least 30 times faster.
Change the model. The transducer of §36.3 adds a prediction network that reads the labels emitted so far. That removes the independence while keeping the frame-by-frame sum over alignments. Attention encoder-decoders (§36.4) drop explicit alignments, and there CTC returns as an auxiliary loss that keeps attention moving forward through the audio. In streaming systems (§36.6), a fast CTC first pass is often rescored by a slower second pass.

	CTC
How it handles alignment	sums over all monotone alignments with blanks, by the forward algorithm
Output dependence	none given $\mathbf X$ (conditionally independent frames)
Length condition	$T\ge U + R(\mathbf y)$ , at most one label per frame
Training cost	$O(TU)$ per clip on top of the encoder, small memory
Decoding	greedy argmax, or prefix beam search, non-autoregressive
Streaming	yes, with a streaming encoder, since outputs come one per frame
Timestamps	from forced alignment, but peaky spikes are not word boundaries
Typical use	fast batch transcription, forced alignment, auxiliary loss for attention models

⚠️ Where CTC implementations go wrong

Deleting blanks before merging repeats turns $\texttt l\varnothing\texttt l$ into one "l" and makes "hello" unreachable.
Allowing the skip between equal labels lets "aa" leak into "a". Forbidding it everywhere makes "ab" need a blank in between.
Forgetting the $\alpha_T(2U)$ term drops every path that ends on its last label.
Multiplying probabilities instead of adding logs returns zero, then an infinite loss, after a few hundred frames.
In PyTorch, passing softmax outputs instead of log_softmax outputs, putting the batch first when the function expects (T, N, C), or giving the blank an index that a real label also uses silently trains the wrong model.
The default reduction="mean" divides by target length, which changes the weighting across a batch, so choose it deliberately.
An infeasible pair makes the batch loss infinite. Find and fix such pairs rather than leaning on zero_infinity=True, and remember the condition is $T\ge U+R$ , not $T\ge U$ .
A literal $-\infty$ in a hand-written autograd version gives NaN gradients. Use a large finite negative number.
Never read CTC spike times as word boundaries without correction.

🧭 What to remember

CTC adds a blank $\varnothing$ and a collapse map $\mathcal B$ (merge repeats, then delete blanks), and defines $p_{\text{CTC}}(\mathbf y\mid\mathbf X) = \sum_{\mathbf a\in\mathcal B^{-1}(\mathbf y)}\prod_tp_t(a_t)$ , assuming the frames are conditionally independent given the input. A transcript has $\binom{T+U-R}{2U}$ alignments.
The forward algorithm on $\mathbf y' = (\varnothing, y_1, \dots, y_U, \varnothing)$ computes that sum in $O(TU)$ , with a skip only between different labels and an end on either of the last two positions. It is the HMM forward algorithm for a fixed topology with unit transition weights and raw posteriors as emissions. Always run it in log space.
The gradient is $\partial\mathcal L/\partial z_t(k) = p_t(k) - \gamma_t(k)$ , with the occupancy $\gamma_t$ from forward-backward. It is the prediction minus a soft target that the model computes itself.
A transcript needs $T\ge U + R(\mathbf y)$ frames. This ties the encoder's frame rate to the vocabulary and pushed 80 ms models to subword units.
Training from a uniform start favors the blank by pure counting, so trained models are peaky. Greedy decoding is then usually right, but CTC spikes are not word boundaries.
Greedy decoding returns the best path, not the best transcript. Prefix beam search sums each prefix's paths with $p_b$ and $p_{nb}$ in $O(TbV)$ and is exact with an unbounded beam. Viterbi on the same trellis gives forced alignments and timestamps.
CTC is the fastest family at the frontier (Parakeet CTC 1.1B at RTFx 2,730) but cannot condition outputs on each other. §36.3 adds a prediction network that reads the labels already emitted, keeping the sum over alignments and the ability to stream.

Graves, Fernández, Gomez, and Schmidhuber (2006). Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks. The original paper, with the forward-backward derivation, best-path and prefix search decoding, and the TIMIT results of Table 1.
Hannun (2017). Sequence Modeling with CTC. A visual walk through alignments, the trellis, the loss, and beam search. With it, Hannun, Maas, Jurafsky, and Ng (2014), First-Pass Large Vocabulary Continuous Speech Recognition using Bi-Directional Recurrent DNNs, which introduced prefix beam search with $p_b$ and $p_{nb}$ and the language model hook. Read its Algorithm 1 critically, since the printed pseudocode overwrites scores that implementations accumulate, and its repeat case updates $p_{nb}$ from $p_b$ where $p_{nb}$ is meant.
Zeyer, Schlüter, and Ney (2021). Why does CTC result in peaky behavior?. The counting argument and convergence analysis behind peaky outputs, and the label-prior variant that avoids them. With it, Miao, Gowayyed, and Metze (2015), EESEN: End-to-End Speech Recognition using Deep RNN Models and WFST-based Decoding, which composes the CTC token transducer with a lexicon and grammar and divides posteriors by label priors at decoding.
Amodei et al. (2015). Deep Speech 2: End-to-End Speech Recognition in English and Mandarin, CTC at industrial scale on 11,940 hours of English, and Srivastav et al. (2025), Open ASR Leaderboard: Towards Reproducible and Transparent Multilingual and Long-Form Speech Recognition Evaluation, where a CTC model posts the highest RTFx in the English short-form table.
Baevski, Zhou, Mohamed, and Auli (2020). wav2vec 2.0: A Framework for Self-Supervised Learning of Speech Representations. A self-supervised encoder fine-tuned with CTC, with full results with and without a language model in Tables 9 and 10 and the typical spelling errors in Table 11.
Rekesh et al. (2023). Fast Conformer with Linearly Scalable Attention for Efficient Speech Recognition. The 8x encoder and the observation that character CTC breaks the length condition at 80 ms frames, hence subword vocabularies.
Lee and Watanabe (2021). Intermediate Loss Regularization for CTC-based Speech Recognition, and Nozaki and Komatsu (2021), Relaxing the Conditional Independence Assumption of CTC-based ASR by Conditioning on Intermediate Predictions. Two ways to strengthen CTC inside the encoder.
Bain, Huh, Han, and Zisserman (2023). WhisperX: Time-Accurate Speech Transcription of Long-Form Audio, and the NeMo Forced Aligner documentation. CTC forced alignment as it is used to put word times on transcripts.
PyTorch documentation. CTCLoss. The exact input layout, reduction semantics, and zero_infinity behavior.

Made for larger screens

Connectionist temporal classification

Why we cannot just label the frames

A blank symbol and a collapsing rule

The collapse map

The probability of a transcript is a sum over its alignments

How many alignments there are

The forward algorithm adds up every alignment

CTC is a hidden Markov model with a blank

Working in log space

The CTC loss in log space

The gradient is the prediction minus a soft target

The CTC gradient by forward-backward

CTC in PyTorch

Batched CTC loss over padded inputs

How many frames a transcript needs

Why trained CTC models are peaky

Why CTC gets peaky, from counts

Decoding a transcript

Greedy decoding and where it fails

Prefix beam search

CTC prefix beam search

Which decoder to use

Forced alignment and timestamps

CTC forced alignment

CTC at real scale, and what it cannot do

Read more

Watch next