acceptodds
Under review as a conference paper at ICLR 2027

SearchProof: Checkable Negative Evidence from Zero-Result Agent Search

Abstract

Search tools tell language-model agents what they found, but rarely what they actually covered. This asymmetry makes a zero-result call unusually difficult to reason about: an empty result can justify absence inside a searched directory while saying nothing about the rest of a repository. We introduce SearchProof, an inference-time interface that compiles a proposed negative claim into a claim-relative coverage obligation. Each search returns a compact receipt recording the relevant universe, executed scope, result set, coverage, and minimal completion set. The agent can pass this checked set directly to ordinary search before licensing a global negative conclusion. We evaluate this capability with ScopeBench: 72 controlled dependency-graph tasks and 144 query-matched tasks mined from 8 repositories spanning 5 language ecosystems and 2,625 source files. Every identifier appears once in each case type, and query-only balanced accuracy remains near chance. Across 4 agents and 1,872 analyzed model–task outcomes, agents recognize incomplete coverage reliably, yet exact controlled completion planning is only 25.0% from raw results and 100.0% with SearchProof. In interactive use, SearchProof raises grounded success from 94.8% to 100.0% in the two-model ablation grid. A preregistered full-corpus confirmation across DeepSeek and GLM-5.3 then moves 267/288 paired outcomes (92.7%) to 288/288 (100.0%): 21 wins, no losses. The direction remains positive at every nonzero session, query-group, and repository aggregation. Removing the executable completion field reduces DeepSeek to 95.1% (7–0 restored outcomes), isolating the operative mechanism. A source-backed deterministic executor reaches 144/144 tasks with exact completion and no follow-up language-model decision. Across 720 saved agent scopes, direct file execution agrees with the frozen backend on 100.0% of outcomes. SearchProof reads 62.0% fewer files and 60.6% fewer bytes than full-universe restart, reducing median scan latency by 54.3%. On the discriminating incomplete-absence stratum, the two-model gain is 79.2% to 100.0%. A third-agent stress replication moves from 41.7% to 85.4% (paired +43.8 points, 95% CI [25.0, 62.5]), with positive effects after holding out every repository. Median receipt construction plus checking is 4.53 ms at 4,096 components. These results make coverage a first-class evidence type and turn “not found” into a precise, executable observation for tool-using agents.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
language agents, tool-using agents, code search, negative evidence, coverage verification, retrieval completeness

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_awDbOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates a failure mode in LLM search agents where interpreting miss result as global absence could be conflated with incomplete search coverage. The authors introduce SearchProof, an interface that represents negative results in negative claim relative obligation that will be passed to search agent to prevent a global negative conclusion. The authors introduce ScopeBench with 72 dependency graph tasks and 144 tasks from public code repositories and report that their method brings improvement in LLM tool execution success rate.

Critical strengths
  1. The paper identifies a meaningful failure mode in tool-calling agents and motivates that zero-result searches cannot justify global negative conclusions.

  2. The comparison between coverage receipts with and without executable completion sets demonstrates that external action guidance contributes more than generic warnings or coverage reporting.

Critical weaknesses
  1. The mathematical formulation in Section 2 is correct by being nearly tautological. If we already know the complete universe Uc and exactly what has been searched, then computing Uc \ X is ordinary set subtraction. The overall theoretical contribution of the paper is neither significant nor novel.

  2. Query completeness, negative evidence, machine-readable completeness statements, and executable query planning have substantial precedents in database research. In particular, Darari et al. (2013) and the subsequent CoRNER system address closely related concepts. The contribution appears primarily to be an adaptation of established principles to an LLM-agent interface, rather than a fundamentally new methodology.

  3. The reported reductions in files scanned and latency are measured against a restart rather than a competitive incremental-search baseline.

  4. The paper's own deterministic controller achieves 144/144 grounded success without further LLM decisions. The paper does not sufficiently distinguish the proposed agent-facing interface from a conventional stateful controller that automatically tracks coverage and enforces completion.

Questions for authors
  1. How does SearchProof differ substantively from established query-completeness frameworks, particularly completeness statements and executable federated query rewriting in CoRNER? Beyond adapting these concepts to LLM tool interfaces, what is the principal methodological novelty?

  2. Can the authors demonstrate improvements on end-to-end coding-agent tasks in which unsupported absence conclusions lead to actual software-engineering errors, rather than evaluating only exact-identifier search completion?

Reviewer_j85pOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper introduces a tool for helping LLM agents reason about negative search results. The tool tracks which components have been searched and identifies those that remain unchecked. It introduces coverage receipts that encode search completeness and the additional search required, assuming a predefined search universe and exhaustive retrieval. Experiments on synthetic tasks and real software repositories report improvements in answer correctness and search efficiency compared with simple baselines.

Critical strengths

The paper identifies a potentially important problem in agentic search: distinguishing between an absence of search results and sufficient evidence that a target is absent.

Critical weaknesses

The framework assumes away the central difficulty of negative evidence. My primary concern is that the framework assumes away the two main sources of uncertainty in negative evidence: 1) determining the relevant search universe; 2) establishing whether the retrieval procedure can miss relevant results. The proposed method assumes a complete, predefined universe and exhaustive exact-match search within each component.

The correctness guarantees are nearly tautological. The theoretical guarantees are elementary consequences of exhaustive search and set difference. Neither of the two results stated in lines 175-183 provides substantial theoretical insight.

The experimental evaluation does not demonstrate a meaningful contribution. The benchmark consists of constructed exact-identifier search tasks, the proposed interface explicitly supplies the missing components, and a deterministic controller achieves perfect task success without further language-model reasoning. The reported efficiency improvements are also measured against a full-universe search restart, which unnecessarily repeats previously completed searches. This is a weak comparison, since any straightforward implementation that tracks previously searched components and avoids redundant execution could obtain similar effects. The reported reductions primarily demonstrate the obvious benefit of avoiding redundant work, rather than strength of this particular implementation.

Presentation and clarity. In my opinion, the paper’s writing is unnecessarily dense and convoluted. It makes the core contribution difficult to identify and evaluate. The exposition is overloaded with terminology, experimental statistics, and repeated claims of empirical results. The simplicity of the underlying set-accounting mechanism and the strength of its assumptions are obscured by extensive formalism. The abstract and results sections are especially difficult to read, given the numerous overlapping statistics.

Questions for authors

See Weaknesses above.

Reviewer_rUN1OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces SearchProof, an inference-time interface for interpreting zero-result searches by language-model agents. Given a predefined claim universe and the executed search scope, it produces a checkable coverage receipt containing the remaining components that must be searched before concluding absence. The authors evaluate the method on ScopeBench, comprising controlled dependency-graph tasks and exact-identifier search tasks constructed from eight public repositories. The experiments report improvements in exact completion and grounded success, including an increase from 92.7% to 100.0% in the two-model full-corpus comparison. Ablations identify the explicit completion set as the main source of improvement. The demonstrated guarantees assume a correct manifest, a supplied claim universe, and exact component search.

Critical strengths
  1. The problem is clearly defined, and the evaluation metric is practically meaningful. The paper distinguishes between failing to find a target and having sufficient evidence to establish its absence. Its grounded success metric further separates answer correctness from evidential support. This distinction is relevant to code-search agents and highlights failures that final-answer accuracy alone can overlook.

  2. The experimental controls and validation are reasonably thorough. Matched queries, field ablations, source-backed replay, and protocol audits address label leakage, the role of the completion field, and execution consistency. These experiments support a clear finding: when the complete search universe is given, explicitly providing the remaining components is more reliable than asking the model to compute them.

  3. The method is simple and inexpensive to deploy. It requires neither training nor changes to the underlying model, and receipt construction and checking introduce little overhead. The interface could be useful in applications that support exact search and maintain a complete component manifest.

Critical weaknesses
  1. The core technical contribution is limited, and the novelty is insufficiently established. The central operation is to compute Uc∖XU_c\setminus X, given the complete universe UcU_c and the searched scope XX, and then verify basic set relations. The correctness and minimality guarantees follow almost directly from these definitions and the exact-search assumption. The paper provides substantial evidence that this implementation reduces models’ set-accounting errors, but it does not sufficiently establish a substantive methodological advance over ordinary search-state tracking, deterministic scope completion, or completeness statements discussed in the related work. The contribution currently appears closer to a useful tool-interface improvement, with a gap between its technical depth and the breadth of its framing.

  2. The crucial problem of determining the relevant universe is assumed to be solved by the task adapter. The method relies on knowing the complete scope over which a claim must be verified. Although the paper uses the term “claim compilation,” the implementation primarily constructs a repository scope or dependency closure from a task-provided root or entry component. The experiments do not evaluate how to reliably infer the relevant universe from general natural-language questions, or how the method behaves with incomplete manifests, incorrect dependencies, or misspecified scopes. Consequently, the receipt guarantees search completeness only relative to the supplied universe; it does not independently establish the validity of a natural-language negative conclusion. This substantially limits the method’s applicability.

  3. The experiments primarily demonstrate that deterministic set computation is more reliable than asking a language model to perform it, with limited implications for broader agent capabilities. SearchProof explicitly supplies the exact next search set, whereas the main baselines require the model to recover or compute that set. The improvement in exact completion is therefore largely expected. Moreover, the paper’s deterministic execute-Δ controller solves all 144 tasks without any follow-up language-model decision. This supports the practical value of programmatic execution, but also indicates that the current tasks are largely solvable by a deterministic procedure once the universe is given. The paper does not clearly establish what additional value the full receipt design provides over ordinary state tracking and automatic completion search.

  4. The tasks and interaction protocol are restrictive, leaving the benefits for realistic coding agents unclear. Although the repository experiments use real source code, the tasks remain constructed exact-identifier existence checks, and the main protocol permits at most one batched follow-up search. The evaluation does not cover semantically equivalent implementations with different names, fuzzy queries, multi-step search decisions, changing repository states, or actual software-modification tasks. The current evidence therefore primarily concerns exact lookup over a frozen manifest and does not establish comparable benefits for more complex code-understanding or software-engineering tasks.

Questions for authors

please ref to the weakness

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.