Group testing screens many samples with few assays by mixing samples into pools. The textbook model treats a pool as a logical OR: the pool reads positive if any member is positive. Real assays such as RT-qPCR (quantitative PCR, which detects viral RNA) do not behave this way. Pooling dilutes each sample, so one weak positive mixed into a large pool can fall below the assay's detection limit and read negative. The fastest known decoders work poorly under this physics, because they are built on splitting trees. A splitting tree tests a huge pool first and then recursively halves the positive pools, which lets it find $k$ positives among $N$ items while touching only about $k\log N$ tests rather than scanning all $N$ items. Its top-level pools are exactly the largest and most diluted ones. A single false negative there silently discards an entire subtree, and no later test can recover it.
We propose a splitting decoder that sets the number of repeated tests at each tree level to match how diluted the pools at that level are. Our claim is that, under the density-dependent model $f(\rho)\approx\rho^\alpha$ with zero false-positive background, this schedule uses a number of tests that matches, up to constants, the $(n/k)^\alpha$ sample complexity proven for slow linear-scan decoders. Its decoding time is proportional to the number of tests, and therefore sublinear in $N$ whenever $\alpha<1$. In the same calculation, the pooling efficiency threshold appears as the point where the per-level cost stops decreasing with pool size.
Core Claim
Density-Dependent Group Testing models a pool's chance of reading positive as $f(\rho)$, where $\rho$ is the fraction of positive items in the pool. When $f(\rho)\approx\rho^\alpha$ and $f(0)=0$, it shows that order $(n/k)^\alpha$-type test counts are necessary and achievable. It also shows that the requirement jumps to $(n/k)^{2\alpha}$ when $f(0)>0$, and that $\alpha\ge1$ makes pooling useless. Its decoder, NCOMP, scores every one of the $n$ items. We want the same test count with a decoder that never scans the population.
The mechanism uses the asymmetry of the noise. When $f(0)=0$, a positive pool reading is essentially certain to contain a positive item. So a pool that is repeated $R$ times with fresh random sub-assignments can be declared positive if any repetition is positive. That is an OR over repetitions, not a majority vote. Only false negatives need to be fought, and they are fought only where they occur.
Suppose items are first hashed into about $k$ bins of size $s_0=n/k$, and level $\ell$ of the tree uses pools of size $s_\ell=s_0 2^{-\ell}$. A pool at level $\ell$ that contains a single positive then has density about $1/s_\ell$. For each of the $L=\log_2 s_0$ levels to lose a true positive with probability at most $\delta/(kL)$, the level needs
$$R_\ell \approx \frac{\ln(kL/\delta)}{f(1/s_\ell)} \approx s_\ell^{\alpha}\,\ln(kL/\delta),$$
where $\delta$ is the target overall failure probability. The tree explores about $2k$ pools per level, so the total test count is approximately
$$T \approx 2k\ln(kL/\delta)\sum_{\ell=0}^{L} s_\ell^{\alpha} \approx \frac{2k\,(n/k)^{\alpha}\ln(kL/\delta)}{1-2^{-\alpha}}.$$
The sum is a geometric series with ratio $2^{-\alpha}$, so it is dominated by the top level. Decoding inspects each of these tests once, using hash-defined pool memberships, so its time is $O(T)$ with no $O(n)$ matrix storage.
Three consequences follow, and each can be tested. First, the leading term matches the density-dependent bound. Second, a uniform schedule that applies the top-level repetition count at every level pays an extra factor of about $\log(n/k)$. Third, as $\alpha\to0$ the constant $1/(1-2^{-\alpha})$ grows like $1/\alpha$, which recovers the noiseless $k\log n$ behaviour of Price et al..
The analysis also predicts a threshold. If the top bins are shrunk from size $s_0$ to some smaller $s$, there are $n/s$ bins, and the top-level cost becomes about $n s^{\alpha-1}$. For $\alpha<1$ this cost falls as pools grow, up to $s\approx n/k$. At $\alpha\ge1$ it no longer falls, and the method degrades gracefully to individual testing. This is the threshold Morjaria et al. identify, now read directly off the decoder's cost.
Research Program
The first step is to build the decoder and prove its guarantee for $f(0)=0$. Two technical issues need care. The repetitions at a level must use independent sub-assignments so that their failures are independent. Collisions, where two positives share a pool, need handling, but they only raise the density and therefore help detection.
The second step extends the decoder to Arpino et al.'s item-level dilution, in which each positive independently drops out with probability $q$, so a pool with $d'$ positives misses with probability $q^{d'}$. Here $R_\ell$ depends on how many positives a pool holds rather than on its size. We will test whether this yields a sublinear analogue of their $O(d\log n/(1-q))$ bound.
The third step handles nonzero background, $f(0)>0$. OR aggregation then admits false positives, so the decoder must compare a count of positive repetitions against a threshold. The separation between the mean count for pools with and without positives is about $f(1/s)$, so detecting it needs on the order of $1/f(1/s)^2\approx s^{2\alpha}$ repetitions. We will check empirically that the cost of the counting decoder tracks the $2\alpha$ jump.
The fourth step calibrates $f$ to real assays. We will use the Ct-shift model from Semi-quantitative group testing. Ct is the PCR cycle at which signal first appears. That paper models the pool Ct as $\text{Ct}_{\text{ind}}+M\log_{10}(g)$, where $g$ is pool size and $M$ is an amplification slope, and maps the shifted Ct to a false-negative rate through a sigmoid. We will estimate an effective $\alpha$ from this curve and check it against two published sensitivity figures: Shenzhen's 96.7% sensitivity at pool size 6, and the 5.4% error upper bound at pool size 10 reported by Smart pooling.
Relation to Prior Work
Two papers supply the method. Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing introduces per-level repetition and a look-ahead decoder for constant-rate symmetric noise, and size-capped variants that cost $O(n/\rho)$. We reuse the tree, but make repetition depend on the level, aggregate repetitions by OR rather than majority, and avoid size caps. NEON achieves $O(K\log N)$ tests and decoding time on asymmetric channels, but only when false negatives are rare and do not depend on pool contents. Our regime is the opposite: false negatives are common and concentrated in the large pools.
Three papers motivate the work. Morjaria et al. and Arpino et al. give the target sample complexities with linear-scan decoders. Sejdinovic et al. show that false negatives depend on how many positives a pool contains, and that belief propagation, a message-passing decoder over the full test-item graph, needs about $4\times$ the information-theoretic number of tests while still scaling with $N$.
Two lines of work constrain the design. The $\alpha\ge1$ impossibility result rules out any sublinear-test claim in that regime. Bui et al. reach $\text{poly}(\log n)$ decoding for inhibitors, which are discrete masking items, using deterministic matrices with larger constants. That work shows sublinear decoding can coexist with masking-type false negatives, but not with false negatives that vary continuously with concentration.
Baselines
The naive reference points are individual testing, which uses $n$ tests, and two-stage Dorfman pooling with pool size optimized for prevalence. Both will be run on the same simulated populations. Their test counts and missed-positive rates define what "pooling helps" means at each $(\alpha,k/n)$.
The strongest competitor on test count is NCOMP from Morjaria et al. under the same Bernoulli-style density-dependent model. That paper reports 99% success at $n=5000$ for $k\in\{13,166\}$, with test counts between its bounds, but the file gives no explicit test count, so no reported result was found on Lacuna for NCOMP's exact test count. We will reimplement NCOMP and give it the same $f$, the same 99% exact-recovery target, and a matched grid search over its inclusion probability. Beating it means reaching 99% exact recovery with at most $2\times$ its tests at $n=5000$, while showing a decoding-time slope below 1 on a log-log plot of time against $n$ up to $n=10^9$. NCOMP cannot run at that scale without an $O(n)$ pass.
On the item-dilution model, the corresponding competitor is Arpino et al.'s noise-tuned design with $\alpha=\log 2/(1-q)$. No numerical result for it was found on Lacuna, so we will reimplement it under the same protocol.
The strongest sublinear competitor is Price–Scarlett–Tan splitting configured for a symmetric channel. Its uniform repetition count will be tuned by search, with the same tuning budget as ours, to the smallest value that reaches 99% recovery under the true $f$. We will also run NEON with false-negative rate set to the worst-level value.
For belief propagation, the only number in the file is Sejdinovic et al.'s: about 1600 tests for 99% reconstruction at $N=5000$, $K=50$, $u=0.05$, $q=0.01$, against about 400 for joint typicality decoding. We will reproduce that setting as a sanity check for our counting variant. Here $u$ is the false-negative rate and $q$ the false-positive rate, so the setting has nonzero background.
The key ablation isolates the schedule. It keeps our tree and OR aggregation but uses a single repetition count $R$ at all levels. The predicted gap is about $\log(n/k)$ times $(1-2^{-\alpha})$, which should grow with $n$.
Why not just…?
Why not just run NCOMP and accept linear time? At clinical scales of tens of thousands of samples, linear decoding takes milliseconds, and this is a genuine threat to the proposal's relevance. We concede it for routine screening. The case for sublinear decoding rests on the very large inventories (from $10^7$ items up) that motivate Bui et al. and Li–Mazumdar, and on avoiding storage of an $n$-column matrix. The timing experiments will report the $n$ at which our decoder overtakes NCOMP in wall-clock time. If that crossover lies beyond any realistic population, we will say so.
Why not just use symmetric-noise splitting with a large uniform repetition count? This baseline will reach the target recovery rate, so the question is only its cost. Our analysis predicts it pays an extra $\log(n/k)$ factor in tests. That gain is modest at $n=5000$ and real at $n=10^8$. The ablation measures it directly. If the gap is under 20% across our grid, the scheduling contribution is weak, and the paper's claim reduces to the analysis and the threshold characterization.
Why not just cap pool size to stay above the detection limit? Capped designs, such as the size-constrained variant of Price, Scarlett, and Tan and the row-degree construction of Yi et al., keep sensitivity high but cost $O(n/\rho)$ tests, which is linear in $n$. Our cost argument shows that for $\alpha<1$ larger pools with more repetitions are strictly cheaper, so capping gives up the gain. We will plot test count against cap size to confirm the predicted $s^{\alpha-1}$ curve.
Why not just triage with metadata or use Dorfman pooling? Smart pooling extends viability to 50% prevalence, but it needs linked clinical metadata and adaptive re-testing. Dorfman misses weak positives, as the 3.3% misses in Shenzhen show, and collapses at 10–30% prevalence. Our method is single-stage and needs no metadata. It is complementary, since triage can lower prevalence before our design is applied. We will report where on the prevalence axis each method beats individual testing.
Decisive Experiments
All synthetic runs will sweep $n$ from 5000 to $10^9$ and $k/n$ from 0.1% to 30%. The test functions are $f(\rho)=\rho^\alpha$ with $\alpha\in\{0.25,0.5,0.75,0.9,1.1\}$, the same functions with $f(0)\in\{0,0.01\}$, Arpino-style item dilution with $q\in\{0.1,0.3,0.5\}$, and the Ct-calibrated sigmoid. Metrics are the tests needed for 99% exact recovery, item-level false-negative and false-positive rates, and decoding wall-clock time and memory.
Four outcomes would decide the matter. The first is whether our test count tracks $k(n/k)^\alpha$ with slope $\alpha$ in a log-log plot of tests against $n/k$, while NCOMP's tracks the same curve. The second is whether decoding time scales with $T$ rather than $n$. The third is whether the uniform-schedule ablation loses by a factor that grows like $\log(n/k)$. The fourth is whether, at $\alpha=1.1$ and with $f(0)>0$, the method behaves as theory predicts: no advantage over individual testing in the first case, and $s^{2\alpha}$ repetitions in the second.
The empirical prevalence at which our design stops beating individual testing will be compared with the 10–15%, 17% and roughly 30% ceilings reported by Verdun et al., Ng et al. and Escobar et al. If the Israeli cohort's Ct records are accessible, we will also replay its pool and individual results through the calibrated $f$. Otherwise we will use only the published Ct-shift model.
References
- Density-Dependent Group Testing
- A Fast Binary Splitting Approach to Non-Adaptive Group Testing
- Group Testing in the High Dilution Regime
- Semi-quantitative group testing for efficient and accurate qPCR screening of pathogens with a wide range of loads
- Exploring Chlamydia trachomatis screening in Shenzhen: a cost-effective sample pooling strategy for pre-marital and pre-pregnancy populations
- Smart pooling: AI-powered COVID-19 informative group testing
- Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing
- Nonadaptive Noisy Group Testing with Optimal Tests and Decoding
- Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction
- Sublinear Decoding Schemes for Non-adaptive Group Testing with Inhibitors
- Optimal pooling matrix design for group testing with dilution (row degree) constraints
- Group Testing for SARS-CoV-2 Allows for Up to 10-Fold Efficiency Increase Across Realistic Scenarios and Testing Strategies
- Implementation of the compulsory universal testing scheme in Hong Kong: Mathematical simulations of a household-based pooling approach