Viterbi and BIO validity

After the encoderencoderThe part of a transformer that turns input tokens into contextualized vector representations. Mailwoman's classifier is a small encoder-only transformer (~30M parameters). produces per-tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. emission logitsemission logitThe per-token, per-label logit the transformer encoder emits before any external prior is added — the model's own evidence for each label at each position. and the FSTFST (finite-state transducer). A compact automaton that reads an input sequence and emits an output sequence. Mailwoman encodes gazetteer names and street affixes as FSTs for fast prefix matching and prior injection without search overhead. priors add their additive biasesadditive biasA logit adjustment added before softmax from a prior or external knowledge source, typically soft-capped so it influences but never overrides the model's prediction. The mechanism behind shallow fusion., there's still a problem: the per-tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. argmax produces structurally invalid sequences.

Concretely: BIO labelsBIO tagging (Begin-Inside-Outside). A token-level labeling scheme where each token is tagged as B-X (beginning of an entity of type X), I-X (inside an entity of type X), or O (outside any entity). Mailwoman uses BIO over SentencePiece tokens to annotate address components. follow a grammar. An I-X labelcomponent tagOne of the 33 labels in Mailwoman's address schema — street, locality, region, postcode, house_number, unit, po_box, country, venue, intersection, and others. Each parsed span carries exactly one component tag. has to come after a B-X (begin of the same tag) or another I-X. The sequence O B-street O I-street is invalid — the second street tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. starts in the middle of a spanspanA contiguous range of characters or tokens in the input string, tagged with an address component type (street, locality, postcode, etc.). Parsed addresses are represented as collections of spans, possibly nested in a tree. with no begin.

The ViterbiViterbi decodingA dynamic programming algorithm that finds the most likely sequence of hidden states (labels) given a sequence of observations (token emissions). Mailwoman uses Viterbi over a linear-chain CRF to produce globally coherent BIO label sequences from per-token model scores. decoderdecoderIn a transformer encoder-decoder model, the part that produces output sequences. Mailwoman's classifier is encoder-only (no decoder); the 'CRF decoder' is a different thing — a structured-prediction layer that picks the best label sequence from the encoder's outputs. enforces this grammar globally. This article explains how, why it matters, and why no learned CRFCRF (Conditional Random Field). A statistical modeling method that predicts structured outputs by modeling dependencies between adjacent labels. Mailwoman uses a linear-chain CRF as the Viterbi decoder at inference time to enforce BIO label consistency — a B-street must be followed by I-street or O, never I-locality. transitions ship alongside it today — see CRF decoder for the short version, and How Mailwoman parses an address for this step in the context of a full parseaddress parsingThe process of decomposing a free-text postal address string into structured components — house number, street name, locality, region, postcode, and country — so a geocoder can resolve them to coordinates..

The BIO label space

Mailwoman's Stage 3 schema has 33 BIO labelsBIO tagging (Begin-Inside-Outside). A token-level labeling scheme where each token is tagged as B-X (beginning of an entity of type X), I-X (inside an entity of type X), or O (outside any entity). Mailwoman uses BIO over SentencePiece tokens to annotate address components.:

O
B-country  I-country
B-region  I-region
B-locality  I-locality
B-dependent_locality  I-dependent_locality
B-postcode  I-postcode
B-subregion  I-subregion
B-cedex  I-cedex
B-venue  I-venue
B-street  I-street
B-house_number  I-house_number
B-street_prefix  I-street_prefix
B-street_suffix  I-street_suffix
B-unit  I-unit
B-po_box  I-po_box
B-intersection_a  I-intersection_a
B-intersection_b  I-intersection_b

O means "no tag" (a comma, whitespace tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words., or word that doesn't contribute to any component). Every other labelcomponent tagOne of the 33 labels in Mailwoman's address schema — street, locality, region, postcode, house_number, unit, po_box, country, venue, intersection, and others. Each parsed span carries exactly one component tag. is paired — a B-X starts a spanspanA contiguous range of characters or tokens in the input string, tagged with an address component type (street, locality, postcode, etc.). Parsed addresses are represented as collections of spans, possibly nested in a tree. of type X, and I-X continues that spanspanA contiguous range of characters or tokens in the input string, tagged with an address component type (street, locality, postcode, etc.). Parsed addresses are represented as collections of spans, possibly nested in a tree..

What "valid" means

A labelcomponent tagOne of the 33 labels in Mailwoman's address schema — street, locality, region, postcode, house_number, unit, po_box, country, venue, intersection, and others. Each parsed span carries exactly one component tag. sequence is valid under BIO grammar iff:

• The first non-O labelcomponent tagOne of the 33 labels in Mailwoman's address schema — street, locality, region, postcode, house_number, unit, po_box, country, venue, intersection, and others. Each parsed span carries exactly one component tag. is a B-X (not I-X).
• Every I-X is preceded by B-X or I-X (same tag).
• No I-X follows B-Y or I-Y where X ≠ Y.
• O can appear anywhere.

So [O, B-street, I-street, O, B-locality, B-region] is valid. [B-street, I-locality] is invalid (mid-tag switch).

If you just take per-tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. argmax, you get whatever each tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words.'s highest-probability labelcomponent tagOne of the 33 labels in Mailwoman's address schema — street, locality, region, postcode, house_number, unit, po_box, country, venue, intersection, and others. Each parsed span carries exactly one component tag. is — regardless of validity. That can produce nonsense like [B-street, I-locality, O] if the encoderencoderThe part of a transformer that turns input tokens into contextualized vector representations. Mailwoman's classifier is a small encoder-only transformer (~30M parameters).'s emissions push the second tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. toward I-locality and the first toward B-street.

What Viterbi does

ViterbiViterbi decodingA dynamic programming algorithm that finds the most likely sequence of hidden states (labels) given a sequence of observations (token emissions). Mailwoman uses Viterbi over a linear-chain CRF to produce globally coherent BIO label sequences from per-token model scores. searches for the highest-scoring labelcomponent tagOne of the 33 labels in Mailwoman's address schema — street, locality, region, postcode, house_number, unit, po_box, country, venue, intersection, and others. Each parsed span carries exactly one component tag. SEQUENCE, not per-tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. argmaxes:

best_path = argmax over all valid sequences s of (
  sum over t of emission_score(token_t, label_t)
  + sum over (t, t+1) of transition_score(label_t, label_{t+1})
)

The emission scoresemission logitThe per-token, per-label logit the transformer encoder emits before any external prior is added — the model's own evidence for each label at each position. come from the encoderencoderThe part of a transformer that turns input tokens into contextualized vector representations. Mailwoman's classifier is a small encoder-only transformer (~30M parameters). + priors. The transition scores come from a single source today: the structural BIO mask (always present) — -∞ for invalid transitions, 0 for valid ones. That's the whole matrix. There's no second, learned layerlayerOne transformer block — attention plus a feed-forward network, with normalization and residual connections — applied to every position. Stacking layers lets the model build up richer representations; Mailwoman's encoder has 6. of transition scores stacked on top of it; see CRF decoder for why — CRFCRF (Conditional Random Field). A statistical modeling method that predicts structured outputs by modeling dependencies between adjacent labels. Mailwoman uses a linear-chain CRF as the Viterbi decoder at inference time to enforce BIO label consistency — a B-street must be followed by I-street or O, never I-locality. trainingtrainingThe process of adjusting a model's parameters so its predictions match labeled examples, by repeatedly measuring error and nudging the weights to reduce it. Distinct from inference, when the trained model is run on new input. was tried, destabilized repeatedly, and has been permanently disabled (CE-only) since v0.6.3.

The output is a valid labelcomponent tagOne of the 33 labels in Mailwoman's address schema — street, locality, region, postcode, house_number, unit, po_box, country, venue, intersection, and others. Each parsed span carries exactly one component tag. sequence that maximizes the total score. Per-tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. argmaxes that violate BIO are replaced with the globally-best valid choice.

A concrete example

123 Main St:

Position	TokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words.	Per-tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. argmax	Argmax score	ViterbiViterbi decodingA dynamic programming algorithm that finds the most likely sequence of hidden states (labels) given a sequence of observations (token emissions). Mailwoman uses Viterbi over a linear-chain CRF to produce globally coherent BIO label sequences from per-token model scores. pick
0	123	B-house_number (0.95)	0.95	B-house_number
1	Main	I-locality (0.4)	0.4	B-street (next-best, 0.35)
2	St	I-street (0.85)	0.85	I-street

The per-tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. argmax for Main was I-locality — but that violates BIO because I-locality can't follow B-house_number. ViterbiViterbi decodingA dynamic programming algorithm that finds the most likely sequence of hidden states (labels) given a sequence of observations (token emissions). Mailwoman uses Viterbi over a linear-chain CRF to produce globally coherent BIO label sequences from per-token model scores. rejects that sequence and picks the next-best valid option: B-street with score 0.35. The total B-house_number + B-street + I-street sequence scores higher than any alternative valid sequence.

Why the tree builder needs valid BIO

The tree builder that turns BIO sequences into AddressTrees assumes valid BIO. It walks the sequence, opens a new node on B-X, extends the current node on I-X, closes on transition to a different tag or O. If the BIO is invalid, the tree builder either drops tokenstokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. (orphan I-X becomes part of the previous spanspanA contiguous range of characters or tokens in the input string, tagged with an address component type (street, locality, postcode, etc.). Parsed addresses are represented as collections of spans, possibly nested in a tree.'s value) or produces structurally wrong output.

ViterbiViterbi decodingA dynamic programming algorithm that finds the most likely sequence of hidden states (labels) given a sequence of observations (token emissions). Mailwoman uses Viterbi over a linear-chain CRF to produce globally coherent BIO label sequences from per-token model scores. prevents this. The tree builder always sees a valid sequence, and the resulting AddressTree is structurally correct (even when the labelscomponent tagOne of the 33 labels in Mailwoman's address schema — street, locality, region, postcode, house_number, unit, po_box, country, venue, intersection, and others. Each parsed span carries exactly one component tag. themselves might be wrong about the address content).

When the structural mask is insufficient

The mask says "this transition is structurally allowed." It doesn't say "this transition is statistically likely."

Consider: B-region → B-locality is structurally valid. So is B-region → B-postcode. But in real addresses, region is almost always followed by postcode (MA 02101), not another localitylocalityThe city / town / settlement component of an address: a populated place sitting between region and neighbourhood in the hierarchy.. The structural mask treats both as equally allowed.

A learned transition matrixtransition matrixThe CRF's learned table of per-label-pair scores. It encodes which BIO transitions are preferred or forbidden — e.g. that an I-tag must follow a matching B- or I-. could in principle encode that statistical preference — after trainingtrainingThe process of adjusting a model's parameters so its predictions match labeled examples, by repeatedly measuring error and nudging the weights to reduce it. Distinct from inference, when the trained model is run on new input., it would score B-region → B-postcode higher than B-region → B-locality, and ViterbiViterbi decodingA dynamic programming algorithm that finds the most likely sequence of hidden states (labels) given a sequence of observations (token emissions). Mailwoman uses Viterbi over a linear-chain CRF to produce globally coherent BIO label sequences from per-token model scores. would prefer the more common sequence. Mailwoman doesn't ship one. ViterbiViterbi decodingA dynamic programming algorithm that finds the most likely sequence of hidden states (labels) given a sequence of observations (token emissions). Mailwoman uses Viterbi over a linear-chain CRF to produce globally coherent BIO label sequences from per-token model scores. runs on emission scores alone, which is what ships today. It works well enough because the encoderencoderThe part of a transformer that turns input tokens into contextualized vector representations. Mailwoman's classifier is a small encoder-only transformer (~30M parameters).'s emissions already carry most of the sequencing signal via attentionattentionThe core mechanism inside a transformer encoder. Each token's representation is updated by looking at every other token, with learned weights deciding how much each one matters. — a learned transition layerlayerOne transformer block — attention plus a feed-forward network, with normalization and residual connections — applied to every position. Stacking layers lets the model build up richer representations; Mailwoman's encoder has 6. would be an additive refinement on top of that, not a replacement for it.

Why there's no learned CRF

Mailwoman tried this. A trainable CRFCRF (Conditional Random Field). A statistical modeling method that predicts structured outputs by modeling dependencies between adjacent labels. Mailwoman uses a linear-chain CRF as the Viterbi decoder at inference time to enforce BIO label consistency — a B-street must be followed by I-street or O, never I-locality. shipped in v3.0.0, and StagestageOne of the dataflow stages in the runtime pipeline (normalize, locale gate, kind classify, phrase group, token classify, sequence correct, reconcile, resolve). Distinct from tier (model vocabulary) and phase (plan milestone). 3's 33×33 transition matrixtransition matrixThe CRF's learned table of per-label-pair scores. It encodes which BIO transitions are preferred or forbidden — e.g. that an I-tag must follow a matching B- or I-. (masked -∞ entries) was re-attempted more than once — including a run that hit NaNNaN (not a number). A floating-point result for an undefined operation (log of a negative, 0/0). Appearing in the training loss usually halts the run; recovering from it follows the NaN protocol. gradientsgradientThe direction and rate at which the loss would change if each parameter were nudged. Training follows the gradient downhill to reduce error. Huge gradients are tamed by gradient clipping. traced to bf16bf16 (bfloat16). A 16-bit floating-point format used during training. Half the memory of fp32 with similar numeric range, which lets the training batch fit on the lab's GPU. precisionprecisionOf the spans the model labeled as a given tag, the fraction it got right. High precision means few false positives. Paired with recall to compute F1. on the masked logsumexp, described in the fp32-CRF diagnostic. Every attempt after v0.4.0's lossloss functionA number measuring how wrong the model's predictions are on a batch of examples. Training minimizes it. Mailwoman's loss combines per-token negative log-likelihood with the CRF sequence loss.-scale fix still diverged, three times over. The recipe first went CE-only (crf_loss_weight: 0.0) at v0.5.0, and apart from those labeled diagnostic reactivations (the v0.6.2 fp32fp32 / fp1632-bit and 16-bit floating-point formats. Mailwoman trains in bf16 (a 16-bit variant) and exports the ONNX model in int8 for size. probe), every config from v0.6.3 on has stayed at 0.0 — the current one included. Dual-loss curvature conflict has the full diagnostic story of why the two lossesloss functionA number measuring how wrong the model's predictions are on a batch of examples. Training minimizes it. Mailwoman's loss combines per-token negative log-likelihood with the CRF sequence loss. fought instead of cooperating. There's no active plan to revisit it — the structural mask alone already buys the concrete win (no orphan-Iorphan-IA label-sequence bug where I-X appears without a matching preceding B-X (e.g. O, I-locality). Structurally invalid in BIO; the CRF prevents it.), and the encoderencoderThe part of a transformer that turns input tokens into contextualized vector representations. Mailwoman's classifier is a small encoder-only transformer (~30M parameters).'s attentionattentionThe core mechanism inside a transformer encoder. Each token's representation is updated by looking at every other token, with learned weights deciding how much each one matters. covers most of the rest.

What a learned CRF would buy (if one ever ships)

A learned transition layerlayerOne transformer block — attention plus a feed-forward network, with normalization and residual connections — applied to every position. Stacking layers lets the model build up richer representations; Mailwoman's encoder has 6. would add soft transition preferences on top of the hard structural mask. For example:

• B-house_number is almost always followed by B-street or O, B-street — a learned matrix could encode that preference.
• B-postcode rarely precedes anything (it's usually the last component) — B-postcode → O could get a boost.
• B-street_prefix → B-street is common; B-street_prefix → B-locality is rare — a learned matrix could rank these apart.

It would not buy:

• Better encoderencoderThe part of a transformer that turns input tokens into contextualized vector representations. Mailwoman's classifier is a small encoder-only transformer (~30M parameters). representationshidden stateThe model's internal vector for a token after the encoder has mixed in surrounding context. The contextualized representation the classifier head reads to assign a label.. The encoderencoderThe part of a transformer that turns input tokens into contextualized vector representations. Mailwoman's classifier is a small encoder-only transformer (~30M parameters). is the upstream learner; a CRFCRF (Conditional Random Field). A statistical modeling method that predicts structured outputs by modeling dependencies between adjacent labels. Mailwoman uses a linear-chain CRF as the Viterbi decoder at inference time to enforce BIO label consistency — a B-street must be followed by I-street or O, never I-locality. layerlayerOne transformer block — attention plus a feed-forward network, with normalization and residual connections — applied to every position. Stacking layers lets the model build up richer representations; Mailwoman's encoder has 6. is downstream of it, not a substitute for it.
• Handling of novel patterns. If a sequence isn't represented well in trainingtrainingThe process of adjusting a model's parameters so its predictions match labeled examples, by repeatedly measuring error and nudging the weights to reduce it. Distinct from inference, when the trained model is run on new input., a transition matrixtransition matrixThe CRF's learned table of per-label-pair scores. It encodes which BIO transitions are preferred or forbidden — e.g. that an I-tag must follow a matching B- or I-. has no opinion either.
• InferenceinferenceRunning the trained model on new input to get predictions, as opposed to training, which produces the model. In Mailwoman that means a small transformer encoder reads an address string and classifies every token — house number, street, locality, region, postcode, and the rest. A Who's On First gazetteer can feed soft location hints into the pass, but the model makes the final call on every label. Where a generative model writes text token by token, Mailwoman's output is a retrieval-augmented token classification: one label per input piece. speed. ViterbiViterbi decodingA dynamic programming algorithm that finds the most likely sequence of hidden states (labels) given a sequence of observations (token emissions). Mailwoman uses Viterbi over a linear-chain CRF to produce globally coherent BIO label sequences from per-token model scores. over a learned matrix is marginally slower than the structural-mask-only version (one more score lookup per transition).

Decoder modes

The parse() API accepts a decode option:

• "viterbi" (default): full ViterbiViterbi decodingA dynamic programming algorithm that finds the most likely sequence of hidden states (labels) given a sequence of observations (token emissions). Mailwoman uses Viterbi over a linear-chain CRF to produce globally coherent BIO label sequences from per-token model scores. over the BIO validity mask — no learned transitions ship, so this is the mask alone. Produces structurally valid sequences.
• "argmax": per-tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. argmax with no sequence consideration. Faster but produces invalid sequences. Used in ablation studies to measure how much ViterbiViterbi decodingA dynamic programming algorithm that finds the most likely sequence of hidden states (labels) given a sequence of observations (token emissions). Mailwoman uses Viterbi over a linear-chain CRF to produce globally coherent BIO label sequences from per-token model scores. contributes vs how much is in the encoderencoderThe part of a transformer that turns input tokens into contextualized vector representations. Mailwoman's classifier is a small encoder-only transformer (~30M parameters)..

The "argmax" mode is kept for diagnostic purposes. Production always uses "viterbi".

See also

• How Mailwoman parses an address — the full parseaddress parsingThe process of decomposing a free-text postal address string into structured components — house number, street name, locality, region, postcode, and country — so a geocoder can resolve them to coordinates. this step plugs into
• How the model reasons — the central pipelinestaged pipelineMailwoman's runtime architecture: a sequence of pure-function stages (normalize → query-shape → locale-gate → kind-classifier → phrase-grouper → classifier → decoder) connected by typed handoffs. Each stage is published as its own npm package. doc
• Attention and bidirectional context — what's UPSTREAM of ViterbiViterbi decodingA dynamic programming algorithm that finds the most likely sequence of hidden states (labels) given a sequence of observations (token emissions). Mailwoman uses Viterbi over a linear-chain CRF to produce globally coherent BIO label sequences from per-token model scores.
• FST priors as shallow fusion — the additive biasesadditive biasA logit adjustment added before softmax from a prior or external knowledge source, typically soft-capped so it influences but never overrides the model's prediction. The mechanism behind shallow fusion. on the emissions ViterbiViterbi decodingA dynamic programming algorithm that finds the most likely sequence of hidden states (labels) given a sequence of observations (token emissions). Mailwoman uses Viterbi over a linear-chain CRF to produce globally coherent BIO label sequences from per-token model scores. consumes
• CRF decoder — the short version of this page
• Dual-loss curvature conflict — why learned CRFCRF (Conditional Random Field). A statistical modeling method that predicts structured outputs by modeling dependencies between adjacent labels. Mailwoman uses a linear-chain CRF as the Viterbi decoder at inference time to enforce BIO label consistency — a B-street must be followed by I-street or O, never I-locality. trainingtrainingThe process of adjusting a model's parameters so its predictions match labeled examples, by repeatedly measuring error and nudging the weights to reduce it. Distinct from inference, when the trained model is run on new input. was abandoned
• BIO labels — the per-tag labelcomponent tagOne of the 33 labels in Mailwoman's address schema — street, locality, region, postcode, house_number, unit, po_box, country, venue, intersection, and others. Each parsed span carries exactly one component tag. space (existing reference)