compiler-theory-illuminates-tokenizer-model-separation

IN derived (depth 2)

Created 2026-06-21T13:01:36+00:00 · Reviewed 2026-06-21T14:41:08+00:00

The formal language hierarchy separating lexer-level processing (regular languages, finite-state machines) from parser-level processing (context-free languages, pushdown automata) has a structural analog in LLM architecture: subword tokenization (BPE/WordPiece) operates at the finite-state statistical level while attention provides the unbounded context-sensitivity that finite-state processing cannot, illuminating why tokenization remains a separate preprocessing stage rather than being absorbed into the model's core computation.

Justifications

SL — Formal language hierarchy explains why tokenization and attention are architecturally separate

Antecedents (all must be IN):

IN lexer-fsm-parser-pushdown-automaton — In compiler design, the lexer uses a finite-state machine (FSM) while the parser uses a pushdown automaton (stack-based); regular expressions cannot count or match recursive structures.
IN subword-tokenization-bridges-lexical-and-neural-worlds — Subword tokenization (BPE, WordPiece) occupies a unique position between classical lexical analysis and neural processing — it uses statistical merging rules rather than linguistic grammars, producing variable-granularity tokens that differ fundamentally from both compiler tokens and word-level NLP tokens.

Dependents

These beliefs depend on this one:

IN disambiguation-boundary-violation-is-universal-computational-constraint — The need for semantic context to resolve disambiguation appears as a recurring pattern across processing hierarchies: both compilers (the C lexer hack requiring symbol table feedback across the lexer-parser boundary) and LLMs (prompt injection exploiting the inability to distinguish instructions from data) exhibit cases where lower-level processing cannot resolve meaning without higher-level semantic knowledge, suggesting that formal processing-level separations face inherent pressure from disambiguation demands that cross those boundaries.