The cube nobody actually pays

Every textbook introduction to the CYK algorithm ends with the same sentence: it runs in time cubic in the length of the input. That is true, and it is the least useful true thing you can say about the algorithm. The full bound, the one I proved for the parser in my ACL Student Research Workshop paper, is O(n cubed times the size of the grammar), and for the grammars anyone actually parses with, the second factor is the one you pay. The cube is a threat that only arrives for sentences longer than people write.

The bound, read properly

CYK fills a triangular chart with one cell for every span of the sentence: n squared over two cells for n tokens. Each cell asks, for every split point inside the span, whether some binary rule A to B C has B covering the left part and C covering the right. That inner loop is where the cube comes from: n squared cells, up to n split points each. But for each split point the parser considers every binary rule in the grammar, and that is the factor the textbook sentence drops.

So the work is roughly n cubed times the number of binary rules, or, more carefully, n cubed times a constant that depends on how many rules can fire per cell. Written that way, the question of which term dominates is a question about a number: the sentence length at which n cubed first exceeds the grammar size. Call it n star, the grammar-length crossover. Below it the parser is grammar-bound and the way to make it faster is to shrink the grammar or prune the cells. Above it the parser is length-bound and the split-point tricks start to matter.

Measured on a real grammar

The numbers below come from the Penn Treebank sample that ships with NLTK, about a tenth of the Wall Street Journal portion of the treebank described by Marcus, Santorini and Marcinkiewicz. Reading every production off its parse trees gives an induced grammar with 707 nonterminals and 21,763 distinct productions, of which 13,781 are lexical (a part of speech to a word) and 7,982 are phrasal. Of the phrasal rules, 666 are unary, 1,848 are binary, and 5,468 have three or more symbols on the right-hand side and would each become several binary rules under conversion to Chomsky normal form.

Take the 7,982 phrasal rules as the grammar size and the crossover is the cube root of 7,982, which is 20. Take all 21,763 productions and it is about 28. Convert to normal form first, which expands the 5,468 long rules, and it moves higher still.

Now put that beside the sentences. The same sample has 3,914 sentences with a mean length of 25.7 tokens, a median of 25, and a 90th percentile of 41. About a third of them are shorter than 20 tokens, and those sit entirely below the phrasal crossover: for them, the parser spends more of its time on the grammar than on the length. Most of the rest sit between 20 and 40, where the two terms are within a small factor of each other. The sentences where the cube is clearly the cost, above 50 tokens, are about 3.5 percent of the corpus.

What conversion does to the number

The crossover moves in one direction under conversion to Chomsky normal form, and it is worth knowing which. Of the sample's phrasal rules, 5,468 have three or more symbols on the right-hand side, and CYK cannot use them as they are. Binarisation replaces each rule of arity k with k minus 1 binary rules, introducing a fresh nonterminal at each step, so a rule with five symbols on the right becomes four rules. The unary rules go the other way, being eliminated by composing them into the rules they chain to, which can add rules too. The exact size after conversion depends on the order of the steps and on how much sharing the binarisation finds, but for a grammar shaped like this one the binary rule count after conversion is several times the 1,848 that were binary to begin with, and the crossover rises with it.

The lexical rules deserve a separate note because they look like the largest part of the grammar and are not part of the cube at all. The 13,781 lexical rules are consulted once per token, to fill the bottom row of the chart, and never again. Their cost is linear in the sentence length and proportional to the lookup, not to the number of splits. Counting them in the grammar term overstates the constant; the term that multiplies the cube is the number of binary rules the split loop can try, and that is the number to shrink.

What the practitioner actually pays

The consequence is a reversal of where the effort should go. If the cube were the cost, the right optimisations would be about the split loop: better memory layout for the chart, vectorising the inner comparison, pruning split points. Those are the optimisations people reach for, because the textbook sentence told them where the cost was. For sentences of the length that exists, the cost is the number of rules that can fire in each cell, and the optimisations that pay are the ones that make that number small.

Shrinking the grammar is the first. Two grammars that recognise the same language can differ in rule count by a large factor, and every rule the parser does not have to try is work saved in every cell of every sentence. The conversion to Chomsky normal form is where a grammar's size is most often decided, and it deserves more care than it gets. Indexing the grammar is the second: rather than trying every binary rule at every split, index rules by their right-hand-side symbols so that a cell only looks at rules whose B and C are actually present. That turns the per-cell constant from the grammar size into the number of matching rules, which for most cells is a small number.

Why the sentence survives

The textbook sentence survives because it is true for a fixed grammar, and a course fixes the grammar on the whiteboard. Once the grammar is a constant, the only variable is n, and the bound is cubic in the only variable. The sentence is not wrong. It answers a question nobody building a parser is asking.

There is also a fairness point on the other side. For very long inputs, and for grammars that are small by design, the cube is real. A parser for a programming language with a few hundred rules and inputs of thousands of tokens is length-bound from the first line, which is one reason nobody parses programs with CYK. The crossover is a number, and for that grammar it is low. For a grammar read off a treebank it is roughly where the sentences are, and that is the whole point of computing it rather than quoting it.

If you are building or benchmarking a CYK parser, do the arithmetic before the engineering. Count the rules after conversion, take the cube root, and put that number next to the length distribution of what you will parse. Whichever side of the crossover your sentences sit on tells you which term you are paying, and it is usually not the one on the whiteboard.