PaperlayerView exact revision on arXiv

Source-linked AI summary

Knowing When the Evidence Is Enough: Requirement-Directed Search with Horn-Closure Certificates

Xinyu Zhang, Weiwei Sun

arXiv:2610.34684v1cs.IRcs.AIcs.CL

TL;DR

Search-augmented systems must decide whether retrieved evidence supports an answer, but holistic judgements can miss a required fact. Certify decomposes questions into requirements and uses entity-checked links with Horn closure to return a minimal certificate or abstain. Across three pooled corpora, it outperforms default search agents, graph retrieval, and sufficiency judges.

  • Problem

    Holistic context judgements can miss a required fact in multi-hop questions, while sufficiency also requires deriving question requirements and linking evidence to the right entity.

    Source: §1 · p. 1

  • Method

    Certify searches per requirement, accepts links after entity checks, and applies Horn closure to return a minimal sufficient context with derivation or abstain with open requirements.

    Source: §1 · p. 1, §4 · p. 4

  • Results

    Certify decides significantly more accurately than search agents, graph retrieval, and sufficiency judges in default configurations across three pooled corpora with search-checked twins.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The certificate exposes the supporting passages and derivation, while abstention names the open requirements that remain to be searched.

    Source: §1 · p. 1, §4 · p. 4

    Its soundness and completeness depend on gold retrieval, correct requirements, and exact linking, with completeness limited by the entity check.

    Source: §1 · p. 1, §4 · p. 4

Abstract

from arXiv · show

After each Web search, a search-augmented model must decide whether its evidence suffices: answer, search again, or abstain. Prevailing systems leave this to holistic model judgement, which can accept a context naming every entity yet lacking one required fact. We instead make sufficiency structural: a per-query requirement hypergraph states which facts jointly yield another fact. This raises two challenges: deriving requirements from the question alone, and linking each requirement to passages about the right entity. Certify therefore decomposes the question, searches per requirement, and accepts links only after entity checks. Horn closure over the links yields a certificate, the minimal sufficient passages and their derivation, or an abstention naming open requirements. Given correct retrieval, requirements and links, the decision is sound, and complete up to the entity check. Pooled over three corpora with unanswerable twins, Certify decides significantly more accurately than search agents, graph retrieval and sufficiency judges in default configurations. On the same evidence, it matches a proprietary model's sufficiency label without an additional model call. Over 21M Wikipedia passages, entity checks add 4 to 13 points of decision accuracy where gold evidence exists. Finally, answers from its certificate are 80% correct, against 57% from all retrieved passages.

1 Introduction

Certify treats evidence sufficiency as a structural decision: its requirement hypergraph makes missing conjuncts explicit and guides search or abstention. Across three pooled corpora, it outperforms default search agents, graph retrieval, and sufficiency judges.

1 Introduction

  • Holistic context judgements can miss a required conjunct even when the context names every entity and contains most of the facts.Making sufficiency explicit also requires deriving requirements from the question, linking passages to the correct entity, and constructing unanswerable questions whose deciding fact is absent.Source: §1 · p. 1
  • Certify represents jointly required facts as directed hyperedges, searches one requirement at a time, and uses Horn closure to answer with a minimal certificate or name open requirements.The closure returns the derivation and directs the next search without an additional model call.Source: §1 · p. 1
  • With correct retrieval, requirements, and links, the certificate is sound and complete on the retrieval event up to the entity check.Pairwise projections cannot distinguish a conjunction from a disjunction.Source: §1 · p. 1
  • Certify decides significantly more accurately than search agents, graph retrieval, and sufficiency judges in default configurations across three pooled corpora with search-checked twins.It also matches a proprietary model’s sufficiency label on the same evidence without an additional model call; certificate answers are 80.0% correct versus 56.7% from the whole pool.Source: §1 · p. 2

2 Related Work

Prior work addresses sufficiency, stopping, and retrieval through model judgements, graph representations, or formal reasoning. Certify instead uses directed requirement hyperedges to determine whether retrieved evidence suffices and to expose what remains missing.

Deciding sufficiency and abstaining in RAG

  • Sufficiency judges, stopping rules, and step verifiers typically use a model to assess a context, claims, or reasoning path; Certify derives sufficiency from requirement hyperedges.Related benchmarks often use deletion or context removal, while Certify deletes evidence from the corpus and checks by search that it is gone.Source: §2 · p. 2

Iterative retrieval and search agents

  • Search agents, decomposition methods, and planners select what to search next, while Certify’s closure returns a minimal context or the open requirement without a model call.Other approaches verify steps or let an LLM judge whether subanswers or paths suffice.Source: §2 · p. 2

Graphs and hypergraphs for retrieval and memory

  • Graph-based RAG links passages through entities, whereas Certify’s directed requirement hyperedges decide evidence sufficiency and preserve n-ary conjunctions.A rule using only pairwise projections cannot reliably make that decision.Source: §2 · p. 2

Directed hypergraphs and Horn reasoning

  • Classical Horn reasoning, provenance, completeness, and minimal-evidence methods provide related tools, but Certify applies closure to the per-query decision of whether retrieved context suffices.Its certificate is deductive and per query.Source: §2 · p. 2

3 Evidence, Requirements and Sufficiency

The paper formalizes sufficiency by representing query-relevant facts and their dependencies as a requirement hypergraph, then checking whether evidence derives the target. This representation preserves conjunctions that pairwise projections lose.

Evidence, Requirements and Sufficiency

  • A requirement hypergraph has atoms as vertices and directed hyperedges whose tail atoms are jointly required to derive a head atom.Its tail size counts the conjoined facts; evidence units state atoms and may witness hyperedges.Source: §3 · pp. 2–3
  • A context is sufficient when its facts and witnessed rules, together with query-given atoms, derive the target atoms under Horn closure.Sufficiency is monotone in the context because the closure operator is monotone.Source: §3 · p. 3
  • For Web questions, requirements are single-fact lookups that may refer to earlier answers; reasoning requirements combine previously derived facts into a value.For interaction logs, action preconditions support facts that become true, while deleted facts only close validity intervals and generate no hyperedge.Source: §3 · p. 3
  • Pairwise tail-to-head projection preserves which atoms touch a rule but loses whether its tail atoms are conjunctive.The tail shuffle replaces multi-atom tails with singleton rules while leaving the projection unchanged.Source: §3 · p. 3
  • A rule receiving only the query, atom contents, stated facts, and pairwise projection must give the same decision on a hypergraph and its tail-shuffled twin.A separate 2-section result shows that removing a unit can leave the entity-pair graph unchanged even when sufficiency flips.Source: §3 · p. 3
  • Certify’s algorithm takes a query, unit collection, retriever, linker, and search schedule, and returns either an answer with certificate or abstention with open requirements.The procedure retrieves for requirements, links units, checks whether the target is derived, and prunes units while preserving sufficiency.Source: §3 · p. 4

4 Certified Sufficiency

Certify searches and links evidence per requirement, then applies an entity check and Horn closure to produce a minimal derivation certificate or identify what remains open. Its guarantees are conditional on retrieval, requirements, and links being correct.

4 Certified Sufficiency

  • Web retrieval decomposes the question into requirements, searches each instantiated requirement separately, and links a unit only when it states that lookup’s answer.Reasoning requirements compute values from previously derived facts, and each lookup search stops after the first round that links a unit.Source: §4 · p. 4
  • A lookup link is accepted only when its value is anchored to the requirement’s subject or passes verification against the named entity.Title matching anchors a unit; otherwise a reader checks the first two supporting passages for the exact entity.Source: §4 · p. 4
  • Horn closure over accepted links yields a minimal context and derivation, or abstention naming resolved open requirements or a failing lookup.The certificate attests that its context states every required fact, not that the answer is correct.Source: §4 · p. 4
  • Under gold retrieval, correct requirements, exact links, and one true value per lookup, Certify is complete on the retrieval event except for violations or failed entity checks, and any answer is sound.The returned context is sufficient and violates no hyperedge in its derivation under the stated assumptions.Source: §4 · p. 4
  • With a single derivation and unique producing units for its stated atoms and rules, the certificate is the unique inclusion-minimal sufficient subset, independent of pruning order.Certification takes at most |C0|+1 closure computations, each linear in instance size.Source: §4 · p. 5
  • On twins that delete a fact every derivation needs, a false certificate requires a surviving accepted statement or a false accepted link.With correct requirements, the false-certificate rate is bounded by those two rates.Source: §4 · p. 5

5 Experimental Setup

The experiments evaluate Certify and baseline systems on pooled Wikipedia question-answering corpora and controlled unanswerable twins, using shared retrieval and reading components. They also measure answer quality, decision quality, and cost.

5 Experimental Setup

  • The 2WikiMultiHopQA and MuSiQue test sets use shared Wikipedia pools, a common dense retriever and reader, and 800-question test splits after 200-question validation splits.HotpotQA comes from the same release, with twins deleting one of two Gemini-2.5-Flash lookup passages.Source: §5 · p. 5
  • Unanswerable twins remove a deciding fact and any found restatements; memory filtering leaves 529 2WikiMultiHopQA twins and 826 MuSiQue twins.Retained twins are not answered correctly without context by either reader in five samples; the filter removes most guessable yes/no comparisons from 2WikiMultiHopQA.Source: §5 · p. 5
  • ProofWriter depth-5 theories and AMA-Bench-protocol TextWorld logs provide exact requirement hypergraphs for 959 episodes, including 671 test episodes.Each query asks which turns enable an action, and its twin deletes one.Source: §5 · p. 5
  • Baselines use default configurations under the shared retriever, reader, and corpus, with validation selecting subject anchoring or verification for pooled tests and subject anchoring for Web scale.The selected pooled setting achieved 68.4% decision accuracy on validation; the Web-scale setting achieved 52.4%.Source: §5 · p. 5
  • The evaluation reports answer accuracy and answered-question accuracy, plus coverage, twin-answer behavior, abstention precision, decision accuracy, LLM calls, and input-token cost.Decision accuracy credits correct original answers and abstentions on twins; always abstaining scores 50.Source: §5 · pp. 5–6
  • Certify has the highest SAcc on both answerable test corpora; only HALT and SR-RAG make more LLM calls.Table 1 reports accuracy and cost on the 8B test setting; offline indexing is excluded.Source: Table 1 · p. 6

6 Results

Across the evaluated settings, Certify improves answer-or-abstain decisions over baselines, while its certified answers are more reliable than answers drawn from the full passage pool. Results also test the entity-linking and exact-requirement assumptions behind its guarantees.

6.1 RQ1: Answerable questions

  • 85.8% and 74.5% of answers produced through accepted-link requirement hypergraphs are correct; Certify answers 73.0% of all 2WikiMultiHopQA originals correctly.On MuSiQue, it answers 30.8% of originals correctly, while agents answering 34.6–47.2% also answer most twins.Source: §6.1 · p. 6

6.2 RQ2: Answering or abstaining

  • The entity check reduces twin answers from 20.6% and 13.2% to 8.2% and 7.6%, with decision-accuracy gains of +5.3 and +1.1 points.The gains are significantly +2.7 pooled across the three corpora; comparisons assume half the queries are unanswerable.Source: §6.2 · p. 6, Table 2 · p. 7
  • Certify decides more accurately than every baseline and is as accurate as a Gemini-2.5-Flash label on the same answers; on 429 complex pairs, it stays significantly above every baseline by 5.1 to 42.0 points.Source: §6.2 · p. 7, §6.3 · p. 8

6.3 RQ3: What the certificate delivers

  • On complex pairs, Certify remains significantly above every baseline; certification costs mostly linking calls, at 17 and 22 LLM calls per question versus Search-R1’s 4.The certificate’s named open requirement can identify the failing lookup on traceable twin abstentions.Source: §6.3 · pp. 7–8, Table 4 · p. 8

6.4 RQ4: The hypotheses in practice

  • Anchored links are more often correct than rejected links on every corpus and at both scales; on 2WikiMultiHopQA, the rates are 96.7% versus 20.0%.A blind annotator confirmed the pattern on 135 links: 97.8% anchored versus 50.0% rejected links were correct.Source: §6.4 · p. 8, Table 5 · p. 8

6.5 RQ5: Exact requirements

  • On 959 TextWorld episodes, closure recovers every enabling set, whereas pairwise rules fail; with ProofWriter, fixing one rule per requirement misses 20.6% of provable questions.At depth 5, the committed plan misses 36.1%; the closure misses none.Source: §6.5 · p. 8

6.6 Web-scale retrieval: anchoring the links

  • On gold-verified Wikipedia pairs, entity-title anchoring raises decision accuracy in all six model-and-corpus cells by 4.2–13.3 points.The 2018 snapshot lacks gold support for many questions, so reported Web results use verified pairs.Source: Table 3 · p. 7, §6.6 · p. 8

7 Conclusion

The conclusion presents requirement-hypergraph closure as a way to decide sufficiency and direct further search. It reports improved decisions on pooled corpora and gains from entity anchoring at Web scale.

7 Conclusion

  • On three pooled corpora, Certify decides significantly more accurately than search agents, graph retrieval, and sufficiency judges in default configurations.On the same evidence, closure matches a fast proprietary model’s sufficiency label.Source: §7 · p. 8
  • Horn closure returns a minimal sufficient context with its derivation, or names open requirements to direct the next search.The decision is sound and complete up to the entity check when retrieval, requirements, and links are correct.Source: §7 · p. 8
  • With exact requirements, closure recovers every derivation, while pairwise projections miss conjunctions and advance-committed plans miss alternatives.At Web scale, entity-title anchoring raises decision accuracy on every corpus and model size.Source: §7 · p. 8

A Proofs

Horn closure gives a structural sufficiency test whose guarantees depend on correct retrieval, requirements, and links. Two separation results show why decision rules must preserve directed requirements and individual passage identity.

A Proofs

  • Under correct maps and links, closure is monotone and extensive, and the pruning procedure returns an inclusion-minimal sufficient context.The proof also establishes completeness up to the entity check on the retrieval event.Source: A Proofs · p. 11
  • Rules using only the tail-to-head projection cannot distinguish conjunctive requirements from disjunctive ones, producing errors on balanced paired instances.For any pair whose true labels differ, the rule is wrong on exactly one member.Source: A Proofs · p. 11
  • Pairwise entity co-occurrence can remain unchanged when a unit is removed even though that unit states a fact required for sufficiency.Such indistinguishable inputs can have different sufficiency labels, yielding a two-point error lower bound for rules using only the 2-section.Source: A Proofs · p. 11

B Implementation Details

Certify searches per instantiated requirement, links passages after entity checks, and evaluates sufficiency through the resulting certificate. Its experiments compare this process with baselines and examine performance under search, twin-construction, and Web-scale settings.

B Implementation Details

  • Certify retrieves up to three rounds of 5, 5, and 10 passages per lookup requirement, while a linker accepts answers only for the right entity.A single reader call with four in-context examples builds the hypergraph; two other example sets shift pooled decision accuracy by −1.2 and −1.7.Source: B Implementation Details · p. 11
  • Across pooled corpora, Certify significantly outperforms search agents, graph retrieval, and sufficiency judges in their default configurations.On the same evidence it matches a proprietary model’s sufficiency label without an additional model call.Source: B Implementation Details · p. 11
  • With one search round of five passages per requirement, Certify links 10.7, 11.1, and 9.3 passages per question and decides accurately at 79.5%, 60.4%, and 71.5% (fresh run).Default linked counts are 13.2, 20.0, and 12.9 passages per question.Source: B Implementation Details · p. 11
  • Unanswerable twins are formed by deleting evidence, with fixed-seed hop selection for 2WikiMultiHopQA and HotpotQA and audits for surviving deleted facts.Deleting 1–4 passages preserves context size; a length-only classifier distinguishes originals from twins at chance (AUROC 0.50–0.52).Source: B Implementation Details · p. 12
  • On HotpotQA, Certify exceeds six listed systems by 14.8–42.0 points; on all Web pairs, anchoring adds 4.0–8.6 points.The HotpotQA lookup setup retains questions only when each hop is supported and the bridge lookup yields the gold answer.Source: B Implementation Details · p. 12

C Entity Anchoring and Verification

Entity anchoring and verification determine whether a passage is accepted as evidence for a lookup requirement. Audits report link correctness and decision comparisons, while an example illustrates certification and abstention across original and twin questions.

C Entity Anchoring and Verification

  • Titles anchor a passage when its informative title tokens occur in the instantiated requirement; otherwise, verification checks whether a passage gives the value for exactly the named entity.The first two supporting passages are checked in order; a lookup must be anchored or verified, or Certify abstains and names it.Source: C Entity Anchoring and Verification · p. 12
  • Most false links concern another entity, often a near-namesake, and anchored links are more precise than rejected links across corpora.DeepSeek also finds fewer false derivations when grading those links.Source: C Entity Anchoring and Verification · p. 12
  • Verified links are correct on 76.1% of the human-audited sample, and DeepSeek agrees with annotators on 89.6% (κ=0.74).The annotator sampled 135 of 270 links and 100 twins, blind to class and model verdicts.Source: C Entity Anchoring and Verification · p. 12
  • On audited-clean Web twins, anchored Certify exceeds every baseline in all six cells by 1.1–10.8 points.Across the pooled corpora, baselines remain significantly below Certify after excluding flagged twins or twins with confirmed surviving statements.Source: C Entity Anchoring and Verification · p. 12
  • For the film comparison, Certify derives Je Fais Le Mort from four passages but abstains on its twin, naming the missing director-birth lookup.Search-R1, LogicRAG, and S2G-RAG answer the twin; Search-R1 and LogicRAG also miss the original.Source: C Entity Anchoring and Verification · p. 12

Related papers

Loading 2610.34684v1…