CTC Loss: Sequence-to-Sequence Without Alignment

Suppose you are building a Hindi speech-to-text engine for a railway enquiry line. A caller says a two-second sentence. Your feature extractor slices the audio into 10-millisecond acoustic frames, so two seconds becomes roughly 200 frames, each a vector describing the sound at that instant. The transcript your training data gives you is the sentence text — maybe 30 characters. Nowhere in the training set does anyone mark which of the 200 frames corresponds to which of the 30 characters. You know the caller said "अगला ट्रेन कब है" and you know the 200 frames that produced it, but the correspondence between them — the alignment — was never recorded and would be absurdly expensive to hand-label for millions of training utterances.

This is the specific problem CTC (Connectionist Temporal Classification, introduced by Alex Graves and colleagues in 2006) was built to solve: how do you train a network to map a long, frame-by-frame input sequence to a shorter, unaligned output sequence, when your only supervision is the final output string, never the frame-to-character correspondence? The same problem shows up whenever an input sequence is systematically longer than its label sequence and no alignment is given — online handwriting recognition, gesture-to-text, and the acoustic layer of almost every production ASR system before attention-based decoders became dominant (and still today, as one head in hybrid CTC/attention systems). Understanding CTC is understanding how a network can discover its own alignment as a byproduct of learning to output the right sequence.

Why per-frame classification does not work

The obvious first idea is to treat this as ordinary supervised classification: run each of the 200 frames through a shared classifier that outputs a probability distribution over characters, train with per-frame cross-entropy, then read off the predicted character at each frame. Two things break immediately. First, cross-entropy needs a target label at every frame, and you only have a target for the whole utterance. Someone would have to tell you that frames 1–14 are silence, 15–40 are "अ", 41–52 are "ग", and so on — exactly the alignment you do not have. Getting it via forced alignment against a separate acoustic model is circular (you need a trained model to align data to train a model) and brittle, because phoneme and character durations vary wildly with speaking rate, so a fixed frame-to-character mapping learned on one utterance does not transfer to another spoken faster or slower.

Second, even granting an alignment, characters are not equally long. A held vowel might span 25 frames; a stop consonant might span 3. A naive per-frame classifier has no mechanism to say "these 14 consecutive frames are all still the same character" versus "the character changed here" without an external duration model bolted on. CTC solves both problems with one idea: let the network output a label (or "nothing new happened") at every single frame, and define a many-to-one function that turns any such frame-level output sequence into a final, collapsed label sequence — then sum the probability over every frame-level sequence that collapses to the correct answer.

The blank token and the collapsing function

CTC augments the label vocabulary with one extra symbol, the blank, written ε (or "–"). At every frame t, the network's softmax layer outputs a probability distribution p_t over (vocabulary ∪ {blank}). A path π is one full sequence of T such per-frame symbols — one symbol per frame, exactly as long as the input. Define the collapsing function B: first merge any run of consecutive identical symbols into one, then delete every blank. For example, with T = 7 frames, the path "C C – A A T T" collapses under B to "CAT": the run "C C" merges to "C", the run "A A" merges to "A", the run "T T" merges to "T", and the single blank in the middle is deleted (it also serves the important job of separating the two C's-that-aren't from the two A's, which we return to below).

Because B is many-to-one, many different frame-level paths collapse to the same target label sequence y. CTC defines the probability the network assigns to y as the sum over every path that collapses to it, weighting each path by the product of the per-frame probabilities the network assigned along that path:

p(y | x) = Σ_{π ∈ B⁻¹(y)} Π_{t=1}^{T} p_t(π_t | x)

Training minimises the negative log of this quantity, L = −ln p(y | x), with ordinary backpropagation through the softmax outputs. Nothing in this loss ever requires knowing which specific path actually happened — it marginalises over all of them, so the network is free to discover, on its own, whichever alignment makes the data most likely.

Summing over exponentially many paths without enumerating them

The set B⁻¹(y) has size exponential in T (there are up to |vocabulary ∪ {blank}|^T raw paths to filter), so computing p(y | x) by brute-force enumeration is intractable for any real T. CTC computes it in polynomial time with a dynamic program that is structurally identical to the forward algorithm used for hidden Markov models. Build the extended label sequence l′ by inserting a blank before, after, and between every symbol of y: for y of length U, l′ has length 2U + 1. For y = "CAT" (U = 3), l′ = [–, C, –, A, –, T, –], length 7.

Define the forward variable α_t(s) as the total probability, summed over all valid partial paths of length t, of having emitted a path whose collapse matches the prefix of y ending at position s of l′, and which is sitting in state s at time t. The recursion allowed at each step reflects exactly three things a path can do from frame t−1 to frame t: stay in the same state (repeat the same symbol, or stay in a blank one more frame), advance one state in l′ (move on to the next symbol), or — only when l′_s is a non-blank label different from l′_s−2 — skip over the intervening blank entirely, because that blank was optional (nothing forces you to visit it when the two labels on either side are different). Formally, for t ≥ 2:

α_t(s) = [ α_{t-1}(s) + α_{t-1}(s-1) + skip_term ] · p_t(l'_s)
skip_term = α_{t-1}(s-2)  if l'_s ≠ '-' and l'_s ≠ l'_{s-2}, else 0

with α₁(1) = p₁(l′₁), α₁(2) = p₁(l′₂), and all other α₁(s) = 0. The total probability is p(y | x) = α_T(2U+1) + α_T(2U) — the path is allowed to end either on the final trailing blank or on the last label itself. This costs O(T · U) instead of exponential time, the same complexity trick that makes Viterbi and the HMM forward algorithm tractable.

Worked example: aligning "AB" over three frames

Take the smallest non-trivial case: target y = "AB" (U = 2), vocabulary {A, B}, T = 3 acoustic frames. The extended sequence is l′ = [–, A, –, B, –], length 5. Suppose the network's softmax has produced these per-frame probabilities (only A, B, and blank shown; they sum to 1 each frame):

Applying the recursion, using 1-indexed states s = 1..5 for l′ = [–, A, –, B, –]:

t = 1 (initialisation): α₁(1) = p₁(–) = 0.300. α₁(2) = p₁(A) = 0.600. α₁(3) = α₁(4) = α₁(5) = 0.

t = 2: α₂(1) = α₁(1)·p₂(–) = 0.300 × 0.30 = 0.090. α₂(2) = [α₁(2)+α₁(1)]·p₂(A) = 0.900 × 0.20 = 0.180. α₂(3) = [α₁(3)+α₁(2)]·p₂(–) = 0.600 × 0.30 = 0.180. α₂(4) = [α₁(4)+α₁(3)+α₁(2)]·p₂(B) — the skip term α₁(2) is included because l′₄ = B ≠ l′₂ = A — = 0.600 × 0.50 = 0.300. α₂(5) = [α₁(5)+α₁(4)]·p₂(–) = 0.

t = 3: α₃(1) = 0.090 × 0.20 = 0.018. α₃(2) = (0.180+0.090) × 0.10 = 0.027. α₃(3) = (0.180+0.180) × 0.20 = 0.072. α₃(4) = (0.300+0.180+0.180) × 0.70 = 0.660 × 0.70 = 0.462. α₃(5) = (0+0.300) × 0.20 = 0.060.

The total probability is p("AB" | x) = α₃(5) + α₃(4) = 0.060 + 0.462 = 0.522, so the CTC loss for this training example is L = −ln(0.522) ≈ 0.650 nats.

This can be checked by brute force: there are 3³ = 27 possible length-3 paths over {A, B, –}. Applying B to each shows exactly five of them collapse to "AB" — AAB, ABB, AB–, A–B, and –AB — and their probabilities sum to exactly 0.084 + 0.210 + 0.060 + 0.126 + 0.042 = 0.522, confirming the dynamic program. The code below implements the same recursion and was traced by hand against these numbers:

def ctc_forward_prob(target, probs):
    # target: label string, e.g. "AB"; probs: list of T dicts
    # mapping each frame's symbol -> probability (must include '-')
    ext = ['-']
    for c in target:
        ext.append(c)
        ext.append('-')
    T, S = len(probs), len(ext)
    alpha = [[0.0] * S for _ in range(T)]
    alpha[0][0] = probs[0][ext[0]]
    if S > 1:
        alpha[0][1] = probs[0][ext[1]]
    for t in range(1, T):
        for s in range(S):
            val = alpha[t - 1][s]
            if s > 0:
                val += alpha[t - 1][s - 1]
            if s > 1 and ext[s] != '-' and ext[s] != ext[s - 2]:
                val += alpha[t - 1][s - 2]
            alpha[t][s] = val * probs[t][ext[s]]
    return alpha[T - 1][S - 1] + alpha[T - 1][S - 2]

probs = [
    {'A': 0.6, 'B': 0.1, '-': 0.3},
    {'A': 0.2, 'B': 0.5, '-': 0.3},
    {'A': 0.1, 'B': 0.7, '-': 0.2},
]
print(ctc_forward_prob("AB", probs))   # 0.522

Production frameworks (PyTorch's torch.nn.CTCLoss, TensorFlow's tf.nn.ctc_loss) implement exactly this forward–backward recursion, but in log-space. Raw probabilities are products of up to hundreds of numbers below 1, which underflows to zero in floating point well before T reaches real utterance lengths — so every serious implementation carries log α and combines terms with the log-sum-exp trick rather than multiplying probabilities directly.

Visualising the mechanism

The diagram below is the exact trellis for the worked example above — every α value shown is one you just derived by hand.

Trace the amber dashed "skip" edges and you can see why they exist: they run from the A-row directly into the B-row, jumping over the blank between them, because a path is never forced to linger on a separating blank when the labels on either side are different. That freedom is exactly what let five different paths — with the blank appearing in five different places, or not at all — all collapse to the same answer "AB", and it is why the total probability the network assigns to "AB" is the sum over all of them rather than the value along any single path.

Decoding: turning probabilities back into text

Training uses the sum because the network must be allowed credit for any alignment that produces the right answer, since the true alignment is unknown. Inference is a different question: given the trained network's frame-by-frame distributions, what is the single best output string? The exact answer is ŷ = argmax_y p(y | x), which in principle requires summing over the same exponential path space for every candidate y — intractable in general.

The cheap approximation used everywhere in practice is greedy (best-path) decoding: take arg max_k p_t(k) independently at every frame, then apply B to the resulting single path. This is fast (O(T)) but not exact, because the most probable single path does not have to belong to the most probable label sequence — many mediocre paths for the correct answer can together outweigh one excellent path for a wrong answer. Production systems that need higher accuracy use beam search: at each frame, extend and re-rank a fixed-size beam of partial label sequences, merging beam entries whose collapsed output already agrees (since two different partial paths can be building toward the identical output), and often folding in scores from an external language model — exactly the hybrid the "0.522"-style sum is designed to make tractable one frame at a time rather than over the whole utterance at once.

How the gradient actually teaches the network to align

Because L = −ln p(y | x) is differentiable with respect to every per-frame softmax output, ordinary backpropagation trains the network end to end with no separate alignment stage. The mechanism is a mirror of the forward pass: define a backward variable β_t(s), computed by an analogous recursion running from t = T back to t = 1, representing the probability of completing the suffix of l′ from state s onward using frames t+1..T. Graves et al. (2006) show the resulting gradient at frame t for label k is proportional to the total forward–backward probability mass, α_t(s)·β_t(s), summed over every state s in l′ that carries symbol k, normalised by p(y | x). In plain terms: the gradient pushes up the network's confidence in symbol k at frame t in proportion to how much of the total "successful alignment" probability mass happens to pass through k at that exact frame — a soft, fully differentiable version of forced alignment that the network discovers for itself, purely by trying to make the sum in the denominator as large as possible.

Misconception: "CTC can never output two of the same letter in a row"

The single most common mistake students make on first reading the collapsing rule is to conclude that CTC's output can never contain a repeated adjacent character — after all, the rule says "merge consecutive identical symbols," so surely "HELLO" (with its double L) is impossible to produce? This is wrong, and the fix is to notice that the merging happens on the raw path, before blanks are removed, not on the final string. A path like "H, E, L, –, L, O" merges no consecutive symbols at all (H, E, L, blank, L, O are pairwise distinct as written), and only then has its single blank deleted, correctly yielding "HELLO" with both L's intact. The blank's job is precisely to act as a separator that lets the network say "the same character again, deliberately, not a leftover repeat of the previous frame." Concretely: for any target with r adjacent-repeated-letter pairs (like the one "LL" in HELLO), every valid path must actually visit a blank state between that pair — the skip-transition that lets a path jump over a blank is explicitly disallowed exactly when the two surrounding labels are identical, which is the same rule you traced by hand in the trellis above. The direct consequence: the minimum number of frames T needed to represent a target y of length L is not L, but L + r, where r counts the adjacent-repeat pairs in y.

Active recall

Attempt these before reading the answers.

1. Why can a speech model not simply be trained with per-frame cross-entropy against the transcript directly, the way an image classifier is trained against a single label?
2. Write out the extended label sequence l′ for the target "ISRO" and state its length.
3. What is the minimum number of acoustic frames T needed for a valid CTC path to produce the target "APPLE"? Justify it using the skip-transition rule.
4. In the worked "AB" example, α₂(4) = 0.300 received a contribution from α₁(2) = 0.600 via a skip edge. Explain in words what real-world event that skip edge represents.
5. Why does CTC training sum over all paths that collapse to y, while decoding cannot simply do the same to find the best y?
6. A trained CTC model, decoded greedily, outputs the path "C, C, A, –, T, T" for an audio clip whose true label is "CAT". Does greedy decoding get this one right? Show the collapse.

Answers.

1. Cross-entropy needs a target class at every single input position, but the dataset only supplies one label sequence for the whole utterance — no frame-by-frame ground truth exists, and manually producing it (or deriving it from a separate forced-alignment model) is either too expensive at scale or circular. CTC instead defines a loss over sequence-level labels by marginalising over every frame-level path consistent with that label sequence.

2. Insert a blank before, after, and between every character: l′ = [–, I, –, S, –, R, –, O, –]. Length = 2×4 + 1 = 9.

3. y = "APPLE" has length L = 5 and exactly one adjacent-repeated pair, "PP" (r = 1). The skip transition that lets a path jump over the blank between two consecutive labels is disallowed whenever those two labels are identical, so any valid path must actually spend a frame in the blank state between the two P's. Minimum T = L + r = 5 + 1 = 6.

4. α₁(2) = 0.600 is the accumulated probability of paths that, by frame 1, have already emitted "A" as their first character. The skip edge into α₂(4) = "B" means: at frame 2, the network jumps straight from having emitted "A" to emitting "B", with no separating blank frame in between — i.e., it represents the event "the speaker moved directly from character A's sound into character B's sound with no silence or held blank between them," which is completely normal in fluent speech.

5. Training never knows the true alignment, so it must give credit to every path consistent with the correct label — that is the whole point of the sum, it is what makes learning possible without alignment supervision. Decoding, by contrast, is being asked to search over all possible label sequences y (not paths for one fixed y), and evaluating the true best y exactly would require running the same expensive path-sum computation once for every candidate y in an unbounded space — intractable, so decoding falls back to cheaper approximations (greedy best-path, or beam search over partial label sequences).

6. Apply B: merge consecutive identical symbols "C,C" → "C" and "T,T" → "T", leaving "C, A, –, T", then delete the blank, giving "CAT". Yes — greedy decoding recovers the correct label here, because the single most probable path happened to collapse correctly. (This will not always happen: greedy decoding is only an approximation to the true argmax over label sequences, which is why beam search exists.)

Think About It

Think about this: How would you explain ctc loss: sequence-to-sequence without alignment to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind ctc loss: sequence-to-sequence without alignment, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.