CS Paper Radar

Sparse Identification for Automatic Large-Scale Screening: A Constraint-Aware Framework with Ultra Fast Decoding Algorithm

Jianing Li, Li Chai, Yingcheng Lai

cs.LG stat.MLeess.SP ·submitted 2026-09-18 04:58 UTC · v1

Abstract

In the early stages of a pandemic, identification of a small number of infected individuals through large-scale screening is critical for pandemic control, yet remains challenging under limited reagents and testing capacity. Existing group testing methods suffer from either high computational complexity or low identification accuracy. Even worse, no available methods provide theoretically rigorous analysis for sparse identification with hard constraints caused by the sample usage constraint and the dilution effect existing ubiquitously in practical applications. In this article, we propose the Logic Screening method (LoSc), an ultra fast, accurate, and theoretically grounded framework for large-scale screening. LoSc introduces a novel decoding algorithm with a very simple selection strategy, achieving identification of all positives with only O(klogn) pooled tests. The decoding relies only on logical operations, enabling direct hardware implementation and yielding ultra fast computational implementation. Moreover, LoSc explicitly incorporates dilution and sample usage constraints into pooling designs, and establishes theoretical guarantees to guide optimal pooling configurations. Extensive simulations confirm the superior effectiveness, efficiency, and scalability. We believe LoSc offers a fast and reliable solution for automatic large-scale screening.

Comment
This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

Closest papers

Nearest neighbours by meaning across the whole index.

Robust Recovery of Sparse Support in Constrained Group Testing

eess.SP ·2026-09-17 ·Jianing Li, Li Chai, Xinyao Rao, Hailin Zhang
similarity 0.71
Abstract · This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may…

In the early stage of a pandemic, rapidly identifying a small number of infected individuals through large-scale screening is critical for pandemic control. Group testing has been widely used to improve testing efficiency and numerous studies have investigated the problem under noisy measurements, typically modeled as bit-flipping of test outcomes. However, these methods do not consider the constraints imposed by dilution, pool size, and the limit of detection (LOD), which can lead to false negatives when the viral load in a pool falls below the LOD. In addition, liquid dispensing errors, common in laboratory settings, affects diluted viral loads in a nonlinear manner. In this work, we introduce a novel measurement model that characterizes the process of sample pooling and dilution, incorporating LOD-induced binary quantization as well as liquid dispensing errors. For the case with known sparsity level, we propose a low-complexity decoding algorithm and provide theoretical guarantees for exact support recovery under both noiseless and noisy settings. For the case with unknown sparsity level, we develop a blind support recovery algorithm, along with a heuristic variant to enhance robustness, which can achieve exact support recovery with only O(klogn) measurements. Extensive simulations show that the proposed algorithms outperform existing combinatorial group testing algorithms, validating the effectiveness, efficiency and robustness in large-scale screening.

0.54

Graph-Aware Group Testing with Locally Clustered Infections

eess.SP ·2026-09-17 ·Jianing Li, Li Chai, Hailin Zhang
theory similarity 0.57
Abstract · This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may…

Group testing has been widely used to identify infected individuals with a limited number of tests, typically under the assumption of independent infections. Recent studies have exploited correlations among individuals, but often require additional information beyond the contact graph, such as community structures, interaction strengths, or detailed infection dynamics. Such information may be unavailable, incomplete or unreliable in practice. In this work, we assume that only the contact graph is known and develop a graph-aware group testing framework that exploits localized infection clustering in pooling design, fundamental limits of recovery, and decoding. Specifically, we propose an optimal transport-based pooling design that incorporates graph proximity and pooling constraints into a unified optimization framework. We prove that, under mild conditions, the proposed design eliminates uninfected individuals with higher probability than the Bernoulli pooling design, reducing the feasible search space for decoding. Then, we characterize the family of possible infected sets induced by localized infection clustering and derive necessary conditions on the number of tests required for exact recovery, revealing a lower testing requirement than that under the combinatorial prior. For decoding, we model the infection states of the population as a piecewise-constant graph signal and propose a graph total variation regularized decoder. We establish sufficient conditions for exact recovery under the Bernoulli pooling design in both noiseless and noisy settings, and show that O(Klog(n/K)) tests are sufficient under mild conditions in the noiseless case. Extensive simulations on synthetic and real-world networks demonstrate the effectiveness of the proposed framework and the benefit of exploiting graph-induced correlations in group testing.

0.30

TopU-LBVS: A Realistic Multi Target Benchmark for Ligand Based Virtual Screening

cs.LG cs.AI ·2026-09-24 ·Surbhi Kumar, Yuhe Zhou, Varun Shiralkar, Niu Huang, Baris Coskunuzer
benchmarkcode/data similarity 0.52
Abstract · 75 pages

Ligand-based virtual screening (LBVS) is a practical first-pass tool in early-stage drug discovery, but existing benchmarks can overestimate performance through random negatives, easy decoys, limited target coverage, and non-standardized evaluation protocols. We introduce TopU-LBVS, a multi-target benchmark for LBVS under hard-negative screening conditions. Starting from curated ChEMBL~35 bioactivity data, TopU-LBVS covers 93 protein targets across 7 protein classes and constructs target-specific screening libraries with property-matched, structurally similar decoys at a fixed 1:40 active-to-decoy ratio. Libraries contain roughly 400 to 10,000 compounds and are designed to reduce simple physicochemical and nearest-neighbor fingerprint shortcuts. TopU-LBVS provides three fixed protocols. TopU-LBVS-full evaluates ChEMBL$^\ast \rightarrow$ TopU generalization across all 93 targets. TopU-LBVS-low evaluates low-data TopU $\rightarrow$ TopU learning within the hard-negative distribution. TopU-LBVS-mini provides a compact seven-target protocol with a paired random-decoy control that changes only the test decoys, enabling low-cost development and direct measurement of the gap between random ChEMBL$^\ast$ and TopU decoys. Across ten reference baselines spanning fingerprint methods, molecular GNNs, fingerprint hybrids, and modern molecular models, performance under random-decoy evaluation degrades sharply under hard-negative screening. We release data, fixed splits, evaluation code, and baseline implementations for reproducible comparison of future LBVS and molecular representation learning methods. Code and data are available at https://github.com/topu-benchmark/topu-lbvs and https://huggingface.co/datasets/topu-benchmark/topu-lbvs.

0.38

GateWatch: Low-Overhead LLM Monitoring with Boolean Circuits

cs.AI cs.LG ·2026-11-18 ·Firas Spanioli, Yaniv David
similarity 0.51
Abstract · 23 pages

As large language models (LLMs) and LLM-based agents are increasingly deployed, monitoring their behavior becomes important for detecting unsafe or unintended actions. Activation probes offer an efficient approach, but existing methods face trade-offs between accuracy, interpretability, and computational overhead. Probes on raw activations lack interpretable inputs, whereas sparse autoencoder (SAE) probes use interpretable features but often rely on additive classifiers and large SAE encoders, limiting interpretability and increasing memory overhead. We introduce GateWatch, a compact, interpretable classifier that expresses its entire decision rule as an explicit Boolean logic over a small number of binarized SAE features. We explore three approaches to constructing these circuits under a specified gate budget. For efficient deployment, GateWatchServe computes only selected SAE features, enables streaming of their binary values across layers during inference, and evaluates multiple GateWatch classifiers in parallel using compact lookup tables. Across 24 tasks on Gemma-2-9B, GateWatch achieves 80.49% mean test accuracy using only 3.8 SAE features and 3.5 logic gates per probe on average, just 1.17 percentage points below full 16K-feature SAE probes, while matching or outperforming them on 10 tasks and reducing probe memory by 99.98%. Inside vLLM, 1,000 concurrent multi-layer, multi-token GateWatch classifiers retain 97-98% of baseline throughput and 99.8% of KV-cache capacity.

0.38

Robustness Verification against Patch Attacks via Group-Lasso Semidefinite Relaxation

cs.CV ·2026-11-03 ·Yukina Nakagawa, Takami Sato, Ken Kobayashi, Kazuhide Nakata
similarity 0.50
Abstract

Robustness verification is essential for ensuring the safety and security of neural networks, but current methods focus heavily on norm-ball attacks, which do not adequately model typical real-world threats that present physical perturbations, known as patch attacks. A naive approach requires computationally prohibitive enumeration of all possible patch positions. To address the challenge, we propose a novel neural network verification method specialized to the patch-attack threat. Instead of enumerating patch locations, we first model the patch attack with group-wise sparsity and formulate its verification methods as a mixed-integer semidefinite program (MISDP) by applying SDP relaxation to the neural network. We then propose three relaxations, including Group-Lasso relaxation, that remove the integer variables while preserving the sparse, group-wise structure of the original attack, enabling substantially efficient verification. Our empirical analysis demonstrates that the proposed relaxations require less than 3% of the computation time of the original MISDP, while the Group-Lasso relaxation incurs only a 0.34\% average increase in the objective value over the original formulation. Furthermore, Group-Lasso achieves a verified rate of 91%, compared with under 70% for prior methods.

0.25

Efficient and Generalizable Archetypal Analysis for Discrete Data

cs.LG stat.ML ·2026-10-08 ·A. Emilie J. Wedenborg, Jesper Løve Hinrich, Morten Mørup
similarity 0.50
Abstract

Archetypal Analysis (AA) represents observations as convex combinations of extremal data-driven profiles, yielding interpretable low-dimensional descriptions of complex datasets. Classical AA relies on a least-squares objective, which is poorly suited to discrete observations such as binary, count, and categorical data. We introduce an efficient likelihood-based framework for AA supporting Bernoulli, Poisson, and multinomial observation models. Our optimization scheme employs local quadratic approximations of the negative log-likelihood, enabling constrained updates through sequential minimal optimization (SMO) and an active-set method. Scalability is improved by bounding the active set while preserving simplex feasibility. We further introduce a cross-validated predictive likelihood criterion for selecting the number of archetypes, providing a principled alternative to reconstruction-error heuristics and stability-based diagnostics. Synthetic experiments demonstrate computational efficiency and accurate recovery of model complexity. Applications to single-cell RNA sequencing, microbiome composition, and somatic mutation data show that the learned archetypes capture interpretable domain-specific structures while achieving competitive likelihood fits and stable solutions. Overall, the proposed framework enables efficient likelihood-based archetypal analysis of discrete data, complemented by predictive likelihood-based model selection.

0.25

SAT Sampling at Scale via GPU-based Boolean Constraint Propagation

cs.LO cs.DC ·2026-10-20 ·Alexander Nadel, Yogev Shalmon, Ofer Strichman
benchmark similarity 0.49
Abstract · 22 pages, 3 figures, 3 tables

Constrained-random verification tests hardware designs by sampling solutions of Boolean formulas. Existing samplers largely follow one of two approaches: CPU-based SAT samplers (e.g., CMSGen), which remain effective even at rare targets but offer limited throughput, and GPU-based gradient samplers, which achieve high throughput at high-probability targets but collapse at rare ones. We introduce Gpap-S, the first GPU sampler built on Boolean constraint propagation (BCP). At its core is Gpap, a new GPU engine for BCP that efficiently propagates many independent partial assignments concurrently on a shared Boolean formula. This capability allows Gpap-S to combine the rare-target robustness of SAT-based sampling with the throughput of GPU parallelism by exploring thousands of decide-and-propagate trajectories simultaneously. On the benchmark families used to evaluate prior GPU gradient samplers, Gpap-S is 2.2-18.7x faster at the high-probability targets considered in those evaluations. At rare targets, where those samplers often fail to generate any samples, Gpap-S achieves a geometric-mean speedup of roughly two orders of magnitude. Across all benchmarks, Gpap-S is also 83.4-1,571x faster than the CPU-based CMSGen. This throughput does not come at the expense of sample quality: under Barbarik, the statistical tester used to evaluate CMSGen, Gpap-S is accepted on every instance we test, as is CMSGen. We release Gpap as a reusable GPU library for high-throughput BCP.

0.30

Trajectory-Based Bayesian Discovery of a Host-Pathogen Model from Quasi-Steady-State Observations

cs.LG stat.ML ·2026-11-13 ·Reymart Salcedo Lagunero, Andreas Langer, Cordula Reisch
similarity 0.49
Abstract

System identification of nonlinear dynamical systems becomes challenging when the measured data come from a nearly settled state. We study this situation in the case of a bistable host-pathogen interaction model with a cubic term, whose seven true mechanisms are hidden among twenty candidate terms. The data are from one noise-free trajectory on a quasi-steady-state observed window and the initial state. In this situation, classical sparse identification approaches fail to identify the correct mechanisms as the candidate library becomes ill-conditioned along the quasi-steady-state trajectory. To address this, we propose an alternative approach in which sparse Bayesian learning and $\ell_{0}$ iterative hard thresholding with pursuit provide a good start, and a two-swap climb on the Bayesian evidence of the candidate ODE solutions recovers the true model. Our results show successful model recovery, i.e., correct identification of its support and accurate estimation of its coefficients, as validated by exhaustive scoring.

0.28