Modern autoregressive language models do not see text as a sequence of whole words or linguistic phrases. Instead, they operate on subword tokens—fragments of text generated by statistical algorithms (like Byte-Pair Encoding or WordPiece) designed to optimize vocabulary efficiency.
While subwords prevent out-of-vocabulary errors, they introduce a fundamental granularity mismatch with the structural rules of language. Linguistic syntax (such as dependency trees and constituency grammars) and formal languages (such as Python, SQL, or JSON grammars) operate on discrete, meaningful units: words, phrases, or grammar terminals.
When a subword token splits a single variable name, keyword, or syntactic unit into arbitrary fragments, standard parsing and constraint mechanisms break down. A single token might contain half a keyword, span across two distinct syntactic boundaries, or represent a partial terminal symbol. Overcoming this discrepancy is essential for injecting linguistic biases into transformers and ensuring that code generation strictly adheres to formal grammars.
Mapping Word-Level Syntax to Subword Graphs
In natural language processing, incorporating structural "common sense"—such as dependency trees that show how words relate to one another—can significantly improve model performance. However, because traditional syntax trees are structured around whole words, mapping these trees onto subword embeddings without introducing noise is a major challenge, as noted by Mensah et al..
To reconcile word-level syntactic annotations with subword-based tokenization, researchers have developed explicit structural mapping strategies.
Word Level: [ The ] ----(det)----> [ cats ] ----(nsubj)----> [ sleep ]
/ \
Subword Level: [ The ] [ ca ] [ ts ] [ sleep ]
\______/
Internal Chain
Head-Subword Routing
When a word is split into multiple subwords, where should its incoming and outgoing dependency edges go? Deguchi et al. and Deguchi et al. proposed a mapping heuristic: assign the original word's syntactic head to its rightmost subword. The preceding subwords within the split word are then supervised to point sequentially to their immediate right neighbor. This preserves a continuous internal structure within the subword sequence while anchoring external linguistic relations to a single token.
Head-to-All Broadcasting
Alternatively, Sachan et al. explored constructing edges between the head wordpiece of a source word and all wordpieces of its dependent word. This ensures that structural information is fully distributed across the entire fragmented span, though the authors note that these gains can be fragile if the underlying parse trees are imperfect.
Graph Expansion and Token Grouping
Rather than forcing a tree onto subwords, Zhu et al. extended the underlying graph representations (such as Abstract Meaning Representation graphs) to include subword units directly as nodes, ensuring structural consistency from the start. Conversely, Kai et al. introduced specific embeddings designed to group subwords back into single units for structural analysis, preventing the parsing mechanism from treating subword fragments as independent grammatical entities.
Grammar-Constrained Decoding with Fractional Tokens
The subword mismatch is even more disruptive when generating code or structured data (like JSON). Formal languages require strict adherence to a grammar defined by a deterministic finite automaton (DFA) or context-free grammar (CFG). As Poesia et al. observed, a language model's subword tokens frequently do not align with the keywords and identifiers of a programming language's grammar, making it difficult to determine if a partial token sequence will eventually form a valid statement.
If a model generates the subword pr, a standard compiler parser cannot determine if this is valid without knowing the future. If the next token is int, it forms the valid keyword print. If it is ox, it forms prox, which might be a syntax error in that specific context.
LLM Vocabulary Tokens: ["pr", "int", "ox", "if"]
Grammar Terminals: KEYWORDS(print, if), IDENTIFIERS
Valid Path: [ pr ] + [ int ] ---> "print" (Valid Keyword)
Invalid Path: [ pr ] + [ ox ] ---> "prox" (Syntax Error)
To enforce grammar constraints during inference, decoding algorithms must track these fractional states.
Character Remainder Tracking
To resolve this, Ugare et al. developed a method that tracks character remainders during the decoding process. When a token does not form a complete grammar terminal, the system holds the unfinished string fragment in a buffer. The decoding layer then filters the model's vocabulary, masking out any tokens that are incompatible with both the current unfinished fragment and the valid transitions defined by the language's DFA.
Transducer Composition
Park et al. formalized this interaction by treating the lexer as a finite state transducer and composing it with a detokenizing transducer. By precomputing an "inverse token spanner table," their framework (GREATGRAMMA) maps the model's subword output space directly to the formal grammar's terminal symbols. This eliminates the need for slow, character-by-character runtime verification, allowing the system to instantly determine which subwords can legally complete or extend a partial terminal.
Handling Boundaries and Partial Contexts
The tokenization mismatch also manifests at the boundaries of text generation—such as when a user prompt ends in the middle of a word, or when a model needs to copy specific spans from a source text.
The Partial Token Issue
When a prompt cuts off mid-word, the tokenizer often generates a different token than it would if the word were complete. Athiwaratkun et al. addressed this "partial token issue" by introducing an inference-time technique that backtracks to the last certain full token. It then uses character-level matching to ensure the model completes the partial word correctly, preventing frequent syntax errors in code autocompletion.
Navigational Anchors and Copying Mismatches
For tasks requiring structural corrections or precise extraction, operating on raw tokens can lead to failures. Ugare et al. developed IterGen, which uses high-level grammar symbols (like "table names" or "statements") as navigational anchors rather than raw subwords, allowing models to safely backtrack and correct structural errors.
Similarly, in information extraction, Li et al. demonstrated that subword tokenization frequently splits entities or numerical values in ways that conflict with the span boundaries required for accurate pointer-based copying. Aligning these granularities ensures that the model copies complete semantic units rather than fragmented character chunks.
Key Foundational Work
DoughnutPRIS at TAC KBP 2016 (2016) — contributed 1 concept elements to this direction.
Hybrid Multilingual Parsing with HPSG for SRL (2009) — contributed 1 concept elements to this direction.