Covering the Readings: Minimum Path Covers of Word Lattices for Chinese Word-Pooled Models

Chinese is written without spaces, so a model has to decide where words begin and end. A short string can often be split into two or more readings, and each looks fine locally. Current systems either commit to one segmentation up front, which means one wrong boundary corrupts everything downstream, or skip segmentation and read raw characters, which is slow and still falls for locally attractive words. We propose a middle path. First, find the smallest set of complete segmentations of a sentence that together include every plausible word. Then let a word-level model read all of them and weigh them against each other. Finding that smallest set is a minimum path-cover problem, the kind of covering problem solved exactly in workforce and sports scheduling. Closing the paths into cycles makes it a minimum-cost circulation, which runs in polynomial time.

The idea, in two sentences: ambiguity is not handled by guessing one reading or by keeping a cloud of overlapping word candidates. Instead, the system enumerates the fewest whole, internally consistent readings that cover all plausible words. That number is a measurable "ambiguity width" for each sentence, and it tells the model exactly how much extra computation that sentence deserves.

Core Claim

Each reading of a sentence is a path through a graph whose nodes are candidate words, with an edge wherever one word can immediately follow another. Exact single-best decoding over this graph is already standard; the semi-Markov models in A Probabilistic Toolkit for Multi-grained Word Segmentation in Chinese do it with CKY. So the novelty cannot be "global decoding." The novelty is the covering question: what is the smallest number $K$ of complete readings such that every candidate word above a probability threshold appears in at least one of them?

By Dilworth's theorem, $K$ equals the largest set of candidate words no two of which can appear in the same reading. That makes $K$ a principled, per-sentence measure of how ambiguous the sentence is. We claim two things. First, feeding a word-pooled model exactly these $K$ readings resolves garden-path errors better than feeding it the top $K$ Viterbi readings, $K$ random samples, or the unstructured union of all candidates. Second, the benefit concentrates on sentences with large $K$.

How the cover is computed

The method has three steps.

  1. Generate candidates. We take candidate words from the span marginals of the multi-grained segmenter cited above. Its three criteria (fine CTB, medium PKU, coarse MSR) share one BERT encoder, so the candidate set naturally mixes granularities.
  2. Prune. We keep spans whose marginal probability exceeds a threshold $\tau$. We then remove any span that cannot lie on a path from sentence start to sentence end.
  3. Solve a circulation. Every remaining word node $v$ must carry at least one unit of flow. A return edge from sink to source closes every reading into a cycle, so the problem becomes a minimum-cost circulation:

$$\min_{f \ge 0}\; M\, f_{\text{ret}} + \sum_{e} c_e f_e \quad \text{s.t. flow conservation and } \sum_{e \in \text{in}(v)} f_e \ge 1 \;\; \forall v.$$

Here $f_e$ is the integer flow on edge $e$, and $f_{\text{ret}}$ is the flow on the return edge, which equals $K$. The edge cost $c_e$ is the negative log marginal of the word the edge enters. $M$ is a large constant, so the solver first minimizes $K$ and then, among covers of that size, prefers probable words.

The construction is borrowed directly from COMBINATORIAL APPROACHES FOR HARD PROBLEMS IN MANPOWER SCHEDULING. That work turns rest-constrained shift schedules into disjoint paths found by minimum-cost flow, and solves the tableau-shaped case as an optimal DAG path cover in $O(n^{2.5})$. The cycle-closing view mirrors The Inter-League Extension of the Traveling Tournament Problem and its Application to Sports Scheduling. That paper covers a distance-weighted graph with 4-cycles so that every team's road trip is feasible by construction, and lands within 3.8% of the lower bound on the NBA.

We differ from both in what is covered: candidate word spans instead of workstretches or stadiums. We also differ in what we allow. Our paths may share nodes, because two readings can agree on most words. That sharing is the same redundancy that Graph-Structured Speculative Decoding exploits when it merges identical drafted subsequences into a DAG. Here we use it to avoid recomputing pooled embeddings for shared words.

Research Program

The model extends the hierarchical architecture of Learn Your Tokens: Word-Pooled Tokenization for Language Modeling. In that architecture, a shallow encoder pools the characters of each word into word embeddings, a main transformer runs over the words, and a shallow decoder emits characters. The authors state that it needs whitespace and is unsuited to Chinese without an external segmenter. We remove that dependency as follows:

  • Pooling. Each distinct word node in the cover is pooled once.
  • Reading through the main model. Each of the $K$ readings is run through the main transformer as a batch element.
  • Classification tasks. A learned attention over the $K$ reading summaries produces the sentence representation.
  • Language modeling. Next-character probability is a learned mixture over readings, which approximates marginalizing over segmentations.

Because $K$ adapts per sentence, unambiguous text pays nearly nothing extra. Measuring the distribution of $K$ on news versus web text is itself a deliverable.

The citations play distinct roles:

  • Motivation. ERAS: Evaluating the Robustness of Chinese NLP Models to Morphological Garden Path Errors shows that character transformers commit to locally frequent words. Its example is 留心机, which should read 留 + 心机 but gets read as 留心 + 机. It also shows that the sentiment of the false word leaks into the prediction. Analysis and Repair of Name Tagger Errors shows that single-segmentation pipelines propagate boundary errors downstream.
  • Constraint. The multi-grained toolkit shows that cross-domain conflicts rise from 1.7% of sentences (NEWS) to 10.9% (BAIKE). Ambiguity width should therefore be domain-dependent, and the method must stay cheap when $K=1$.

Baselines

Naive reference. The do-nothing reference is a character-level transformer of matched parameter count and training data, the setting ERAS evaluates. On ERAS, a character RoBERTa-110M reaches a Garden Path Error Rate as high as 45.4% and humans score 91.3% accuracy (both reported by ERAS). We retrain this baseline on our pretraining corpus so the comparison is like-for-like.

Pipeline baseline. This is the same word-pooled model fed only the single best segmentation from the multi-grained toolkit's CKY decoder. The toolkit reports 94.19% F1 on NEWS-test and 64.73% on BAIKE-test. It is the most direct form of "just segment first."

Learned-boundary pipeline. The same word-pooled model fed the boundaries of the statistical pre-tokenizer from Entropy-Driven Pre-Tokenization for Byte-Pair Encoding. That pre-tokenizer reaches 58.73% F1 on PKU, against 49.30% for plain BPE.

Strongest existing robustness method. The joint whole-word-masking plus segmentation model from ERAS, which reports the lowest garden-path error rate of 18.8%. Beating it on ERAS is our headline target. Because it changes pretraining rather than input structure, we also test whether combining it with our input helps further.

Ablations isolating the cover. All of these use the identical model, candidate set, and per-sentence $K$; only the choice of readings changes:

  • the top-$K$ Viterbi readings;
  • $K$ readings sampled from the semi-Markov posterior;
  • a lattice-union variant, in which all retained candidate words are pooled and attended to as one set with span position encodings, with no complete readings at all.

Fairness and the bar to clear. Every variant gets the same pretraining tokens, the same GPU-hour budget (the $K$-fold main-model cost is charged against our method), and the same hyperparameter search budget. Beating a baseline means a lower ERAS error rate with non-overlapping bootstrap confidence intervals, at no worse character-level perplexity. For Chinese word-pooled language modeling there is no reported result on Lacuna for an eByte/eChar-style model, so that baseline's numbers come from our runs only.

Why not just…?

Why not just use the top-K Viterbi segmentations? This is the most serious threat, because it is trivial to implement. Our reason for doubting it is structural. N-best lists from a semi-Markov model are dominated by near-duplicates that differ at the highest-probability uncertain spot. A low-marginal but correct reading, such as 留 + 心机 inside a sentence that strongly suggests 留心, can fall below rank $K$, while the cover is guaranteed to contain it whenever its words pass the threshold. This is settled cheaply before any model training. We compute oracle-best-reading F1 and gold-word recall for the cover versus N-best at equal $K$ on NEWS-test, BAIKE-test, and the ERAS test sites. If N-best matches the cover there, we drop the cover and report that negative result.

Why not just let a character-level model learn boundaries internally? Interpreting Word-Level Hidden State Behaviour of Character-Level LSTM Language Models finds that character models do concentrate word information at implicit boundaries. But ERAS shows that the learned boundaries follow local frequency and fail on garden paths. Word-Pooled Tokenization also reports a 6.8x training speedup of pooling over pure character models. The character baseline above measures both accuracy and cost directly.

Why not just pool every candidate word and let attention sort it out? If the lattice-union ablation matches our method, then the cover's notion of coherent complete readings adds nothing, and the simpler union model should be preferred. We treat this outcome as a live possibility. Our hypothesis is that a reading-level summary forces the model to score whole interpretations, which is what blocks sentiment leakage from a word that is absent from the correct reading. The ERAS leakage measure in that ablation is the direct test.

Why not just retrain with whole-word masking and segmentation supervision? That model is the strongest baseline, and it is orthogonal to ours. We run it alone and combined with our input. If it alone matches our combined system, our contribution reduces to the diagnostic value of $K$.

Proposed Experiments

The first, decisive, and cheap experiment is purely combinatorial. On PKU, NEWS-test, BAIKE-test, and the 203,944 ERAS pairs, we measure:

  • the distribution of $K$;
  • gold-word recall and oracle F1 of the cover versus N-best and samples at matched $K$;
  • whether $K$ is larger on BAIKE than NEWS, as the conflict rates predict;
  • whether ERAS test sentences have larger $K$ than their controls.

Second, we pretrain the word-pooled model and all baselines at matched budget on the same Chinese corpus. We then evaluate:

  • ERAS error rate and sentiment leakage;
  • segmentation F1 of the highest-weighted reading on PKU and BAIKE;
  • character-level bits per character.

Third, we bin ERAS items by $K$. The method predicts that its advantage over the pipeline and N-best grows with $K$ and vanishes at $K=1$; a flat profile would falsify the mechanism even if average scores improve. Finally, we report wall-clock overhead as a function of $K$, to confirm that the adaptive cost on news text is close to the single-segmentation pipeline.