Constrained Decoding That Notices When Retrieval Missed

Language models that write machine-readable output, such as database queries, often fail on a single wrong name: a column called T2.cust_seg where the model wrote customer_segment, or a drug or athlete that exists in the knowledge base under a different spelling. Two families of tools address pieces of this. Grammar-constrained decoding blocks, at each generation step, any token that would break the output's syntax. Retrieval-constrained decoding goes further and lets the model emit only entity names that a retriever pulled from an external knowledge base. The second idea is powerful. Restricting Llama-3.1-70B to retrieved Wikidata/YAGO candidates raised F1 on the niche-domain benchmark KAMEL from 8.7% to 32.0% (Retrieval-Constrained Decoding Reveals Underestimated Parametric Knowledge in Language Models). It also has a built-in weakness. If the retriever misses the right entity, the decoder is forced to pick a wrong one, and nothing downstream can tell. A hard filter turns every retrieval miss into a confident, well-formed, silent error.

We propose to treat that weakness as a signal. When the decoder enters a knowledge-bearing slot, such as a table name, column name, cell value, or entity, we restrict that slot to retrieved candidates and leave the rest of the output only lightly constrained. We also measure how much probability the unconstrained model puts outside the allowed set. A large outside mass suggests the retriever probably missed. In that case the system re-retrieves, using the model's own unconstrained guess as the query, and decodes the slot again. This is a concrete form of the "intelligent backtracking" that UCS-SQL names as its missing piece. The test bed is domain-heavy Text-to-SQL and long-tail factual question answering, where vocabulary mismatch is the main source of failure.

Core Claim

The probability mass that a hard mask removes is information that current constrained decoders throw away. If we keep it, constraints can be applied where they help, and retrieval misses can be caught before they reach the output. The claim has two parts, and each can be tested separately.

The first part is about where to constrain. Grammar-Constrained Decoding Makes Large Language Models Better Logical Parsers found that full-grammar masking helps small models but hurts large ones: qwen2.5-14b on GSM-symbolic with 5-shot prompting fell from 0.56 to 0.36. Retrieval tries, by contrast, help even 70B models. Our hypothesis is that constraints help when they restrict content the model does not know, such as entity identity and schema names. They hurt when they restrict tokens the model would have produced correctly on its own, such as the shape of its reasoning or its formatting. On this view, constraints should be scoped to slots.

The second part is about detection. For a slot $s$ with retrieved candidate set $C_s$, define the outside mass

$$m_s = 1 - \frac{1}{|s|}\sum_{t \in s} \sum_{v \in A_t(C_s)} p(v \mid x, y_{<t}),$$

where $A_t(C_s)$ is the set of tokens that keep the slot's partial string consistent with some candidate in $C_s$ at step $t$, $p$ is the unconstrained model distribution given input $x$ and prefix $y_{<t}$, and the average runs over the slot's tokens. We predict that $m_s$ separates retrieval hits from retrieval misses well enough to act on. When $m_s$ exceeds a threshold $\tau$, which is tuned on development data, the system re-retrieves and decodes the slot again.

Relation to Prior Work

Two papers supply the method. Flexible and Efficient Grammar-Constrained Decoding builds GREATGRAMMA, which compiles a grammar into a token-level mask with 5 to 32 ms of overhead per token. That speed matters here because our candidate sets change with every request. RCD contributes the trie of retrieved entity names. Neither combines grammar and retrieval, and neither has any fallback for a retrieval miss. Our contribution is to splice per-request candidate tries into the identifier positions of a SQL grammar, and to add the miss detector and the re-retrieval loop.

Three papers motivate the proposal by documenting cascades. UCS-SQL splits Text-to-SQL into separate pipelines for content (schema linking) and structure (the query skeleton). It reaches 68.95% execution accuracy on BIRD with GPT-4o, but an early linking error flows one way to the final query. SCoRe reports the same one-way failure in its distillation of retrieved text into knowledge triples for visual question answering. Can Pre-trained Vision and Language Models Answer Visual Information-Seeking Questions? shows that entity identification is the bottleneck: an oracle entity lifts accuracy from 18.2% to 45.6%. That is why we place the safeguard at the entity slot rather than at passage comprehension.

Claim-Dissector motivates soft decisions over hard ones, since it treats evidence relevance as a continuous latent variable. It is purely discriminative, however, and our setting is generative. One result constrains the design. TheoremQA found that pasting theorem definitions into the prompt barely helps. This warns us not to expect that showing the model more knowledge in the prompt will close the domain gap. Our mechanism instead acts on which names the model can emit.

Research Program

We will build a decoder for open-weight models (Llama-3.1-8B/70B, Qwen2.5-7B/14B, Gemma2-2B) on top of a GREATGRAMMA-style mask. Each SQL identifier and value position, and each answer-entity position in factual question answering, becomes a slot nonterminal. Its terminals are compiled per request from a retriever over schema elements, sampled cell values, and BIRD's external evidence strings, or from Wikidata/YAGO for KAMEL and YAGO-QA.

At each slot we run the unconstrained and the masked distributions from the same forward pass and compute $m_s$. If $m_s > \tau$, we take the model's unconstrained greedy completion of the slot, use it together with the question as a new retrieval query, merge the new candidates into the old set, and decode the slot again. If the outside mass stays high after one retry, the slot is emitted unconstrained and flagged. This is the escape hatch: a slot is never forced into a set we have evidence is wrong.

Outside the slots, we compare three conditions: full SQL grammar masking, a minimal mask that only enforces brackets and keywords, and no mask at all. This comparison tests the scoping hypothesis.

Our analysis will treat the detector as a classifier. We will report how well $m_s$ distinguishes slots where the gold entity is in $C_s$ from slots where it is not. We will also report how this behavior changes with model size, because larger models may hold sharper beliefs about out-of-set names.

Baselines

The naive reference is unconstrained few-shot generation with schema and retrieved candidates in the prompt, run on the same open model. This is what most deployments do.

The strongest existing system on BIRD is UCS-SQL, at 68.95% execution accuracy and 71.10% valid efficiency score with GPT-4o. That number comes from a closed model, so it is not directly comparable. We will report it as an external reference and re-implement the UCS-SQL content-pipe and structure-pipe prompting on each of our open models, with the same retriever and the same evidence.

The strongest constrained-decoding competitor is hard RCD composed with full SQL grammar masking. This is the obvious combination that the research file identifies as missing. On KAMEL we compare against RCD's reported 32.0% F1 for Llama-3.1-70B and 24.3% for Llama-3.2-3B, and on YAGO-QA against 46.0% for Llama-3.1-70B, all from RCD. We will rerun RCD ourselves with matched candidate set sizes.

Two ablations isolate the key ingredients. The first keeps the slot-scoped masking but removes the detector, so that every slot is hard-masked. The second keeps the detector but replaces re-retrieval with simple unconstrained fallback. That tells us whether the gain comes from detecting misses or from fixing them.

All methods use the same retriever, the same index, the same number of retrieval calls, the same number of decoding samples, and the same budget for tuning the threshold on development data.

We will count the proposal as beating the field if it does two things. First, it must exceed hard RCD-plus-grammar by a statistically reliable margin on BIRD execution accuracy and on KAMEL F1 at matched compute. Second, it must lose markedly less accuracy than hard RCD as retrieval recall is degraded.

Why not just…?

Why not just execute the SQL and retry on errors? Executing the query and regenerating on database errors is cheap, and on BIRD it is a real threat. It catches queries that fail to compile and references to nonexistent columns. It cannot catch a query that runs and returns the wrong rows, for example a filter on the wrong but existing value string, and retrieval misses produce exactly that kind of query. We will include execution-retry as a baseline with an equal retry budget, and also combine it with our method. We will split the errors into those that crash and those that run silently. If execution-retry matches our method on silent errors, the detector adds nothing, and we will say so.

Why not just retrieve more candidates so the gold one is almost always in the trie? Raising $k$ does raise recall, but each extra candidate weakens the constraint. In the limit the constraint becomes a plain grammar mask over every name in the schema or knowledge base, which loses RCD's benefit. We will sweep $k$ for hard RCD and plot accuracy against $k$. If some $k$ matches our method at equal cost, the simpler fix wins.

Why not just put the candidates in the prompt and let a strong model choose? This is essentially UCS-SQL's approach, and with GPT-4o it works well. The question is whether it works at open-model scale and with schemas containing cryptic names. RCD's KAMEL result suggests it does not, since vanilla decoding with a 70B model reached only 8.7% F1. The prompt-only baseline above, run with the same retrieved candidates, answers this question directly.

Why not just compose hard RCD with a grammar mask? That is the obvious idea, and it is our main baseline. It inherits RCD's failure mode: if the retriever misses, the correct answer cannot be emitted. The recall-stress experiment below is designed to show whether this matters in practice.

Proposed Experiments

The decisive check is a recall-stress test on BIRD, Spider, and KAMEL. With probability $p \in \{0, 0.1, 0.2, 0.4\}$ we delete the gold schema element or entity from the retrieved candidates and measure execution accuracy or F1. Hard RCD-plus-grammar should fall roughly in step with the drop in recall. If our method's curve is not clearly flatter, the core claim fails. Alongside this we report how well $m_s$ detects the injected deletions and the misses that occur naturally.

The second check tests the scoping hypothesis across model sizes. On BIRD and on FOLIO and GSM-symbolic, we compare full-grammar masking, slot-only masking, and no masking for 2B, 7B, 14B, and 70B models. The first step is to reproduce the reported drop for qwen2.5-14b from 0.56 to 0.36. The prediction is that slot-only masking keeps the large-model accuracy of unconstrained decoding while keeping the gains for small models.

We will also report added latency per query, which comes from candidate compilation and extra retrievals, against the 5 to 32 ms per-token GREATGRAMMA overhead. Finally, we will stratify BIRD errors by type: crash, silent wrong value, and wrong structure.