Online Evidence-Containment Prediction over Text Spans under Distinct Queries

Xiang Liu, Haochen DingarXiv 2026 · arXiv

In the world of Retrieval-Augmented Generation (RAG) and automated fact-checking, "verification" is the expensive final step. After a system retrieves a set of candidate text spans, it must check each one to see if it actually contains the evidence needed to answer a question. This is often done by calling a large, slow, and costly model.

A new paper, "Online Evidence-Containment Prediction over Text Spans under Distinct Queries," argues that we are doing this inefficiently. By ignoring the logical "nesting" of text spans—sentences inside paragraphs, paragraphs inside documents—we are throwing away free information.

TL;DR

The authors formalize evidence localization as Online Evidence-Containment Prediction (OECP), showing it is equivalent to a structured 2D learning problem. By exploiting the logical dependencies between nested spans and using a new decision rule called Expected Search-space Reduction (ESR), they can find evidence with significantly fewer expensive verifier calls.

What Problem Does This Paper Address?

When an NLP system verifies evidence, it usually treats each candidate span as an independent trial. However, text is hierarchical. If a specific sentence contains the answer, then the paragraph containing that sentence must also contain the answer. Conversely, if a paragraph is found to be irrelevant, every sentence within it is also irrelevant.

Existing systems for retrieval and adaptive acquisition don't fully exploit how verification outcomes propagate across these nested candidates. The challenge is to find a way to use these logical constraints to minimize the number of times we have to ask an expensive "verifier" model for a label.

Methods

The authors tackle this by framing the problem through the lens of online learning theory:

  1. OECP Framework: They prove that span containment is exactly a triangular two-dimensional product order. This allows them to treat evidence prediction as online isotonic regression—a type of learning where predictions must respect a specific order (e.g., a superspan's probability of containing evidence must be greater than or equal to its subspan's).
  2. Endpoint-Rank Compression: Instead of dealing with every token in a document, they compress the search space to only the "effective scale" ($m_{\text{eff}}$)—the unique start and end points of the proposed candidates. This often reduces the problem size by 30-60x.
  3. Expected Search-space Reduction (ESR): This is their novel decision rule. Instead of greedily checking the most likely span, ESR calculates which span's verification outcome (positive or negative) is expected to prune the largest portion of the remaining search space. It balances the probability of a span being "correct" with its "informativeness" regarding other spans.
Figure 1. Overview of OECP. (A) Nested spans with monotone containment labels, each verified once. (B) Exact map from spans to a triangle in the m × m grid (m: raw token length). (C) Endpoint-rank compression to the meff × meff grid of observed endpoints. (D) Distinct-query regret is eΘ(m) on the raw grid, hence eO(meff) after compression.

Datasets

The researchers evaluated their approach on several key benchmarks:

  • Natural Questions (NQ): Used to analyze the geometry of real-world candidate spans and evaluate neural predictors.
  • SciFact: A scientific claim verification dataset used to test how quickly ESR can localize evidence in abstracts.
  • ERASER: A benchmark for explainable NLP, featuring documents where multiple different spans might count as valid evidence.

Key Insights and Ideas

  • Caching Changes the Complexity: In standard online learning, you might query the same point repeatedly. In OECP, you query a span once and cache the result. The authors prove this "distinct query" constraint makes the problem much easier theoretically, dropping the worst-case error (regret) from a polynomial rate to a near-linear one.
  • The Power of Deduction: A huge portion of the performance gain comes from simple logical deduction (e.g., "if the parent is negative, the child is negative"). However, there is still a reproducible "learned signal" that helps models predict outcomes for spans that aren't yet logically determined.
  • Multi-Target vs. Single-Target: The problem is significantly harder when there are multiple valid evidence targets (like in ERASER) versus a single fixed answer (like standard QA). The theoretical regret jumps from logarithmic to near-linear in the multi-target case.

Key Results

  • Fewer Verifier Calls: On the SciFact dataset, ESR reduced the median number of verifier calls needed to find the minimal evidence region from 6 to 4. On ERASER, calls dropped from 16 to 11.
  • Outperforming State-of-the-Art: Under fixed verification budgets, ESR outperformed four recent external selectors, including NEST-Adapt and REARANK, in localizing evidence.
  • Improved Prediction Accuracy: By simply adding "containment history" features to a standard DeBERTa model, the authors reduced the prediction error (Brier score) by over 50% on Natural Questions.

Limitations and Future Work

While the results are promising, the authors note a few areas for future exploration:

  • Noisy Verifiers: The current framework assumes the verifier is an "oracle" that is always correct. In practice, LLM-based verifiers can be noisy or biased.
  • One-Step Optimality: ESR is a "one-step" rule. It picks the best next move but doesn't guarantee the optimal sequence of moves over the long term.
  • Constructive Multi-Target Learners: While they proved a theoretical upper bound for the multi-target case, finding a practical, efficient algorithm that reaches that bound remains an open challenge.

For researchers building RAG pipelines or fact-checking agents, this work provides a rigorous foundation for making those systems faster and cheaper by simply respecting the logic of the text they are processing.

Summary updated

Abstract

Evidence-grounded NLP systems often verify nested text regions sequentially, so verifying one region constrains others. We formalize this as Online Evidence-Containment Prediction (OECP): each candidate is predicted before exact verification and queried at most once. Span containment is exactly a triangular 2D product order, making OECP distinct-query online isotonic regression. With multiple admissible targets, worst-case regret is near-linear, $\widetildeΘ(m_{\mathrm{eff}})$, in the effective scale given by endpoint-rank compression; a single fixed target, as in standard QA, admits an explicit polynomial-time learner with optimal $Θ(\log m_{\mathrm{eff}})$ regret, run on real NQ episodes. On Natural Questions, containment yields a large deductive gain plus a smaller learned gain on unresolved candidates, reproduced across two backbones and DPR hierarchies. Expected Search-space Reduction (ESR) turns these probabilities into decisions, localizing evidence in fewer verifier calls on SciFact, ERASER, and DPR hierarchies; on DPR hierarchies under call budgets it outperforms four recent external selectors and raises fixed-reader F1 over learned and generator-greedy scheduling.
BibTeX
@misc{liu2026online,
  author = {Xiang Liu and Haochen Ding},
  title = {{Online Evidence-Containment Prediction over Text Spans under Distinct Queries}},
  year = {2026},
  eprint = {2610.41384},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41384},
}
Figure