Binding-Checked Query Trees for Multi-Hop Questions

Multi-hop question answering means answering questions that need several pieces of evidence chained together, such as "In what city was the director of Inception born?" A common fix is to break the question into a tree of smaller sub-questions and answer them one at a time. These trees work well when each hop is named by an entity, like "the director of Inception." Many real hops are not named that way. They are picked out by a combination of properties: "the French director whose debut won at Cannes," or "the player in the red jacket next to the man in blue."

A separate literature shows that language and vision models handle such combinations badly. They tend to register that "French," "debut," and "Cannes" all appear somewhere in the text without tracking which entity has which property. This is the attribute-binding problem. We propose that, once a multi-hop pipeline has to pick out an intermediate entity by a combination of properties, binding failure becomes the main cause of errors that cascade down the chain. We further propose that it can be repaired inside the decomposition itself. The planner would rewrite each property-defined hop as a separate list of properties for each entity. It would then add an explicit check that a candidate document supports the correct property–entity pairing and does not merely mention the right words in a swapped arrangement.

The opportunity is that two problems usually studied apart turn out to be the same problem. Embedding retrievers, which find documents by comparing vector summaries of text, are close to additive over their parts. The vector for "red cube and blue sphere" is roughly the sum of its pieces, so it cannot tell that scene apart from "blue cube and red sphere" (How can embedding models bind concepts?). Multi-hop pipelines rely on exactly such retrievers to find the bridge entity at each hop. A swapped-attribute distractor document at hop one is therefore an ideal trigger for the cascading hallucinations that decomposition was meant to prevent.

Core Claim

Our central hypothesis is that the error lies in the representation used to plan a hop, not in the reasoning ability of the model that answers it. The fix we propose is a query tree with two kinds of leaf. The first is the usual retrieval leaf, which collects candidate documents. The second is a binding leaf: a small first-order-logic-style predicate for each entity, for example $\exists x\,(\text{Director}(x) \wedge \text{French}(x) \wedge \text{DebutWonAt}(x,\text{Cannes}))$. Each candidate passage is tested against this predicate by a model that reads the passage and the predicate together. The test is contrastive. The passage must support the correct pairing better than it supports the version with attributes exchanged across the entities it mentions. If no candidate passes, the tree backtracks to retrieval instead of passing a guess down the chain.

What is new relative to the closest work is where the check sits and what it compares. ProbTree (Probabilistic Tree-of-thought Reasoning for Answering Knowledge-intensive Complex Questions) builds query trees whose nodes are entity-level sub-questions. It decides between parametric memory and retrieval using answer confidence, and never asks whether a passage pairs properties with the right entity. DTKG (DTKG: Dual-Track Knowledge Graph-Verified Reasoning Framework for Multi-Hop QA) goes further in the wrong direction for our purposes. Its denoising step deliberately prunes "non-essential" entity attributes to keep graph search tractable, which removes exactly the modifiers that tell candidates apart. Its authors also report failure on hybrid queries that combine chained hops with attribute comparison. Our binding leaves are designed for that hybrid case.

Research Program

The work has three parts. The benchmark is a first-class contribution, because no existing dataset isolates this failure.

The benchmark. Neither family of existing benchmarks measures the failure. MuSiQue (MuSiQue: Multi-hop Questions via Single-hop Question Composition) composes single-hop questions through named bridge entities and filters out shortcut-solvable items. Binding benchmarks such as ColorSwap (ColorSwap: A Color and Word Order Dataset for Multimodal Evaluation) test single images with no chaining.

We will build BindHop following MuSiQue's bottom-up recipe, with one change. In each composed question, at least one bridge entity is referred to only by a conjunction of two or three attributes drawn from Wikidata. Every such item comes with a distractor passage that mentions a second entity and contains exactly the same attribute words with the pairing swapped. We will apply MuSiQue's adversarial connectivity filter so that the downstream hop cannot be answered without resolving the bridge.

Following the BindSplit audit (CLIP Models Generalize Less Than Compositional Benchmarks Suggest), we will split items by how familiar the correct pairing is. That audit showed that compositional benchmarks are dominated by attribute pairings already seen in training. Our proxy for familiarity is Wikipedia co-occurrence frequency, giving a familiar split, a mixed split, and a counter-stereotypical split. The last one is the text analogue of the purple-lemon test from When are Lemons Purple? The Concept Association Bias of Vision-Language Models, which found that models assign the familiar attribute even when the evidence contradicts it.

A smaller multimodal slice will reuse WebQA's format. Image evidence will carry the swapped-color construction from ColorSwap, so that the binding has to be resolved visually.

The planner. A large language model will produce the query tree in a single structured call, in the JSON tree style that ProbTree uses. We add one instruction: any node whose referent is defined by properties becomes a binding leaf, written as a separate predicate for each entity.

We take this predicate form from Learning Semantic Structure through First-Order-Logic Translation. That paper showed that question-answer prompting falls back on word adjacency, linking an adjective to whichever noun is nearby, and breaks down under relative clauses. Translation into first-order logic, by contrast, makes the pairing explicit. The same paper also limits our design. It found hallucination rates above 10% in its logic translations, so the planner's own binding errors must be measured and not assumed away.

The verifier. Each binding leaf is scored by a cross-encoder, a model that reads the predicate and the passage together in one pass instead of comparing two separate vector summaries. We choose this design because of a striking result in ColorSwap. A cross-attention matching model (BLIP) reached an 87% group score, while the contrastive dual encoders reached 12% (CLIP) and 30% (SigLIP).

The verifier computes $s(\text{passage}, \phi) - \max_{\phi'} s(\text{passage}, \phi')$. Here $s$ is the verifier's support score, $\phi$ is the correct predicate, and $\phi'$ ranges over predicates formed by permuting attributes across the entities the passage mentions. A passage passes when this margin exceeds a threshold tuned on development data. Requiring a margin over the swaps is the key ingredient. A verifier that only scores $\phi$ by itself can be satisfied by a passage that merely contains the right words.

For the image slice, we will test the same margin rule using a VLM as the verifier.

Baselines

The naive reference point is one-shot retrieval followed by reading. The whole question is embedded once, the top passages are retrieved, and a language model answers. This baseline sets the floor and directly exposes the additive-retrieval failure. On standard benchmarks, the closest reported comparison is MuSiQue's single-paragraph model, which scores 32.0 F1 on MuSiQue-Ans against a human score of 78.0 (MuSiQue: Multi-hop Questions via Single-hop Question Composition).

The first strong competitor is IRCoT (Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions). It alternates one sentence of step-by-step reasoning with one retrieval call, using each new sentence as the next search query. It is the canonical linear chain and reports retrieval recall gains of 11–21 points and QA F1 gains of up to 15 points across four multi-hop benchmarks.

The strongest tree-based competitor is ProbTree, which reports a 7.3% F1 improvement over prior methods on MuSiQue. The file gives only this relative gain, not an absolute score.

DTKG reports 83.0% semantic-match accuracy on MuSiQue against a 53.5% baseline. It is the strongest reported number in the file, but its metric is not F1. We will therefore rerun it rather than compare against the published figure.

No reported result was found on Lacuna for any system on attribute-conjunction bridges or swapped-binding distractors. That is the reason BindHop exists.

All systems will use the same reader model, the same BM25-plus-dense retrieval index, and the same limit on model calls per question. Each method will get the same budget for tuning prompts and thresholds on a shared development split.

Two ablations isolate the key ingredient. The first keeps the full tree and verifier but scores only $\phi$ with no swap margin. The second keeps the verifier but replaces the per-entity predicates with the raw sub-question text.

We will count it as beating the baselines if the method meets three conditions. On BindHop's counter-stereotypical split, it must reduce the swap error rate relative to the best rerun baseline by a margin larger than the run-to-run variance. The swap error rate is the share of wrong answers that equal the answer implied by the distractor's pairing. Second, it must improve answer F1. Third, it must stay within two F1 points of that baseline on MuSiQue and HotpotQA, so the gain is not bought by losses on ordinary questions.

Why not just…?

Why not just add a cross-encoder reranker to IRCoT and skip the tree? This is the most serious threat. The ColorSwap gap between cross-attention and dual-encoder models suggests that much of the binding failure may simply be retrieval ranking, which a reranker would fix. The swap-margin ablation and an "IRCoT plus the same cross-encoder" baseline are designed to settle this. Our bet is that the reranker scores the passage against a chain-of-thought sentence that has already blurred the attributes together, so it cannot ask the swap question. If IRCoT with the reranker matches our method on the counter-stereotypical split, we will report that binding errors in multi-hop QA are a ranking problem and not a planning problem. That would still be a useful result, and the benchmark would carry the contribution.

Why not just prompt the decomposer to keep every modifier in its sub-questions? This approach is cheap and might work on familiar pairings. Two cited results argue it will fall short. The logic-translation results show that models link modifiers by word adjacency when generating free text, so a sub-question written in prose can inherit the same swap. The concept-association results predict that this failure concentrates on counter-stereotypical pairings. We include "ProbTree with a modifier-preserving prompt" as a baseline, and we expect any gap to appear specifically on the counter-stereotypical split.

Why not just use a frontier model with a long context and let it read everything? Scale has not removed binding failure. GPT-4V still fails nearly 3 in 10 ColorSwap items. The BindSplit audit found that larger CLIP models pay a larger penalty, losing 38–43 points from familiar to unfamiliar pairings on PUG:SPARE. We will nonetheless run a frontier model with all gold and distractor passages in its context as a ceiling-style baseline. If it already solves BindHop, the method is unnecessary at that scale, and the question shrinks to whether the method lets small models match it.

Why not just fine-tune the retriever on swapped-attribute hard negatives? Prior work found that fine-tuning on pairings memorizes the specific pairs seen in training. In Does CLIP Bind Concepts? Probing Compositionality in Large Image Models, fine-tuned CLIP fell to near 0% on unseen two-object combinations. In Common Data Properties Limit Object-Attribute Binding in CLIP, hard negatives gave only marginal gains. We will include a hard-negative-tuned retriever trained on the familiar split and test it on the counter-stereotypical split, where we expect it to collapse.

Proposed Experiments

The first decisive check is diagnostic and comes before any method claim. On BindHop, we will measure whether the swap error rate of IRCoT and ProbTree rises from the familiar to the counter-stereotypical split. We will also check whether these errors are traceable to the first hop, using passage-level attribution to see which hop retrieved the distractor. If baseline errors are not dominated by swaps, the premise fails, and we stop.

The second check measures planner reliability on its own. Using hand-written gold predicates for 300 items, we will compare the generated binding leaves against the gold ones. Following the hallucination warning from the logic-translation paper, we will report how often the planner itself swaps attributes. We will then rerun the full method with gold predicates, which separates planning errors from verification errors.

The third check is the main comparison, run under the matched budget described above. We report answer F1, swap error rate, number of backtracks, and model calls per question for each split of BindHop, MuSiQue-Ans, and HotpotQA.

The fourth check tests whether the margin rule transfers to images. On the multimodal slice, and on WebQA, where MMAPG reports 65.9 QA accuracy (MMAPG: A Training-Free Framework for Multimodal Multi-hop Question Answering via Adaptive Planning Graphs), we will use a VLM as the verifier. The question is whether MMAPG's practice of treating each image as a single whole leaves recoverable binding errors.

The pattern that would support the claim combines three results. The method should beat the reranker-augmented IRCoT on swap errors. The gap should be largest on counter-stereotypical items. And the gap should disappear when the swap margin is ablated.