Parsing with Bounded Working Memory

235 concepts126 papers1 proposal

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.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 128 papers
  2. Version 1 · 2026-10-04 · 146 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_memory_constrained_parsing_f96d4ee3,
  title = {memory-constrained parsing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memory-constrained-parsing/rdr_f96d4ee30a8541afa557f2d1cfe305b7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_memory_constrained_parsing_f96d4ee3_v2,
  title = {memory-constrained parsing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memory-constrained-parsing/rdr_f96d4ee30a8541afa557f2d1cfe305b7/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake