Feasibility Preservation under Monotone Retrieval Truncation

• URL: http://arxiv.org/abs/2601.15241v1
• Date: Wed, 21 Jan 2026 18:25:16 GMT
• Title: Feasibility Preservation under Monotone Retrieval Truncation
• Abstract summary: We study retrieval from a structural perspective, modeling query answering as a feasibility problem under truncation.<n>We show that monotone truncation suffices to guarantee finite witnessability for individual queries.<n>We further exhibit sharp counterexamples demonstrating failure under non-monotone truncation, non-finitely-generated query classes, and purely slotwise coverage.
• Score: 0.12183405753834557
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Autoformalizing Argumentative Material Inferences [26.35292656634472]
  We develop an autoformalization for argumentative material inference as guard completion.<n>GUARD yields significant improvements in verified-faithful.<n>We show that the symbolic soft critique and the explicit assumption layer account for most of these gains.
  arXiv  Detail & Related papers  (2026-09-15T11:05:26Z)
• Common-Witness Certificates and Sharp Feature Bounds for Counterfactual Image Auditing [0.0]
  An image editor may satisfy every plausibility constraint separately even when no single latent explanation fits the complete output.<n>We formalize this local-to-global failure using a common witness grade and witness nerve.
  arXiv  Detail & Related papers  (2026-09-03T15:09:52Z)
• ProofPulse: Interactive Proof Coverage Analysis for Dafny [47.23158426199152]
  Deductive verification ensures that an implementation satisfies its specification, but successful verification does not guarantee the quality of the specification.<n>We present proofpulse, a tool for Dafny that diagnoses specification quality using a three-valued proof coverage model.
  arXiv  Detail & Related papers  (2026-08-31T14:00:31Z)
• CaIRec: Calibrated Modality Imputation for Incomplete Multimodal Recommendation [49.24608818070328]
  Real-world recommender systems often face incomplete modality observations, where items lack images, text, or other content features.<n>Existing modality imputation methods estimate missing representations from available item content, but two challenges remain.<n>First, they optimize the recovered representation itself without explicitly considering its relations with other modalities of the same item.<n>Second, even structurally coherent recovered information may remain ineffective for personalized ranking.<n>We propose Calibrated Imputation for Incomplete Multimodal Recommendation (CaIRec) to address these challenges.
  arXiv  Detail & Related papers  (2026-07-29T10:10:20Z)
• Revisiting Uncertainty: On Evidential Learning for Partially Relevant Video Retrieval [70.47320120707029]
  Partially relevant video retrieval aims to retrieve untrimmed videos using text queries that describe only partial content.<n>In this setting, vague queries often induce semantic ambiguity across videos, a challenge that is further exacerbated by the sparse temporal supervision within videos.<n>We propose Holmes, a hierarchical evidential learning framework that aggregates multi-granular cross-modal evidence to quantify and model uncertainty explicitly.
  arXiv  Detail & Related papers  (2026-05-07T12:06:13Z)
• Cycle-Consistent Search: Question Reconstructability as a Proxy Reward for Search Agent Training [80.20022221643414]
  Cycle-Consistent Search is a gold-supervision-free framework for training search agents.<n>We show that CCS achieves performance comparable to supervised baselines.<n>These results suggest that CCS provides a scalable training paradigm for training search agents in settings where gold supervision is unavailable.
  arXiv  Detail & Related papers  (2026-04-14T17:00:18Z)
• When Verification Fails: How Compositionally Infeasible Claims Escape Rejection [30.404615085122046]
  We show that existing verification benchmarks cannot distinguish between rigorous claim verification and simple salient-constraint reliance.<n>We construct compositionally infeasible claims where the salient constraint is supported but a non-salient constraint is contradicted.<n>We show that different models occupy distinct positions on a shared ROC curve, indicating that the gap between model families reflects differences in verification threshold rather than underlying reasoning ability.
  arXiv  Detail & Related papers  (2026-04-13T04:48:20Z)
• Machine Learning for Stress Testing: Uncertainty Decomposition in Causal Panel Prediction [2.289837306672451]
  Regulatory stress testing requires projecting credit losses under hypothetical macroeconomic scenarios.<n>We propose a framework for policy-path counterfactual inference in panels.<n>We validate all results through simulation and semi-synthetic experiments with real unemployment data.
  arXiv  Detail & Related papers  (2026-03-08T03:22:38Z)
• Eidoku: A Neuro-Symbolic Verification Gate for LLM Reasoning via Structural Constraint Satisfaction [0.0]
  Large Language Models (LLMs) frequently produce hallucinated statements that are assigned high likelihood by the model itself.<n>This suggests that hallucination is often not a low-confidence phenomenon, but a failure of structural consistency.<n>We reformulate the verification of LLM reasoning as a Constraint Satisfaction Problem (CSP) operating independently of the generation likelihood.
  arXiv  Detail & Related papers  (2025-12-19T05:29:43Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• Towards Effective Extraction and Evaluation of Factual Claims [1.8262547855491458]
  A common strategy for fact-checking long-form content generated by Large Language Models (LLMs) is extracting simple claims that can be verified independently.<n>We propose a framework for evaluating claim extraction in the context of fact-checking along with automated, scalable, and replicable methods for applying this framework.<n>We also introduce Claimify, an LLM-based claim extraction method, and demonstrate that it outperforms existing methods under our evaluation framework.
  arXiv  Detail & Related papers  (2025-02-15T16:58:05Z)
• SUMI-IFL: An Information-Theoretic Framework for Image Forgery Localization with Sufficiency and Minimality Constraints [66.85363924364628]
  Image forgery localization (IFL) is a crucial technique for preventing tampered image misuse and protecting social safety.<n>We introduce a novel information-theoretic IFL framework named SUMI-IFL that imposes sufficiency-view and minimality-view constraints on forgery feature representation.
  arXiv  Detail & Related papers  (2024-12-13T09:08:02Z)
• Mitigating LLM Hallucinations via Conformal Abstention [70.83870602967625]
  We develop a principled procedure for determining when a large language model should abstain from responding in a general domain. We leverage conformal prediction techniques to develop an abstention procedure that benefits from rigorous theoretical guarantees on the hallucination rate (error rate) Experimentally, our resulting conformal abstention method reliably bounds the hallucination rate on various closed-book, open-domain generative question answering datasets.
  arXiv  Detail & Related papers  (2024-04-04T11:32:03Z)
• A Unified Framework for Pattern Recovery in Penalized and Thresholded Estimation and its Geometry [1.9949261242626628]
  We consider the framework of penalized estimation where the penalty term is given by a real-valued polyhedral gauge.<n>We define a novel and general notion of patterns based on subdifferentials and formalize an approach to measure pattern complexity.
  arXiv  Detail & Related papers  (2023-07-19T17:39:30Z)
• Interpretable Automatic Fine-grained Inconsistency Detection in Text Summarization [56.94741578760294]
  We propose the task of fine-grained inconsistency detection, the goal of which is to predict the fine-grained types of factual errors in a summary. Motivated by how humans inspect factual inconsistency in summaries, we propose an interpretable fine-grained inconsistency detection model, FineGrainFact.
  arXiv  Detail & Related papers  (2023-05-23T22:11:47Z)
• GERE: Generative Evidence Retrieval for Fact Verification [57.78768817972026]
  We propose GERE, the first system that retrieves evidences in a generative fashion. The experimental results on the FEVER dataset show that GERE achieves significant improvements over the state-of-the-art baselines.
  arXiv  Detail & Related papers  (2022-04-12T03:49:35Z)
• Taming Adversarial Robustness via Abstaining [7.1975923901054575]
  We consider a binary classification problem where the observations can be perturbed by an adversary. We include an abstaining option, where the classifier abstains from taking a decision when it has low confidence about the prediction. We show that there exist a tradeoff between the two metrics regardless of what method is used to choose the abstaining region.
  arXiv  Detail & Related papers  (2021-04-06T07:36:48Z)
• Exploiting Sample Uncertainty for Domain Adaptive Person Re-Identification [137.9939571408506]
  We estimate and exploit the credibility of the assigned pseudo-label of each sample to alleviate the influence of noisy labels. Our uncertainty-guided optimization brings significant improvement and achieves the state-of-the-art performance on benchmark datasets.
  arXiv  Detail & Related papers  (2020-12-16T04:09:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.