Decentralized Sequence Labeling When Every Hospital Labels Different Entities

Picture sixteen hospitals, each with clinical text annotated for a different subset of entity types. One annotated drugs and diseases, another genes and procedures. They want to train one shared tagger. There is no central server, and each hospital can only exchange model parameters with a few neighbors. Decentralized optimization offers a promise here: methods like gradient tracking, where each node keeps a running estimate of the network-wide average gradient, can make a sparse peer-to-peer network eventually learn as fast as a central server. This property is called topology-independent convergence. We argue that in this setting the promise is hollow unless the local objectives are first made mutually consistent. A standard sequence tagger treats every unlabeled entity as "not an entity." Each hospital's loss then actively contradicts its neighbors'. A topology-independent optimizer will converge quickly, and on any graph, to the average of those contradictory losses. In centralized experiments that objective is badly wrong: on MedMentions, naive training on disjoint label sets falls from 59.4 to 35.3 F1 (Greenberg et al.).

We therefore propose to combine two existing ingredients and characterize the combination carefully. The first is the marginal-likelihood CRF, which treats missing labels as unknown rather than as "not an entity." The second is decentralized gradient tracking. We will measure what governs the slow initial phase of training that remains. Our central, testable prediction concerns that phase. Once the objective is consistent, its length is set less by the graph's overall connectivity than by where the label schemas sit on the graph: how many hops separate a node from the nearest neighbor that annotates each entity type.

Core Claim

The tagger is a BiLSTM-CRF. A bidirectional LSTM reads the sentence in both directions and produces per-token scores. A linear-chain conditional random field (CRF) sits on top: it adds a learned table of tag-to-tag transition scores and scores whole tag sequences jointly, as in Ma and Hovy's BiLSTM-CNN-CRF. Node $i$ annotates only the entity types $S_i$. Following Greenberg et al., its local loss is the negative marginal log-likelihood

$$f_i(\theta) = -\log \sum_{\mathbf{y} \in C_i(\mathbf{x})} p_\theta(\mathbf{y}\mid\mathbf{x}),$$

where $\theta$ collects the encoder weights and the transition matrix $A$. The set $C_i(\mathbf{x})$ contains every tag sequence that agrees with node $i$'s annotations and allows any type outside $S_i$ wherever node $i$ wrote "O." This loss is computed with two runs of the forward algorithm, one restricted to $C_i$ and one unrestricted.

We claim three things. First, with this loss, gradient tracking over sparse graphs recovers the F1 of centralized marginal training. With the naive loss, gradient tracking recovers only the degraded centralized-naive F1, however good the topology. Second, even under the marginal loss, the local gradients still disagree. Node $i$ supervises the emission and transition parameters of types in $S_i$ and is nearly silent about the rest. This disagreement is concentrated in type-specific parameters. The encoder itself remains largely shared. Third, as a consequence, the number of communication rounds needed to reach a target F1 depends on the placement of schemas on the graph. It should be driven by the largest hop distance from any node to the nearest holder of each type. Plain gossip averaging should be far more sensitive to that distance than gradient tracking.

To our knowledge nothing in the literature puts these pieces together. Decentralized theory, including EXTRA, GT-SAGA/GT-SVRG, unified contraction analysis, LSGT and D-NASA, has been tested on least squares, logistic regression, MNIST and LeNet. These methods supply our optimizer, but none studies structured losses. Nor does any study heterogeneity arising from label schemas rather than from class frequencies. Greenberg et al. supply our loss and our motivating negative result, but they train on one machine. Federated Incremental NER handles "O"-label conflicts across clients with prototype pseudo-labeling. That work relies on a central server, uses no CRF, and tracks no gradients. It is the closest competitor in spirit, and we differ on all three axes.

Research Program

We will build decentralized marginal-CRF gradient tracking. Each node runs a character-CNN BiLSTM-CRF. We choose the character CNN over a character LSTM because Zen et al. found the two statistically comparable in F1 (87.88 vs 87.79 on CDR), with the CNN adding far less training cost. That saving matters when every round transmits both parameters and a tracking variable. On each round, a node computes a stochastic gradient of its marginal loss. It then updates its tracking variable by mixing neighbors' tracking variables and adding the change in its own gradient. Finally, it steps its parameters along the tracked direction after mixing with neighbors.

We will run two variants. One uses $E$ local steps between exchanges, as in LSGT. The other normalizes the tracked direction, as in D-NASA. The normalized variant should be robust to the heavy-tailed gradients that Zipfian token statistics produce, a concern raised by work on heavy-tailed decentralized noise. It also needs no knowledge of the spectral gap, the standard measure of how quickly averaging mixes information across the graph.

The analysis has three parts. The first is instrumentation. We will log consensus error, meaning how far each node's copy is from the network average, separately for three blocks: the encoder, the type-specific emission rows, and the transition matrix. We will also log each node's gradient disagreement with the network average at the end of training. The second is placement. We will use a placement statistic: for each type, the maximum hop distance from any node to the nearest node annotating it. We will then test whether this statistic predicts rounds-to-target better than the spectral gap does.

The third is a small theoretical piece. Standard gradient-tracking bounds, such as LSGT's, control the transient phase through the magnitude of gradient heterogeneity. We will bound that heterogeneity for the marginal loss in terms of the schema overlap of neighboring nodes. The bound starts from one observation: the gradient of $f_i$ with respect to type-$k$ transition entries is the difference of two posterior marginals. That difference vanishes exactly when $k \notin S_i$ and the restricted and unrestricted posteriors agree on type $k$.

If placement matters as predicted, we will test one cheap remedy. The remedy is placement-aware mixing weights, which upweight edges between nodes with complementary schemas. It needs only schema metadata, not data.

Baselines

The naive reference point is local-only training. Each node trains its own BiLSTM-CRF on its own labels, and we evaluate each node's model on the full test schema. This measures what cooperation buys at all.

The ceiling is centralized marginal CRF trained on all pooled partial annotations. This is Greenberg et al.'s method, reported at 56.8 F1 on the disjoint MedMentions split, against a fully annotated ceiling of 59.4 F1 (Greenberg et al.). We will reproduce it on our partitions with the same encoder. Success is measured as the fraction of this number our decentralized runs reach, and how fast they reach it.

The strongest decentralized competitor is marginal CRF with plain gossip SGD. Each node takes a gradient step on its marginal loss and averages parameters with its neighbors, with no tracking. It isolates the value of gradient tracking once the loss is already consistent. Two further ablations isolate each ingredient in turn. Naive CRF with gradient tracking isolates the value of the marginal loss. Token-level partial-label softmax isolates the value of the CRF. That model marginalizes each "O" token over {O} ∪ unannotated types, but independently per token and with no transition matrix.

We will also run FedAvg with a central server on marginal loss, as a reference for what a star topology achieves. There is no reported decentralized result on Lacuna for any of these NER benchmarks. On MNIST, LSGT reports vanilla gradient tracking needing 378 rounds to reach 95% accuracy versus 65 with $E=10$. That is the only communication-round figure in the file, and we cite it only as an order-of-magnitude expectation.

All methods share the encoder, the partitions, the per-node batch size and the per-round bytes budget. Tracking methods send twice the parameters, so for bytes-matched comparisons gossip SGD is also allowed two exchanges per round. Each method gets the same number of step-size trials, chosen on a held-out dev split under the ring topology.

Gradient tracking counts as beating gossip if two things hold. It must reach 95% of centralized marginal F1 in meaningfully fewer bytes on ring and grid. Its advantage must also grow with the placement statistic.

Why not just…?

Why not just use marginal CRF with plain gossip SGD? This is the real threat. If the marginal loss removes most of the disagreement between nodes, plain gossip may already be good enough, and gradient tracking would add bandwidth for nothing. The evidence against gossip, EXTRA's and GT-VR's error floors, comes from convex problems. It may not carry over to a non-convex tagger evaluated by F1. Our experiment settles this directly. We will plot the F1 gap between gossip and tracking against the placement statistic and the spectral gap. If the gap is negligible even on schema-adversarial rings, we will report that as the finding: consistent objectives make naive decentralization sufficient. The placement analysis would still stand.

Why not just add a central server and run FedAvg? Where a trusted server exists, one should. Our FedAvg run shows the cost of lacking one. The proposal targets cross-institution settings where no party will host a server, which is the scenario Federated Incremental NER leaves unaddressed.

Why not just drop the CRF and use a per-token partial-label classifier? It is cheaper and makes the local loss a plain cross-entropy. Ma and Hovy found that the CRF helps over softmax in the fully supervised setting. Under partial labels the question is open, because marginalizing over whole sequences uses transition constraints to resolve ambiguous "O" spans, and per-token marginalization cannot. Running this model as a baseline answers the question. If it matches the CRF, the structured part of our story is unnecessary, and we will say so.

Why not just gradient tracking with the naive loss? It is the obvious combination of the two research areas, and we predict it fails. It should converge to the centralized-naive solution, which Greenberg et al. show sits around 35 F1 on MedMentions. Topology independence cannot fix an inconsistent objective. The ablation will confirm or refute this.

Proposed Experiments

We will use three benchmarks. The first is MedMentions, with its 19 types split into 16 node-level subsets of four to five types each, with controlled overlap. The second pairs BioCreative V CDR with ChemProt as natural silos, split into CDR-like and ChemProt-like nodes; there the Zen et al. 87.88 overall F1 anchors a single-schema CDR model. The third is CoNLL-2003 with type-disjoint nodes as a clean sanity case, where full supervision reaches 91.21 F1 (Ma and Hovy).

We will test complete, exponential, grid and ring graphs. The ring is run twice: once with schemas placed to maximize holder distance, and once with them interleaved. Holding the spectral gap fixed while changing placement is the key manipulation. The metrics are span micro-F1 and per-type F1 against rounds and bytes, rounds-to-95%-of-centralized, and blockwise consensus error.

The decisive checks are three. First, naive-loss tracking must plateau near centralized-naive F1 on every topology. Second, marginal-loss tracking must reach near-centralized-marginal F1 on the ring. Third, on the two rings with equal spectral gap, rounds-to-target must differ substantially and in the direction the placement statistic predicts. If the third check fails, the placement hypothesis is wrong. The engineering result would remain, and we would say plainly that only the first two claims survive.