Verifying Classification with Limited Disclosure

• URL: http://arxiv.org/abs/2502.16352v1
• Date: Sat, 22 Feb 2025 20:56:03 GMT
• Title: Verifying Classification with Limited Disclosure
• Abstract summary: We consider the multi-party classification problem introduced by Dong, Hartline, and Vijayaraghavan (2022) motivated by electronic discovery.<n>Our goal is to design a protocol that guarantees the requesting party receives nearly all responsive documents while minimizing the disclosure of nonresponsive documents.
• Score: 4.88160756739524
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We consider the multi-party classification problem introduced by Dong, Hartline, and Vijayaraghavan (2022) motivated by electronic discovery. In this problem, our goal is to design a protocol that guarantees the requesting party receives nearly all responsive documents while minimizing the disclosure of nonresponsive documents. We develop verification protocols that certify the correctness of a classifier by disclosing a few nonresponsive documents. We introduce a combinatorial notion called the Leave-One-Out dimension of a family of classifiers and show that the number of nonresponsive documents disclosed by our protocol is at most this dimension in the realizable setting, where a perfect classifier exists in this family. For linear classifiers with a margin, we characterize the trade-off between the margin and the number of nonresponsive documents that must be disclosed for verification. Specifically, we establish a trichotomy in this requirement: for $d$ dimensional instances, when the margin exceeds $1/3$, verification can be achieved by revealing only $O(1)$ nonresponsive documents; when the margin is exactly $1/3$, in the worst case, at least $\Omega(d)$ nonresponsive documents must be disclosed; when the margin is smaller than $1/3$, verification requires $\Omega(e^d)$ nonresponsive documents. We believe this result is of independent interest with applications to coding theory and combinatorial geometry. We further extend our protocols to the nonrealizable setting defining an analogous combinatorial quantity robust Leave-One-Out dimension, and to scenarios where the protocol is tolerant to misclassification errors by Alice.

Related papers

• Observation Design for Certified Control Authority: Projection--Estimability Separation and Active-Face Equivalence [2.7954473524479275]
  A gate executes only actions it can certify, and certifies only what its observations support.<n>This paper asks how observations should be designed to maximize the set of actions that can be safely admitted.
  arXiv  Detail & Related papers  (2026-09-05T07:57:04Z)
• Codebook Agent: Amortized Topology Design for LLM Multi-Agent Systems [67.04448659688579]
  We develop a query-independent 16-entry codebook that ranks the top decoded candidates in a single batched forward pass.<n>With no iterative search and no message passing at test time, Codebook Agent is the most accurate method on all six benchmarks.
  arXiv  Detail & Related papers  (2026-09-02T08:10:22Z)
• Secret MCP: Evidence-Bounded and Context-Isolated Design Specification Generation from Web Screenshots [0.0]
  Secret MCP produces one auditable design specification per public web reference.<n>Document structure, interaction logic, responsive rules, and provenance needed to distinguish observation from guesswork.
  arXiv  Detail & Related papers  (2026-08-24T14:32:52Z)
• From Positionwise Confidence to Prefix Scheduling: Verifier Skipping in Speculative Decoding [41.41611499810411]
  Speculative diffusion decoding (SDD) generates every position in a draft block in parallel with a discrete diffusion model.<n>This paper recognizes that this creates a new control handle: whether to invoke the verifier at all.
  arXiv  Detail & Related papers  (2026-08-14T18:00:08Z)
• A Reproducibility Protocol for Cross-Implementation Evaluation of Post-Quantum ACVP Test Vectors [0.0]
  This study defines a product-neutral protocol for three public implementations of NIST ML-KEM.<n> Protocol v2 freezes provider-specific capabilities, applies one validation-error symmetrically, preserves every selected case, and separates bytes, validation verdicts, unsupported operations, and adapter errors.
  arXiv  Detail & Related papers  (2026-08-13T21:29:59Z)
• Correction and Corruption: A Two-Rate View of Error Flow in LLM Protocols [51.56484100374058]
  We propose a paired-outcome measurement interface for auditing a single protocol step on exact-match tasks.<n>For each instance, the interface records a baseline correctness bit and a post-step correctness bit.<n>These rates predict accuracy changes and define a reusable empirical interface testable across seeds, mixtures, and pipelines.
  arXiv  Detail & Related papers  (2026-04-20T13:25:40Z)
• Audit the Whisper: Detecting Steganographic Collusion in Multi-Agent LLMs [0.0]
  Audit the Whisper is a conference-grade research artifact that spans theory, benchmark design, detection, and validation.<n>Our contributions are: (i) a channel-capacity analysis showing how interventions such as paraphrase, rate limiting, and role permutation impose quantifiable capacity penalties-operationalised via paired-run Kullback-Leibler diagnostics.<n>We release anonymized regeneration scripts, anonymized manifests, and documentation so external auditors can reproduce every figure, satisfy double-blind requirements, and extend the framework with minimal effort.
  arXiv  Detail & Related papers  (2025-10-05T17:51:52Z)
• The Medium Is Not the Message: Deconfounding Document Embeddings via Linear Concept Erasure [98.71456610527598]
  Embedding-based similarity metrics can be influenced by spurious attributes like the text's source or language.<n>This paper shows that a debiasing algorithm that removes information about observed confounders from the encoder representations substantially reduces these biases at a minimal computational cost.
  arXiv  Detail & Related papers  (2025-07-01T23:17:12Z)
• Document Attribution: Examining Citation Relationships using Large Language Models [62.46146670035751]
  We propose a zero-shot approach that frames attribution as a straightforward textual entailment task.<n>We also explore the role of the attention mechanism in enhancing the attribution process.
  arXiv  Detail & Related papers  (2025-05-09T04:40:11Z)
• Collapse of Dense Retrievers: Short, Early, and Literal Biases Outranking Factual Evidence [56.09494651178128]
  Retrieval models are commonly used in Information Retrieval (IR) applications, such as Retrieval-Augmented Generation (RAG) We show that retrievers often rely on superficial patterns like over-prioritizing document beginnings, shorter documents, repeated entities, and literal matches. We show that these biases have direct consequences for downstream applications like RAG, where retrieval-preferred documents can mislead LLMs.
  arXiv  Detail & Related papers  (2025-03-06T23:23:13Z)
• Riddle Me This! Stealthy Membership Inference for Retrieval-Augmented Generation [18.098228823748617]
  We present Interrogation Attack (IA), a membership inference technique targeting documents in the RAG datastore.<n>We demonstrate successful inference with just 30 queries while remaining stealthy.<n>We observe a 2x improvement in TPR@1%FPR over prior inference attacks across diverse RAG configurations.
  arXiv  Detail & Related papers  (2025-02-01T04:01:18Z)
• Efficient Document Ranking with Learnable Late Interactions [73.41976017860006]
  Cross-Encoder (CE) and Dual-Encoder (DE) models are two fundamental approaches for query-document relevance in information retrieval. To predict relevance, CE models use joint query-document embeddings, while DE models maintain factorized query and document embeddings. Recently, late-interaction models have been proposed to realize more favorable latency-quality tradeoffs, by using a DE structure followed by a lightweight scorer.
  arXiv  Detail & Related papers  (2024-06-25T22:50:48Z)
• Trading off Consistency and Dimensionality of Convex Surrogates for the Mode [6.096888891865663]
  In multiclass classification over $n$ outcomes, the outcomes must be embedded into the reals with dimension at least $n-1$. We investigate ways to trade off surrogate loss dimension, the number of problem instances, and restricting the region of consistency in the simplex. We show that full-dimensional subsets of the simplex exist around each point mass distribution for which consistency holds, but also, with less than $n-1$ dimensions, there exist distributions for which a phenomenon called hallucination occurs.
  arXiv  Detail & Related papers  (2024-02-16T16:42:09Z)
• Error-Tolerant E-Discovery Protocols [18.694850127330973]
  We consider the multi-party classification problem introduced by Dong, Hartline, and Vijayaraghavan (2022) Based on a request for production from the requesting party, the responding party is required to provide documents that are responsive to the request except for those that are legally privileged. Our goal is to find a protocol that verifies that the responding party sends almost all responsive documents while minimizing the disclosure of non-responsive documents.
  arXiv  Detail & Related papers  (2024-01-31T15:59:16Z)
• Generative Dense Retrieval: Memory Can Be a Burden [16.964086245755798]
  Generative Retrieval (GR) autoregressively decodes relevant document identifiers given a query. Dense Retrieval (DR) is introduced to conduct fine-grained intra-cluster matching from clusters to relevant documents. DR obtains an average of 3.0 R@100 improvement on NQ dataset under multiple settings.
  arXiv  Detail & Related papers  (2024-01-19T04:24:07Z)
• Factcheck-Bench: Fine-Grained Evaluation Benchmark for Automatic Fact-checkers [121.53749383203792]
  We present a holistic end-to-end solution for annotating the factuality of large language models (LLMs)-generated responses. We construct an open-domain document-level factuality benchmark in three-level granularity: claim, sentence and document. Preliminary experiments show that FacTool, FactScore and Perplexity are struggling to identify false claims.
  arXiv  Detail & Related papers  (2023-11-15T14:41:57Z)
• CoP: Factual Inconsistency Detection by Controlling the Preference [45.4045488637761]
  We propose an unsupervised framework named CoP by controlling the preference of the generation model with the help of prompt. With the properly designed prompt, our framework could evaluate specific preferences and serve as measurements for fine-grained categories of inconsistency. Experiments show that our framework achieves new SOTA results on three factual inconsistency detection tasks.
  arXiv  Detail & Related papers  (2022-12-03T13:05:24Z)
• Classification Protocols with Minimal Disclosure [12.308957254601243]
  We consider multi-party protocols for classification motivated by applications such as e-discovery in court proceedings. We identify a protocol that guarantees that the requesting party receives all responsive documents and the sending party discloses the minimal amount of non-responsive documents. This protocol can be embedded in a machine learning framework that enables automated labeling of points.
  arXiv  Detail & Related papers  (2022-09-06T17:57:52Z)
• 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)
• Online Selective Classification with Limited Feedback [82.68009460301585]
  We study selective classification in the online learning model, wherein a predictor may abstain from classifying an instance. Two salient aspects of the setting we consider are that the data may be non-realisable, due to which abstention may be a valid long-term action. We construct simple versioning-based schemes for any $mu in (0,1],$ that make most $Tmu$ mistakes while incurring smash$tildeO(T1-mu)$ excess abstention against adaptive adversaries.
  arXiv  Detail & Related papers  (2021-10-27T08:00:53Z)
• Active Learning from Crowd in Document Screening [76.9545252341746]
  We focus on building a set of machine learning classifiers that evaluate documents, and then screen them efficiently. We propose a multi-label active learning screening specific sampling technique -- objective-aware sampling. We demonstrate that objective-aware sampling significantly outperforms the state of the art active learning sampling strategies.
  arXiv  Detail & Related papers  (2020-11-11T16:17:28Z)
• Fast(er) Reconstruction of Shredded Text Documents via Self-Supervised Deep Asymmetric Metric Learning [62.34197797857823]
  A central problem in automatic reconstruction of shredded documents is the pairwise compatibility evaluation of the shreds. This work proposes a scalable deep learning approach for measuring pairwise compatibility in which the number of inferences scales linearly. Our method has accuracy comparable to the state-of-the-art with a speed-up of about 22 times for a test instance with 505 shreds.
  arXiv  Detail & Related papers  (2020-03-23T03:22:06Z)

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.