Semantic expressive capacity with bounded memory

Antoine Venant, Alexander Koller

Abstract

We investigate the capacity of mechanisms for compositional semantic parsing to describe relations between sentences and semantic representations. We prove that in order to represent certain relations, mechanisms which are syntactically projective must be able to remember an unbounded number of locations in the semantic representations, where nonprojective mechanisms need not. This is the first result of this kind, and has consequences both for grammar-based and for neural systems.

Introduction

Semantic parsing—the task of translating natural language into formal representations like graphs or logic formulas—often relies on compositional mechanisms. These systems build meaning step-by-step based on a sentence's syntax. A long-standing intuition in linguistics suggests a trade-off between syntactic structure (projectivity) and the "memory" (placeholders) required to maintain semantic coherence.

This paper provides a formal theoretical foundation for this intuition. The authors demonstrate that "projective" parsers, which only combine adjacent words, require an unbounded number of placeholders to represent complex linguistic relations. Consequently, popular "bounded memory" systems, such as those based on unification or fixed-size graph algebras, are fundamentally less expressive than non-projective systems or those utilizing lambda calculus.

The Projectivity-Memory Trade-off

Two major design choices define semantic parsers:

  1. Projectivity: Whether the parser combines only adjacent substrings (projective) or can skip around (non-projective).
  2. Memory (Placeholders): How the parser handles arguments that haven't appeared yet. Some systems allow infinite placeholders (e.g., lambda calculus), while others (e.g., HR graph algebras) assume a fixed, bounded number.

The authors investigate whether restricting a parser to be both projective and memory-bounded limits its expressivity. While linguists have suspected this, particularly regarding "cross-serial dependencies" (CSD) in languages like Swiss German, this work provides the first formal proof of this gap.

Methods and Formalisms

The study compares two classes of grammars that generate the same set of strings but differ in their structural derivations:

  • Tree Adjoining Grammars (TAG): A non-projective formalism.
  • Linear Monadic Context-Free Tree Grammars (LM-CFTG): A projective formalism.

The authors evaluate these grammars on their string-graph relations using the Hyperedge Replacement (HR) graph algebra. To prove the expressive gap, they define the CSD Relation, a synthetic dataset mapping strings to graphs where dependencies cross, forcing projective parsers to maintain multiple "open" placeholders.

Comparison of syntactic derivations (TAG vs. projective) and the resulting semantic graph for a Swiss German sentence.

The CSD Relation and the Pumping Lemma

The core of the proof involves showing that a projective grammar eventually "runs out of memory" as the sentence length increases. The authors use a pumping lemma to demonstrate that for any fixed number of sources (memory slots), there exists a CSD relation that the projective grammar cannot generate.

The formal construction of the CSD relation, showing how tree derivations map to graph fragments.

Key Results

The theoretical findings are summarized in two primary theorems:

  • Theorem 1: Projective grammars with a fixed number of sources ($k$) cannot represent the CSD relation if tokens and edges are aligned.
  • Theorem 2: Even without alignment assumptions, projective LM-CFTGs cannot simulate non-projective TAGs with only two sources for the CSD relation.

The "Aha" moment of the research is that a TAG with only two sources is more semantically expressive than a projective grammar with any fixed number of sources $k$.

Discussion and Impact

This "projectivity tax" implies that if a system insists on projective syntax, it must pay in semantic memory. This has significant implications for neural parsers. Many transition-based models are projective (using a stack and buffer); this research suggests such models may be fundamentally unable to capture certain semantic structures without incorporating non-projective "jump" actions or more flexible semantic algebras.

While the CSD relation is a mathematical construction, it mirrors real-world phenomena. Empirical work on AMRBank and Geoquery suggests that roughly 37% of Abstract Meaning Representation (AMR) data requires non-projective derivations, highlighting the practical relevance of these theoretical bounds. Future work may explore how bounded systems can be adapted to regain expressivity without sacrificing computational efficiency.

Summary updated

Abstract

We investigate the capacity of mechanisms for compositional semantic parsing to describe relations between sentences and semantic representations. We prove that in order to represent certain relations, mechanisms which are syntactically projective must be able to remember an unbounded number of locations in the semantic representations, where nonprojective mechanisms need not. This is the first result of this kind, and has consequences both for grammar-based and for neural systems.
BibTeX
@inproceedings{venant2019semantic,
  author = {Antoine Venant and Alexander Koller},
  title = {{Semantic expressive capacity with bounded memory}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2019},
  doi = {10.18653/v1/p19-1008},
}
Figure