Theoretical linguistics often treats natural language as a system capable of infinite recursion, implying that a parser would require the computational power of a Turing Machine. However, human cognition is physically constrained by a finite and noisy working memory. This discrepancy between formal competence and actual performance suggests that the structures of human language are not arbitrary, but are instead optimized for a system with a very limited "stack."
The Finite State Bottleneck
The fundamental intuition behind memory-constrained parsing is that human language processing is more akin to a Finite State Machine (FSM) than a complex, unbounded automaton. As Church argues, the assumption that language requires infinite memory contradicts the observed limitations of human cognition. By imposing strict memory limits, such as a bounded stack depth, researchers can create models that naturally replicate human linguistic behavior—specifically, why we excel at processing right-recursive structures ("the dog that chased the cat that bit the rat") but fail on deeply center-embedded ones ("the rat the cat the dog chased bit died").
In these models, center-embedding is difficult because it requires the parser to keep multiple incomplete dependencies active in memory simultaneously. Martin notes that limiting stack capacity prevents a parser from getting lost in these infinite recursions, which rarely occur in natural communication anyway. This constraint forces the system to resolve structures within human-like cognitive bounds, improving robustness by avoiding the computational overhead of linguistically implausible structures.
Left-Corner Parsing and Cognitive Plausibility
To bridge the gap between fixed memory and recursive grammar, researchers often employ left-corner parsing. This strategy is particularly effective because it allows for incremental processing—building the structure of a sentence word-by-word—while maintaining a low memory footprint for the types of branching common in natural language.
Noji and Miyao demonstrate that left-corner transition systems exhibit memory requirements that mirror human working memory constraints: they handle left- and right-branching structures easily but penalize center-embedding. By mapping syntactic trees to a left-corner representation, Noji shows that stack depth can serve as a proxy for cognitive load. Imposing a hard limit on this depth during training acts as a structural regularizer, biasing models toward learning grammars that reflect universal linguistic patterns.
Memory as a Filter for Learning
Constraints on memory do not just limit what a system can process; they also shape what a system can learn. In the context of language acquisition, Shain et al. found that incremental models constrained by human-like memory limits can achieve competitive performance in grammar induction. These bottlenecks may actually facilitate acquisition by forcing the learner to prioritize fundamental, simple structures over noisy or overly complex data.
This idea extends to modern large language models. Kuribayashi et al. observed that models equipped with human-like cognitive biases, such as restricted memory, are better at predicting which word orders are common across the world's languages. This suggests that linguistic universals—like the tendency to minimize the distance between dependent words—emerged as an adaptation to the biological limits of the human brain.
Strategic Forgetting and Active Buffers
In practical applications, memory constraints are often implemented through "forgetting" mechanisms or active buffers. For example, Henderson proposed that parsers should incrementally discard completed structural components to free up resources for new input. This mirrors the human tendency to focus on the "active frontier" of a sentence.
Similarly, for tasks like coreference resolution, Toshniwal et al. developed bounded memory neural networks that track only a small, fixed number of entities at any time. By learning an intelligent strategy for which entities to "forget," these models achieve high efficiency on long documents without sacrificing accuracy. This aligns with the findings of Miller and Schuler, who showed that a limited buffer of just six entities is sufficient to resolve the vast majority of pronouns in natural text.
The Cost of Bounded Rationality
When memory limits are reached, both humans and machines must resort to heuristics. Asami notes that as memory load increases, processing shifts from precise analysis to "good-enough" shortcuts. While these shortcuts allow for rapid communication, they also lead to systematic errors. Levy et al. modeled this using particle filters, showing that when a parser can only maintain a finite set of discrete hypotheses, it becomes prone to total processing failure when encountering highly ambiguous or complex structures—a phenomenon well-documented in human psycholinguistics.
Ultimately, treating memory as a finite resource rather than an infinite abstraction allows researchers to build systems that are not only more computationally efficient but also more deeply aligned with the biological reality of human language.
Key Foundational Work
On Parsing Strategies and Closure (1980) — contributed 8 concept elements to this direction.
Parsing (1980) — contributed 4 concept elements to this direction.