What it actually does
You have a thousand audio frames and a nine-character transcript, and nobody has told you which frames belong to which character. Rather than guess an alignment, add a blank symbol meaning "emit nothing here" and score every alignment that collapses to the transcript, summing them all. There are exponentially many, but because the alignment can only move forward, the sum factorizes into a two-pass dynamic program that computes it exactly.
- The alignment between input and output is monotonic — the output is consumed left to right with no reordering, which is what makes the dynamic program possible and what rules out translation
- The input is at least as long as the target with one blank wedged between every pair of repeated labels; otherwise the likelihood is exactly zero
- Outputs are conditionally independent across frames given the input, so any dependency between adjacent labels must come from outside the model
- Frames arrive on a common clock — the encoder is frame-synchronous and emits exactly one distribution per input step
- One target label sequence per example is available, and no frame-level alignment is needed or assumed
Likelihood
Read the inner sum as a marginalization: the alignment is a latent variable and it is integrated out rather than estimated. The loss is then an ordinary negative log-likelihood of the label sequence given the input. Two things are worth pausing on. First, the product inside means the model treats frames as conditionally independent given the input — there is no term coupling one output to the next, which is the single most consequential thing about CTC. Second, the sum is exact: unlike an ELBO, nothing is bounded and nothing is sampled, because the monotonicity of the alignment gives the latent space a Markov structure a dynamic program can traverse.
- an alignment — exactly one symbol per input frame, blank allowed
- the collapse map: merge runs of identical symbols, then delete every blank
- every length-T alignment that collapses to the target — exponentially many of them
- the encoder softmax at frame t over the label set plus blank
- input length in frames; must be at least the target length plus one blank per repeated pair
How it is minimized
Forward-backward dynamic programming over the alignment lattice, differentiated in closed form and minimized by Adam
- the pre-softmax logit for label k at frame t — the gradient is taken here, not at the probability
- forward score: every path consuming the extended target up to position s by frame t
- backward score: every way frames t+1..T finish the extended target from position s
- the target with a blank inserted before, between and after every label; length S = 2U+1
- posterior occupancy — the probability that frame t emits k, summed over all alignments
- the marginal likelihood; a valid path ends on the final label or the trailing blank
The whole method is one observation: because the collapse map only ever moves forward through the extended target, the exponential sum over alignments has the structure of a chain, and forward-backward computes it exactly in O(T·S). The gradient then arrives in a form worth memorizing — softmax minus target, where the target is the posterior occupancy rather than a one-hot vector. That is the only structural difference between CTC and ordinary per-frame cross-entropy: same gradient shape, soft target computed by a dynamic program instead of read from a label file. Everything is done in log space with log-sum-exp; a thousand-frame utterance underflows to exactly zero in probability space, and the failure is a NaN rather than a warning.
time subsampling factor
How much the encoder downsamples in time; too aggressive and T drops below the extended target length, making the loss infinite (2x to 8x)
blank index
Not tuned but a hard contract — training, loss and decoder must agree, and a mismatch fails silently (0 or the last index)
beam width (decoding)
Width of the prefix beam search; 1 is greedy best-path decoding (1 to 500)
language-model weight
How much an external LM is trusted, since the loss provides no output-to-output dependency of its own (0.0 to 3.0)
insertion bonus
Counteracts the LM and blank bias systematically shortening the output (0.0 to 5.0)
gradient clip norm
CTC gradients spike hard on near-impossible alignments early in training (1 to 400)
The dynamic program is exact, so the gradient is unbiased and there is no estimator variance to fight — but the surface is the encoder’s, non-convex, with one characteristic and very recognizable failure. Early in training the cheapest way to reduce the loss is to predict blank everywhere, so the model does exactly that, the loss plateaus at the score of the all-blank path, and it can sit there for thousands of steps before any label emerges. The other failure is a length violation: if T is shorter than the extended target the likelihood is genuinely zero and the loss is infinite, and the usual mitigation of zeroing infinite losses quietly trains the model on a length-biased subset of the data. Converged CTC posteriors are also famously peaky — near-blank at almost every frame with narrow spikes — which is a property of the objective and not a defect, but it makes the alignments unsafe to read as timings.
O(T · S) per sequence for forward-backward, with S = 2U+1 — linear in both input and output length, and negligible beside the encoder that produced the frames. Sequential in T and fully parallel across the batch and across the state axis. Prefix beam decoding with a language model is a different matter and is usually the dominant inference cost.
How, where, and why it is used
Time-Series Forecasting
Not applicableThe collapse map deletes blanks and merges repeats, which discards duration and timing outright — the two things a forecast is made of. CTC produces an unaligned symbol sequence from a longer signal; forecasting asks for values at specified future instants, and there is no target sequence shorter than the input to marginalize over.
Anomaly Detection
Not applicableIt is a supervised loss requiring a target label sequence per example, with no notion of normality, density or outlyingness; the per-frame posterior is a confidence over labels, not a measure of how unusual the input was.
Optimization
Primary fitThe technique *is* a dynamic program, and it is the cleanest instance in this reference of exact inference over an exponential space. The lattice has T·S cells; the exponentially many alignments through it are summed by two linear passes because the recursion has only three legal predecessors per cell — stay, advance one, or skip the blank when the next label is not a repeat. Decoding then poses a second and separate optimization problem: find the highest-probability *label sequence*, which is not the collapse of the highest-probability *alignment*, because many alignments collapse to the same output. Prefix beam search is the tractable heuristic, and the gap between it and the true answer is real.
- Forward-backward over the alignment lattice as the canonical exact-marginalization dynamic program, alongside HMM inference and belief propagation
- Log-sum-exp in the semiring position of a sum-product recursion — swap it for max-plus and the same code becomes Viterbi
- Prefix beam search as a bounded-width heuristic over label sequences, distinct from the best-path shortcut that is exact only for the alignment
- Length and insertion penalties as explicit corrections to a scoring function that is biased by construction
Worth studying because it is a rare case where a hard combinatorial problem is solved exactly rather than approximated, and the reason is structural and legible: monotonicity of the alignment makes the latent space a chain. The contrast with variational inference is the lesson — a VAE bounds its marginal because the latent has no such structure, while CTC computes the same kind of quantity exactly because it does. The decoding half then teaches the opposite lesson: greedy best-path decoding is exact for the wrong question, and the distinction between the most likely alignment and the most likely output catches people who have used the loss for years.
- Run every recursion in log space with log-sum-exp; probability space underflows to zero in a few hundred frames and reports it as a NaN
- Precompute the skip-legality mask once per target rather than testing the repeat condition inside the frame loop
- Represent the extended target explicitly with blanks interleaved; the special cases people write to avoid materializing it are where the bugs live
- Swap log-sum-exp for max to obtain Viterbi alignment from identical code, which is the right way to extract timings if you need them
Check the dynamic program against brute-force enumeration over every alignment on a toy instance — a handful of frames and two labels — which is the only way to be sure the skip condition is right. Verify that the posterior occupancy sums to one at every frame; it is a cheap invariant that catches most implementation errors immediately. For decoding, compare greedy, prefix beam and exhaustive enumeration on short inputs where exhaustive is feasible, and read the gap as the cost of the heuristic.
- Allowing the skip transition into a repeated label, which silently over-counts paths and yields a loss that is too low but never obviously wrong
- Confusing best-path decoding with maximum-likelihood decoding — the first is exact for the alignment and merely a heuristic for the output
- Reading the peaky posterior as an alignment; it locates the spike, not the extent of the symbol
- Zeroing infinite losses on length-violating examples, which silently biases training toward short targets
Natural Language
Primary fitThe formulation automatic speech recognition was rebuilt on. An encoder turns a spectrogram into one distribution per frame over the character or subword set plus blank; CTC supplies the loss without any frame-level alignment, replacing the forced-alignment stage that HMM-based systems required. At inference, greedy decoding collapses the per-frame argmax, or a prefix beam search fuses in an external language model.
- End-to-end speech recognition, including the streaming systems where frame-synchronous output is the requirement rather than a preference
- Keyword spotting and wake-word detection, where the target is a single short label sequence in a long stream
- Phoneme recognition and pronunciation modelling, the task the technique was introduced on
- The alignment-free half of hybrid CTC/attention systems, where a CTC head regularizes an attention decoder and enforces monotonicity it does not otherwise have
It removed the requirement for a frame-aligned corpus, which was the practical bottleneck in speech for two decades — transcripts are cheap and alignments are not. Against it: the conditional independence across frames means the acoustic model carries no language model of its own, so an external LM is not a refinement but a necessity on open vocabulary, and a CTC system without one makes spelling errors no human would. It is also strictly monotonic, which is why the same era gave machine translation to attention-based encoder-decoders instead — reordering is exactly what CTC cannot express.
- Subword or character targets rather than words, which keeps the label set small and removes the unknown-token problem
- Pass true pre-padding input lengths into the loss; padded frames included in T inflate the marginal and corrupt every gradient in the batch
- Check the subsampled frame count against the extended target length per example before the batch is formed, not after the loss returns infinity
- Feed log-probabilities, not probabilities — every mainstream implementation expects log-softmax output and reports nothing if given the wrong one
Word and character error rate on a held-out set, always reported with the decoding configuration and the language model attached — a CTC model quoted without its LM and beam width is not a comparable number. Track the blank emission rate as a training diagnostic: a rate near one means the model is stuck on the all-blank plateau.
- Comparing CTC against an attention decoder without matching decode-time language models, which measures the LM rather than the acoustic model
- Blank index disagreeing between the loss and the decoder, which produces fluent nonsense with no error anywhere
- Expecting word timings from the posterior; the spikes are not extents, and Viterbi alignment is the correct tool
- Over-subsampling in time to save encoder compute, which makes long targets unrepresentable and the loss infinite
Computer Vision
ViableThe standard recognition head for text in images. A convolutional encoder reduces a cropped line image to a left-to-right sequence of column features, a recurrent or attention layer contextualizes them, and CTC trains the whole stack against the transcription alone — no character bounding boxes, which is the entire appeal. The reading order of a text line is monotonic, so the assumption CTC makes is genuinely true here rather than merely tolerated.
- Scene-text and document OCR recognition, where CTC has been the default head for line-level recognition
- Handwriting recognition, both offline images and online pen trajectories
- Licence-plate and meter reading, where the label set is small and constrained and the technique is hard to beat
- Continuous sign-language recognition, where the gloss sequence is monotonic in the video
The labelling economics are even better than in speech: annotating a transcription per line is minutes of work, annotating per-character boxes is hours, and CTC makes the difference free. On constrained alphabets — digits, plates, forms — the absence of an implicit language model barely matters, so the main objection to CTC largely disappears and it beats more elaborate heads at a fraction of the cost. It falls apart on curved, rotated or multi-line text, where the left-to-right monotonic assumption is simply false and a rectification stage or an attention decoder is required.
- Rectify and normalize line height before the encoder; CTC assumes a monotonic left-to-right reading order and cannot recover one that is not there
- Keep enough width after downsampling that the column count exceeds the character count with repeats — narrow images with long labels are the usual source of infinite loss
- Augment with the distortions the deployment actually contains, since the head is only as good as the column features it is handed
- Segment into lines before recognition rather than after; the technique has no way to express two lines at once
Character and word accuracy per line, stratified by image quality and by label length — aggregate accuracy hides that long lines fail disproportionately. Include an explicit count of examples rejected for length violation, which is otherwise invisible.
- Curved or rotated text violating monotonicity, which no amount of training fixes
- Aggressive width downsampling making long labels unrepresentable, seen as infinite loss on exactly the hardest examples
- Adjacent identical characters collapsing when the encoder resolution is too coarse to place a blank between them
- Evaluating on cropped ground-truth lines and deploying on detector output, where the accuracy drop comes from the detector rather than the head
What it costs to run
The loss itself is negligible — O(T·S) of scalar arithmetic against an encoder doing matrix products, typically a low single-digit percentage of step time even in a naive implementation. What costs is the encoder and the sequence length; the loss is only ever the bottleneck when it runs unbatched on CPU while the encoder is on the accelerator.
The loss does not exist at inference; what remains is the encoder plus a decode. Greedy best-path decoding is one argmax per frame and a collapse, which is microseconds and streams naturally — output can be emitted as frames arrive, which is the property that keeps CTC in production for streaming recognition. Prefix beam search with a language model is orders of magnitude more expensive and is usually the largest single line item in a CTC serving budget.
Driven by the encoder and the domain, not by the loss: quarterly or on acoustic or visual domain shift. The decoder-side language model is retrained far more often than the acoustic model, since vocabulary drifts faster than acoustics.
- Track the blank emission rate; a rise toward one is the all-blank collapse reappearing, and it is visible long before error rate moves
- Count examples rejected for length violation every epoch — a nonzero and growing count means subsampling and target length have drifted apart
- Assert that posterior occupancy sums to one per frame in a test, as a permanent guard on the forward-backward implementation
- Monitor error rate separately by target length; CTC degrades on long sequences first, and the aggregate hides it
- The blank index is a contract between training, loss and decoder. Off by one and the system produces confident nonsense with no error raised anywhere — the single most common CTC bug
- Every implementation expects log-probabilities; passing probabilities trains a model that converges to something plausible and wrong
- Input lengths must be the true pre-padding lengths. Padding counted into T adds alignments through padded frames and corrupts the gradient for the whole batch
- Zeroing infinite losses to keep training alive silently drops the length-violating examples, biasing the model toward short targets
- The loss assumes conditional independence, so a language model applied at decode time is part of the system and must be versioned with the acoustic model
Pros and cons, in context
Trains on unaligned pairs, removing the forced-alignment stage entirely
The whole reason it exists, and the reason end-to-end speech and OCR became practical — transcripts cost minutes to annotate and alignments cost hours. Worth nothing if you already have frame-level labels, in which case plain cross-entropy is simpler and stronger.
Marginalizes exactly rather than bounding or sampling
Unlike an ELBO or a policy-gradient estimator, the gradient is exact and has no variance to fight, because the monotonic latent space has chain structure. Directly comparable to HMM forward-backward, and the reason CTC training is boringly stable once past the blank plateau.
Frame-synchronous, so decoding streams
Output can be emitted as frames arrive, which is decisive for live captioning and dictation. An attention decoder must see the whole utterance before it emits anything, and no amount of engineering removes that.
A loss, not an architecture — the encoder is free
The same objective has served recurrent, convolutional and transformer encoders unchanged, so it survives architectural fashion. It also composes: a CTC head bolted onto an attention model regularizes it and enforces monotonicity the attention lacks.
Cheap enough to ignore
O(T·S) beside an encoder doing matrix products means the loss is a rounding error in the training budget. Relevant because it makes the exactness free — there is no accuracy-for-speed trade to consider.
Conditional independence across frames means no implicit language model
Decisive on open-vocabulary speech, where a CTC system without an external LM makes spelling errors no human would; nearly irrelevant on constrained alphabets like digits or licence plates, where the objection largely evaporates.
Strictly monotonic alignment
Rules out translation, any reordering, and curved or multi-line text. Exactly why machine translation went to attention-based encoder-decoders while speech stayed with CTC — the assumption is true in one domain and false in the other.
Peaky posteriors make the alignment unsafe to read
Fine when the transcript is all you want; wrong tool when you need timings or extents, and people ship word-level timestamps from CTC spikes without realizing the spike marks a position, not a duration. Viterbi over the same lattice is the correct tool.
Silent failure on length violation
A target longer than the input has genuinely zero likelihood and infinite loss. The standard mitigation zeroes those batches, which keeps training alive and biases the model toward short targets without ever logging that it happened.
The blank plateau at the start of training
Predicting blank everywhere is the locally cheapest thing to do, so the model does it and can stay there for thousands of steps. Harmless once recognized, but indistinguishable from a broken implementation if you have not seen it before.
Intuitive, idiomatic, optimized
The same algorithm in three languages, each progressing through Kent Beck's three stages. Every optimization names the lever it pulls and the trade-off it accepts — cost profiles are illustrative, not measured benchmarks.
The math, transcribed literally. No dependencies.
"""CTC loss and gradient, transcribed the way the definition reads.
The alignment between T input frames and U output labels is unknown. CTC adds
a blank symbol meaning "emit nothing here", scores every alignment that
collapses to the target, and sums them. There are exponentially many, but the
collapse map only moves forward, so a two-pass dynamic program computes the
sum exactly.
Probability space, no log-sum-exp, no libraries. This underflows to zero past
a few hundred frames, which is the first thing the next stage fixes.
"""
import math
BLANK = 0
def extend_with_blanks(targets):
"""[a, b] becomes [blank, a, blank, b, blank]. Length 2U + 1."""
extended = [BLANK]
for label in targets:
extended.append(label)
extended.append(BLANK)
return extended
def ctc_loss_and_grad(probs, targets):
"""probs is T rows of K per-frame probabilities. Returns (loss, dL/dlogits)."""
num_frames = len(probs)
num_labels = len(probs[0])
ext = extend_with_blanks(targets)
num_states = len(ext)
# ----- forward pass -------------------------------------------------
# alpha[t][s]: total probability of every path that has consumed the
# extended target up to position s after t + 1 frames, with frame t
# emitting ext[s]. The emission at t is included in the value.
alpha = [[0.0] * num_states for _ in range(num_frames)]
alpha[0][0] = probs[0][BLANK]
if num_states > 1:
alpha[0][1] = probs[0][ext[1]]
for frame in range(1, num_frames):
for state in range(num_states):
# Three legal predecessors and no more: stay where you are,
# advance one position, or skip a blank entirely.
total = alpha[frame - 1][state]
if state >= 1:
total += alpha[frame - 1][state - 1]
# The skip is legal only into a real label, and only when that
# label is not a repeat of the one two positions back: two
# identical labels in a row MUST keep the blank between them,
# or the collapse map would merge them into one.
if state >= 2 and ext[state] != BLANK and ext[state] != ext[state - 2]:
total += alpha[frame - 1][state - 2]
alpha[frame][state] = total * probs[frame][ext[state]]
# A valid path ends on the final label or on the trailing blank.
likelihood = alpha[num_frames - 1][num_states - 1]
if num_states > 1:
likelihood += alpha[num_frames - 1][num_states - 2]
# ----- backward pass ------------------------------------------------
# beta[t][s]: probability that frames t + 1 .. T finish the extended
# target from position s, given frame t emitted ext[s]. Excludes the
# emission at t, so alpha * beta is exactly the paths through (t, s).
beta = [[0.0] * num_states for _ in range(num_frames)]
beta[num_frames - 1][num_states - 1] = 1.0
if num_states > 1:
beta[num_frames - 1][num_states - 2] = 1.0
for frame in range(num_frames - 2, -1, -1):
for state in range(num_states):
total = beta[frame + 1][state] * probs[frame + 1][ext[state]]
if state + 1 < num_states:
total += beta[frame + 1][state + 1] * probs[frame + 1][ext[state + 1]]
if (
state + 2 < num_states
and ext[state + 2] != BLANK
and ext[state + 2] != ext[state]
):
total += beta[frame + 1][state + 2] * probs[frame + 1][ext[state + 2]]
beta[frame][state] = total
# ----- gradient -----------------------------------------------------
# gamma[t][s] = alpha * beta / Z is the posterior probability that frame t
# sits at extended position s. Summed over s it is 1.0 for every frame,
# which is the cheapest correctness check there is.
grad = [[0.0] * num_labels for _ in range(num_frames)]
for frame in range(num_frames):
occupancy = [0.0] * num_labels
for state in range(num_states):
posterior = alpha[frame][state] * beta[frame][state] / likelihood
occupancy[ext[state]] += posterior
# Softmax minus target, where the target is the posterior occupancy
# instead of a one-hot vector. That single substitution is the whole
# difference between CTC and per-frame cross-entropy.
for label in range(num_labels):
grad[frame][label] = probs[frame][label] - occupancy[label]
return -math.log(likelihood), grad
def greedy_decode(probs):
"""Best path: argmax per frame, merge runs, then drop blanks.
Exact for the most likely ALIGNMENT and merely a heuristic for the most
likely OUTPUT, because many alignments collapse to the same label
sequence and this counts only the single best one.
"""
best_per_frame = [max(range(len(row)), key=row.__getitem__) for row in probs]
collapsed = []
previous = None
for label in best_per_frame:
if label != previous and label != BLANK:
collapsed.append(label)
previous = label
return collapsed
def brute_force_likelihood(probs, targets):
"""Enumerate every alignment. Only tractable for a toy case - and the only
way to be certain the skip condition above is right."""
num_frames = len(probs)
num_labels = len(probs[0])
total = 0.0
def collapse(path):
out = []
previous = None
for label in path:
if label != previous and label != BLANK:
out.append(label)
previous = label
return out
def walk(path):
nonlocal total
if len(path) == num_frames:
if collapse(path) == list(targets):
score = 1.0
for frame, label in enumerate(path):
score *= probs[frame][label]
total += score
return
for label in range(num_labels):
walk(path + [label])
walk([])
return total
O(T * S) cells, each a handful of Python float operations, plus a full K-wide gradient row per frame. Illustrative, not a measured benchmark: a 1000-frame utterance is roughly a million interpreter iterations, and underflows to a NaN before it finishes being slow.
How this language actually wants it written.
"""CTC in log space, with the precondition that makes the loss finite checked.
Identical dynamic program. The arithmetic moves into log space so a long
utterance does not underflow, the length precondition is asserted rather than
discovered as an infinity, and the two things that always travel together -
loss and gradient - are returned together.
"""
from __future__ import annotations
import math
from typing import NamedTuple, Sequence
BLANK: int = 0
NEG_INF: float = -math.inf
class CtcResult(NamedTuple):
"""Loss, gradient and marginal share one forward-backward pass."""
loss: float
logit_grad: list[list[float]]
log_likelihood: float
class AlignmentImpossible(ValueError):
"""No alignment exists. Raised, rather than returned as an infinite loss."""
def log_add(left: float, right: float) -> float:
"""log(exp(left) + exp(right)), stable and total on negative infinity."""
if left == NEG_INF:
return right
if right == NEG_INF:
return left
high, low = (left, right) if left > right else (right, left)
return high + math.log1p(math.exp(low - high))
def extend_with_blanks(targets: Sequence[int]) -> list[int]:
"""Interleave blanks: [a, b] becomes [blank, a, blank, b, blank]."""
extended: list[int] = [BLANK]
for label in targets:
extended.append(label)
extended.append(BLANK)
return extended
def minimum_frames(targets: Sequence[int]) -> int:
"""Target length plus one forced blank per repeated adjacent pair."""
repeats = sum(1 for left, right in zip(targets, targets[1:]) if left == right)
return len(targets) + repeats
def skip_allowed(extended: Sequence[int]) -> list[bool]:
"""Precompute the repeat condition once per target, not once per cell."""
return [
state >= 2
and extended[state] != BLANK
and extended[state] != extended[state - 2]
for state in range(len(extended))
]
def _forward(
log_probs: Sequence[Sequence[float]],
extended: Sequence[int],
can_skip: Sequence[bool],
) -> list[list[float]]:
num_frames, num_states = len(log_probs), len(extended)
log_alpha = [[NEG_INF] * num_states for _ in range(num_frames)]
log_alpha[0][0] = log_probs[0][BLANK]
if num_states > 1:
log_alpha[0][1] = log_probs[0][extended[1]]
for frame in range(1, num_frames):
previous = log_alpha[frame - 1]
current = log_alpha[frame]
for state in range(num_states):
total = previous[state]
if state >= 1:
total = log_add(total, previous[state - 1])
if can_skip[state]:
total = log_add(total, previous[state - 2])
current[state] = total + log_probs[frame][extended[state]]
return log_alpha
def _backward(
log_probs: Sequence[Sequence[float]],
extended: Sequence[int],
can_skip: Sequence[bool],
) -> list[list[float]]:
num_frames, num_states = len(log_probs), len(extended)
log_beta = [[NEG_INF] * num_states for _ in range(num_frames)]
log_beta[num_frames - 1][num_states - 1] = 0.0
if num_states > 1:
log_beta[num_frames - 1][num_states - 2] = 0.0
for frame in range(num_frames - 2, -1, -1):
nxt = log_beta[frame + 1]
emit = log_probs[frame + 1]
current = log_beta[frame]
for state in range(num_states):
total = nxt[state] + emit[extended[state]]
if state + 1 < num_states:
total = log_add(total, nxt[state + 1] + emit[extended[state + 1]])
if state + 2 < num_states and can_skip[state + 2]:
total = log_add(total, nxt[state + 2] + emit[extended[state + 2]])
current[state] = total
return log_beta
def ctc_loss(
log_probs: Sequence[Sequence[float]],
targets: Sequence[int],
) -> CtcResult:
"""Negative log marginal likelihood of the target over every alignment.
log_probs must be log-softmax output, T rows of K. Passing probabilities
instead trains a model that converges to something plausible and wrong,
and nothing in the arithmetic will complain.
"""
# Guard clauses first. Each of these is a real production failure and each
# one is silent if it is allowed through.
if not log_probs:
raise AlignmentImpossible("no frames were supplied")
if BLANK in targets:
raise AlignmentImpossible("the blank index cannot appear in the target")
required = minimum_frames(targets)
if len(log_probs) < required:
raise AlignmentImpossible(
f"{len(log_probs)} frames cannot cover a target needing {required}"
)
extended = extend_with_blanks(targets)
can_skip = skip_allowed(extended)
num_frames, num_states = len(log_probs), len(extended)
log_alpha = _forward(log_probs, extended, can_skip)
log_beta = _backward(log_probs, extended, can_skip)
log_z = log_alpha[num_frames - 1][num_states - 1]
if num_states > 1:
log_z = log_add(log_z, log_alpha[num_frames - 1][num_states - 2])
if log_z == NEG_INF:
raise AlignmentImpossible("the lattice admits no path to the target")
num_labels = len(log_probs[0])
logit_grad: list[list[float]] = []
for frame in range(num_frames):
occupancy = [0.0] * num_labels
for state in range(num_states):
log_gamma = log_alpha[frame][state] + log_beta[frame][state] - log_z
if log_gamma != NEG_INF:
occupancy[extended[state]] += math.exp(log_gamma)
logit_grad.append(
[
math.exp(log_probs[frame][label]) - occupancy[label]
for label in range(num_labels)
]
)
return CtcResult(loss=-log_z, logit_grad=logit_grad, log_likelihood=log_z)
def occupancy_sums_to_one(result: CtcResult, tolerance: float = 1e-6) -> bool:
"""Permanent invariant: the gradient row must sum to zero at every frame.
Softmax sums to one, posterior occupancy sums to one, so the difference
sums to zero. Cheapest possible guard on a forward-backward pass, and it
catches nearly every way the skip condition can be written wrongly.
"""
return all(abs(sum(row)) < tolerance for row in result.logit_grad)
What changed: Every recursion moves into log space with a log-sum-exp that is total on negative infinity, which is not a refinement but the difference between a function that works on real utterances and one that returns NaN past a few hundred frames. The length precondition — target length plus one blank per repeated pair — is checked before any work rather than surfacing as an infinite loss, and it is raised as a specific exception so a caller can drop the example deliberately instead of zeroing infinities and silently training on a length-biased subset. The repeat condition governing the skip transition is precomputed once per target rather than re-evaluated in every cell, which removes the place that condition is most often written wrongly. Loss, gradient and marginal come back in one NamedTuple because they are produced by one pass and separating them invites a second.
Same O(T * S) cells, now three log_add calls each instead of three multiplications. Illustrative, not a measured benchmark: log space costs perhaps two to three times the arithmetic and buys numerical validity at any sequence length, which is not a trade so much as a correction.
Faster, and the justification for each change.
"""Batched CTC in log space. The frame loop stays; everything inside it goes.
The recursion over frames is genuinely sequential - frame t needs frame t - 1
and no reformulation changes that. Everything else is not. The state axis
becomes three shifted slices added together, the batch axis becomes a leading
dimension, and T * S * B interpreter iterations become T iterations over whole
arrays.
"""
from __future__ import annotations
import numpy as np
from numpy.typing import NDArray
BLANK = 0
FLOAT = np.float32
class BatchedCtc:
"""Owns the scratch buffers. Allocating them once is the optimization."""
def __init__(self, batch: int, num_states: int, num_labels: int) -> None:
shape = (batch, num_states)
self._num_labels = num_labels
# Three shifted views of the previous frame, plus the emission row.
# Pre-allocated so the frame loop never touches the allocator.
self._stay = np.empty(shape, dtype=FLOAT)
self._step = np.empty(shape, dtype=FLOAT)
self._skip = np.empty(shape, dtype=FLOAT)
self._emit = np.empty(shape, dtype=FLOAT)
self._scratch = np.empty(shape, dtype=FLOAT)
def __call__(
self,
log_probs: NDArray[np.float32],
targets: NDArray[np.int32],
input_lengths: NDArray[np.int32],
target_lengths: NDArray[np.int32],
) -> tuple[NDArray[np.float32], NDArray[np.float32]]:
"""log_probs is (T, B, K), time-major so one frame is contiguous.
Time-major is not a stylistic choice: the inner operation reads a whole
frame across the batch, and in batch-major layout that read is strided.
"""
num_frames, batch, num_labels = log_probs.shape
log_probs = np.ascontiguousarray(log_probs, dtype=FLOAT)
max_target = targets.shape[1]
num_states = 2 * max_target + 1
# ext[b, s]: extended targets for the whole batch at once, blanks on
# even positions. One vectorized write instead of B * S appends.
ext = np.full((batch, num_states), BLANK, dtype=np.int32)
ext[:, 1::2] = targets
# Skip legality is a property of the target, not of the frame, so it
# is computed once for the batch rather than B * T * S times.
can_skip = np.zeros((batch, num_states), dtype=bool)
can_skip[:, 2:] = (ext[:, 2:] != BLANK) & (ext[:, 2:] != ext[:, :-2])
states = np.arange(num_states, dtype=np.int32)
live = states[None, :] < (2 * target_lengths[:, None] + 1)
rows = np.arange(batch, dtype=np.int32)[:, None]
log_alpha = np.full((num_frames, batch, num_states), -np.inf, dtype=FLOAT)
log_alpha[0, :, 0] = log_probs[0, rows[:, 0], BLANK]
log_alpha[0, :, 1] = log_probs[0, rows[:, 0], ext[:, 1]]
self._recurse(log_probs, ext, can_skip, live, rows, log_alpha, forward=True)
log_beta = np.full((num_frames, batch, num_states), -np.inf, dtype=FLOAT)
end = input_lengths - 1
tail = 2 * target_lengths
log_beta[end, rows[:, 0], tail] = 0.0
log_beta[end, rows[:, 0], np.maximum(tail - 1, 0)] = 0.0
self._recurse(log_probs, ext, can_skip, live, rows, log_beta, forward=False)
# Gather the marginal from each sequence's own final frame, not from a
# shared T - 1 that padded sequences never reach.
final = log_alpha[end, rows[:, 0], :]
log_z = np.logaddexp(
final[rows[:, 0], tail], final[rows[:, 0], np.maximum(tail - 1, 0)]
)
# gamma = alpha + beta - Z, exponentiated and scattered onto labels.
log_gamma = log_alpha + log_beta - log_z[None, :, None]
np.copyto(log_gamma, -np.inf, where=~live[None, :, :])
gamma = np.exp(log_gamma, dtype=FLOAT)
grad = np.exp(log_probs, dtype=FLOAT)
frame_ids = np.arange(num_frames, dtype=np.int32)[:, None, None]
batch_ids = np.arange(batch, dtype=np.int32)[None, :, None]
# Many states map to the same label, so this must accumulate rather
# than assign - the one place a plain fancy-index write is wrong.
np.add.at(
grad,
(frame_ids, batch_ids, np.broadcast_to(ext[None, :, :], gamma.shape)),
-gamma,
)
return -log_z, grad
def _recurse(
self,
log_probs: NDArray[np.float32],
ext: NDArray[np.int32],
can_skip: NDArray[np.bool_],
live: NDArray[np.bool_],
rows: NDArray[np.int32],
table: NDArray[np.float32],
forward: bool,
) -> None:
"""One sequential sweep. Both directions are the same three shifts."""
num_frames = log_probs.shape[0]
order = range(1, num_frames) if forward else range(num_frames - 2, -1, -1)
offset = -1 if forward else 1
for frame in order:
previous = table[frame + offset]
emit_frame = log_probs[frame if forward else frame + 1]
# Gather every state's emission for the whole batch in one
# indexed read: (B, S) out of a (B, K) frame, no per-state loop.
np.copyto(self._emit, emit_frame[rows, ext])
if forward:
# Fused: the emission is added once, after the three-way
# log-sum-exp, so no intermediate frame array is materialized.
self._stay[...] = previous
self._step[:, 0] = -np.inf
self._step[:, 1:] = previous[:, :-1]
self._skip[:, :2] = -np.inf
self._skip[:, 2:] = previous[:, :-2]
np.copyto(self._skip, -np.inf, where=~can_skip)
np.logaddexp(self._stay, self._step, out=self._scratch)
np.logaddexp(self._scratch, self._skip, out=self._scratch)
self._scratch += self._emit
else:
# Backward carries the emission on the successor, so the shift
# and the add happen together on the same buffers.
self._stay[...] = previous
self._stay += self._emit
self._step[:, -1] = -np.inf
self._step[:, :-1] = self._stay[:, 1:]
self._skip[:, -2:] = -np.inf
self._skip[:, :-2] = self._stay[:, 2:]
np.copyto(self._skip[:, :-2], -np.inf, where=~can_skip[:, 2:])
np.logaddexp(self._stay, self._step, out=self._scratch)
np.logaddexp(self._scratch, self._skip, out=self._scratch)
np.copyto(self._scratch, -np.inf, where=~live)
table[frame] = self._scratch
What changed: The state axis is the whole win. In the literal version the inner loop tests the skip condition and reads three neighbours per cell; here the three predecessors become three shifted slices of the previous frame, added with a pair of log-sum-exp calls that write into pre-allocated buffers, so the frame loop performs no allocation at all. The skip mask is computed once per target rather than once per cell, since it is a property of the label sequence and nothing in the recursion changes it. The batch becomes a leading dimension, and the layout is time-major on purpose: the inner operation reads one frame across all sequences, which is contiguous time-major and strided the other way. What remains sequential is the sweep over T, which is inherent — frame t depends on frame t minus one, and no rearrangement removes that dependency.
Eliminate Python-level loops over samples
The state and batch axes both become array dimensions, leaving one interpreter iteration per frame instead of one per (sequence, frame, state) cell.
Trade-off: Every sequence in the batch is padded to the longest target, so a batch with one long transcript does wasted work on all the others — length bucketing becomes a prerequisite rather than a nicety.
Pre-allocate output arrays and use in-place operations
The three shift buffers and the log-sum-exp accumulator are allocated once in the constructor, so the sequential frame sweep never enters the allocator.
Trade-off: The class now holds mutable state sized to a specific batch and target shape, so it is neither reentrant nor safely shared across threads, and a shape change means rebuilding it.
Ensure contiguous memory layout and a single dtype
Time-major float32 makes each frame read contiguous and halves the bandwidth of the two full lattices against float64.
Trade-off: float32 log-sum-exp over thousands of frames accumulates visible error, and this is exactly the arithmetic where precision matters — the reference implementations keep the lattice in float32 but the log-sum-exp reduction in float64 for that reason.
T sequential steps over (B, S) arrays instead of T * B * S interpreter iterations. Illustrative, not a measured benchmark: the remaining hot spot is the np.add.at scatter for the gradient, which is unbuffered and slower than the recursion it follows — the reason production CTC ships as a fused CUDA kernel rather than as array code.