Certify checks each needed fact before answering a search question
Knowing When the Evidence Is Enough: Requirement-Directed Search with Horn-Closure Certificates · arXiv:2610.34684
In plain words
A search assistant often has to decide whether its pages contain every fact needed to answer a question. Certify is a search method that checks the needed facts one by one, then answers with a small set of supporting passages or abstains and says what is missing.
On paired questions with answerable originals and twins missing key evidence, Certify made more accurate answer-or-abstain decisions than the tested methods in their default configurations. This result is limited to those evaluations.
The research
When a search assistant answers too soon, it may state something its retrieved pages do not support. Yet a context can mention the right people and places while missing one fact the answer depends on. Can an assistant check each required fact and identify what remains missing?
Certify searches for each required fact, then derives whether the evidence supports an answer or names what remains missing.
By representing the facts a question requires, Certify searches for each one and checks whether the linked evidence derives the answer. It then returns a minimal supporting context or abstains and names open requirements.
The paper tests this decision on answerable questions paired with twins missing their supporting evidence.
Certify was significantly more accurate than the tested search, graph-retrieval, and sufficiency-judgment methods in their default configurations, supporting requirement-by-requirement checks in these evaluations.
The formal guarantees depend on retrieving the gold evidence, stating the correct requirements, and linking passages exactly; the paper also gives a soundness result when accepted links are correct.
A certificate shows that its context states the facts used in its derivation, but does not by itself prove the answer is correct.
What the evidence shows
- The missing-fact problem
Certify is a requirement-directed search method for deciding whether retrieved evidence supports an answer. Search assistants must choose whether to answer, search again, or abstain, and a context judged as a whole can hide a missing fact.
This matters especially when a question needs several facts together: having most of them does not make the evidence sufficient.
- Search by requirement
Certify represents the facts a question needs and the links between them, then searches for each requirement using values already found. It links passages to the requirement they state and uses rule-based derivation to check whether the answer follows.
It returns a minimal supporting context and derivation, or abstains and identifies open requirements.
- Compare paired decisions
To test the answer-or-abstain decision, the paper pairs answerable questions with twins whose supporting evidence has been deleted and checks for other passages that state the missing fact. Decision accuracy counts a correct answer on an original or abstention on its twin.
Across three question-answering corpora, Certify was significantly more accurate than search agents, graph retrieval, and sufficiency judges in their default configurations.
- Test the selected context
A separate reader comparison tests the context Certify supplies. On its answered original questions, the same 8B reader answered correctly on 80.0% with the certificate context and 56.7% with the whole retrieved pool.
This supports the view that selecting a concise context can help the reader, while the figures apply only to that reader and those answered originals.
- Check links at larger scale
In a separate search over 21 million Wikipedia passages, the method linked passages more carefully by checking whether a title named the lookup subject. On pairs with verified gold evidence, subject anchoring raised decision accuracy by 4 to 13 percentage points across the tested corpus and model-size cells.
The paper’s formal guarantee is conditional on correct requirements and evidence, with exact links; its accepted-link soundness result also requires correct requirements and every accepted link used in the derivation to be correct.
Deep
- Original paper authors
- Xinyu Zhang, Weiwei Sun
- Submitted to arXiv
- License
- arXiv non-exclusive