Constrained Tagging for Span Labeling

1 Introduction

• Generative outputs may not identify which occurrence of a repeated span was selected, or may return text that cannot be aligned to the input.This makes precise localization a central challenge for generative span labeling.Source: §1 · p. 1
• Constrained tagging reproduces the input and wraps each identified span in inline markup carrying its label.A logits processor permits only input continuations or valid tags, enforcing verbatim copying and labels from the supplied set.Source: §1 · pp. 1–2
• The method is training-free and allows span boundaries at any character boundary, including inside a token.Two-phase decoding leaves reasoning unconstrained and applies the constraint to the answer.Source: §1 · p. 2
• Evaluation spans six datasets and six open-weight models, with the guarantee holding in all but 0.022% of 255,312 constrained generations.The remaining errors are attributed to which spans models choose, not where they are located.Source: §1 · p. 2

2 Background and Related Work

• Encoder-only classifiers directly map token predictions to positions, but require task-specific labeled data and retraining for new classes or domains.This motivates exploring generative LLMs for span labeling.Source: §2 · p. 2
• Several generative approaches return entity lists without positions, leaving spans to be matched back to the input; surveys report persistent boundary and alignment difficulties.GPT-NER instead reproduces the input with special entity markers, while other systems use free text, code, or fine-tuned output.Source: §2 · p. 2
• Among tagging, indexing, and matching strategies, Semin et al. (2026) found tagging most robust on four tasks, but their constrained matching method did not extend to tagging because of boundary tokenization issues.Their LogitMatch restricts matching spans to input substrings; constrained tagging here handles boundaries with byte-level prefix search and a copy cursor.Source: §2 · p. 2
• Grammar decoders constrain outputs to formal languages, but a fixed grammar cannot require verbatim input reproduction; input-dependent inline-markup grammars have instead been explored at word granularity.The related work describes tokenizer-specific workarounds for word-level approaches.Source: §2 · pp. 2–3
• Prior trie- and copy-based methods insert markup or draw entity text from the input, but fine-tune models and operate at token granularity.The byte-level trie in this paper lets an off-the-shelf model place boundaries inside tokens.Source: §2 · p. 3

3 Datasets

• The six datasets cover named entity recognition, toxic-span detection, extractive question answering, machine-translation error detection, and grammatical error correction.The dataset table summarizes the axes along which they differ.Source: §3 · p. 3, Table 1 · p. 4
• NER uses CoNLL-2003 and UniversalNER, with four entity types in the former and three coarse types across 18 treebanks in 12 languages in the latter.NER spans are guaranteed to fall on word boundaries, and both datasets are represented as BIO tags over whitespace tokens.Source: §3 · p. 3
• Toxic Spans evaluates character-level toxicity annotations on 1,000 posts; 48.6% have no majority-agreed toxic span despite toxic comment-level tone.Annotations come from three to five crowdworkers, with a character labeled gold when a majority marked it.Source: §3 · p. 3
• LegalQAEval contains 1,206 legal-passage questions, exactly half unanswerable, while ESA-MT covers 867 translations with error spans labeled MINOR or MAJOR.ESA-MT spans 24 source–target–domain files and eight target languages; its source text is context and is not copied or tagged.Source: §3 · p. 3
• MultiGEC uses 504 learner essays with edits grouped into replacement, missing, and unnecessary categories; missing spans have zero length.CoNLL-2003 and UniversalNER are subsampled uniformly per seed, while the other four datasets are fully evaluated.Source: §3 · pp. 3–4

4.1 Problem Statement

• Span labeling returns labeled character-offset intervals, including an optional empty set and zero-length spans; constrained tagging encodes them as markup in a copy of the input.A cursor fixes each span's offsets when its tag opens, so repeated surface forms need no alignment step.Source: §4.1 · p. 4

4.2 Byte-Level Token Trie

• A byte-level vocabulary trie permits span boundaries at any character boundary, including inside an input token.In ESA-MT, 22% of error spans begin or end inside a word; byte-level search also handles tokens containing only part of a multibyte character.Source: §4.2 · p. 4

4.3 Constrained Logits Processor

• The finite-state processor masks invalid tokens, allowing only input continuations or valid markup and labels, with end-of-sequence available after the full input is copied.Guards restrict markup to codepoint boundaries, disambiguate literal < characters, and apply label-specific rules to zero-length spans; the guarantee can fail if generation is cut off.Source: §4.3 · p. 5, Figure 2 · p. 5

4.4 Two-Phase Reasoning-Aware Decoding

• Two-phase decoding leaves reasoning unconstrained and activates the constraint at the reasoning-closing marker, while accommodating models that may answer directly.The exact-copy guarantee is conditional on the model closing its reasoning; budget exhaustion or ending while still reasoning can leave an empty answer.Source: §4.4 · p. 6

4.5 Complexity

• Trie construction is linear in vocabulary byte length, and constrained decoding costs O(G · |V|), the same order as unconstrained decoding.The per-step masking cost dominates and does not depend on input length.Source: §4.5 · p. 6

5 Experiments and Results

• The evaluation covers six open-weight models from three families, compares constrained tagging with unconstrained tagging, context-based prompting, and XGrammar, and reports pooled character-overlap F1.Context-based prompting was tested for one model per family and XGrammar only with reasoning off; the headline metric distinguishes hard F1, which requires the right label, from soft F1, which credits correct location.Source: §5 · p. 6

5.1 Main Results

• Constrained tagging beats unconstrained tagging on five of six datasets and is on par with context-based prompting on average on LegalQAEval (+1.0) and ESA-MT (+0.1), but trails it on four datasets.Table 2 reports hard F1 (soft F1 in parentheses) across the six datasets; the largest gap is for the smallest model, gemma-4-E2B-it.Source: §5.1 · pp. 6–7, Table 2 · p. 7
• Against Semin et al. (2026), constrained tagging matches their tagging within 0.2 points on UniversalNER and ESA-MT for gemma-4-31B-it, but is 2.2 points lower on MultiGEC and 9.0 points higher than LogitMatch.For Qwen3-8B, it is ahead on ESA-MT and behind on the other two datasets; Table 3 compares hard F1 with published tagging and LogitMatch results.Source: §5.1 · p. 7, Table 3 · p. 7

5.2 The Verbatim Guarantee

• 56 of 255,312 constrained generations (0.022%) failed to finish; unconstrained tagging produced wrong text in 34.6% of generations, while context-based prompting lost 8.5% of proposed spans.Constrained failures were due to reasoning not closing or reaching the answer token budget; context prompting lost 22.4% of spans on LegalQAEval.Source: §5.2 · pp. 7–8, Table 4 · p. 7

5.3 Where Accuracy Is Lost

• The guarantee fixes location, not span selection or labels: constrained tagging misses the fewest gold spans on every dataset but tends toward more, longer proposals and lower precision.On CoNLL-2003, 12.8% of its spans have the right label but wrong boundaries, versus 3.7% for context-based prompting; 31.7% of correctly delimited ORG spans are labeled LOC.Source: §5.3 · p. 8

5.4 Effect of Reasoning

• More reasoning raises each model’s average hard F1 across six datasets by 2.6 to 6.7 points, but some model-dataset pairs decline and reasoning-token costs can be high.Under two-phase decoding, reasoning fails to close in at most 0.13% of batch-size-1 generations and up to 5.5% at batch size 64.Source: §5.4 · p. 8

5.5 Cost and Batch Size

• The constraint adds no measurable decoding cost, but copying the input makes tagging slower when inputs contain few spans and faster when span lists are longer.At batch size 64, recall falls for most models; constrained tagging is more accurate for gpt-oss-20b on UniversalNER, while gemma-4-E2B-it falls to 8.5 hard F1 on CoNLL-2003.Source: §5.5 · p. 8

• 0.022% of 255,312 constrained generations failed the verbatim guarantee, with each failure caused by a reasoning model exhausting its token budget or not closing its reasoning.Source: §6 · p. 8
• Constrained tagging never loses a span it proposes, whereas context-based prompting loses up to 22% on long passages.Source: §6 · p. 8
• Constrained tagging matches context-based prompting on legal question answering and translation error detection, while missing the fewest gold spans on every dataset.Source: §6 · p. 8
• Remaining errors concern which spans the model chooses, not where they are located, and may be reduced by better prompts or light fine-tuning.Source: §6 · p. 8

• The verbatim guarantee holds only when the model closes its reasoning and finishes its answer within budget; a failed generation yields no spans.Reasoning effort and batch size therefore need to be chosen with the budget in mind.Source: Limitations · p. 9
• The guarantee concerns span location, not whether spans or labels are correct; context-based prompting is more accurate on four of six datasets.Source: Limitations · p. 9
• The processor requires modifiable decoding logits, so it cannot be used through a chat API that returns only text.Source: Limitations · p. 9
• Without reasoning, constrained tagging generates 3.6 times as many tokens as context-based prompting on LegalQAEval, though reasoning narrows the ratio to 1.3.The constraint itself adds no measurable decoding cost.Source: Limitations · p. 9
• No significance tests were run, so differences of a point or two between arms should not be read as established; two datasets were subsampled and results average three seeds.Source: Limitations · p. 9
• The evaluation uses one untuned English prompt and public datasets whose test data may have appeared in pretraining, limiting universality and potentially inflating absolute scores.Not every configuration was run, no fine-tuned model was tested, and inherited benchmark conventions include 19 unreachable zero-length spans; the guarantee is relative to NFC-normalized input.Source: Limitations · p. 9

• The six public datasets were used only for research evaluation, no new annotations were collected, and dataset and metric licenses or usage terms are acknowledged.The MultiGEC corpus is not included in released code and must be obtained from its licensor.Source: Ethics Statement · pp. 9–10
• Toxic Spans contains toxic user comments, and the released prompts quote two short examples of such language.Source: Ethics Statement · p. 10
• Constrained tagging is intended to assist human annotators, and outputs for consequential decisions should be reviewed because span and label errors remain possible.Source: Ethics Statement · p. 10
• Experiments used about 4,300 GPU-hours, including pilot runs and failed jobs.Source: Ethics Statement · p. 10

• The six models were evaluated using vendor-recommended sampling parameters and an 18,000-token generation budget, with batch size 1 and batch size 64 on the two NER datasets.Source: A Experimental Setup · p. 12
• Every configuration used seeds 42, 43, and 44, and reported values are three-seed means with standard deviations over seeds as error.Source: A Experimental Setup · p. 12
• Context-based prompting returns JSON spans with copied context for exact matching, while XGrammar enforces the JSON schema and label set; baseline coverage was limited by model and reasoning setting.Source: A Experimental Setup · pp. 12–13
• Hard and soft F1 were computed with Semin et al.'s implementation, with UniversalNER and ESA-MT subset scores macro-averaged.Source: A Experimental Setup · p. 13
• Experiments used Transformers and PyTorch, with constrained-tagging results from H200 runs and XGrammar mostly on A100 GPUs.Source: A Experimental Setup · p. 13

B.1 Runtime

• Without reasoning, gemma-4-31B-it averages 5.0 seconds per generation; reasoning multiplies gemma-4-E2B-it time by 7.6 to 75.7 seconds.Generation time depends more on reasoning length than model size; reasoning can take a generation past 2,000 seconds when it approaches the token budget.Source: §B.1 · p. 13

B.2 Reasoning

• Reasoning gains vary by dataset: they are largest on MultiGEC for Qwen3.8-27B and UniversalNER for gpt-oss, but negative on Toxic Spans for gpt-oss and UniversalNER for Qwen3.8-27B.Within a dataset, the answer is nearly constant in length; tokens above it are reasoning.Source: §B.2 · p. 13

B.3 Failures

• Table 7 accounts for every constrained generation whose output differs from its input: none is a copying error; failures arose when reasoning never closed or, at batch size 64, the token budget ran out during answer copying.Source: §B.3 · p. 13

B.1 Runtime

• Against the context-based baseline, constrained tagging is slower on Toxic Spans, LegalQAEval, and ESA-MT, faster on MultiGEC, and close on both NER datasets.The comparison is indicative because the methods ran as separate jobs with different numbers of model copies per GPU.Source: §B.1 · p. 13, Figure 3 · p. 14

C Additional Tables

• The additional tables report per-arm results and failures, decompose span and label errors, compare reasoning settings, and contrast batch sizes 1 and 64.Table 6 also reports standard deviations over seeds and averages for arms run with all three methods.Source: C Additional Tables · p. 14

D System Prompts

• Prompts share a task description, label definitions, output format, rules, and one or two worked examples; context-based prompts use four to eight words, or three to eight for Toxic Spans.Source: D System Prompts · p. 14

E Processor Details

• Token-Aware tracks the input token and byte offset, while Whole-Sequence uses one byte pointer; both allow within-token boundaries, but earlier tests favored Token-Aware on CoNLL-2003.The two variants were within the seed spread on Toxic Spans and LegalQAEval; the CoNLL-2003 gap widened with batch size.Source: E Processor Details · p. 16

F Algorithms

• The byte-level trie stores token IDs at token-ending nodes, and prefix search returns tokens whose byte strings prefix the remaining input.The trie’s nodes map bytes to child nodes.Source: F Algorithms · p. 17
• Figure 6 separates generated tokens into reasoning and answer; the answer is a near-constant-length copy of the input plus tags within each dataset.Tokens above the answer portion represent reasoning.Source: Figure 6 · p. 18
• The supplementary tables cover hard F1 by reasoning setting and batch size, plus recall and precision breakdowns for the two NER datasets.Table 6 reports hard F1 by model, reasoning setting, and method; Tables 10–12 provide the additional comparisons.Source: Table 6 · p. 19, Table 10 · p. 21, Table 11 · p. 21
• At batch size 1, ten constrained generations failed because reasoning did not close; at batch size 64, 46 further UniversalNER failures included 28 answer-budget exhaustions.Four of the ten batch-size-1 reasoning failures reached the 18,000-token cap; six ended the model turn while still reasoning.Source: Table 7 · p. 19
• Table 8 classifies span errors by boundary and label correctness, spurious spans, and missed gold spans; Table 9 reports predicted-label confusion for spans with exact boundaries.Source: Table 8 · p. 20, Table 9 · p. 20
• Earlier smaller-model tests favored Token-Aware over Whole-Sequence on CoNLL-2003 for every model, with a widening gap as batch size grew; the variants were within seed spread on two other tasks.Figure 7 covers CoNLL-2003 results from three smaller instruction-tuned models, averaged over greedy and sampling decoding.Source: Figure 7 · p. 22