Instance Dependent Testing of Samplers using Interval Conditioning

• URL: http://arxiv.org/abs/2512.06458v1
• Date: Sat, 06 Dec 2025 14:45:56 GMT
• Title: Instance Dependent Testing of Samplers using Interval Conditioning
• Authors: Rishiraj Bhattacharyya, Sourav Chakraborty, Yash Pote, Uddalok Sarkar, Sayantan Sen,
• Abstract summary: In this work, we design the first tester of samplers with instance-dependent efficiency.<n>Our tests are developed via a novel distance estimation algorithm between an unknown and a known probability distribution.<n>Experiments establish up to 1000x speedup over state-of-the-art testers.
• Score: 10.939345026823842
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sampling algorithms play a pivotal role in probabilistic AI. However, verifying if a sampler program indeed samples from the claimed distribution is a notoriously hard problem. Provably correct testers like Barbarik, Teq, Flash, CubeProbe for testing of different kinds of samplers were proposed only in the last few years. All these testers focus on the worst-case efficiency, and do not support verification of samplers over infinite domains, a case occurring frequently in Astronomy, Finance, Network Security, etc. In this work, we design the first tester of samplers with instance-dependent efficiency, allowing us to test samplers over natural numbers. Our tests are developed via a novel distance estimation algorithm between an unknown and a known probability distribution using an interval conditioning framework. The core technical contribution is a new connection with probability mass estimation of a continuous distribution. The practical gains are also substantial: our experiments establish up to 1000x speedup over state-of-the-art testers.

Related papers

• Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions [4.200594864147057]
  We address the problem of testing the independence of $p$ over multiple random variables.<n>We design testers that incorporate auxiliary, but potentially untrustworthy, predictive information.<n>Our framework ensures that the tester remains robust, maintaining worst-case validity regardless of the prediction's quality.
  arXiv  Detail & Related papers  (2026-03-04T21:55:08Z)
• Large Language Models Are Bad Dice Players: LLMs Struggle to Generate Random Numbers from Statistical Distributions [50.1404916337174]
  We present the first large-scale, statistically powered audit of native probabilistic sampling in large language models (LLMs)<n>We show that batch generation achieves only modest statistical validity, with a 13% median pass rate, while independent requests collapse almost entirely.<n>We conclude that current LLMs lack a functional internal sampler, necessitating the use of external tools for applications requiring statistical guarantees.
  arXiv  Detail & Related papers  (2026-01-08T22:33:12Z)
• DOTA: Distributional Test-Time Adaptation of Vision-Language Models [69.41389326333771]
  Vision-language foundation models can be unreliable when significant distribution gaps exist between training and test data.<n>We propose DOTA (DistributiOnal Test-time Adaptation), a simple yet effective method addressing this limitation.<n>This distribution-centric approach enables the model to continually learn and adapt to the deployment environment.
  arXiv  Detail & Related papers  (2024-09-28T15:03:28Z)
• Active Sequential Two-Sample Testing [18.99517340397671]
  We consider the two-sample testing problem in a new scenario where sample measurements are inexpensive to access. We devise the first emphactiveNIST-sample testing framework that not only sequentially but also emphactively queries. In practice, we introduce an instantiation of our framework and evaluate it using several experiments.
  arXiv  Detail & Related papers  (2023-01-30T02:23:49Z)
• Sequential Kernelized Independence Testing [77.237958592189]
  We design sequential kernelized independence tests inspired by kernelized dependence measures.<n>We demonstrate the power of our approaches on both simulated and real data.
  arXiv  Detail & Related papers  (2022-12-14T18:08:42Z)
• TTAPS: Test-Time Adaption by Aligning Prototypes using Self-Supervision [70.05605071885914]
  We propose a novel modification of the self-supervised training algorithm SwAV that adds the ability to adapt to single test samples. We show the success of our method on the common benchmark dataset CIFAR10-C.
  arXiv  Detail & Related papers  (2022-05-18T05:43:06Z)
• MixNorm: Test-Time Adaptation Through Online Normalization Estimation [35.65295482033232]
  We present a simple and effective way to estimate the batch-norm statistics during test time, to fast adapt a source model to target test samples. Known as Test-Time Adaptation, most prior works studying this task follow two assumptions in their evaluation where (1) test samples come together as a large batch, and (2) all from a single test distribution.
  arXiv  Detail & Related papers  (2021-10-21T21:04:42Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  We study the problem of testing discrete distributions with a focus on the high probability regime. We provide the first algorithms for closeness and independence testing that are sample-optimal, within constant factors.
  arXiv  Detail & Related papers  (2020-09-14T16:09:17Z)
• Noisy Adaptive Group Testing using Bayesian Sequential Experimental Design [63.48989885374238]
  When the infection prevalence of a disease is low, Dorfman showed 80 years ago that testing groups of people can prove more efficient than testing people individually. Our goal in this paper is to propose new group testing algorithms that can operate in a noisy setting.
  arXiv  Detail & Related papers  (2020-04-26T23:41:33Z)

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.