cs.AIOct 30, 2026

Online Evidence-Containment Prediction over Text Spans under Distinct Queries

Authors: Xiang Liu, Haochen Ding

Organizations: Xiamen University, China · Northeast Forestry University, China

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, Θ~(meff)\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⁡meff)Θ(\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.

Figures & tables

Appendix figures & tables25 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. CoRA-Bench: Evaluating Evidence Preservation by Context Selectors Under Token Budgets

    Nov 6, 2026Huzaifa Pardawala, Siddhant Sukhani, Sudheer Chava +1Evidence SelectionLong-Context Language Model Evaluation

  2. LENS: In-Context Search via Latent Evidence Exploration over Dynamic Raw Documents

    Aug 17, 2026Xingjun Wang, Gongsheng Li, Qi Fan +3In-Context RetrievalEvidence Retrieval

  3. SEEDS: Preview-Guided Evidence Admission for Search Agents

    Oct 9, 2026Jiajin Liu, Chenxi Xu, Dongzhe Fan +2Evidence SelectionAgentic Search