Underspecified Semantics to Resolve Combinatorial Ambiguity

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 224 papers24 conceptsfrozen 2026-10-04

In natural language processing, a single sentence can often be interpreted in a staggering number of ways. Consider the sentence: "Every student read a book." Does it mean there is one specific book that every student read, or does every student have their own book? This is quantifier scope ambiguity, and as Jong C. Park and Samuel S. Epstein point out, the number of possible logical orderings grows factorially with the number of quantifiers. A sentence with just five or six quantifiers can technically yield hundreds of distinct interpretations.

If a computer tries to "understand" by exhaustively listing every possible meaning, it hits a wall known as the combinatorial explosion. Research into underspecified semantics seeks to bypass this wall by representing the entire set of possible meanings in a single, compact form, delaying the "choice" of a specific meaning until absolutely necessary.

The Problem of Combinatorial Explosion

Traditional semantic parsers attempt to map a sentence directly to a specific logical form. However, as Jerry R. Hobbs observed, this is computationally prohibitive. When you combine scope ambiguities with word sense ambiguity (where one word has multiple meanings) and structural ambiguity (where a phrase could attach to different parts of a sentence), the search space becomes intractable.

Peter Clark and Philip Harrison describe this as the "brittleness" of interpretation. If a system commits to one interpretation too early and guesses wrong, it fails. If it tries to evaluate every interpretation, it times out. This bottleneck is a recurring theme across decades of research, from early work by Fernando Pereira to modern compositional systems like the UD Type Calculus proposed by Laurestine Bradford and Timothy John O'Donnell.

Representing the Set, Not the Members

The core intuition of underspecification is to treat the set of all possible meanings as a single first-class object. Instead of a list of twelve different logical formulas, we create one "underspecified" description that encompasses all twelve.

Several mechanisms have been proposed to achieve this:

  • Scope-Neutral Logic: Jerry R. Hobbs proposed using "typical elements" and flat logical forms that remain vague about which quantifier takes precedence.
  • Packed Representations: Jochen Dörre introduced algorithms to construct "packed" semantic forests. By factoring out common logical components—similar to how a chart parser stores a shared forest of syntactic trees—the system can represent millions of interpretations in a structure that can be processed in polynomial time.
  • Dominance Constraints: Joachim Niehren and Stefan Thater showed that complex frameworks like Minimal Recursion Semantics (MRS) can be viewed as a set of constraints on how pieces of a formula can "dominate" or contain one another. This allows for efficient extraction of specific meanings only when needed.

Computing on the Unknown

The real power of this approach is that you don't just store these ambiguous representations—you can actually perform logic on them. Manuel Bodirsky and colleagues demonstrated Underspecified Beta Reduction, a method for simplifying logical formulas while they are still in their ambiguous, "packed" state. This means a system can perform reasoning and simplification on thousands of potential meanings simultaneously without ever enumerating them.

Similarly, Michael Schiehlen applied this to ellipsis resolution, allowing a system to resolve omitted text (like "John likes coffee, and Mary [likes coffee] too") even when the exact scope of the original sentence is still undecided.

Disambiguation through External Knowledge

If we never fully commit to a meaning, how does a computer eventually answer a question? The answer lies in deferred commitment. By holding multiple possibilities in suspension, the system can use context, world knowledge, or user interaction to prune the search space.

Graeme Hirst pioneered this with the Semantic Enquiry Desk (SED), which checks candidate interpretations against a knowledge base to see if they "make sense" in the real world. Peter Z. Yeh and Bruce W. Porter extended this by using ontologies to resolve mismatches between text and formal knowledge, effectively using the "best fit" with known facts to pick the right sense and role.

In modern applications like question answering over tables, Mukund Sundararajan and colleagues use abductive matching to navigate the space of logical forms. By using neural networks to "fill in" the most likely links between a query and a database, they avoid the "spurious interpretations" that plague systems trying to guess the right logic in a vacuum.

Summary

Underspecified semantics works because it changes the fundamental unit of processing. Instead of trying to find the "one true meaning" of a sentence in isolation—which leads to an exponential explosion of guesses—it maintains a compact, mathematical description of all valid meanings. By delaying disambiguation, systems can use the full context of a conversation or a database to filter out the noise, making natural language understanding both more efficient and more robust.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_combinatorial_scope_ambiguity_d75ec1b6,
  title = {combinatorial scope ambiguity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-scope-ambiguity/rdr_d75ec1b644a64182838cdfe68f70ef83},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_underspecified_semantics_to_resolve_comb_d75ec1b6_v1,
  title = {Underspecified Semantics to Resolve Combinatorial Ambiguity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/underspecified-semantics-to-resolve-combinatorial-ambiguity/rdr_d75ec1b644a64182838cdfe68f70ef83/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}