Reservoir Probes for How Tokenization Shapes Incremental Parsing

Incremental parsers build a syntax tree one input symbol at a time, the way people read. Recent cross-lingual work found that the best way to do this is not universal: some languages favor parsers that guess upcoming structure early, others favor parsers that wait for evidence. Every such study fixes the tokenizer, meaning the procedure that cuts text into subword pieces, and never asks whether that choice moves the answer. We propose to ask exactly that. The tool is a reservoir: a large, fixed, randomly wired recurrent network whose only trained part is a linear output layer. A reservoir cannot learn to repair bad tokenization, and its states can be computed once and reused for any number of output tasks. That makes it a cheap and controlled instrument for crossing many tokenizers with many parsing strategies across many languages.

The core claim is that token fertility, the average number of subword tokens per word, interacts with how much a parsing strategy guesses ahead. When fertility is high, the evidence a speculative parser needs sits further back in the token stream, and a fading-memory encoder loses it. We therefore predict that tokenizers with higher fertility push the best strategy for a language toward less speculative, more bottom-up parsing. If this holds, and if it transfers to fully trained parsers, then tokenizer choice and parsing strategy have to be selected together for each language rather than one after the other.

Why this question, and what is already known

The motivating result is Is Incremental Structure Prediction Process Universal across Languages?. It compares 15 parsing strategies, ranging from fully top-down to local-first, inside recurrent neural network grammars on 10 languages. Head-initial languages such as English, German, Hebrew and Swedish favor speculative top-down parsing at large beams. Head-final Chinese and Korean favor bottom-up or local-first parsing. Speculation also breaks down at small beams. The same study found that a preprocessing change as small as deleting the lowest layer of nonterminals in Polish flips the winning strategy. It applied one standard subword split and did not vary it. Given how sensitive the result was to the Polish change, the untested tokenizer is a plausible confound. Modeling Human Sentence Processing with Left-Corner Recurrent Neural Network Grammars supports the same language-specificity on Japanese. That work used word-segmented text only. Both studies motivate the question, and neither answers it.

The tokenizer literature also motivates the question but works in a different setting. Papers adapting vocabularies for Italian, French, Hindi and Bangla (Optimizing LLMs for Italian, CroissantLLM, Hindi LLMs, TituLLMs) show that language-specific vocabularies lower fertility. They measure the gain as sequence length, speed and flat language-model quality, never as structure building. Zero-Shot Tokenizer Transfer trains a hypernetwork that predicts embeddings for a new vocabulary and keeps XNLI accuracy within 1% while shortening sequences by 14%. We borrow its premise that tokenizers should be swappable without retraining the encoder. We do not use its learned hypernetwork, because a learned embedding predictor would be another trained component whose quality could differ between tokenizers.

Reservoir work supplies the method and also limits what we claim. Echo State Neural Machine Translation shows that frozen random recurrent layers can translate but reach only 70–80% of trained BLEU, with 31–32 against roughly 39–40 on WMT'14 English-French. We do not expect a reservoir parser to compete on accuracy, and we do not claim it will. That paper also found that upper layers learn larger spectral radius, the scale that sets how slowly past inputs fade, which suggests memory length is the key setting to sweep. Reservoir states do not depend on the training target, so one set of cached states serves many output layers (Lukosevicius et al.). The echo state property guarantees that memory fades (Gallicchio et al.). Fading memory is usually treated as a limitation. Here it is the mechanism through which fertility should bite. Reservoir Transformers and Echo State Transformer combine frozen and trained parts in flat models, and neither touches syntax or tokenization. No paper in the file combines a reservoir, tokenizer variation and incremental parsing.

Research Program

The central construction turns each parsing strategy into a token-labeling problem. Fix a strategy $s$ and a tokenized sentence. Replay the gold tree under $s$. Each token $t$ receives a tag $y^s_t$: the exact run of transitions that strategy $s$ issues after shifting token $t$ and before shifting token $t+1$. The transitions are opening a phrase, closing a phrase, and so on. Tokens inside a word receive the empty run, because no constituent can close mid-word. Speculative strategies open phrases about material not yet seen, so their tags are harder to predict from the prefix. Cautious strategies postpone decisions, so their tags are easier to predict but delay structure. How predictable each strategy's tags are from the prefix is therefore a direct, measurable cost of speculation.

The encoder is a leaky echo state network driven by the token stream alone. Its states $h_t$ are computed once per tokenizer and language and cached. For every strategy, a separate multinomial logistic readout, which is convex, predicts $y^s_t$ from $h_t$. Fifteen strategies thus cost fifteen convex fits on one cached state matrix rather than fifteen training runs of a recurrent parser.

At test time, a beam over tags is restricted so that the stack stays valid. A complete tag sequence maps deterministically to a tree, which is scored as word-level labeled bracket F1. We report greedy decoding and beam $k=10$, because small beams are where the earlier study saw speculation fail.

Reservoirs need continuous inputs, which raises the question of how to embed discrete tokens fairly across tokenizers. Each token's input vector is a fixed sum of random vectors for its character n-grams. This rule needs no training and applies identically to any vocabulary, so no tokenizer gets better-trained embeddings than another.

The tokenizer condition is varied along a controlled ladder for each language:

  • word-level input,
  • language-specific Unigram and BPE vocabularies at several sizes trained on that language's treebank text,
  • a multilingual vocabulary of the XLM-R kind.

The ladder spans a wide range of measured fertility. Spectral radius and leak rate are swept on a grid. Because states are cheap to recompute, we can locate each condition's memory-optimal setting and ask whether higher fertility shifts that optimum toward longer memory.

Baselines

The naive reference point is a readout that predicts each token's tag from the identity of that token and its predecessor, with no recurrent memory. It is run on the same tags, splits and constrained decoder. It sets the floor that reservoir memory has to clear and shows how much of each strategy's tags are locally determined. The other reference condition is the default setup of a multilingual vocabulary with one fixed strategy chosen per language family. This is the "do nothing about tokenization" pipeline the field currently uses.

The strongest existing method is the fully trained recurrent neural network grammar. Recurrent Neural Network Grammars reports 93.3 F1 on the Penn Treebank and 86.9 F1 on Chinese Treebank 5.1 for the generative model. For the 15-strategy multilingual setting of Ishii & Miyao, the file gives no exact F1, so we find no reported result on Lacuna for per-strategy SPMRL F1. We will not beat 93.3 and do not try. The trained grammar is the reference whose strategy rankings our probe must reproduce. We retrain it, in that paper's setup, on a subset of 3 languages × 3 tokenizers × 4 strategies with an equal hyperparameter budget per cell. Beating it is not the target. Success means the probe ranks strategies within each language and tokenizer the same way the trained grammar does, with Kendall's tau above 0.6 on the held-out cells.

The ablation that isolates the key ingredient keeps everything identical but replaces the reservoir with a trained unidirectional LSTM of matched state size. It uses the same tags, inputs, decoder and tuning trials. If the fertility–strategy interaction appears with the reservoir and vanishes with the LSTM, then the effect belongs to fading memory and is not a property of the languages. That would be a meaningful finding in its own right, but it would limit how far our claim reaches. A second ablation freezes the tokenizer and varies only the spectral radius. This separates "more tokens" from "too little memory".

Why not just…?

Why not just train recurrent neural network grammars for every combination? Ten languages, five or more tokenizer conditions and 15 strategies give roughly 750 trained parsers, each sensitive to its own tuning. A trained encoder can also partly learn around a bad segmentation, which mixes the tokenizer's effect with the encoder's ability to adapt. This alternative is a real threat if the reservoir rankings disagree with trained ones. The subset retraining experiment exists to settle that. If agreement fails, we report the probe as invalid and fall back to a smaller trained study.

Why not just parse at word boundaries and pool subwords? That removes the question rather than answering it. Streaming systems built on subword language models, such as the setting of StreamingThinker, see subword tokens as they arrive. We include word-level input as one end of the ladder. If word-level input dominates every subword condition for every strategy, the practical conclusion is simply "parse words". That is still a useful negative result.

Why not just put a linear readout on a frozen pretrained language model? That is also fixed features plus a linear readout, and its features are far richer. However, its tokenizer is welded to its weights, so tokenization cannot be varied without retraining or adding a learned embedding transfer. Fertility would then be confounded with pretraining data and embedding quality. We run it once per language with its native tokenizer as an accuracy reference. We do not use it for the fertility comparison.

Proposed Experiments

The data are the Penn Treebank, Chinese Treebank 5.1, the SPMRL treebanks (French, German, Korean, Basque, Hebrew, Hungarian, Polish, and Polish with lowest nonterminals removed, plus Swedish) and the NINJAL Parsed Corpus of Modern Japanese. These cover both branching directions and the Polish annotation contrast.

The primary analysis regresses, for each language, the identity and margin of the best strategy on measured fertility. It controls for vocabulary size and memory setting. The decisive check has three parts. Within head-initial languages, raising fertility should shift the winning strategy toward less speculation. The gap between speculative and cautious strategies should narrow as spectral radius grows. The shift should reappear in the trained-grammar subset. If fertility moves no strategy ranking in any language, the hypothesis is false, and the existing literature's habit of fixing the tokenizer is vindicated.

A secondary check adds a next-token readout to the same cached states. On BCCWJ-EyeTrack it tests whether reservoir surprisal reproduces the ordering of left-corner over top-down over sequential models found in the left-corner study, where ΔD was about 306, 299 and 260. It also tests whether that ordering survives a change of tokenizer. We report all compute as fit time and state-cache size against the trained-grammar subset, because cheapness is what justifies the probe.