Feasibility Preservation under Monotone Retrieval Truncation
This work addresses a structural limitation in retrieval-based systems that affects their reliability, independent of relevance scoring, making it incremental by formalizing conditions for feasibility preservation.
The paper tackles the problem of retrieval failures due to truncation, where relevant information may exist but is not accessible because compatible evidence does not co-occur in the truncated subset, and it shows that monotone truncation suffices to guarantee finite witnessability for individual queries, with sharp counterexamples demonstrating failure under non-monotone truncation.
Retrieval-based systems approximate access to a corpus by exposing only a truncated subset of available evidence. Even when relevant information exists in the corpus, truncation can prevent compatible evidence from co-occurring, leading to failures that are not captured by relevance-based evaluation. This paper studies retrieval from a structural perspective, modeling query answering as a feasibility problem under truncation. We formalize retrieval as a sequence of candidate evidence sets and characterize conditions under which feasibility in the limit implies feasibility at finite retrieval depth. We show that monotone truncation suffices to guarantee finite witnessability for individual queries. For classes of queries, we identify finite generation of witness certificates as the additional condition required to obtain a uniform retrieval bound, and we show that this condition is necessary. We further exhibit sharp counterexamples demonstrating failure under non-monotone truncation, non-finitely-generated query classes, and purely slotwise coverage. Together, these results isolate feasibility preservation as a correctness criterion for retrieval independent of relevance scoring or optimization, and clarify structural limitations inherent to truncation-based retrieval.