Document Label Inventories for Large-Label Sequence Tagging

Many tagging tasks assign each word one label from a very large set. Examples are syntactic supertags (rich grammatical categories, numbering in the hundreds or thousands) and word senses (over 95,000 WordNet meanings). The classic way to make the labels of neighboring words agree is a conditional random field (CRF), a model that scores every pair of adjacent labels. Its cost grows with the square of the label count, so it becomes impractical at these sizes. A separate problem appears in long documents. Text is cut into sentences or fixed windows before tagging, and the cut removes the distant clues that would settle an ambiguous word. This is called contextual fragmentation. The two problems have been studied apart. Methods that handle large label sets work one sentence at a time, and methods that restore document context have only been tested on label sets of 4 to 18 classes.

We propose to solve both problems with a single object, the document's label inventory: the small subset of the full label set that a given document actually uses. A first, cheap pass reads the whole document with an encoder that sees past sentence boundaries and predicts a soft inventory. A second pass then runs exact structured decoding, but each token only considers candidate labels drawn from its own local guesses and from that inventory. The inventory shrinks the quadratic transition cost from the full label set to a handful of candidates per token. It also carries evidence from elsewhere in the document that a sentence-level tagger cannot see, which is the information fragmentation destroys. The same mechanism therefore makes decoding cheaper and the tagger better informed.

Core Claim

Our hypothesis has two parts. First, in long documents the labels in use are both sparse and predictable. Within a WSJ article or a Brown-corpus text, a small number $k$ of candidate labels per token, chosen with document information, should cover the gold label nearly as often as the full label set does. This is the "one sense per discourse" intuition extended to supertags and fine-grained types. Second, document-conditioned candidates should cover the gold label more often than candidates chosen from the sentence alone, at the same $k$. That gap is where document context earns its place.

If both parts hold, Viterbi decoding over the restricted candidates costs $O(N k^2)$ rather than $O(N L^2)$, where $N$ is the number of tokens and $L$ the label count. It should also be more accurate than both sentence-local pruning and unstructured prediction. Concretely, each token $i$ in document $d$ gets the candidate set

$$C_i = \text{TopK}_y\big[\log p(y \mid x_i, \text{local}) + \lambda \log \pi_d(y)\big].$$

Here $p(y \mid x_i, \text{local})$ is the first-pass label probability for the token, and $\pi_d(y)$ is the document inventory. The inventory is computed by pooling first-pass label distributions over all tokens in $d$ that share the word type, lemma, or encoder neighborhood of $x_i$, plus a document-wide label prior. The weight $\lambda$ is tuned on development data. Setting $\lambda = 0$ recovers purely local pruning, which is exactly the ablation that isolates our contribution.

This differs from the closest work in a specific way. Doc-ARC (Attending to Long-Distance Document Context for Sequence Labeling) retrieves distant sentences that contain the same word and attends over their hidden states. DocL-NER (Leveraging Document-Level Label Consistency for Named Entity Recognition) stores draft label embeddings in a document memory and refines uncertain tokens. The Span Graph Transformer (Span Graph Transformer for Document-Level Named Entity Recognition) links identical mention strings across sentences. All three use document context to enrich representations over small entity label sets. None uses it to restrict the output space so that exact structured decoding becomes affordable. We do the reverse: document evidence decides which labels are worth decoding over.

Research Program

The program builds on prior work in three roles.

The first-pass encoder borrows from late chunking (Late Chunking: Contextual Chunk Embeddings Using Long-Context Embedding Models). That paper encodes a whole long document, using overlapping macro-chunks when it exceeds the window, before pooling chunk vectors. We keep the per-token states instead of pooling them. Each token is then scored against a learned label-embedding matrix, which is linear in $L$, in the manner of LAN (Hierarchically-Refined Label Attention Network for Sequence Labeling). LAN replaced the CRF with label embeddings and attention, but it stayed within sentences.

The second pass is a CRF whose transition scores are computed only among candidates. Transition potentials come from a low-rank product of label embeddings, so no dense $L \times L$ matrix is ever stored. Training uses exact forward-backward over the candidate lattice. When the gold label falls outside the candidates, it is forcibly added during training.

The pruning idea itself descends from tag dictionaries (An Improved Tag Dictionary for Faster Part-of-Speech Tagging), which restrict candidates using corpus-level statistics, and from active/inactive state splitting (Efficient Inference of CRFs for Large-Scale Natural Language Data), which approximates rare transitions by global frequency. Both are static across documents. Ours is recomputed for every document.

Prior work also motivates and constrains the design. Lester et al. (Constrained Decoding for Computationally Efficient Named Entity Recognition Taggers) showed that dropping learned transitions is harmless when most tokens have a single plausible label, but hurts on ambiguous data: on OntoNotes the CRF reached 87.43 F1 against 86.13 for constrained decoding. This motivates a measurable question. Does document context raise the fraction of such single-label tokens? Their finding also constrains us to keep soft, learned transitions rather than hard masks. Deschacht and Moens (Efficient Hierarchical Entity Classifier Using Conditional Random Fields) found that hard top-down taxonomic pruning cannot recover from early mistakes. To avoid that failure, our candidate set always keeps the top few local guesses alongside inventory labels, and we report how often the gold label is pruned away.

The analysis component measures inventory sparsity directly. For each benchmark we plot how often the gold label is among the candidates, as a function of $k$, under three settings: no document information, a document-wide label prior only, and the full type-linked inventory. We also recompute Lester et al.'s token-dominance statistic with and without document context. This tests Gap 2 of the file empirically rather than by assumption.

Baselines

The naive reference point is a sentence-level encoder with independent per-token softmax over all $L$ labels and no transitions. It shows how much any structure or context buys.

The strongest existing method on large label sets is LAN. It reports 94.7% accuracy on CCG supertagging and runs about 20% faster than a CRF there (Hierarchically-Refined Label Attention Network for Sequence Labeling). We will rerun LAN with the same pretrained backbone as our system so that encoder strength is not confounded. Beating it means higher CCG accuracy at equal or lower decoding time per token.

On word senses, the reference points are the hierarchical WordNet CRF at 77.82% and the most-frequent-sense baseline at 67% on SemCor (Efficient Hierarchical Entity Classifier Using Conditional Random Fields). Those numbers come from a much older feature set, so we will also train a modern sentence-level CRF-over-local-top-$k$ baseline on the same backbone. The comparison we treat as decisive is against that retrained baseline.

On document-level NER, Doc-ARC reports 84.25 F1 on OntoNotes$_{1000}$ against a local baseline of 82.20 (Attending to Long-Distance Document Context for Sequence Labeling). DocL-NER is the strongest label-memory competitor. The file gives its CoNLL score (92.13 F1) but no quoted OntoNotes figure, so we will reimplement it with our backbone on every benchmark. Its memory then scales to the full label set, and its uncertainty threshold receives the same tuning budget as our $\lambda$ and $k$. On this small-label setting we only aim to match these systems. The point there is to show that inventory pruning loses nothing when $L$ is small.

The key ablation is identical to our full system with $\lambda = 0$. It uses the same candidate size, the same CRF, and the same late-chunked encoder, but chooses candidates from the token alone. A second ablation keeps $\lambda > 0$ but builds the inventory from a sentence-only encoder. Together they separate the contribution of the inventory from the contribution of cross-boundary encoding.

All systems share the training data, backbone, a fixed GPU-hour budget, and an equal number of hyperparameter trials.

Why not just…?

Why not just prune each token to its local top-$k$ labels and run a CRF over those? This is the most serious threat. If the local top-$k$ already contains the gold label as often as the document-informed set does, our method reduces to standard beam pruning. The $\lambda = 0$ ablation settles this directly. We will report gold-label coverage and final accuracy at matched $k$, broken out for rare and document-specific word types. Doc-ARC's +17.6 F1 gain on the rarest 1% of TF-IDF words suggests that is where local candidates fail. If no gap appears there either, we will report the negative result and stop claiming a document effect.

Why not just feed the whole document to a long-context encoder and predict each label with a softmax? This handles fragmentation but adds no label structure. Lester et al.'s OntoNotes result shows structure matters precisely when labels are ambiguous. HiPool (HiPool: Modeling Long Documents Using Graph Neural Networks) found that Longformer and BigBird trail hierarchical models on documents over 4,000 tokens, though that was for document classification, not tagging. We include this system with our own encoder, so the comparison isolates the second pass.

Why not just scale DocL-NER's label memory to thousands of tags? It is a plausible competitor. However, its refinement fires only above an uncertainty threshold, and with thousands of labels almost every draft is uncertain, so the threshold stops being selective. It also never prunes the output space, so transition modeling remains either absent or quadratic. Our reimplementation reports its accuracy and latency at full label scale.

Why not just use a corpus-level tag dictionary? Moore's dictionaries are fixed across documents and cannot express that one article uses a different sense or supertag distribution from another. A dictionary-only variant, with candidates allowed only if seen with the word type in training, is included at matched $k$.

Proposed Experiments

The main benchmarks are three. CCG supertagging on WSJ provides hundreds of labels, and its articles serve as documents. SemCor provides WordNet senses, with Brown-corpus texts as documents. OntoNotes$_{1000}$ provides 18 entity types with BIO tags. LitBank is a secondary long-document check.

Metrics are tagging accuracy (or F1 for NER), gold-label coverage as a function of $k$, Lester-style dominance with and without context, decoding milliseconds per token, and peak memory. Peak memory addresses the compound memory concern raised by late chunking.

The first decisive check is the coverage curve. If document-informed candidates at $k = 8$ do not cover the gold label noticeably more often than local candidates at $k = 8$, the core claim fails. The second check is matched-$k$ accuracy against the $\lambda = 0$ ablation, reported separately for frequent and rare word types. The third is whether, at the same encoder, our system beats LAN on CCG accuracy and speed, and beats the retrained local-pruning CRF on SemCor. The fourth is the dominance analysis, which tells us whether document context makes cheap structured decoding safe. That would answer the open tension Lester et al. leave between hard constraints and ambiguous corpora.