Evidence-Joined Constrained Decoding for Structured Extraction from Noisy Context

Language models are often asked to turn a pile of retrieved text into a structured record, such as a JSON object or a list of (subject, relation, object) facts. Two failures compound here. Without constraints, the output often breaks the required format. With grammar-constrained decoding, which blocks any next token that would violate the format, the output always parses, but its content is still at the mercy of distractor passages. A model that has read twenty documents will happily pair a subject from one passage with an object from an unrelated one. The result is a well-formed fact that nothing in the context supports. Format guarantees and noise robustness have so far been studied separately.

We propose to make the decoding constraint check evidence as well as syntax. As the model writes a fact slot by slot, the set of allowed next tokens is computed by joining the partial fact against an index of which entities occur together in which passages. A subject and an object can only be combined if some passage mentions both. Recomputing that join at every token over hundreds of passages and thousands of candidate entities is too slow for interactive use. We therefore borrow the incremental matching machinery of classic rule engines, which keeps partial matches between steps and stops visiting sources that can no longer match. The claim is that this gives format-valid, evidence-grounded extraction under heavy distraction, with per-token overhead that stays roughly flat as the context grows.

Core Claim

Existing input-dependent grammars already restrict the output vocabulary to entities relevant to the input. Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning does this for closed information extraction and entity disambiguation. It lets zero-shot LLaMA-33B reach 36.0 F1 on SynthIE-text and lifts disambiguation accuracy from 54.1% to 80.3%. That paper plays two roles for us: it supplies the method and it is our starting point.

Its candidate set, however, is a flat bag. Each slot of a fact is restricted independently, so every entity mentioned anywhere in the context is a legal choice for every slot. That is harmless on clean single-sentence inputs. With distractors it is exactly the wrong design: the grammar legitimizes the "forced logical connections" that distraction produces. The paper itself never evaluated noisy inputs.

Our claim is that replacing the flat candidate bag with a join over passage-level co-occurrence removes most cross-passage fabrications. This join-based constraint must be recomputed as each slot is filled. We further claim that it can be kept cheap by retaining partial matches across decoding steps and unlinking empty sources, as rule engines do. What is new is the combination: the constraint is dynamic per input, relational across slots, and evaluated under controlled distraction.

How the Pieces Fit

The noise direction motivates the work. Improving Zero-shot Reader by Reducing Distractions from Irrelevant Documents in Open-Domain Question Answering shows zero-shot readers degrade sharply as retrieved documents go from 5 to 100. Superposition Prompting: Improving and Accelerating Retrieval-Augmented Generation shows that processing passages along separate paths and pruning weak ones helps both accuracy and compute. Reducing Distraction in Long-Context Language Models by Focused Learning trains the model to ignore masked-out irrelevant chunks. All three produce free text, and all three filter passages by soft scores. None of them constrains what combinations of content the output may contain.

The structured-output direction supplies the decoding substrate but also a constraint. The fast engines in Automata-based constraints for language model decoding and Flexible and Efficient Grammar-Constrained Decoding achieve microsecond-to-millisecond per-token overhead. They do so by compiling a static grammar offline, which is precisely what a per-input, per-slot relational constraint rules out. Their offline compilation cannot be reused for the evidence join, so the join must be cheap online.

The rule-matching direction supplies the method for that online step. In the Rete algorithm from Forgy et al., rules are compiled into a network whose node memories store partial matches, and only changes propagate between cycles. Our output fact is the "rule" and the passages' mention sets are the "working memory." Combining Left and Right Unlinking for Matching a Large Number of Learned Rules unlinks join nodes whose input memory is empty. This cut null activations in the Soar Assembler benchmark from 2,214.8 to 0.11 per change. The analogue here is that once the subject is fixed, most passages have an empty support set and should never be touched again.

Eliminating Expensive Chunks by Restricting Expressiveness shows that forcing each attribute to hold one value keeps match cost linear in the number of conditions. Autoregressive decoding gives us this restriction for free, because each committed slot holds exactly one value. We use that observation to bound the join cost.

Research Program

We will build an extraction decoder in three layers. The first layer is a preprocessing pass. It runs an alias-matching entity linker over each passage and records, per passage (optionally per sentence window), the set of candidate entities and their Wikidata types. The second layer is the outer grammar: a standard JSON or triple schema compiled with an existing fast engine, so syntax masking costs what it costs today. The third layer is an evidence matcher that tightens the mask inside entity slots.

The evidence matcher works slot by slot. When the subject slot is open, the allowed entities are the union of all passage candidates, which is the same as the input-dependent-grammar baseline. When the subject is committed, the matcher keeps only passages containing it. That surviving set is the "alpha memory," the store of single-condition matches in Rete terms. The relation slot is then limited to relations whose type signature is compatible with the subject and with at least one co-mentioned entity. The object slot is limited to entities co-occurring with the subject in a surviving passage.

For question-answering records that require a chain across documents, we allow one explicit bridge. A second fact may start from the object of the first, and its evidence may lie in a different passage. Cross-document composition is thus permitted, but only through a shared entity rather than arbitrary mixing. This matters because filtering is known to destroy multi-hop dependencies.

Within an entity slot, the per-token mask is the intersection of the tokenizer-level prefix trie with the surviving entity set. The matcher updates this incrementally as each subword is emitted. Passages whose support becomes empty are unlinked so they cost nothing afterward. We will measure null activations directly, mirroring the Doorenbos analysis.

Two analyses matter beyond accuracy. The first asks how constrained decoding fails under noise. We want to know whether the model, denied a fabricated object, falls to a plausible grounded alternative, emits a vacuous fact, or closes the list prematurely. These are the "valid nonsense" failures noted in Constrained Decoding for Code Language Models via Efficient Left and Right Quotienting of Context-Sensitive Grammars. The second tracks how mask latency scales with passage count and candidate count.

Baselines

The naive reference point is unconstrained decoding with a format instruction, followed by a JSON parse. We report both validity and content accuracy for it.

The strongest existing method is input-dependent grammar-constrained decoding as in Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning. It restricts every entity slot to the flat set of entities linked anywhere in the context. The paper reports 36.0 F1 on clean SynthIE-text with LLaMA-33B, against 34.8 for supervised GenIE T5-base. It is the right competitor because it already uses the same candidate extraction and the same kind of grammar, so the only difference is the cross-slot join. We will rerun it ourselves on the same backbone, the same linker output, the same prompts and the same distractor sets. Its reported clean number serves as a sanity check that our reimplementation matches.

Beating it means two things. First, a significantly higher triple F1 at 20 and 100 distractors. Second, no loss larger than half a point at zero distractors, since the join should be nearly free when every entity is relevant.

The second strong competitor is a fork-per-passage pipeline in the spirit of Superposition Prompting: Improving and Accelerating Retrieval-Augmented Generation. It runs constrained extraction on each passage independently, scores each passage by query likelihood as in Improving Zero-shot Reader by Reducing Distractions from Irrelevant Documents in Open-Domain Question Answering, and unions the high-scoring outputs. It gets passage-level grounding by construction. It is run with the same backbone and a matched total token budget. We report its wall-clock cost separately, because it needs one pass per passage.

The third competitor is a simpler grounding design in which the schema forces the model to emit a passage identifier before each fact. Every later slot is then restricted to that passage's candidates. This achieves grounding with a trivial constraint and no join machinery.

Two ablations isolate our ingredients. The first compares the join computed naively, by rescanning all passages at every token, against the incremental matcher with unlinking. Accuracy should be identical and only latency and null activations should differ. The second compares a sentence-window join against a whole-passage join, which measures the precision–recall cost of the evidence granularity.

Why not just…?

Why not just re-rank and drop distractor passages before extraction? This is a real threat on single-hop tasks. We run it as an additional baseline: flat input-dependent decoding over the top-5 re-ranked passages. The evidence cuts both ways. Improving Zero-shot Reader by Reducing Distractions from Irrelevant Documents in Open-Domain Question Answering shows retriever-level noise persists deep in the ranking. Reducing Distraction in Long-Context Language Models by Focused Learning notes that filtering loses context needed across documents. The deciding experiment uses our hard-distractor condition, in which distractors share entities with the gold passage and therefore survive re-ranking. If re-ranking plus flat decoding matches the join there, we will report that the join adds nothing beyond a good re-ranker.

Why not just run extraction on each passage separately? Per-passage forking gives grounding without a join, and on single-hop extraction it may match our accuracy. It then loses only on cost, since it needs one pass per passage instead of one pass total. It cannot compose facts across passages, and the bridge rule in our design exists for that case. The multi-hop condition settles the question: if forking equals the join on MuSiQue-derived structured answers, the relational constraint is unnecessary.

Why not just ask the model to cite its passage first? Cite-first decoding forces an early commitment to one document. Under distraction the model may commit to a distractor and then be locked into it. The join keeps every supporting passage alive until the content itself narrows the set. We cannot cite evidence settling this, so the cite-first ablation above is the test. A tie would mean the simpler design should be preferred.

Why not just fine-tune for noise robustness? Training approaches such as focused learning, or training on synthetic data as in Exploiting Asymmetry for Synthetic Training Data Generation: SynthIE and the Case of Information Extraction, are complementary rather than competing. SynthIE assumes every fact in the text is in the target, an assumption distractor passages break. We will evaluate a SynthIE-trained Flan-T5 under our distractor protocol, with and without the evidence mask. The mask should add to fine-tuning rather than replace it; if it adds nothing to a fine-tuned model, that bounds its value.

Proposed Experiments

The main benchmark is SynthIE-text and Wiki-cIE Text with injected distractor passages. We use k ∈ {0, 5, 20, 100}. Distractors come in two kinds: random passages drawn from other instances, and hard passages chosen to share at least one entity with the gold facts.

The metrics are triple micro-F1 and structural validity. We also measure a cross-passage fabrication rate: the fraction of predicted facts whose subject and object never co-occur in any single passage. That rate is zero by construction for our method, so its value lies in exposing the baselines. The meaningful accuracy quantities are F1 and the rate of wrong-but-grounded facts.

For disambiguation under noise we use AIDA-CoNLL with added distractor paragraphs, where the reported clean accuracy for input-dependent decoding is 80.3%. For query-conditioned records we use NaturalQuestions-Open and MuSiQue with a JSON answer schema. The MuSiQue schema includes a supporting chain. There is no reported result found on Lacuna for structured-output variants of NaturalQuestions-Open or MuSiQue, so all numbers there come from our own reruns of the baselines.

Latency is measured as per-token mask time and null activations per step, as passage count grows from 5 to 100 and candidate count from hundreds to tens of thousands. These are compared against the reported 5–32 ms per-token overhead of Flexible and Efficient Grammar-Constrained Decoding for static grammars.

Three checks are decisive. First, the gap in F1 over flat input-dependent decoding should grow with k and be largest on hard distractors. Second, the incremental matcher should keep per-token overhead roughly flat in passage count while naive recomputation grows linearly. Third, on MuSiQue the join should beat per-passage forking. If the first check fails, relational constraints do not help with noise. If only the third fails, the contribution shrinks to a faster way of doing what forking already does.