The pumping lemma as a model test

The pumping lemma is taught as a tool for proving that a language is not regular, or not context-free, and students learn it as a ritual with five variables and a contradiction at the end. It is simpler than that and more useful. It is a doubling argument: any recogniser with a finite amount of memory that accepts a long enough string must have repeated a memory state somewhere in the middle, and if it repeated a state, it must also accept the string with that middle section repeated any number of times. That is a statement about any finite machine, and a neural network run once over an input is a finite machine. So the lemma gives a direct experimental test of whether a model learned the grammar of a task or memorised the lengths it was trained on, and it is a test I would run before believing any claim that a model parses.

The argument, without the ritual

Take a recogniser with a bounded number of internal states, and feed it a string longer than that number. By the time it has read the string, some state must have occurred twice, because there are more positions than states. Call the section between the two occurrences the middle. The machine was in the same state before and after the middle, so if you delete the middle, or repeat it, or repeat it a thousand times, the machine ends in the same state as before and gives the same answer. If the language requires the answer to change, the machine cannot be recognising it. That is the whole lemma for regular languages, and the context-free version is the same argument applied to a pushdown automaton's stack, where two pumpable sections appear instead of one because the stack has to grow and shrink in matched pairs.

Two things about the argument matter for models. The first is that it is about memory, not about training. A machine with a bounded number of states cannot recognise a language that needs unbounded counting, however it was built, and more examples of the language do not add states. The second is that the argument is constructive: it tells you what string to build to expose the limit. Take a string the machine handles and repeat its middle. If the machine has the grammar, the answer is forced. If it does not, the answer will drift, and it will drift at a length that reveals how much memory the machine actually has.

What the benchmark found

Delétang and colleagues ran the closest thing to this test at scale in Neural Networks and the Chomsky Hierarchy, training 20,910 models across fifteen tasks arranged by the hierarchy and testing on inputs longer than anything seen in training. The finding is the one the lemma predicts. Recurrent networks and transformers failed to generalise on tasks above the regular level. Networks with an explicit counter, the LSTM family, handled regular tasks and counter languages. Only networks with an external memory, a stack or a tape, generalised on context-free and context-sensitive tasks. The grouping by hierarchy level forecast which architectures would generalise, independently of data or compute, which is a polite way of saying that the limits are formal properties and not training bugs.

The transformer row is the one people find hardest to accept, because transformers do so much else. But a transformer run once over an input has a fixed number of layers and a fixed-width state per position, and the lemma does not care what else it can do. More data moves a transformer along its row, toward doing the regular tasks it can already do more reliably. It does not move it down the table, because down the table is a memory it does not have.

The doubling probe

The test that falls out of the lemma is what I call the doubling probe. Take a set of strings the model handles correctly, at the lengths it was trained on. Identify the pumpable middle for each, which for bracket matching is a balanced inner span and for a regular language is any section between repeated automaton states. Pump the middle two, four and eight times, and plot accuracy against the pump count.

The curve has two readings and one number. A flat line means the model has the grammar: the pumped strings are still in the language, the model still accepts them, and the lemma's forced behaviour is what it does. A cliff means the model has the lengths: it handled the training distribution by memorising what strings of those lengths look like, and once the pumped string is longer than anything it saw, it has nothing to say. The position of the cliff is the number, because it is the length beyond which the model's memory of the task runs out, and that is its effective memory for the task in the sense the lemma uses the word.

The probe is cheap because it reuses the model's own successes. There is no need to construct adversarial strings or to search for failures; the lemma says where the failure has to be, if there is one, and the probe goes there directly. It also separates two claims that evaluation sets usually blur: that a model is accurate on a task, and that it has learned the structure the task is defined by. A model can be very accurate on a length-bounded benchmark and fail the probe at pump count two, and that model has not learned to parse, whatever the benchmark says.

One refinement makes the probe sharper. Pumping the middle keeps the string in the language, so a grammar-learner should keep saying yes; the complementary probe pumps only one of the two sections in a context-free language, which takes the string out of the language, so a grammar-learner should switch to no. A model that says yes to both has not learned the grammar; it has learned that long strings with familiar pieces are probably fine. Running both halves distinguishes a model that recognises the structure from one that recognises the vocabulary, and the second is far more common than benchmark scores suggest.

Why the proof is the point

My paper on CYK recognition includes pumping lemma proofs about the limits of context-free recognition, and relating that work to transformer-based parsing is where the probe came from: the same argument that bounds what a pushdown automaton can recognise bounds what any bounded-memory model can, and the argument is constructive enough to run. That is also the clearest example I have of what a mathematics degree teaches that a bootcamp skips. Not the lemma, which is a page in any textbook, but the habit of asking what a proof of impossibility says you can measure, and then measuring it.

The probe's limit is the one the lemma has. It detects the absence of the grammar; it cannot certify its presence, because a flat line to pump count sixteen is consistent with a cliff at thirty-two. What it can do is push the cliff out until it is beyond any input the model will see in use, and report where it was found. A model that parses in production should come with that number, and the lemma is how you get it.