Online prediction reduces verification calls for nested text evidence
Online Evidence-Containment Prediction over Text Spans under Distinct Queries
Artificial Intelligence
Summary
Finding relevant evidence in large texts often requires checking many possible parts, one after another, which takes time. This paper studies how to predict if one piece of text contains another before fully verifying it, based on special ordering rules. The authors created a method that makes these predictions efficiently and tested it on real-world question-answering data, showing it can cut down the amount of checking needed. This helps systems find the right evidence faster and more accurately.
What this means in practice
- •For nlp engineers: Reduce verification calls in evidence retrieval systems by predicting text span containment online to localize evidence more efficiently.
- •For document search teams: Improve question-answering pipelines by cutting search space using online containment predictions, lowering the number of expensive verification steps.
Authors
Xiang Liu, Haochen Ding
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.