The parse that quietly became zero

The probabilistic extension of my CYK parser decodes in the log domain, and when I wrote that sentence in the paper it read like a stylistic choice, the kind of thing a careful implementer does. It is not a choice. Done in the probability domain, the parser is wrong on most real sentences, and it is wrong silently: it returns a legal tree that happens to be the first one it tried, with a score of exactly zero, and nothing in the output says so. I measured how quickly that happens, and the answer is sooner than most people would guess.

The arithmetic of a parse

A probabilistic context-free grammar assigns each rule a probability, and the probability of a tree is the product of the probabilities of the rules used to build it. A Viterbi parse, the most probable tree for a sentence, is found by CYK with the sum replaced by max and the count replaced by product: each chart cell holds the best probability for its span, computed as the product of the best probabilities of two sub-spans and the rule that joins them.

Every factor in that product is below one, and most are well below one, because a nonterminal with many expansions gives each of them a small share. A tree for a sentence of n tokens uses on the order of 2n rules, counting the lexical rules that attach words to tags, so its probability is a product of a few dozen small numbers. That product shrinks geometrically with the length of the sentence, and IEEE floats have a floor.

Measured on a treebank grammar

The grammar and the sentences below come from the Penn Treebank sample that ships with NLTK: 3,914 parsed sentences, from which a PCFG can be induced by counting the rules in the gold trees. For each sentence I computed the log probability of its own gold tree under that grammar, which is a fair proxy for the probability of the best parse, since the gold tree is usually at or near it.

The mean log probability per token comes out at about minus 6.8 nats, and it is nearly flat across lengths: a ten-token sentence's tree scores around minus 100, a thirty-token sentence's around minus 230, a fifty-token sentence's around minus 370. The float floors sit at fixed heights. The smallest normal single-precision value is 2 to the negative 126, whose natural log is minus 87.3; for double precision it is 2 to the negative 1022, with a log of minus 708.4, per the IEEE 754 formats.

The per-token figure includes the lexical rules, one per word, which carry most of the cost: a part-of-speech tag with thousands of possible words gives each word a small probability, and those factors dominate the product. A grammar with a smaller vocabulary per tag would drift down more slowly, and a grammar with finer tags would drift faster. The rate is a property of the grammar, and the floors are not.

Divide the floor by the per-token rate and you get what I call the underflow horizon: the sentence length beyond which the best parse's probability is expected to fall below the smallest normal float. For this grammar it is about 13 tokens in single precision and about 104 in double. The median sentence in the sample is 25 tokens long. In single precision, 3,349 of the 3,914 gold trees, 86 percent, have a probability below the float32 floor. In double precision, three do.

Subnormal floats extend the floors a little, to a log of about minus 103 in single precision, but they lose precision as they go and they do not change the picture: most sentences in a newspaper are past the horizon before the parser is halfway through them.

Why the failure is silent

Underflow in a max-product parse does not raise an error. The chart cell for a span whose best probability is too small simply holds zero, and every larger span built on it holds zero too. When the parser reaches the top cell, the best probability over all trees is zero, and so is the second best, and the third.

The argmax is a tie, and a tie is broken by whatever the implementation does first, usually the first rule tried at the first split point. The traceback then follows those arbitrary choices down the chart and produces a grammatical tree with the right leaves and a structure that has nothing to do with likelihood. The output is well-formed. The score is 0.0. Nothing complains.

It gets worse before it gets to zero. Between the smallest normal value and true zero lie the subnormal floats, where the number of significant bits shrinks as the value falls. A parser operating in that range is comparing probabilities that have lost most of their precision, so two trees whose true probabilities differ by a factor of two can compare equal, or the wrong way round, before either reaches zero. The tie among zeros is the visible end of a failure that began several tokens earlier, when the comparisons quietly stopped being accurate.

There is also the scaling trick, which is worth naming because it is the alternative some implementations choose. Multiply every cell by a large constant at each level and keep track of the exponent separately, the way some HMM implementations do. It works, and it is more bookkeeping than the log domain for no gain: the log form needs no rescaling, has no constant to tune, and turns the multiplication into an addition. For a parser, logs win on every axis.

That is why the log domain is not an optimisation. Replace every probability with its natural log, every product with a sum, and leave max as max, since the log is monotonic and the argmax is unchanged. The chart now holds numbers around minus 200 instead of numbers around 10 to the negative 90, and double precision has room for sentences tens of thousands of tokens long. The arithmetic is slightly different, addition instead of multiplication, and slightly faster on most hardware, but that is incidental. The point is that the answer is the correct tree instead of the first one.

Where the same bug lives

Nothing here is specific to parsing. Any model that scores a sequence as a product of per-step probabilities has the same horizon: hidden Markov models, beam search over a language model, any pipeline that multiplies likelihoods across a long input. The per-step rate differs, the floor is the same, and the failure is the same tie among zeros. The inside algorithm, which sums over trees instead of taking the max, has a harder version of the problem, because a sum of logs is not the log of a sum and needs the log-sum-exp trick at every cell, at a cost in exponentials that Viterbi never pays.

The general rule is the one every numerical methods course teaches and every fresh implementation forgets: a probability is a log until the very end, and it is converted back, if at all, only for display. When the paper says the Viterbi extension decodes in the log domain, that sentence is the difference between a parser that finds the most probable tree and one that finds a tree.