Ordered Slots for Linear-Cost Span Extraction

Many language tasks ask a model to find pieces of text rather than label single words: names of proteins inside longer protein names, noun phrases that refer to the same person across a document. The standard approach scores every possible start-and-end pair. For a text of $N$ tokens that means about $N^2/2$ candidates, which works for sentences and fails for documents. One alternative has a parallel decoder emit a small, fixed set of "slots," each pointing to a start token and an end token. Its training loss then has to decide which slot is responsible for which gold span. Two answers are in use, and both have problems. The first is a fixed order: slot 1 gets the first entity, slot 2 the second. One missed entity then shifts every later assignment, and every later slot is penalized, which is the same failure that non-autoregressive translation hit with word positions. The second is free matching with the Hungarian algorithm, which lets any slot take any entity. That fixes the shift, but slots can wander anywhere in the text, so each must attend over the whole document. The quadratic cost comes back.

We propose a middle path taken from translation. We sort gold spans in reading order and align them to an ordered set of slots with a monotone dynamic program, the same kind of order-preserving, gap-tolerant alignment that Aligned Cross Entropy introduced for words. Because alignment preserves order, each slot can be anchored to a fixed region of the document and point only within a bounded window. Training and inference then cost linear time and memory in document length, with no span-length cap of 10 or 30 tokens. The central claim is that order-preserving alignment is what makes locality, and therefore linear cost, possible for parallel span extractors. Rigid order cannot get there because a single miss cascades. Free matching cannot get there because slots are not tied to any region.

What exists and what is missing

Three lines of work each solve part of this. On the alignment side, Aligned Cross Entropy for Non-Autoregressive Machine Translation (AXE) replaces position-by-position cross-entropy with a monotone dynamic-programming alignment that can skip prediction slots. It reports gains of up to 5 BLEU on WMT'14 En-De at only about 1.2× training cost. Order-Agnostic Cross Entropy drops order entirely through Hungarian matching. That paper also constrains our design: fully order-free matching could not train from scratch without a cross-entropy warm-up. ngram-OAXE restores local order inside fixed-width n-grams. All three align tokens or fixed n-grams. None aligns variable-length spans defined by their two boundaries. We reuse AXE's recursion and change what is being aligned.

On the span side, Coreference Resolution without Span Representations (s2e) scores mentions with a product of start and end token vectors, never building a vector per span. This cuts Longformer-Large memory from 15.7 GB to 4.3 GB. It still scores all boundary pairs up to length 30, so it remains quadratic within that band and blind beyond it. We adopt its boundary-only scoring as the slot's pointer head. Boundary-gating models such as BENSC and the boundary-aware model of Zheng et al. prune candidates with hard thresholds and lose recall when a boundary is scored low. Boundary Smoothing softens near-miss penalties, but it does so over the full span grid.

Closest to us are the set-prediction models. A Sequence-to-Set Network for Nested NER predicts a fixed set of boundary-pointer queries trained with Hungarian matching. It is strong on ACE and KBP but does not beat the prior best on dense biomedical GENIA (80.44 versus 80.50). Propose-and-Refine shows that boundary re-prediction recovers entities longer than 17 tokens (73.42 F1, where its proposal stage gets none), but it relies on a length-capped n-gram proposal pyramid and Hungarian matching. Span Pointer Networks decode boundary pointers in parallel, yet fix the output count with a separate length predictor, so a miscount breaks every later slot. Our proposal differs from all of these in one specific way: the loss is an order-preserving, slot-skipping alignment rather than either fixed assignment or permutation matching, and that ordering is used to localize the decoder.

Core Claim

Slots trained with a monotone alignment over reading-ordered spans have three properties. First, they match Hungarian-trained slots in accuracy on sentence-level nested extraction. Second, they train from scratch without a cross-entropy warm-up. Third, they can be restricted to local windows, which makes cost linear in document length. Free matching loses at least one of these three. Rigid order loses accuracy through the shift cascade.

Research Program

The model is a pretrained encoder (BERT for sentences, Longformer for documents). We split the input into chunks of $w$ tokens and give each chunk $r$ slot queries, initialized from that chunk's pooled states. The slots are ordered by chunk, then by index within the chunk. Each slot attends only to its chunk and a band of $B$ tokens after it. It outputs three things: a start distribution over its chunk, an end distribution over the band, and a type distribution that includes an empty label $\varnothing$. The start and end scores are s2e-style products between a slot-conditioned query and token vectors, so no span vectors are built. With $B$ fixed (we plan 256), memory grows as $O(N(w+B)r/w)$, which is linear in $N$. Spans up to $B$ tokens are reachable, far beyond the usual caps.

Gold spans are ordered by start ascending and then end descending. For nested entities this places each outer span before its inner spans. Let slot $k$ have start, end and type distributions $p^s_k, p^e_k, p^c_k$. Let gold span $g$ be $(s_g, e_g, y_g)$. We define the match cost $C_{k,g} = -\log p^s_k(s_g) - \log p^e_k(e_g) - \log p^c_k(y_g)$. The alignment score $A_{k,g}$ is computed over the first $k$ slots and the first $g$ gold spans by

$$A_{k,g} = \min\big(A_{k-1,g-1} + C_{k,g},\; A_{k-1,g} - \log p^c_k(\varnothing),\; A_{k,g-1} + \delta\big),$$

where the second term lets a slot output nothing and $\delta$ is a fixed penalty for leaving a gold span unmatched, as in AXE. The training loss is $A_{M,G}$ for $M$ slots and $G$ gold spans. We restrict the recursion to a band in which slots from chunk $j$ may match only gold spans that start in chunks $j-1$ through $j+1$. Under that restriction the program costs $O(N)$ and can be computed along anti-diagonals on the GPU, the same way AXE is.

Two variants probe how much order is needed. A hybrid variant permits Hungarian matching inside a chunk while keeping the dynamic program across chunks. This is the "local permutation, global order" objective that the GENIA result for set models hints at. The other variant adds one-dimensional boundary smoothing to the start and end targets, which is a linear-cost version of Boundary Smoothing. At inference each slot takes its highest-scoring start, end and type independently, with no length predictor and no thresholds.

Baselines

The naive reference point is exhaustive span classification with a length cap, as in Deep Exhaustive Model. It concatenates start, end and pooled interior vectors with $L=10$ and reports 77.1 F1 on GENIA. We rerun it with our encoder at $L=10$ and $L=30$ and record memory. This shows what a capped method achieves with no alignment at all.

The rigid-order ablation keeps our exact architecture, slots and banding, but assigns the $k$-th gold span to the $k$-th slot within each chunk and pads the rest with $\varnothing$. It isolates the alignment ingredient. To beat it, the dynamic program must show a clear F1 gain, concentrated on spans that follow a missed or extra span in the same chunk.

The strongest existing method is the Sequence-to-Set network (Tan et al.). It reports 87.26 F1 on ACE 2004, 87.05 on ACE 2005, 80.44 on GENIA and 83.96 on KBP 2017. Boundary Smoothing reports 87.15 on ACE 2005. We reimplement Sequence-to-Set with our encoder, the same number of slots, the same optimizer, and the same hyperparameter-search budget of 20 trials per method, and we also quote the published numbers. At sentence level we count parity within run-to-run variance over five seeds as success, since the claim there is equivalence. A win on GENIA would support the ordering hypothesis.

For document scale, the strongest competitor is s2e (Kirstain et al.). It reports 80.3 average coreference F1 on OntoNotes 5.0 using 4.3 GB of memory. We compare mention-detection F1 and peak memory as documents grow. We also plug our detected mentions into the s2e linker and compare end-to-end coreference F1. Beating it means equal mention F1 with memory that grows linearly where s2e's grows faster, plus recall on mentions longer than 30 tokens, which s2e cannot produce.

Finally, the locality-masked Hungarian ablation uses our localized slots but replaces the dynamic program with Hungarian matching whose cost matrix forbids non-local pairs. It is the sharpest test of whether order, and not just locality, matters.

Why not just…?

Why not just use Hungarian matching, since with a few dozen slots its cubic cost is negligible? For sentence-level NER this is a real threat. We expect parity there and say so. The argument for order rests on two other things. One is training stability: OAXE reports that order-free matching needs a warm-up (Du et al.), and we test cold-start training directly. The other is that unordered slots have no assigned region, so they need global attention. The locality-masked Hungarian ablation settles whether masking alone recovers what order provides. If it matches our accuracy and stability, the contribution shrinks to the linear-time banded dynamic program, and we will report it that way.

Why not just raise the length cap in s2e or an exhaustive span model? Raising $L$ grows memory as $N\cdot L$ for every token, whether or not any entity is present. Even the cap of 30 used by s2e leaves long mentions unreachable, and Propose-and-Refine shows that capped proposals detect zero entities beyond 17 tokens. Our memory-versus-length curves and the long-span recall bucket test this directly.

Why not just gate boundaries with start and end classifiers, as BENSC does? Gating is cheap. However, Zheng et al. reach only 74.7 GENIA F1 with it, and any boundary falling below the threshold is lost for good. We compare recall at matched candidate counts.

Why not just generate spans autoregressively, as GRIT does? GRIT is strong and fast to train on MUC-4 (54.50 micro-F1). However, decoding is sequential and imposes an arbitrary order on spans. Span Pointer Networks report 70% lower latency for parallel decoding at equal accuracy. We include a GRIT-style pointer decoder on MUC-4 and report both F1 and wall-clock decoding time.

Proposed Experiments

Sentence-level accuracy is evaluated on ACE 2004, ACE 2005, GENIA and KBP 2017 using exact-match span F1. Results are also bucketed by span length (at most 10, 11–30, over 30) and by nesting depth. Document-level scaling is evaluated on OntoNotes 5.0 mention detection and coreference, and on MUC-4 role-filler extraction. On OntoNotes we plot peak memory and time per document against length, from 512 to 4096 tokens.

Three checks are decisive. First, the gap between the alignment loss and the rigid-order ablation should be large, and it should be concentrated after the first missed span in a chunk. If it is not, the shift cascade does not matter in practice and the premise fails. Second, without any cross-entropy warm-up, the alignment loss should converge on GENIA, while the Hungarian variants should either need the warm-up or converge more slowly. Third, on OntoNotes, memory should scale linearly while mention F1 stays within one point of s2e, and recall on spans longer than 30 tokens should be nonzero.

If the hybrid variant (Hungarian inside chunks, order across them) beats the pure dynamic program on GENIA, that becomes the recommended objective. It would tell us that nested spans need local freedom while the document as a whole needs order.