Label-Conditioned Routing in Document Graphs

When a classifier reads a long document, different labels need different evidence. That evidence is often scattered: a clinical trial's outcome is stated in the results, the intervention in the methods, and the two are tied together only by a repeated drug name. Today's two best tools each handle half of this. Label-aware attention treats each category as a learned or name-derived query vector that searches the text for its own evidence, but it searches a flat token sequence and only chooses what to pool. Document graphs make sentences, sections and entity mentions into nodes and let information hop between distant units, but the hops are the same whatever label is being predicted. We propose to let the label decide the route. Each candidate label's query gates the edges of a document graph, so the evidence gathered for "adverse effect" travels a different path through the document than the evidence gathered for "efficacy."

The claim is specific enough to be falsified. Choosing which evidence to pool per label is not enough when a label's evidence has to be composed across distant document units. Choosing how evidence propagates per label should therefore help, and the help should grow with how far apart the supporting units are. On short or single-sentence cases it should disappear. We also make the idea affordable: a cheap first pass proposes a short list of candidate labels, and only those labels get their own routing.

Core Claim and Position in Prior Work

Three lines of work motivate the gap. Heterogeneous document graphs such as the dual-tier graph of Zhang et al. connect words, sentences, mentions and entities with typed edges and propagate over them with a relational graph network. The hierarchical inference network of Tang et al. reasons at entity, sentence and document level. The word–sentence graph of Wang et al. lets sentence nodes steer word importance. All three propagate information the same way regardless of which relation type or category is being scored.

Label-aware attention takes the opposite side. LSAN (Xiao et al.) uses label-name embeddings as attention queries over BiLSTM states and fuses them with self-attention. LCAM (Abaho et al.) applies label–word cross-attention to clinical spans. LaMP (Lanchantin et al.) and MrMP (MrMP) add message passing, but only among label nodes, over a flat input. The closest system, Ye et al., is the obvious version of our intersection. It builds heterogeneous graphs over metadata and over labels and fuses them into flat-Transformer text embeddings with label-specific attention. The document's own internal structure is never a graph there, and no label changes how anything propagates.

We differ from all of these in one place: the edge weights inside the document graph are functions of the label query. That choice is our contribution.

Two papers constrain the design rather than motivate it. Buchmann et al. show that long-document Transformers gain structural awareness from delimiter tokens and depth embeddings alone, with no graph network. This makes "structure tokens plus label attention" the main threat, and we treat it as the primary baseline rather than a strawman. Yan et al. show that full end-to-end co-training of a language model with a graph network often runs out of GPU memory. We therefore encode text in chunks and interleave graph layers only in the top few Transformer layers.

That interleaving is the method we borrow from GL-Fusion (Yang et al.). GL-Fusion inserts message passing between Transformer blocks so that text and structure co-evolve. It was built for single-type citation and code graphs with ordinary classification heads, so it contributes the integration mechanism and nothing on the label side.

Research Program

The document graph is built only from signals that do not require a syntactic parser. This follows the error-propagation concern raised in Zhang et al.. Nodes are sentences, paragraphs, sections and entity mentions. Edges are:

  • sentence adjacency;
  • containment (sentence in paragraph, paragraph in section), taken from document markup where available;
  • string-match or dictionary-matched mention links across sentences, which act as the non-local shortcuts described by Christopoulou et al..

Each paragraph is encoded by a pretrained language model. In the top $K$ layers, node states pooled from token states exchange messages, and the updated node states are written back to the tokens by cross-attention, as in GL-Fusion.

Label queries. Each label $l$ has a query $q_l$ initialized from an encoding of its name or definition, following LSAN and LCAM.

Candidate shortlist. A first pass proposes candidate labels. It is a standard label-attention readout over label-agnostic node states, and it keeps the top $k$ labels, with $k$ around 32–64.

Label-conditioned propagation. For each candidate label, propagation over the graph runs with label-specific edge gates:

$$h_i^{(t+1),l} = h_i^{(t),l} + \sum_{j \in \mathcal{N}(i)} \sigma\!\left(q_l^\top A_{r_{ij}} [h_i^{(t),l}; h_j^{(t),l}]\right) W_{r_{ij}} h_j^{(t),l}.$$

Here:

  • $h_i^{(t),l}$ is node $i$'s state at step $t$ in label $l$'s copy of the graph;
  • $\mathcal{N}(i)$ is the set of neighbors of node $i$;
  • $r_{ij}$ is the type of the edge between $i$ and $j$;
  • $W_r$ is the message transform for edge type $r$;
  • $A_r$ is a low-rank matrix that maps a concatenated node pair into query space;
  • $\sigma$ is the logistic function.

The final score for label $l$ is label attention of $q_l$ over label $l$'s own propagated node states.

Cost. This scales as $k \cdot |E| \cdot T$, where $|E|$ is the number of edges and $T$ the number of propagation steps. It does not scale as $L \cdot N$ over the full label set and all tokens, which is the extreme-label bottleneck noted for LSAN and LaMP.

Training. The shortlist is trained jointly with the second pass. Gold labels are forced into the candidate set during training, and shortlist recall@$k$ is reported so that shortlist errors are visible rather than hidden.

Relation extraction. For document-level relation extraction, the "labels" are relation types. The candidate relation types are chosen per document, and entity-pair scoring reads from the propagated states of each candidate type.

Baselines

Naive reference. The same pretrained encoder over the same chunked input, with mean-pooled document states and one independent sigmoid output per label. It tells us how much any structure or label machinery is worth.

Strongest competitor: structure tokens plus label attention. The encoder receives Buchmann et al.-style section and paragraph delimiter tokens and depth embeddings, and an LSAN-style label-attention head is added on top. This is the strongest challenger because it captures document structure and per-label evidence selection without any graph propagation, and Buchmann et al. report that structure infusion alone lifts LongT5 on Evidence Inference by 6.84 F1. They give only this gain; no absolute Evidence Inference score was found on Lacuna. We will run it ourselves with the same backbone, the same token budget, the same shortlist size and the same number of tuning trials.

Reported numbers to compare against. On EUR-Lex, LSAN reports P@1 of 79.17% (Xiao et al.) and HE-AGCRCNN reports Micro-F1 0.688 and Macro-F1 0.330 (HE-AGCRCNN). On CDR, DHG-BERT reports overall F1 of 65.9% and inter-sentence F1 of 54.6% (Zhang et al.). On DocRED, HIN-BERT reports test F1 of 55.60% (Tang et al.). These published numbers come from different backbones. We therefore also reimplement LSAN-style attention and a label-agnostic DHG-style graph on our backbone, and we claim success only against these matched reimplementations.

Key ablation: label-agnostic propagation. Our exact graph and interleaving, with the label query removed from the gate, so every label shares one propagated graph and label attention acts only at readout. This isolates the claim itself.

Capacity control. Here $k$ unconditioned routing heads are each learned freely, and label attention then picks among the heads. It has the same number of propagated copies, but none is tied to a label. If it matches the full model, the gain came from multiple routes rather than label-driven routes.

Label-semantics check. The model is trained with randomly initialized queries instead of name-derived ones.

What counts as beating a baseline. Beating the structure-token baseline and the label-agnostic ablation means a gain beyond the seed-to-seed spread over at least three seeds on the long-range subsets defined below, with no loss on the short-range subsets.

Why not just…?

Why not just use a long-context Transformer with a multi-label linear head? This is the naive reference we run. Existing evidence argues against it: vanilla long-document Transformers show weak structural awareness until structure is infused (Buchmann et al.), and label semantics matter most for rare labels (LSAN's EUR-Lex gain over EXAM, 79.17% versus 74.40% P@1). We expect it to be clearly weakest, but we do not assume that.

Why not just add structure tokens and label attention to a flat Transformer? This is the real threat. It may match us on most documents, because per-label pooling over a structure-aware encoder already selects label-relevant sentences. Our argument is narrower: pooling cannot compose two facts that are only linked through a third unit, while label-gated propagation can. The experiment settles this directly. If the structure-token baseline matches us on the inter-sentence CDR subset and on DocRED's cross-sentence facts, which are 40.7% of that dataset, our claim is wrong, and we will report that the graph is unnecessary.

Why not just feed frozen language-model embeddings into a document graph network with a label-attention readout? This is cheaper and avoids co-training memory problems. However, Yan et al. show that static embeddings prevent the text encoder from adapting to structure: topologically pre-trained features gave over 30% downstream gain on Sports-Fitness. We include the frozen cascade as an extra arm, with label-conditioned gates kept, to separate the value of interleaving from the value of label routing.

Why not just prompt a large language model? With roughly 4,000 EUR-Lex labels, listing labels in a prompt is impractical. The file also reports no prompted-LLM results on these benchmarks. We therefore do not use prompting as a primary baseline, though a small zero-shot comparison on Evidence Inference would be informative.

Proposed Experiments

Datasets. - EUR-Lex: long legal texts with a sparse label space of about 4,000 labels. We report P@1, P@3 and P@5, plus Macro-F1 on tail labels. - Evidence Inference: long clinical reports where the evidence crosses sections. We report macro-F1. - CDR and DocRED: relation types act as labels. We report overall, intra-sentence and inter-sentence F1. - MAG-CS: a negative control. Its documents are short abstracts, so label routing should add little over the reported 93.12% P@1 of Ye et al..

Decisive check: stratify by evidence distance. For relation extraction, the distance is the graph hop distance between the two mentions. For Evidence Inference, it is the section distance between the annotated evidence and the intervention mention. The claim predicts three things. First, the gap between the full model and the label-agnostic ablation increases with hop distance. Second, that gap is near zero for intra-sentence cases. Third, the capacity-matched multi-head control closes less of the gap than label conditioning does. A flat or uniform gain profile falsifies the mechanism, even if average scores improve.

Secondary analyses. We report:

  • shortlist recall@$k$ and the accuracy lost to shortlist misses;
  • wall-clock time and memory against LSAN-style full attention on EUR-Lex;
  • whether the learned edge gates for semantically related labels agree more than those for unrelated labels, compared against shuffled-query models.