L18) The Sign Reversal

Series: “Generation-Recognition Asymmetry”

This article accompanies the research paper The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory (📄 arXiv).
Reading thread: L13 · L14 · L15 · L16 · L17 · L18 · L19 · L20 — or the complete index.

Why “generation is easy, parsing is hard” is false

Everyone repeats it: producing a sentence is trivial, understanding it is costly. It is a half-truth that becomes a lie as soon as one looks closely. Under the right constraint, generating can be strictly more difficult than parsing — and this is not an intuition, it is a theorem.

Where does this article fit in?

This article extends the first dimension (D1, Complexity) of the generation-recognition asymmetry studied in L13 and L17. The complexity matrix of L17 already showed that constrained generation “heats up”; here we follow the reasoning to its conclusion and name the phenomenon: the sign reversal. This is the most counter-intuitive result of the research paper that this series popularizes.

Why is it important?

The slogan “generation is easy, parsing is hard” structures much of the intuition in computer science and computational linguistics. It justifies spending decades of research on parsing algorithms (LL, LR, Earley, CYK — see L14) and much less on generation. But if the slogan is false in the cases that matter, then our mental map of difficulty is wrong.

The stakes are not rhetorical. Designing a system that generates text, music, or code under constraints (a target meaning, an imposed format, a security requirement) means facing exactly the case where generation becomes costly. Understanding when and why prevents under-dimensioning an entire system.

The idea in one sentence

Unconstrained generation is trivial ($\mathcal{O}(n)$), but generation under semantic constraint can be exponential or even NP-complete — thus strictly more difficult than parsing — because the real factor is not “which operation”, but “who imposes the constraint”.

Let’s explain step by step

1. The naive view, and why it is appealing

The intuition behind the slogan is real. To generate, one simply starts from the grammar’s axiom and applies rules randomly until terminal symbols are reached. No difficult decisions: at each step, a rule is chosen and applied. To parse, on the contrary, one must reconstruct a hidden structure from the surface alone — resolving ambiguities, exploring competing hypotheses.

Hence the mental picture: generation $= \mathcal{O}(n)$ (linear in the length of the derivation), parsing $= \mathcal{O}(n^3)$ for context-free grammars (the bound of the CYK algorithm — see L15). Generation easy, parsing hard. End of story?

2. Yes, unconstrained generation is indeed trivial

Let’s start by conceding what is true. Free generation — applying rules without aiming for a particular output — is indeed $\mathcal{O}(n)$ for any formalism, from the simplest to the most powerful. This is the first row of the matrix in L17, uniformly green.

The problem is that this result is useless. A randomly drawn string is “grammatical” (it belongs to the language $L(G)$) but says nothing. No one generates randomly. A composer does not place random notes; a dialogue system does not respond with just any sentence of the French language. Real generation always operates under constraints: a meaning to express, a form to respect, a register to maintain.

3. Constrained generation changes everything

Let’s formalize the constraint. We no longer ask “produce any string from $L(G)$“, but “produce a string from $L(G)$ that additionally satisfies an external condition $C$” — for example: “that expresses this precise meaning”, “that contains exactly these lexical units”, “that respects this format”.

For regular languages ($k=3$ in the Chomsky hierarchy — see L1), everything is still fine. The constraint is encoded as a second automaton $A_C$, and generating becomes producing a string in the intersection of the two languages, $L(G) \cap L(A_C)$ — computable by automaton product in polynomial time. Mohri (1997) shows that the output of a deterministic transducer remains linear in the size of the input. No drama.

The drama begins one step higher, with enriched context-free grammars — those that carry feature structures (attribute-value annotations attached to constituents, to express subject-verb agreement, gender, number, or the subcategorization of a verb). These are the grammars of linguists: LFG, HPSG, FTAG. And there, complexity explodes.

4. Kay’s result (1996): exponential

Martin Kay, one of the founders of computational linguistics, established that generating from a “flat” semantic representation is intrinsically exponential in the worst case. His formulation is crystal clear:

« The process is exponential in the worst case because, if a sentence contains a word with $k$ modifiers, then a version will be generated with each of the $2^k$ subsets of those modifiers, all but one of them being rejected when it is finally discovered that their semantics does not subsume the entire input. »

— Kay (1996, p. 202)

The intuition: in parsing, the string provides a positional index — “between position 3 and position 7, there is a noun phrase”. This index is exactly what makes parsing polynomial (CYK’s dynamic programming exploits positions). In generation, the string does not yet exist: it is the output being constructed. Without a positional index, the generator must consider all compatible semantic groupings — and there are an exponential number of them ($2^k$ for $k$ modifiers).

Decryption — “subsume”. A semantic representation subsumes another if it contains it as a special case. The generator only knows at the end if the subset of modifiers it has assembled exactly covers the intended meaning — hence the waste: $2^k – 1$ discarded attempts.

5. Brew’s result (1992): NP-complete, proven

Kay’s analysis describes a worst-case difficulty. Chris Brew goes further: he proves that the problem is NP-complete, on a minimal generation scheme from a bag (multiset) of lexical signs. The proof proceeds via a polynomial reduction from a known NP-complete problem, 3-Dimensional Matching:

« We now provide a polynomial-time reduction from an arbitrary instance of MENAGE A TROIS to an instance of Shake-and-Bake generation, which allows the same conclusion to be drawn for this problem. »

— Brew (1992, §2.1.3, p. 611)

Decryption — reduction. Reducing problem A to problem B means showing that solving B would allow solving A. If A is already known to be NP-complete (like 3-Dimensional Matching), then B is at least as difficult. Brew’s reduction transforms any instance of 3-Dimensional Matching into a generation instance: therefore, generating is NP-complete.

Why is Brew important beyond Kay? Because he establishes intrinsic difficulty — a property of the problem itself, independent of the algorithm — and not just a worst-case slowness of a particular method. On a scheme stripped of all auxiliary machinery, generating remains NP-complete.

And moving further up the hierarchy, toward context-sensitive grammars ($k=1$), Barton, Berwick & Ristad (1987) show that the membership decision for agreement grammars (CFGs enriched with limited features) is already NP-complete by reduction from 3-SAT — which transfers to constrained generation.

6. The sign reversal

Let’s put the two sides face to face. On the recognition side, complexity grows with the expressive power of the grammar: $\Theta(n)$ for regular, $\mathcal{O}(n^3)$ for context-free, and so on (see L17). On the generation side, free or simply terminating, it remains polynomial everywhere. So far, the slogan holds.

But for semantically constrained generation, the asymmetry changes sign as early as $k=2$ with features: generation becomes exponential (Kay) or NP-complete (Brew), while recognition remains polynomial ($\mathcal{O}(n^3)$). In other words: for the same class of grammar, generating exceeds parsing.

TikZ diagram

Figure 1 — The sign reversal (semi-logarithmic scale). For small constraints, generation seems faster; but its exponential curve ($\mathcal{O}(2^n)$, red) crosses and then exceeds the polynomial curve of parsing ($\mathcal{O}(n^3)$, yellow) around $n \approx 10$. Beyond that, constrained generation costs more than parsing — the exact opposite of the slogan.

7. The real asymmetry is structural

If the slogan is false, what is true? The asymmetry is not a gap in difficulty between two operations; it lies in the locus of the constraint:

  • The parser is always constrained: the input is given to it, non-negotiable. It has no choice in its difficulty — it is imposed by the received string.
  • The generator can be constrained, or not, depending on the task. Without constraints, it enjoys $\mathcal{O}(n)$. Under strong constraints, it matches or exceeds parsing.

The divide is therefore not “generation vs recognition” but “chosen constraint vs imposed constraint”. This is the rigorous formulation of the intuition from L13: the receiver does not have the luxury of choice.

8. In music and in large language models

The reversal can be read directly in real systems.

In computer-aided composition: generating any melody in a style grammar is trivial. Generating a melody that modulates to a target key, respects an imposed meter, and quotes a given motif — that is generation under multiple constraints, exactly the costly regime. The composer using I2 in production mode feels it: the more safeguards they add, the more the search space narrows and becomes complicated.

In large language models (GPT and others): autoregressive sampling seems instantaneous, at $\mathcal{O}(n)$ per token. But as soon as the output is constrained — format compliance (valid JSON), factual accuracy, safety filters —, the analytical cost is reintroduced. The constrained generation of LLMs materializes the sign reversal in modern architectures: what seemed free becomes expensive again as soon as something precise is required.

Key Takeaways

  • Unconstrained generation is trivial ($\mathcal{O}(n)$) but useless: no one generates randomly.
  • Semantically constrained generation can be exponential (Kay 1996) or proven NP-complete (Brew 1992, by reduction from 3-Dimensional Matching).
  • The sign reversal: for the same grammar, constrained generation can be strictly more difficult than parsing — the opposite of the common slogan.
  • The structural cause: without the string, the generator lacks a positional index and must explore an exponential number of semantic overlaps.
  • The real asymmetry is not a gap in difficulty between operations, but the locus of the constraint: the parser always undergoes it, the generator chooses it.

To go further

Constrained generation

  • Kay, M. (1996). “Chart Generation.” Proceedings of ACL, 200-204 — the exponentiality argument.
  • Brew, C. (1992). “Letting the Cat out of the Bag: Generation for Shake-and-Bake MT.” COLING 1992, 610-616 — the proof of NP-completeness. DOI:10.3115/992133.992165
  • Barton, G.E., Berwick, R.C. & Ristad, E.S. (1987). Computational Complexity and Natural Language. MIT Press — NP-completeness of agreement grammars (ch. 3).
  • Mohri, M. (1997). “Finite-State Transducers in Language and Speech Processing.” Computational Linguistics 23(2), 269-311 — the regular case remains linear.
  • Russell, G., Carroll, J. & Warwick-Armstrong, S. (1990). “Asymmetry in Parsing and Generating with Unification Grammars: Case Studies from ELU.” ACL 1990, 205-211 — case studies (clitics, empty semantic heads). DOI:10.3115/981823.981849

The popularized research paper

  • Peyrichou, R. (2026). The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory. §4.1 develops the sign reversal. arXiv preprint:2603.10139 — https://arxiv.org/abs/2603.10139

In the corpus

  • L13 — Overview of the asymmetry (6 dimensions)
  • L15 — Mathematical formalizations
  • L17 — The class × task matrix and differential coupling
  • L1 — Grammar classes
  • L9 — Mildly context-sensitive formalisms

Glossary

  • Free generation: applying the rules of a grammar without aiming for a particular output. Always $\mathcal{O}(n)$.
  • Constrained generation: producing a string that satisfies an external condition $C$ (target meaning, format, lexical occurrences). Can be NP-complete starting from feature-enriched CFGs.
  • Feature structure: attribute-value annotation attached to a grammatical constituent (agreement, gender, number, subcategorization).
  • NP-complete: belongs to the class of the most difficult problems among those whose solution can be verified in polynomial time; no known polynomial algorithm, and likely none exists (unless $P = NP$).
  • Reduction (polynomial): transformation, in polynomial time, of instances of one problem into instances of another; used to transfer difficulty.
  • 3-Dimensional Matching: a matching problem with three sets, a reference NP-complete problem, the starting point for Brew’s reduction.
  • Positional index: position information in the input string (“from position $i$ to $j$“), which makes parsing polynomial and is missing in generation.
  • Sign reversal: the fact that, under semantic constraint, the difficulty asymmetry reverses — generation becomes more costly than recognition.

Links in the series

  • L13 — Generating or recognizing — the asymmetry in 6 dimensions, including the naive view (§1.3)
  • L15 — The formulas of asymmetry — where $\mathcal{O}(n^3)$ and Catalan numbers come from
  • L17 — The complexity matrix — the “constraint” row that this article explores in depth
  • L14 — The direction of parsing — why the parser has a degree of freedom

Prerequisites: L13, L15, L17
Reading time: 11 min
Tags: #asymmetry #constrained-generation #NP-completeness #Kay #Brew #sign-reversal

← Back to index