Online Evidence-Containment Prediction over Text Spans under Distinct Queries
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, , 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 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
| Data | Rel. | Err. | ||||
|---|---|---|---|---|---|---|
| NQ | 6336.5 | 90.5 | 58.37 | 93.43% | 26.5M | 0 |
| ERASER | 4410 | 145 | 30.10 | 100% | 127.6M | 0 |
| ERASER | Macro | Raw | PRC | ROC | BAcc |
|---|---|---|---|---|---|
| STATIC | .2896 | .0704 | .4447 | .8495 | .5928 |
| SEMANT. | .3038 | .0764 | .3384 | .8421 | .5439 |
| BASE | .2783 | .0691 | .4578 | .8700 | .5965 |
| BASE-H | .2732 | .0670 | .5004 | .8757 | .6017 |
| Closure+B. | .1283 | .0294 | .8843 | .9775 | .8594 |
| RAND-CONT | .4303 | .3576 | .1455 | .6302 | .5674 |
| Dataset | P-GREEDY | ESR | P-GREEDY ESR | Calls |
|---|---|---|---|---|
| SciFact | .526 | .451 | .075 [.059, .092] | 6 4 |
| ERASER | .470 | .354 | .116 [.098, .136] | 16 11 |
| DPR@8 | Nonroot+ | Min. tgt+ | Med. | p90 |
|---|---|---|---|---|
| NQ DEV | 70.69% | 66.01% | 40 | 56 |
| max 332; comparable pairs / levels: 99.97% of covered | ||||
| Predictor | Unres. | A2 | 95% CI | |
| A0 semantic | .0762 | .0176 | [.0168,.0184] | |
| A1 +history | .0647 | .0062 | [.0057,.0067] | |
| A2 +contain. | .0586 | – | – | |
Appendix figures & tables25 assets
Supplementary material from the paper’s appendix.
Appendix
| Symbol | Meaning |
|---|---|
| Evidence verification (Section 3.1 ) | |
| , | Query (question or claim) and document. |
| Raw document length in tokens; also the side of the full grid . | |
| Candidate span with left endpoint and right endpoint , . | |
| All spans of a document of tokens. | |
| Finite candidate family, , proposed independently of the gold evidence. | |
| Quantity | Natural Questions | ERASER Ev. Inference | Role in the theory |
| Documents | 3,000 | 2,171 | |
| Evidence instances | – | 8,930 | |
| Median raw length | 6,336.5 | 4,410 | side of the span triangle |
| Median | 413 | 896 | horizon if all candidates are verified |
| Median | 90.5 | 145 | compressed side (Thm. 2 ) |
| Median compression | reduction of the ambient scale |
| System | Macro BBr. | Pooled BBr. | Raw Brier | AUPRC | AUROC | Bal. Acc. |
|---|---|---|---|---|---|---|
| STATIC-POSLEN | 0.289556 | 0.281161 | 0.070421 | 0.444671 | 0.849476 | 0.592813 |
| SEMANTIC | 0.303817 | 0.301019 | 0.076375 | 0.338441 | 0.842072 | 0.543903 |
| BASE | 0.278308 | 0.273260 | 0.069136 | 0.457781 | 0.869953 | 0.596526 |
| BASE-H | 0.273206 | 0.274229 | 0.066958 | 0.500378 | 0.875671 | 0.601722 |
| Closure+BASE | 0.128333 | 0.098892 | 0.029385 | 0.884289 | 0.977516 | 0.859424 |
| RAND-CONT | 0.430307 | 0.408977 | 0.357563 | 0.145537 | 0.630237 | 0.567365 |
| System | Doc.-macro Brier | vs. N2 [95% CI] |
|---|---|---|
| N2 | 0.01732 | – |
| N2+G1 | 0.00692 | 0.01040 [0.00897, 0.01190] |
| N2+G4 | 0.00614 | 0.01118 [0.00970, 0.01275] |
| FULL | 0.00629 | 0.01103 [0.00957, 0.01255] |
| History state | Gain | 95% CI |
|---|---|---|
| S0: none | ||
| S1: open | ||
| S2: pos. closure | ||
| S3: neg. closure | ||
| History none | ||
| Closure open |
| Schedule | BASE | Closure+BASE | COMBINED ∗ |
|---|---|---|---|
| Random | 0.278308 | 0.049931 | 0.037721 |
| seed 17 | 0.049876 | 0.038239 | |
| seed 42 | 0.049941 | 0.037751 | |
| seed 2027 | 0.049976 | 0.037173 | |
| Short long | 0.278308 | 0.018327 | 0.008265 |
| Long short | 0.278308 | 0.273783 | 0.073379 |
| Schedule | Determ. | BASE | Closure | COMB. ∗ |
|---|---|---|---|---|
| Random | 88.41% | 0.2783 | 0.0499 | 0.0377 |
| Short long | 11.23% | 0.2783 | 0.0183 | 0.0083 |
| Long short | 82.25% | 0.2783 | 0.2738 | 0.0734 |
| Semantic-first | 85.63% | 0.2783 | 0.1713 | 0.0625 |
| Setting | Gain | 95% CI |
|---|---|---|
| S0: no history | .0033 | [ .0042, .0025] |
| S1: open | .0090 | [.0069, .0113] |
| S2: positive closure | .7248 | [.6970, .7512] |
| S3: negative closure | .0020 | [.0015, .0027] |
| History none | .0159 | [.0142, .0177] |
| Closure open | .0760 | [.0686, .0836] |
| Model | Seed | Brier | Unres. | ROC | PRC |
|---|---|---|---|---|---|
| A0 | 17 | 0.027973 | 0.049730 | 0.9046 | 0.2177 |
| A0 | 42 | 0.027184 | 0.048738 | 0.9073 | 0.2358 |
| A0 | 2027 | 0.028030 | 0.049673 | 0.9021 | 0.1934 |
| A1 | 17 | 0.028276 | 0.051024 | 0.9018 | 0.1589 |
| A1 | 42 | 0.028971 | 0.051292 | 0.8856 | 0.1663 |
| A1 | 2027 | 0.026837 | 0.048453 | 0.9238 | 0.2376 |
| Learner | Bound | Median | p95 | Satisfied |
|---|---|---|---|---|
| EW (regret) | ||||
| HA-EW (regret) | ||||
| Version space (loss) |
| Component | Scope | Median | p95 |
|---|---|---|---|
| Batch isotonic | fam. | ms | ms |
| ESR decision | dec. | ms | ms |
| Policy | Len. | Orc. | Act. | F1 | |
|---|---|---|---|---|---|
| P-GREEDY | 1 | 1.0000 | 0.0048 | 1.0000 | 0.5373 |
| P-GREEDY | 2 | 0.8155 | 0.0239 | 0.6550 | 0.5500 |
| P-GREEDY | 4 | 0.5653 | 0.1770 | 0.2768 | 0.5500 |
| P-GREEDY | 8 | 0.3199 | 0.8038 | 0.0301 | 0.5437 |
| P-GREEDY | 16 | 0.2860 | 0.9856 | 0.0054 | 0.5451 |
| P-GREEDY | 32 | 0.2856 | 0.9904 | 0.0030 | 0.5451 |
| Gen. | Cov. | A1 A2 unres. | LS ESR AUC | ESR GG S@8 | ||
|---|---|---|---|---|---|---|
| DPR | 4 | .627 | 22 | .0093 [.0086, .0100] | .0038 [ .0068, .0007] | .0071 [ .0116, .0025] |
| DPR | 8 | .707 | 40 | .0062 [.0057, .0067] | .0087 [.0055, .0121] | .0109 [.0031, .0189] |
| DPR | 16 | .755 | 74 | .0043 [.0039, .0046] | .0212 [.0176, .0250] | .0042 [ .0151, .0067] |
| BM25 | 4 | .531 | 23 | .0070 [.0066, .0074] | .0014 [ .0050, .0020] | .0002 [ .0038, .0035] |
| BM25 | 8 | .637 | 44 | .0040 [.0037, .0042] | .0154 [.0116, .0193] | .0284 [.0202, .0362] |
| BM25 | 16 | .721 | 80 | .0027 [.0025, .0028] | .0315 [.0270, .0361] | .0440 [.0329, .0551] |
| DPR | BM25 | |||||||
|---|---|---|---|---|---|---|---|---|
| Policy | AUC | S@8 | S@16 | Calls | AUC | S@8 | S@16 | Calls |
| P-GREEDY | .237 | .644 | .659 | 2 | .236 | .592 | .604 | 2 |
| GENERATOR-GREEDY | .275 | .631 | .668 | 3 | .320 | .560 | .608 | 3 |
| GEOM-BALANCE | .371 | .598 | .636 | 4 | .387 | .550 | .588 | 5 |
| LEARNED-SCHED | .256 | .628 | .651 | 2 | .264 | .573 | .599 | 2 |
| ESR | .247 | .642 | .656 | 2 | .248 | .588 | .603 | 2 |
| Method | Fidelity class | Source / revision | Frozen | Adapted | Score source | Tuning data | Isotonic / contain. |
|---|---|---|---|---|---|---|---|
| REARANK | paper-faithful adapter | le723z/Rearank-7B , rev. 530a7e15 | official checkpoint; one listwise ranking per DPR query | ranking replayed over active candidates | LLM listwise rank | none | no / shared transition only |
| NEST-Adapt | hierarchy adapter | ACL 2026 Industry; frozen adapter | survival scores; top- order | root/paragraph/sentence hierarchy as nest levels | survival/MRR | none | no / shared transition only |
| RCD-Adapt | cost adapter | commit 73e22b3c | official objective, coefficients, TF-IDF features | token-length verification cost | routing objective | none | no / shared transition only |
| Cost-MMR-Adapt | cost adapter | commit dc68c0dd | official MMR objective; Qwen3-Emb.-0.6B embeddings | source-access cost token cost | MMR score | TRAIN token scale | no / shared transition only |
| ESR | OECP | frozen policy code | A2 probabilities | – | calibrated A2 | NQ TRAIN (A2) | no / ESR uses order |
| Verifier-call budget | Verification-token budget | ||||||
| Policy | AUC | S@8 | Hit@32 | Med. calls | AUC | S@512 | Med. tokens |
| P-GREEDY | .2365 | .6438 | .9118 | 2 | .2925 | .6037 | 144 |
| GENERATOR-GREEDY | .2752 | .6310 | .9259 | 3 | .3080 | .5921 | 151 |
| GEOM-BALANCE | .3710 | .5985 | .8778 | 4 | .5012 | .4186 | 386 |
| LEARNED-SCHED | .2560 | .6283 | .8968 | 2 | .3428 | .5363 | 160 |
| REARANK | .3239 | .6265 | .9264 | 3 | .2872 | .6179 | 149 |
| Model | Params | Use |
|---|---|---|
| DeBERTa-v3-base | 184.03M | fine-tuned |
| RoBERTa-base | 124.85M | fine-tuned |
| BERT + MLP | 109.68M | head only |
| SciBERT | 109.92M | App. D.6 |
| DPR encoders (2) | 217.78M | frozen |
| REARANK-7B | 7.616B | frozen |
Evidence Selection
Evidence selection chooses the documents, passages, claims, or observations that best support an answer or decision.
See all 66 papers