Connectionist Temporal Classification

Label unsegmented sequences by adding a blank symbol and summing over every frame-level alignment that collapses to the target. No frame labels are needed, but outputs are conditionally independent and peaky.

13 min read1221 wordsadvanced0 viewsupdated 2026-10-11

Definition

Connectionist Temporal Classification (CTC) is a way to train and decode a network that reads a long input sequence x1:Tx_{1:T} (audio frames, image columns, pen strokes) and must output a shorter label sequence y1:Uy_{1:U}, U≤TU\le T, without knowing which frames belong to which label. The network emits a distribution over the labels plus a special blank ε\varepsilon at every frame; a frame-level path is mapped to a label sequence by merging repeats and deleting blanks, and p(y∣x)p(y\mid x) is the total probability of every path that maps to yy.

Speech is the classic case. One second of audio is 100 feature frames at a 10 ms hop, but the transcript "cat" is three characters, and nobody has marked where the "c" ends and the "a" begins. Before CTC, recognisers needed that segmentation: an HMM produced frame-level targets by forced alignment, and the neural network was trained as a frame classifier on them. CTC removes the alignment step: the network is trained directly on (input, transcript) pairs.

It was introduced by Alex Graves, Santiago Fernández, Faustino Gomez and Jürgen Schmidhuber at ICML 2006 ("Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks"), with bidirectional LSTMs on TIMIT phoneme recognition. Graves and colleagues then used it for unconstrained handwriting recognition (2009), Baidu's Deep Speech (Hannun et al., 2014) built an end-to-end speech recogniser on it, and the CRNN of Shi, Bai and Yao (2015) made it the standard loss for scene-text OCR. Self-supervised speech encoders such as wav2vec 2.0 (Baevski et al., 2020) are still usually fine-tuned with a CTC head.

This article covers the model: the blank, the collapse map, the alignment set, the assumptions and decoding. How −log⁡p(y∣x)-\log p(y\mid x) and its gradient are actually computed (the forward–backward recursion, PyTorch's nn.CTCLoss) is the subject of CTC loss.

The blank and the collapse map B

Let LL be the label alphabet and L′=L∪{ε}L'=L\cup\{\varepsilon\}. At each frame the network outputs a softmax yt(k)=p(k∣x,t)y_t(k)=p(k\mid x,t) over L′L'. A path (or alignment) is a sequence π∈L′ T\pi\in L'^{\,T} with one symbol per frame. The many-to-one map B:L′ T→L≤T\mathcal B:L'^{\,T}\to L^{\le T} turns a path into a labelling in two steps:

B(π): collapse a path

  1. 1Merge consecutive repeats: CC-AA--T becomes C-A-T. A label held for several frames counts once.
  2. 2Delete every blank: C-A-T becomes CAT.
  3. 3The order matters. CA-AT merges nothing (the two A's are separated by a blank) and gives CAAT; CAAT as a path merges to CAT. A blank between two equal labels is the only way to emit a doubled letter.

The blank does two jobs. It lets the network say "nothing new here" on the many frames between labels (silence, transitions, the inside of a long vowel), and it separates genuine repeats such as the "ll" in "hello". Without it, the network could never output "aa" at all.

The probability of a labelling

p(y∣x)  =  ∑π∈B−1(y)p(π∣x),p(π∣x)  =  ∏t=1Tyt(πt)p(y\mid x)\;=\;\sum_{\pi\in\mathcal B^{-1}(y)} p(\pi\mid x),\qquad p(\pi\mid x)\;=\;\prod_{t=1}^{T} y_t(\pi_t)
yt(k)y_t(k)
network softmax output for symbol k∈L′k\in L' at frame tt
π\pi
a path: one symbol of L′L' per frame, ∣π∣=T|\pi|=T
B−1(y)\mathcal B^{-1}(y)
the set of all paths that collapse to the target yy, its alignments
∏t\prod_t
conditional independence: given xx, the frame outputs are independent

Training maximises log⁡p(y∣x)\log p(y\mid x), i.e. minimises −log⁡p(y∣x)-\log p(y\mid x). The set of alignments is large: for a target of UU labels with no adjacent repeats there are exactly (T+U2U)\binom{T+U}{2U} of them (a path is UU label runs of length ≥1\ge1 interleaved with U+1U+1 blank runs of length ≥0\ge0). "CAT" has exactly 1 alignment in 3 frames (CAT itself) and 7 in 4 frames; in 8 frames it has (116)=462\binom{11}{6}=462; at T=100T=100 frames there are about 1.4×1091.4\times10^{9}. The sum is never enumerated: a dynamic programme over the blank-extended target computes it in O(T⋅U)O(T\cdot U) (see CTC loss).

At a glance

Task
sequence labelling with U≤TU\le T and monotonic alignment: speech recognition, handwriting, OCR, sign language, keyword spotting
Output layer
per-frame softmax over ∣L∣+1|L|+1 symbols (labels plus blank); blank is index 0 by convention
Supervision
only the label sequence; no frame boundaries
Length constraint
T≥U+rT\ge U+r, where rr is the number of adjacent equal labels in yy (each needs a blank between)
Alignments
(T+U2U)\binom{T+U}{2U} for UU labels without repeats; fewer with repeats (e.g. 165 for "CAAT" vs 462 for "CAT" at T=8T=8)
Assumption
frame outputs independent given xx; no model of label-to-label dependencies inside the loss
Decoding
greedy best path (fast, approximate), prefix beam search, beam search with an external language model

Interactive: alignments, collapse and decoding

frame posteriors y_t(k) · outlined = path π (click to edit)t=1t=2t=3t=4t=5t=6t=7t=8ε.20.45.46.45.50.15.60.85C.70.10.05.05.05.05.05.05A.05.40.44.40.10.05.05.05T.05.05.05.10.35.75.30.05bold = argmax per frame · violet row = blank ε · path = greedypath π C - - - - T - -merge repeats C - T -drop blanks → CTp(π) = Π_t y_t(π_t) = 0.0125target “CAT”: |B⁻¹(y)| = 462 alignments in 8 framesp(y|x) = Σ over all of them = 0.2460path π above: collapses to CT, not an alignment of CATmost probable alignments of “CAT” (share of p(y|x)):C-A--T-- 0.0119 (4.8%)C--A-T-- 0.0111 (4.5%)CA---T-- 0.0111 (4.5%)C-AA-T-- 0.0106 (4.3%)preset “ambiguous”: the A is smeared over three frames where blank narrowly wins each onedecodinggreedy (best path)C----T-- → CTp(π) 0.0125 · p(ℓ|x) 0.0568prefix beam search, width 31. CAT 0.23232. CT 0.02523. CA 0.0191exact: sum all 4⁸ = 65536 paths1. CAT 0.24602. AT 0.07043. CT 0.0568greedy misses: CT ≠ CAT
network
target
fig.An 8-frame posteriorgram over {ε, C, A, T}. The outlined path starts as the greedy argmax; click cells to edit it and watch B merge repeats and drop blanks. On the default 'ambiguous' network greedy decoding reads C----T-- → "CT" (p(CT|x) = 0.0568), but summing all 65 536 paths shows "CAT" is far more likely (0.2460): its A is spread over three frames where blank narrowly wins each, and no single CAT alignment carries more than 4.8% of its mass. Prefix beam search with width 1 also returns CT; width 2 already finds CAT. On the 'clean' network greedy is right and one alignment, -C-A--T-, carries 65.4% of p(CAT|x) = 0.4752. τ < 1 sharpens every frame, τ > 1 flattens.

Worked example: two frames

Take T=2T=2 and a one-letter alphabet {ε,a}\{\varepsilon,a\}, with yt(ε)=0.6y_t(\varepsilon)=0.6, yt(a)=0.4y_t(a)=0.4 at both frames. Every path and where B\mathcal B sends it:

Path πB(π)p(π|x)
--∅ (empty)0.6×0.6=0.360.6\times0.6=0.36
-aa0.6×0.4=0.240.6\times0.4=0.24
a-a0.4×0.6=0.240.4\times0.6=0.24
aaa0.4×0.4=0.160.4\times0.4=0.16
All 4 paths for T = 2

The single most probable path is -- (0.36), so greedy decoding outputs the empty string. But p(a∣x)=0.24+0.24+0.16=0.64p(a\mid x)=0.24+0.24+0.16=0.64: the labelling "a" is almost twice as likely, because its mass is split over three alignments. "aa" is impossible here (p=0p=0), since it needs at least 3 frames (a-a). This gap between the most probable path and the most probable labelling is what beam search exists to close.

Assumptions and their consequences

Monotonic alignment. Paths move left to right through the target and can never go back. That is right for speech and handwriting, wrong for translation, where word order changes.

Conditional independence. p(π∣x)=∏tyt(πt)p(\pi\mid x)=\prod_t y_t(\pi_t): once the encoder has seen the whole input, each frame's choice ignores the choices at other frames. A bidirectional or Transformer encoder can still use plenty of context to produce yty_t, but the loss cannot express "after 'q' comes 'u'". Character CTC models therefore make phonetically plausible spelling errors, and an external language model helps a lot.

Length. Each label needs at least one frame, and each adjacent repeat needs an extra blank frame: T≥U+rT\ge U+r. Encoders that downsample (convolutional front ends reduce frame rate by 4–8× in modern ASR) can violate this for fast speech or long transcripts, and the loss becomes infinite (see CTC loss for zero_infinity).

Decoding

The ideal output is y^=arg⁡max⁡yp(y∣x)\hat y=\arg\max_y p(y\mid x), a search over labellings in which each candidate is itself a sum over alignments. It is intractable in general, so three approximations are used.

Where it's used

Greedy (best path)

Take arg⁡max⁡kyt(k)\arg\max_k y_t(k) at every frame, then apply B\mathcal B. O(T∣L′∣)O(T|L'|), no search. It finds the most probable path, which is not necessarily the most probable labelling (the two-frame example, and the 'ambiguous' preset in the figure). On peaky, well-trained models the dominant path usually carries most of the mass and the two agree.

Prefix beam search

Keep the WW best label prefixes, not paths. Each prefix stores two numbers, the probability of all paths ending in blank, pbp_b, and ending in its last label, pnbp_{nb}, so that at the next frame a repeated label can be merged (extends from pnbp_{nb}) or appended as a new label (only from pbp_b). Paths that collapse to the same prefix are summed instead of competing.

Beam search with an LM (shallow fusion)

Score prefixes by log⁡pCTC(ℓ∣x)+αlog⁡pLM(ℓ)+β∣ℓ∣\log p_{\text{CTC}}(\ell\mid x)+\alpha\log p_{\text{LM}}(\ell)+\beta|\ell|, where the LM is an n-gram or neural model over characters or words, α\alpha is its weight and β\beta a length (word-insertion) bonus that offsets the LM's preference for short outputs. Deep Speech used exactly this form. WFST decoders (as in EESEN and Kaldi-style pipelines) compile lexicon and grammar into the search graph.

python
1import torch
2from collections import defaultdict
3
4def greedy_decode(log_probs, blank=0): # log_probs: (T, C) for one utterance
5 best = log_probs.argmax(dim=-1).tolist() # best path, one symbol per frame
6 out, prev = [], None
7 for k in best: # B: merge repeats, then drop blanks
8 if k != prev and k != blank:
9 out.append(k)
10 prev = k
11 return out
12
13def prefix_beam_search(probs, width=8, blank=0): # probs: (T, C) softmax outputs
14 beam = {(): (1.0, 0.0)} # prefix -> (p_blank_end, p_label_end)
15 for row in probs.tolist():
16 nxt = defaultdict(lambda: [0.0, 0.0])
17 for prefix, (pb, pnb) in beam.items():
18 nxt[prefix][0] += (pb + pnb) * row[blank] # emit blank
19 for k, pk in enumerate(row):
20 if k == blank:
21 continue
22 if prefix and prefix[-1] == k:
23 nxt[prefix][1] += pnb * pk # repeat: merged
24 nxt[prefix + (k,)][1] += pb * pk # after a blank: new label
25 else:
26 nxt[prefix + (k,)][1] += (pb + pnb) * pk
27 beam = dict(sorted(nxt.items(), key=lambda kv: -sum(kv[1]))[:width])
28 return max(beam.items(), key=lambda kv: sum(kv[1]))
29
30# the two-frame example: blank 0.6, "a" 0.4 at both frames
31probs = torch.tensor([[0.6, 0.4], [0.6, 0.4]])
32print(greedy_decode(probs.log())) # [] best path "--"
33best, (pb, pnb) = prefix_beam_search(probs)
34print(best, pb + pnb) # (1,) ≈0.64 -> "a": 0.24 ending in blank + 0.40 ending in "a"
Greedy CTC decoding and a minimal prefix beam search (blank = 0, no language model)

In production use a tested implementation: torchaudio.models.decoder.ctc_decoder (a lexicon- and KenLM-aware beam search from Flashlight) or pyctcdecode. Probabilities in real models should be handled in log space; the toy above multiplies raw probabilities for readability.

CTC versus attention and transducers

AspectCTCAttention encoder–decoderRNN-Transducer
Alignmentmonotonic, marginalisedlearned soft attention, any ordermonotonic, marginalised
Label dependenciesnone (conditionally independent)full, autoregressive decoderyes, via a prediction network
Output lengthU≤TU\le T requiredunrestrictedunrestricted (emits ≥0\ge0 labels per frame)
Inferenceone parallel pass + collapsesequential, beam searchsequential over frames and labels
Streamingnaturalhard (attends to the whole input)natural
Typical failurespelling errors without an LMlooping, skipping, hallucinated words on long inputsmemory-hungry loss over a T×U×V lattice
Three ways to train a sequence-to-sequence recogniser

The attention route is Listen, Attend and Spell (Chan et al., 2016); the transducer is Graves (2012), "Sequence Transduction with Recurrent Neural Networks", which removes CTC's independence assumption by conditioning each output on previous labels. In practice they are often combined: joint CTC–attention training (Kim, Hori and Watanabe, 2017) uses a CTC head as an auxiliary loss that forces the attention to stay monotonic, and decoding mixes both scores.

Use when

  • +Trains on transcripts alone: no frame-level segmentation or forced alignment needed.
  • +Non-autoregressive: one forward pass gives every frame's output, so greedy decoding is fast and trivially parallel.
  • +Monotonic alignment is a strong, correct prior for speech, handwriting and OCR; it cannot loop or skip like attention can.
  • +Streams naturally with a causal or chunked encoder.
  • +Plays well with external language models and lexicons at decoding time.

Avoid when

  • −Conditional independence: no output-side language model inside the loss, so accuracy depends on the encoder and an external LM.
  • −Needs T≥U+rT\ge U+r: unusable when the output can be longer than the input, or for non-monotonic tasks such as translation.
  • −Peaky, blank-dominated outputs give unreliable timing and phone boundaries.
  • −Most probable path ≠ most probable labelling; exact decoding is intractable.

Check yourself

Which path collapses to "HELLO" under B\mathcal B?

Check yourself

A target has U=3U=3 labels with no adjacent repeats. With T=8T=8 frames, how many alignments does CTC sum over?

Remember

  • ✓CTC adds a blank ε\varepsilon and defines p(y∣x)p(y\mid x) as the sum of ∏tyt(πt)\prod_t y_t(\pi_t) over every path π\pi with B(π)=y\mathcal B(\pi)=y.
  • ✓B\mathcal B merges repeats then removes blanks; a blank between equal labels is the only way to emit a doubled letter.
  • ✓It needs T≥U+T\ge U+ (number of adjacent repeats), assumes monotonic alignment and conditionally independent frames.
  • ✓There are (T+U2U)\binom{T+U}{2U} alignments for a repeat-free target; the sum is done by dynamic programming (see CTC loss).
  • ✓Trained models are peaky: blank almost everywhere, labels as spikes.
  • ✓Greedy finds the best path, not the best labelling; prefix beam search sums paths per prefix and can add an LM via shallow fusion.
  • ✓Attention models add label dependencies but can loop or skip; RNN-T keeps CTC's monotonic alignment and adds a prediction network.
← back to Deep Learning roadmap