Retrieval systems that feed language models usually compress a question and each stored passage into a single vector and match them by dot product. Such systems cannot tell "Whose doctoral advisor was Bohr?" from "Who was Bohr's doctoral advisor?": both questions contain the same entity and the same relation word, and they ask for opposite ends of the same fact. This proposal starts from a structural observation. Constrained generation forces a model to spell out a fact as an ordered string, subject then relation then object, and only strings that exist in an index of the knowledge base are allowed. Under that kind of decoding, order is part of the lookup key, so the decoder cannot satisfy a reversed question with the forward fact. If this holds, constrained decoding over an ordered knowledge index fixes the word-order blindness of dense retrieval, and does so by construction. The remaining obstacle is speed. Constrained decoding is known to be slow, and we propose to recover the speed with a draft-then-verify scheme in which the index check costs no model calls at all.
The work has two parts. The first is a measurement nobody in the literature we found has made: how much of a retrieval-augmented system's error on relational questions comes from direction confusion, meaning the system returns the entity at the wrong end of the right relation. The second is a decoder that generates directed fact paths over an index of the whole knowledge base. It needs no separately linked topic entity, and its cost per query grows with the length of the path rather than the size of the knowledge base.
Core Claim
Dense dual encoders are blind to word order. Contrastive training can be solved by matching keywords, as On the Difference of BERT-style and CLIP-style Text Encoders argues. On attribute-binding minimal pairs, ColorSwap reports CLIP at 12% and SigLIP at 30% Group Score, against 87% for the cross-attention model BLIP ITM. We expect the same blindness in text retrievers to appear as direction confusion on inverse-relation questions.
Standard QA benchmarks would hide this. Similarity benchmarks over-reward lexical overlap (Learning Distributed Representations of Sentences from Unlabelled Data), and referring-expression models lose almost nothing when relational words are stripped out (Visual Referring Expression Recognition: What Do Systems Actually Learn?). Both suggest that ordinary test sets rarely contain the reversed twin of a question.
Our claim is that decoding constrained to directed serialized triples removes most direction confusion. The key test is an ablation: the same decoder over an index with direction removed should bring the confusion back. A speculative variant should keep this property at a small fraction of the cost of constrained beam search.
Relation to Prior Work
Three papers supply the method and motivate the bet.
Graph-constrained Reasoning (GCR) builds a prefix tree of valid entity-relation paths around a pre-linked topic entity and decodes only those paths with beam search. This is the closest existing work, because its paths are already ordered. GCR does not, however, ask whether ordering protects against reversed questions. It also depends on correct topic-entity linking and pays the latency of beam search. We remove the linking step by indexing the whole knowledge base, measure order sensitivity directly, and replace beam search with speculation.
Retrieval-Constrained Decoding (RCD) constrains answers to a prefix tree of retrieved candidate entity identifiers. It shows that vanilla decoding hides much parametric knowledge. Its candidate pool, however, comes from a retriever, so a direction-confused pool caps its accuracy. Our design tests exactly this failure.
RetroLLM constrains generation to verbatim corpus substrings through FM-indexes, which are compressed full-text indexes that answer substring queries. It also adds forward-looking scoring to escape the "greedy trap", where an early valid token leads into a branch with no useful evidence. We reuse the FM-index, but over serialized triples rather than free text, so that order carries meaning.
For speed, Constrained Decoding with Speculative Lookaheads (CDSL) supplies the mechanism. A small model drafts several tokens and a large model verifies them in one parallel pass. CDSL scores drafts with a learned reward. In our setting the index answers "is this prefix valid?" exactly and for free, which removes CDSL's most expensive component.
ColorSwap also constrains the design. Fine-tuning CLIP on its pairs raised the score from 11.67% to 63%, but the gain did not transfer to Winoground. That result warns against fixing order blindness with targeted training data alone.
Research Program
We first build a reversal benchmark from Wikidata. We choose non-symmetric relations whose two directions both have natural phrasings, such as advisor and student, parent and child, or developer and product. For entity pairs where both directions are answerable, we write question twins that share every content word. Two numbers come out of each system. The reversal gap is accuracy on the forward twin minus accuracy on the reversed twin. The direction confusion rate is the fraction of errors whose prediction is the entity at the other end of the queried relation.
To build the index, we serialize every triple as a "subject ∣ relation ∣ object" string using entity surface forms with unique identifiers, following RCD's identifier surface forms. We store the strings in a single FM-index. The decoder generates the subject under the constraint, then the relation, then the object. Each constraint check is a backward-search step whose cost depends on the length of the pattern, not on the number of triples. This is why we expect latency to stay roughly flat as the index grows from a single subgraph to all of Wikidata. The model is fine-tuned briefly to produce such paths, as in GCR.
To recover speed, a small drafter that shares the target model's tokenizer proposes a whole path. The index truncates the draft at the first invalid token without any model call. The target model then verifies the valid prefix in one forward pass. To avoid the greedy trap at the relation slot, we borrow RetroLLM's forward-looking idea: when choosing among relation tokens, we count how many full triples complete each candidate prefix.
Baselines
The naive reference point is closed-book vanilla decoding with the same backbone. RCD reports that Llama-3.1-70B under vanilla decoding reaches 32.3% F1 on YAGO-QA and 8.7% on KAMEL.
The strongest entity-answer competitor is RCD itself. The same paper reports that Llama-3.1-70B with RCD reaches 46.0% F1 on YAGO-QA and 32.0% on KAMEL. We will run RCD with the identical backbone and retriever, and beating it means higher F1 on YAGO-QA and KAMEL together with a lower reversal gap.
For path-based question answering over a knowledge graph, the competitor is GCR. GCR reports 92.6 Hit on WebQSP and 75.8 on Complex WebQuestions, and runs about 4.5 times faster than the agent baseline ToG. We will run GCR with oracle topic entities and with predicted ones. Our target is to match its Hit with predicted linking while lowering wall-clock latency per query.
For free-text grounding, RetroLLM reports 61.6 Exact Match on Natural Questions at 315 tokens per query, against 52.4 for naive retrieval-augmented generation. We use this as a sanity check that triple indexing does not lose open-domain accuracy where triples suffice.
Standard prompt-based retrieval-augmented generation uses a dense retriever, prepends the top passages, and reads with the same model. A Fusion-in-Decoder reader (Izacard and Grave) uses the same retriever with a stronger reader.
The cross-encoder reranker is a dense pool followed by a cross-attention reranker before reading. We found no reported result on Lacuna for a cross-encoder on relation-reversal pairs.
For latency, the reference points are constrained beam search, the GCR setting, and CDSL with its learned reward. CDSL reports a 2.2 to 12.15 times speedup over full lookahead decoding and a reduction in target calls per token from 14.72 to about 0.55.
The ablation that isolates our key ingredient is an undirected index. It stores each triple in both orders with the relation label made symmetric, so that direction is erased while everything else stays fixed.
All systems share the backbone, the Wikidata snapshot, a single GPU type, and an equal hyperparameter-search budget.
Why not just…?
Why not just put a cross-encoder reranker after the dense retriever? This is the real threat, since cross-attention is order-sensitive (87% on ColorSwap for BLIP ITM). A reranker can only reorder the pool it receives, though, and a pool that dense retrieval has already collapsed onto the wrong-direction fact gives it nothing to recover. We will measure how often the correct-direction fact appears in the top-100 dense pool for reversed twins. If the reranker closes the reversal gap at equal latency, we will report that constrained decoding's remaining value here is answer faithfulness, not order sensitivity.
Why not just fine-tune the retriever with reversed hard negatives? ColorSwap's fine-tuning gain did not transfer beyond its own distribution. We will train on reversal negatives for half the relations and test on the held-out half.
Why not just use a bigger closed-book model? The vanilla-decoding numbers RCD reports for 70B models are low. The reversal benchmark will additionally show whether scale shrinks the gap.
Why not just use GCR as-is? It is the right baseline, and we run it. Our additions are removing its reliance on topic-entity linking and replacing its beam search with speculation.
Proposed Experiments
The decisive check is a three-way comparison on the reversal benchmark. We predict that dense retrieval-augmented generation shows a large direction confusion rate, that the directed index shows a small one, and that the undirected ablation brings the confusion back.
If the directed and undirected indexes perform the same, the order-sensitivity claim fails. In that case the proposal reduces to a latency contribution.
Beyond the reversal benchmark, we evaluate on YAGO-QA, KAMEL, WebQSP, Complex WebQuestions and Natural Questions. For each we report F1, Hit or Exact Match, wall-clock latency, and target-model calls per generated token.
Finally, we sweep the index size from a topic subgraph up to the full knowledge base to test the claim that latency stays flat as the index grows.
References
- On the Difference of BERT-style and CLIP-style Text Encoders
- ColorSwap: A Color and Word Order Dataset for Multimodal Evaluation
- Learning Distributed Representations of Sentences from Unlabelled Data
- Visual Referring Expression Recognition: What Do Systems Actually Learn?
- Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
- Retrieval-Constrained Decoding Reveals Underestimated Parametric Knowledge in Language Models
- RetroLLM: Empowering Large Language Models to Retrieve Fine-grained Evidence within Generation
- Constrained Decoding with Speculative Lookaheads
- Leveraging Passage Retrieval with Generative Models for Open Domain Question Answering