6. Incremental ASR Partial-Result Stabilization

Problem

A streaming ASR model keeps re-guessing its transcript as more audio arrives, and early words can still get revised by later context. A downstream consumer wants to start reading words as soon as possible, but only the ones that have stopped changing.

Given the full sequence of partial transcripts (one per model update) and a stability window, determine, at each update, how many leading words have gone unchanged across the most recent updates and can safely be committed.

Source: src/6_asr_partial_stabilizer.py

def stable_prefix_lengths(partials: list[list[str]], stability_window: int) -> list[int]:
    ...

Examples:
>>> stable_prefix_lengths([["hi"], ["hi", "there"], ["hey", "there"]], 2)
[0, 1, 0]

>>> stable_prefix_lengths([["a"], ["a", "b"]], 3)
[0, 0]

Step-by-Step Approach

1. For each update index i, first check whether enough history exists: if i - stability_window + 1 < 0, fewer than stability_window updates have happened yet, so the answer is 0.
2. Otherwise slice out the trailing window partials[i - stability_window + 1 : i + 1] — exactly the most recent stability_window transcripts, ending at i.
3. The shared prefix can never be longer than the shortest transcript in that window, so cap the search at min(len(p) for p in window).
4. Walk word positions from 0 up to that cap; at each position, check whether every transcript in the window has the same word there. Stop at the first mismatch — that position is not part of the stable prefix, nor is anything after it.
5. The count of positions that matched before the first mismatch (or before hitting the length cap) is the stable prefix length for update i.
6. Repeat independently for every index; each window is recomputed from scratch, so a revision at one update only affects windows that include it, not the whole history.

The key insight is that "stable" means unanimous agreement across the entire recent window, not just agreement with the immediately preceding update — a word that flickers back and forth within the window is correctly treated as unstable even if the two most recent updates happen to agree on it.

Reference solution

def stable_prefix_lengths(partials: list[list[str]], stability_window: int) -> list[int]:
    result = []
    for i in range(len(partials)):
        window_start = i - stability_window + 1
        if window_start < 0:
            # not enough history yet to call anything stable
            result.append(0)
            continue
        window = partials[window_start : i + 1]
        # the shared prefix can't be longer than the shortest transcript in the window
        shortest_len = min(len(p) for p in window)
        lcp = 0
        for pos in range(shortest_len):
            word = window[0][pos]
            if all(p[pos] == word for p in window):
                lcp += 1
            else:
                break  # first mismatch caps the stable prefix here
        result.append(lcp)
    return result

Key Functions & Tricks

• i - stability_window + 1 < 0 — the guard that returns 0 before enough updates have accumulated.
• partials[window_start : i + 1] — slices exactly the trailing window ending at the current update.
• min(len(p) for p in window) — bounds the prefix search by the shortest transcript, avoiding index errors.
• all(p[pos] == word for p in window) — checks unanimous agreement at one position across the whole window in one expression.
• Break on first mismatch — a prefix by definition stops at the first disagreement, so there's no need to keep scanning past it.

How to Recognize This Pattern