6 June 2026 · 5 min read

Four parsers, one grammar, no winner

CYK, Earley, LR(1) and recursive descent are usually ranked by asymptotic cost, which is the wrong axis. The right axes are how often the grammar changes and how ambiguous it is.

My paper benchmarked a CYK parser against LR(1), Earley and recursive descent on the same grammars, and the honest summary of what a benchmark like that can tell you is less than people hope. Each parser wins on some input and loses on another, and the asymptotic bounds everybody quotes, cubic for CYK, cubic worst case for Earley, linear for LR(1) and for a hand-written descent, describe the axis on which the comparison is least interesting. The axis that decides which parser to use is not how long the input is. It is how often the grammar changes, and whether the grammar is ambiguous.

The wrong axis

Every parsing textbook ranks the algorithms by running time in the length of the input, and for a compiler that is right. A compiler's grammar is fixed when the compiler is built, so the cost of preparing the grammar, building LR tables or writing descent functions by hand, is paid once and amortised over every file ever parsed. What remains is the per-input cost, and there the table-driven and hand-written parsers are linear and the chart-based ones are not.

That ranking assumes the grammar is a constant, and in a growing class of systems it is not. A structured-output engine for a language model receives a JSON schema with the request, compiles it to a grammar, and uses it to mask tokens for the duration of one response. A tool-calling agent switches between grammars mid-generation. A template engine parses user-supplied formats. In all of these, the grammar arrives with the input, and the cost of preparing it is paid every time. An LR(1) table for a schema-derived grammar can take longer to build than the response takes to generate, at which point the linear per-token cost is irrelevant and the parser that needs no preparation wins.

The grammar churn quadrant

So the two axes I use are grammar stability, fixed at build time against supplied per request, and ambiguity, deterministic against ambiguous. Each quadrant has a natural parser.

Four parsers placed by grammar stability and ambiguity A two by two grid. Horizontal axis: grammar stability, fixed at build time on the left, supplied per request on the right. Vertical axis: ambiguity, deterministic at the bottom, ambiguous at the top. Bottom left: LR(1) tables and hand-written recursive descent. Top left: CYK, when every parse or a probability is needed. Bottom right: Earley, as used by llguidance and XGrammar-2. Top right: Earley again, or CYK if probabilities are needed. CYK every parse, or a probability Earley, or CYK for probabilities no tables to rebuild LR(1), recursive descent compilers: pay once, parse forever Earley llguidance, XGrammar-2 Grammar stability: fixed at build time to supplied per request Ambiguity: deterministic to ambiguous
Illustrative: the placement this post argues for; the dot marks where constrained decoding engines have moved.

Bottom left is the compiler's home: a fixed, deterministic grammar, parsed millions of times, where LR(1) tables or a hand-tuned descent parser earn their preparation cost many times over. Top left is where CYK lives and where my paper's implementation belongs: a fixed grammar that is ambiguous, where the job is not to find a parse but to find all of them or the most probable one, and a chart that holds every sub-parse is the natural structure for that. Bottom right is the new territory: a deterministic or nearly deterministic grammar that arrives with each request, where anything that needs a table build is paying that cost per request, and Earley, which works directly from the rules with no preparation, has an advantage that no per-token bound shows. Top right is Earley again, or CYK when probabilities matter, because Earley handles ambiguity and still needs no tables.

The quadrant predicted a change

What makes me trust the quadrant is that it predicted a decision I had no part in. The first XGrammar engine, from late 2024, compiled a grammar to a pushdown automaton and precomputed token masks per automaton state; its speed came from that cache. XGrammar-2, published in January 2026, replaced the automaton with an Earley parser, keeping the cache-based acceleration, and its stated reasons are the quadrant's: agentic workloads switch structures mid-generation and reuse sub-structures across requests, so the engine needs to handle grammars that change constantly and cannot afford to rebuild an automaton for each. llguidance, the engine behind the Guidance library, was Earley-based from the start for the same reason. Two independent teams, working on the per-request-grammar problem, arrived at the parser the quadrant places there.

Total cost against number of inputs parsed, table-driven against table-free, for one grammar Two lines. A table-driven parser starts with a large fixed cost to build its tables and then rises slowly per input. A table-free parser starts near zero and rises more steeply per input. They cross at some number of inputs; below it the table-free parser is cheaper, above it the table-driven one. A per-request grammar sits at one input, far to the left of the crossing. Where the preparation cost pays back Total cost against inputs parsed with one grammar; illustrative table-driven table-free 1 inputs parsed many Number of inputs parsed with the same grammar crossing a per-request grammar lives here table build, paid before the first input
Illustrative: two straight lines with a fixed cost and a slope, drawn to show why a per-request grammar never reaches the crossing.

Where CYK still belongs

None of this retires the parser my paper is about, and the quadrant is careful about why. CYK's chart holds every nonterminal for every span, which is the structure a probabilistic grammar needs to compute the most likely tree, or the total probability of a sentence, or the expected counts that train the grammar in the first place. Earley can be extended to do the same, and it is, but the extension gives up the simplicity that makes Earley attractive per request, and the two converge on the same amount of work once probabilities are involved. In the top-left cell, a fixed grammar and a need for probabilities, CYK's cube is not a cost to be avoided; it is the size of the answer being computed.

The requirement that trips people is normal form. CYK needs the grammar binarised, which is a preparation cost of its own, small next to an LR table build but not zero, and for a grammar that arrives per request it is one more reason the bottom-right cell prefers Earley, which takes rules as written. For a treebank grammar that is fixed for the life of the model, the conversion is paid once and forgotten.

What the benchmark can and cannot say

Back to the paper's comparison. On a fixed grammar and a batch of inputs, CYK loses to LR(1) on time, as it must, and the comparison is worth publishing because it puts a measured constant on the asymptotic story: how many times slower, on which grammar sizes, for which input lengths. What it cannot say is which parser to choose, because the benchmark fixed the grammar, and fixing the grammar decides the quadrant before the timer starts. A benchmark that included the table-build time per grammar, and ran each grammar against one input, would tell a different story, and it would be the story the structured-output engines are living.

The other thing the benchmark cannot say is what happens under ambiguity. A deterministic grammar gives LR(1) and descent a clean run. An ambiguous one gives LR(1) conflicts, which are resolved by rules that pick one parse and discard the rest, and gives descent an exponential blow-up or a backtracking budget. CYK and Earley keep every parse in the chart, which is why they cost more, and it is the cost of an answer the other two do not offer. Comparing them on a grammar where that answer is not needed is comparing a delivery van with a bicycle on a race track.

An Earley chart and the equivalent CYK cells for a four-token input Left: an Earley chart as five state sets, one per position from zero to four, each holding dotted rules; arrows labelled predict, scan and complete connect them. Right: the CYK triangle for the same four tokens, ten cells, each holding the nonterminals that span the cell's range. A note says both hold every sub-parse, and Earley builds its sets from the rules directly, with no tables. Two charts, same information, no tables Earley state sets on the left; CYK cells on the right, for four tokens S0 S1 S2 S3 S4 predict scan complete dotted rules per position nonterminals per span both keep every sub-parse; Earley needs no preparation, CYK needs normal form
Illustrative: the two chart shapes side by side; the highlighted cells hold the same span.

How to choose

Ask two questions before reading a single benchmark. Does the grammar exist before the inputs, or arrive with them? And does the application need one parse, every parse, or the most probable one? A fixed grammar and one parse is a compiler, and the linear parsers are right. A fixed grammar and all parses or a probability is a chart parser's job, and CYK's cube is the price of the chart. A grammar per request is Earley's quadrant, whatever the input length, because the preparation is the cost and Earley has none. A grammar per request with probabilities is the hard corner, and it is where the interesting research now sits.

The benchmark in my paper is honest about what it measured, and the quadrant is what it did not. Both are needed to choose, and the second one is the one people skip, because it is not a number.

ParsingStructured OutputAlgorithms
All writing

Written by Mohd Shayan

Get new posts by email

Occasional essays on engineering, AI, and building for the people technology leaves behind.

One email per new post. Unsubscribe any time.

Subscribe with RSS