Standard Natural Language Processing (NLP) pipelines traditionally operate under a foundational assumption: text can be neatly divided into a linear sequence of discrete tokens before any higher-level analysis begins. However, across many of the world's languages, this assumption introduces a severe structural bottleneck.
When processing morphologically rich languages (MRLs) like Hebrew and Arabic, or unsegmented languages like Chinese and Japanese, determining word boundaries and internal word structures is highly ambiguous. Forcing a model to commit to a single tokenization early in the pipeline creates a cascading error problem: if the initial tokenizer makes a mistake, every downstream component inherits a flawed foundation.
To solve this, researchers developed lattice input representations. Instead of flattening text into a single sequence of strings, a lattice preserves multiple competing linguistic hypotheses simultaneously, deferring the final decision until global context can resolve the ambiguity.
The Pipeline Bottleneck and the Chicken-and-Egg Problem
The core challenge of processing complex languages is often a "chicken-and-egg" problem. As noted by Goldberg et al., a system cannot easily parse a sentence's syntax without first knowing how to segment its words, yet it cannot accurately segment those words without understanding the sentence's global syntactic structure. In Semitic languages, a single space-delimited word can consist of a prefix preposition, a conjunction, a stem noun, and a pronominal suffix. Deciding which morphemes are present requires syntactic context that a standalone tokenizer simply does not possess.
A similar bottleneck occurs in character-based languages without explicit word boundaries. In Chinese text processing, performing word segmentation as an isolated preprocessing step frequently propagates errors downstream, whereas purely character-based models remain "word-blind" to multi-character semantic units (Zhang et al.). This fundamental uncertainty is not unique to text; it also mirrors the noise inherent in speech recognition and optical character recognition (OCR), where inputs are naturally represented as a set of overlapping possibilities rather than a deterministic string (van Noord).
The Core Mechanism: Representing Text as a Graph
The lattice framework replaces the linear sequence of tokens with a Directed Acyclic Graph (DAG).
In a morphological or word lattice:
- Nodes represent discrete boundaries or positions within the input string (e.g., character boundaries or temporal gaps).
- Edges represent potential token hypotheses—such as a specific word, morpheme, or phrase—along with their associated linguistic metadata, such as part-of-speech (POS) tags or lexical probabilities.
+--- "and" (Conj) ---+--- "the" (Det) ---+--- "ship" (Noun) ---+
| |
(0) ---+ +---> (3)
| |
+---------------------- "submarines" (Noun) -------------------+
By structuring the input this way, a preprocessing engine like the one proposed by Boullier et al. can map out all valid morphological analyses or spelling corrections into a single, compact search space. For unsegmented languages, the lattice can explicitly encode all frequent character n-grams found in raw text, allowing multiple segmentation paths to coexist (Oshikiri). Instead of sweeping ambiguity under the rug by picking a single "best guess," the lattice explicitly formalizes linguistic uncertainty.
Why It Works: Deferred Commitment and Joint Inference
The true power of a lattice representation lies in how downstream models consume it. Rather than evaluating a single sequence, the downstream model performs joint inference, optimizing both the low-level token boundaries and the high-level structural representation at the same time.
Lattice Parsing
In syntactic parsing, a lattice parser searches for the most probable path through the input graph while simultaneously constructing a valid parse tree (Cohen et al.). The number and nature of the sentence's terminal leaves are treated as variables determined by the overall global structure (Goldberg et al.).
This integration spans multiple parsing paradigms:
- Chart Parsing: Probabilistic Context-Free Grammar (PCFG) parsers can intersect their grammars directly with an input lattice, using external lexicons and fuzzy tag mappings to evaluate competing morphological interpretations in parallel (Goldberg et al.; Goldberg et al.). This can even accommodate non-lexical elements, allowing parsers to statistically evaluate optional empty symbols or trace markers between visible words (Cai et al.).
- Transition-Based Parsing: Shift-reduce architectures can be extended to operate directly on DAGs. By employing beam search, transition-based parsers navigate the expanded search space of a word lattice, executing shift and reduce operations across multiple paths with minimal loss in accuracy compared to pre-segmented text (Villemonte de la Clergerie; Playing with parsers).
Because the global syntactic structure provides strong top-down constraints, local ambiguities that are impossible to resolve in isolation (such as whether a word functions as a noun or a verb) are naturally disambiguated.
Evaluation Across Discrepancies
A major challenge of this joint approach is evaluation: how do you score a parser if its predicted token sequence differs from the gold standard? To address this, Tsarfaty et al. introduced an evaluation framework using Tree Edit Distance (TED) over a shared lattice. This provides a common search space that allows researchers to accurately quantify parser performance even when the underlying terminal sequences do not match.
Applications Across NLP Domains
The utility of lattices extends beyond parsing into language modeling, machine translation, and modern deep learning architectures.
Machine Translation and Generation
In Statistical Machine Translation (SMT), feeding a decoder a word lattice allows it to defer morphological reduction or compound word splitting until the translation phase (Bisazza et al.). The decoder leverages target-language context and language model scores to select the most coherent source-side analysis (Dyer et al.; Mi et al.). Lattices can also encode paraphrases, allowing a translation engine to choose synonymous expressions that best align with its training data (Onishi et al.). For natural language generation, representing text alignments as a DAG captures synonyms and flexible word orders, maintaining a consensus path for standard generation while preserving alternative paths for variety (Barzilay et al.).
Language Modeling and Speech
By representing words as lattices of all valid morphological analyses via Finite State Transducers, language models can avoid selecting a single analysis during preprocessing (Heintz). The statistical bias of the language model naturally identifies the most probable path during probability calculation, reducing out-of-vocabulary rates. In speech applications, augmented charts with jump edges allow standard parsing algorithms to handle temporal gaps and overlapping word hypotheses, filtering out acoustic noise through grammatical structure (Chien et al.; Ozeki).
The Neural Resurgence
Although early deep learning models favored uniform linear sequences, modern architectures are re-incorporating symbolic lattices to break through performance ceilings. Bareket et al. argue that processing MRLs effectively requires integrating these symbolic morphological lattices directly into neural architectures.
This hybrid approach has also proven vital in multimodal settings. For example, the text-to-image synthesis model developed by Wang et al. incorporates linguistic word lattices into a Transformer architecture. By digesting a graph of possible word segmentations rather than a single linear sequence, the model prevents early tokenization errors from corrupting the downstream image generation pipeline, demonstrating that the principle of deferred commitment remains highly effective in the neural era.
Key Foundational Work
Morphological Analysis (1973) — contributed 1 concept elements to this direction.
Morphological Analysis (A Formal Approach) (1973) — contributed 1 concept elements to this direction.
Graph Grammar Approach to Natural Language Parsing and Understanding (1983) — contributed 1 concept elements to this direction.