HopRefusalBench: Diagnosing Refusal Failures in Search-Augmented Agents for Multi-Hop Reasoning

Technical Summary: HopRefusalBench

Problem Statement
Search-augmented large language model (LLM) agents are increasingly effective at solving knowledge-intensive tasks; however, their behavior when encountering fundamentally unanswerable multi-hop questions remains poorly understood. Existing benchmarks for abstention primarily expose defects in single-hop queries or surface-level reasoning. They fail to capture failures that emerge only after valid intermediate reasoning and retrieval have occurred. In real-world scenarios, user queries often contain false premises, underspecified contexts, or unknown answers. A reliable search-augmented agent should detect these unanswerable conditions during multi-step retrieval and respond with an epistemically appropriate non-answer (refusal). Current systems, however, often enter costly retrieval loops, force broken connections, or hallucinate answers due to "completion pressure" generated by valid prefix evidence.

Methodology: HopRefusalBench Construction
The authors introduce HopRefusalBench, the first controlled benchmark designed to diagnose refusal failures within multi-hop search. The benchmark consists of 889 unanswerable questions constructed via a four-stage pipeline:

1. Seed Grounding: The authors select seed questions from existing datasets (e.g., CoCoNot, BIG-Bench, FalseQA) that require non-answers or clarifications. These are categorized by three causes of unanswerability:
   • Answer Unknown (AU): The requested fact is not established or knowable.
   • False Premise (FP): The question contains a factually incorrect assumption.
   • Underspecified Context (UC): Necessary qualifiers are missing.
2. KG-Guided Path Construction: Using the KILT Wikipedia hyperlink graph, the authors construct valid reasoning chains. They perform bidirectional traversal: backlink traversal builds valid prefixes toward a "backward anchor," and outgoing-link traversal extends suffixes from a "forward bridge." This ensures semantic continuity while isolating the unanswerable step.
3. Topology-Controlled Synthesis: The core innovation is the control over where the unanswerability interrupts the reasoning chain. The benchmark crosses the three causes with three topologies:
   • Root: The unanswerable seed is the first step, masked by a plausible continuation.
   • Middle: The unanswerable step acts as a broken bridge between a valid prefix and a dependent suffix.
   • Terminal: The unanswerable step appears only after a valid prefix has been fully resolved.
4. Quality Control: A multi-stage audit ensures that hidden anchors are not leaked, the chain coherence is maintained, and the original cause of unanswerability is preserved without the fusion model accidentally correcting the premise.

Evaluation Framework
The authors propose a diagnostic framework that evaluates both final outcomes and source-aware evidence timelines:

• Final Outcome Taxonomy: Responses are classified into Correct Refusal (Target-Aware Correct Halting, TACH), Pseudo-refusal (premature halting, wrong rationale, or uninformative rationale), Hallucination (accepting the defective premise), and Search Exhaustion (consuming the search budget without a final decision).
• Source-Aware Metrics: The framework identifies the first turn ($T_{trap}$) where sufficient evidence for refusal appears. It measures Post-Trigger Token Waste (PTTW) and Post-Trigger Over-Search Rate (PTOS) to quantify inefficiency after the model could have stopped.
• Search-Induced Shifts: By comparing search-augmented and no-search modes, the authors measure how search alters behavior, specifically calculating the Search-Induced Override Rate (SIOR) (how often search turns a correct refusal into a failure) and the Search-Induced Rescue Rate (SIRR).

Key Results
The authors evaluated ten frontier proprietary and open-weight models (including GPT-5.4, Claude-Sonnet-5, Qwen3.5/3.6, Kimi-K2.5/2.6, DeepSeek-V4-Pro, and GLM-5.1/5.2) in search-augmented mode:

• Low Overall Performance: The best-performing model achieved a Target-Aware Correct Halting Rate (TCHR) of only 42.9%.
• Search Destabilizes Refusal: For nine of the ten models, search-augmentation decreased TCHR compared to no-search mode. Search frequently overrides correct refusals (20.4–67.3% of cases) rather than rescuing failures (4.2–16.9%).
• Topology and Cause Difficulty:
  • Root and Middle items are consistently harder than Terminal items, suggesting that plausible downstream goals mask early defects more effectively.
  • Models perform best on False Premises (where retrieval can directly contradict claims) and worst on Underspecified Context questions (which invite the agent to supply plausible referents).
• Divergent Failure Modes:
  • Models exhibit different failure channels: some (e.g., GPT-5.4) predominantly hallucinate answers despite evidence, while others (e.g., Qwen3.6-27B) tend toward search exhaustion.
  • Commitment vs. Recognition: A critical finding is that 84.7–98.4% of explicit refusal-like responses correctly identify the rationale. The primary bottleneck is not recognizing the unanswerability, but committing to a non-answer.
• Inefficiency: Many trajectories continue searching after sufficient evidence is found, generating significant token waste (up to 10,321 post-trigger tokens on average for some models).

Significance and Claims
The paper claims that HopRefusalBench establishes refusal in multi-hop search as a consequential evaluation problem. It provides a foundation for diagnosing reliability by separating evidence discovery, refusal commitment, and efficient stopping. The authors argue that current search-augmented agents lack the coordinated capability to verify premises, decide to refuse, and control search budgets simultaneously. The benchmark is publicly available to facilitate further research into improving the reliability of agentic search systems.