REVIEW 4 major objections 5 minor 10 references
This paper claims that a learning-based adaptive query strategy can, for the first time, reduce the average number of subset-sum queries in quantitative group testing below the non-adaptive information-theoretic bound — and, with two defect
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
An adaptive Decision Transformer policy, trained on heuristic-generated trajectories, is claimed to beat the non-adaptive query-count bound for quantitative group testing.
T0 review reviewed 2026-08-05 challenge →
load-bearing objection Useful reduction, competent imitation, but the central claim compares averages to a worst-case bound and doesn't hold. the 4 major comments →
Learning to Ask: Decision Transformers for Adaptive Quantitative Group Testing
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
Core claim
Central claim: adaptive quantitative group testing can be solved by two linked ideas. A binary-splitting reduction turns the n-item binary recovery problem into log2(n/k) rounds of recovering a length-k integer vector, each coordinate bounded by an earlier group measurement; a Decision Transformer — a transformer trained offline to predict the next query from prior results and remaining budget — chooses the queries in each round. The paper reports a per-round average of m queries, giving total log2(n/k)·m + k, claimed to fall below the non-adaptive bound (2k/log k)·log(n/k) for every k from 2 to 8, the first algorithm to do so. For k=2, the per-round average reaches 1.26, identified as the l
What carries the argument
Two linked mechanisms carry the argument. The binary-splitting reduction: partition the n items into k groups and spend k queries measuring each group's defective count; split every group in half, and note that recovering the left-half counts is exactly recovering a length-k integer vector with known per-coordinate upper bounds (the earlier group totals). Subtract the recovered left counts from the totals to get the right halves, and recurse for log2(n/k) stages, so the problem becomes a chain of k-dimensional integer-vector recovery tasks. The Decision Transformer: a transformer trained offline to predict the next query from the history of remaining-budget, result, and query tokens, imitati
Load-bearing premise
The per-stage query counts Mi are assumed to follow the same distribution at every level of the recursion, so the total query count is written as (number of stages) times one averaged per-stage cost plus the k initial queries — but the paper does not show that the distribution of query costs is unchanged as the groups shrink and the upper bounds tighten.
What would settle it
Run the full pipeline end-to-end — recursive splitting plus the learned per-stage policy — on instances of increasing n (say n = 2^12 to 2^24) for k = 2 through 8, counting every query including the initial k group measurements, and compare the total against (2k/log k)·log(n/k). If the measured total reaches or exceeds the bound, or if per-stage counts show the mean drifting as the recursion deepens, the bound-beating claim fails. Separately, for k=2, build the optimal decision tree for the length-2 integer-vector subproblem by exhaustive search; if the true optimal average depth is below 1.26
If this is right
- For two defectives (k=2), the learned policy is claimed to match the information-theoretic lower bound exactly, making the total query count log2(n/2)·1.26 + 2 the best any adaptive scheme can achieve.
- For k=3 through 8, the claimed end-to-end total stays below the non-adaptive bound (2k/log k)·log(n/k) in all tested settings — the first demonstration that adaptivity's promised query savings are practically achievable.
- Because the action space, model size, and decoding cost scale with k rather than n, training happens once on the reduced length-k problem and the same solver transfers across any population size n.
- The learned policy reproduces the behavior of expensive covariance- or entropy-guided experts at a fraction of the per-query latency, making the adaptive savings practical where running the experts would be too slow.
- The gap between the achieved per-stage cost and the adaptive lower bound remains open for k ≥ 3, which the paper identifies as the next target.
Where Pith is reading between the lines
- The reduction-plus-policy pipeline is agnostic to the outer problem, so the same trained length-k solver could transfer to other subset-sum recovery tasks — heavy-hitter detection, rare-variant sequencing, one-bit compressed sensing — wherever the hidden vector is sparse.
- Because the decision transformer only imitates the expert that generated its training set, its ceiling is set by that expert; training on stronger offline experts (for instance, bounded-lookahead or beam-search policies) could push the k ≥ 3 rates closer to the adaptive floor without changing the architecture.
- The return-to-go input acts as a budget knob at inference, so the same policy can trade expected query count against risk of exceeding its allowance — a practical degree of freedom that hand-designed algorithms do not expose.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper addresses adaptive quantitative group testing (QGT), where the goal is to recover a k-sparse binary vector of length n using subset-sum queries. The authors propose a reduction: after an initial query of k disjoint groups, each subsequent binary-splitting step becomes the problem of recovering an integer vector of length k with known upper bounds. This reduced problem is formulated as an offline reinforcement learning task and solved with a Decision Transformer (DT) trained on trajectories from random, covariance-guided, and entropy-guided policies. The total query count is claimed to be log2(n/k)*m + k, where m is the expected per-stage query count. Experiments report per-stage average query counts for k=2,...,8, and the conclusion claims that for k=2 the method matches the information-theoretic lower bound and that for all k it surpasses the non-adaptive lower bound, thereby demonstrating that adaptivity reduces query complexity.
Significance. The dimensionality reduction from n to k is a useful idea, and the latency results in Table 2 show that a trained DT can amortize the expensive covariance- and entropy-guided computations at inference time. If the query-complexity claims were properly supported, the paper would be an interesting empirical contribution to adaptive QGT. However, the central advertised result rests on a comparison of average adaptive performance to a worst-case non-adaptive lower bound, which is not a valid basis for the claim that adaptivity reduces query complexity. The per-stage constant-m assumption is unverified, and the lower-bound row in Table 1 is not derived. These issues are load-bearing and currently prevent the main conclusions from being accepted.
major comments (4)
- [Section 7, Eq. (1), Table 1] The headline claim that the adaptive algorithm 'reduces the average number of queries below the well-known non-adaptive information-theoretic bound' is not supported. Equation (1) is a worst-case lower bound for non-adaptive schemes: it lower-bounds the number of tests required to identify every vector in B_{n,k}. Table 1, however, reports the mean number of queries of an adaptive policy averaged over random instances. Since an average can fall below a worst-case lower bound without any reduction in worst-case complexity, the comparison in Section 7 mixes metrics. To demonstrate that adaptivity reduces query complexity, the paper must compare like with like: worst-case adaptive vs. worst-case non-adaptive, or expected adaptive vs. expected non-adaptive under the same prior. Neither is provided. This is independent of the constant-m assumption and is the core of the paper's main claim.
- [Section 4, paragraph on total query complexity] The derivation of the total query count relies on the assumption that 'the query cost Mi at each stage follows a similar distribution' and that E[M_i]=m for all stages. Random coordinate shuffling at the beginning of each stage does not establish this invariance: the upper bounds u_i transmitted across stages are the leftover counts from the previous stage, and the distribution of feasible integer vectors changes as groups shrink and some groups become empty. The formula log2(n/k)*m + k, and hence every comparison to Eq. (1), depends critically on this claim. The paper must either prove the distributional invariance, replace the formula with a stage-dependent sum, or validate the constant-m assumption empirically across stages.
- [Table 1, row 'Lower Bound'] The lower-bound row is not derived anywhere in the paper. For k=2, the entry 1.26 is presented as 'the fundamental information-theoretic limit,' but the paper does not state the probability model over upper bounds and target vectors that would yield this value. Under the natural model described in Section 4, with two coordinates and upper bounds (1,1), the target lies in {0,1}^2 and a single subset-sum query cannot uniquely identify it; the average optimal query count depends on the prior over the initial group counts. Without a derivation or a precise statement of the lower bound's model, the claim that DT-Entropy Guided 'achieves the lower bound' is unsupported. The lower bound is load-bearing for the 'optimal for k=2' claim and must be justified.
- [Section 6, Tables 1 and 2] The paper reports query counts only for DT agents trained on random, covariance-guided, and entropy-guided datasets. It does not report the query counts of the raw covariance-guided and entropy-guided expert policies (the 'Cov-Agent' and 'Ent-Agent' that appear in Table 2's latency comparison). Since the DT is trained to imitate these experts, its query count should be compared against the experts' query counts to show whether the DT preserves or improves on the expert performance. Without this baseline, the reader cannot assess whether the DT contributes anything beyond distilling the expert policy. This is especially important because the paper's contribution is framed as 'learning to ask,' not merely as an efficient implementation of an existing heuristic.
minor comments (5)
- [Section 6, after 'challenging.'] The text contains the uninterpretable token sequence 'DFC ´C1QW' immediately after 'making the learning task significantly more challenging.' This appears to be a corrupted insertion and should be removed or corrected.
- [Section 6, Table 2 reference] The reference to Table 2 appears as 'Table??' in the sentence 'We compare the latency of each method in Table??.' The citation should be fixed.
- [Table 1] The table reports averages without standard deviations, confidence intervals, or the number of test instances. Given that some differences (e.g., 1.26 vs. 1.28 for k=2) are small, the absence of variability information makes it difficult to judge whether the reported optimality is meaningful.
- [Throughout] The notation for the non-adaptive bound is inconsistent: Eq. (1) is written as m0 = 2k/log k * log(n/k), but the text sometimes refers to it as a bound on 'the number of tests required' and later as a value that the adaptive average 'surpasses.' Please clarify whether the bound is worst-case, average-case, or a function of n and k, and ensure the comparison is metric-matched.
- [Section 4, 'query budget of k'] The initial partition into k disjoint groups and the k queries are clear, but the paper should state explicitly whether the group sizes are equal and what happens when n is not divisible by k. Small technical details about rounding are omitted.
Circularity Check
No significant circularity; the central comparison is an empirical average-vs-average claim, and the DT's query counts are measured outputs, not fitted inputs.
full rationale
The paper's derivation chain is not circular. The non-adaptive bound in Eq. (1) lower-bounds the fixed number of tests of any non-adaptive scheme; because non-adaptive schemes use a constant number of tests, their average query count equals that fixed number, so comparing the adaptive algorithm's average total to m0 is metric-for-metric. The total query count is computed from Table 1 as log2(n/k)*m + k, which is an arithmetic composition of an empirically measured per-stage mean, not a definitional identity with the lower bound. The DT is trained on expert trajectories, but its evaluation query count is generated by its own policy and the Gurobi identifiability oracle; imitation can fail, so matching the lower bound for k=2 is an empirical result rather than a tautology. The only self-citation (Soleymani & Javidi 2024) appears in Related Work and is not load-bearing. The main weaknesses are the unverified assumption in Section 4 that per-stage query-cost distributions are identical, and the unsourced 'Lower Bound' row in Table 1; these are correctness and rigor concerns, not circularity, because they do not reduce the paper's claimed result to its own inputs by construction.
Axiom & Free-Parameter Ledger
free parameters (2)
- initial return-to-go =
swept from -1 to -l
- sequence length l =
not specified
axioms (4)
- standard math The non-adaptive information-theoretic lower bound m0 = 2k/log k * log(n/k) is valid.
- domain assumption The adaptive lower bound is half of the non-adaptive bound.
- ad hoc to paper The per-stage expected query count Mi has the same distribution across all splitting stages.
- domain assumption Gurobi-based identifiability check is an exact oracle for unique solvability of the reduced integer-vector problem.
Cite this review
Pith. "Pith review of Learning to Ask: Decision Transformers for Adaptive Quantitative Group Testing." pith.science (2026). https://pith.science/paper/A7SBVWPZ
@misc{pith2026250901723,
author = {Pith},
title = {Pith review of: Learning to Ask: Decision Transformers for Adaptive Quantitative Group Testing},
year = {2026},
howpublished = {\url{https://pith.science/paper/A7SBVWPZ}},
note = {Machine review of arXiv:2509.01723}
}
read the original abstract
We consider the problem of quantitative group testing (QGT), where the goal is to recover a sparse binary vector from aggregate subset-sum queries: each query selects a subset of indices and returns the sum of those entries. Information-theoretic results suggest that adaptivity could yield up to a twofold reduction in the total number of required queries, yet no algorithm has surpassed the non-adaptive bound, leaving its practical benefit an open question. In this paper, we reduce the QGT problem to an integer-vector recovery task whose dimension scales with the sparsity of the original problem rather than its full ambient size. We then formulate this reduced recovery task as an offline reinforcement learning problem and employ Decision Transformers to solve it adaptively. By combining these two steps, we obtain an effective end-to-end method for solving the QGT problem. Our experiments show that, for the first time in the literature, our adaptive algorithm reduces the average number of queries below the well-known non-adaptive information-theoretic bound, demonstrating that adaptivity can indeed reduce the number of queries.
Figures
Reference graph
Works this paper leans on
-
[9]
Namiko Matsumoto, Arya Mazumdar, and Soumyabrata Pal
URL https://arxiv.org/abs/2211.15657. Namiko Matsumoto, Arya Mazumdar, and Soumyabrata Pal. Improved support recovery in universal one-bit compressed sensing. IEEE Transactions on Information Theory,
-
[13]
Prompting Decision Transformer for Few-Shot Policy Generalization
URL https://arxiv. org/abs/2206.13499. 10
work page internal anchor Pith review Pith/arXiv arXiv
-
[1943]
Amir Emad and Olgica Milenkovic
URL https://projecteuclid.org/ euclid.aoms/1177731363. Amir Emad and Olgica Milenkovic. Poisson group testing: A probabilistic model for non- adaptive streaming boolean compressed sensing. IEEE Transactions on Signal Processing, 62(20):5374–5387,
-
[2014]
Quantitative Group Testing and the rank of random matrices
Uriel Feige and Amir Lellouche. Quantitative group testing and the rank of random ma- trices. arXiv preprint arXiv:2006.09074,
work page internal anchor Pith review Pith/arXiv arXiv 2006
-
[2016]
Support Recovery in Universal One-bit Compressed Sensing
Arya Mazumdar and Soumyabrata Pal. Support recovery in universal one-bit compressed sensing. arXiv preprint arXiv:2107.09091,
work page internal anchor Pith review Pith/arXiv arXiv
-
[2017]
Group testing under sum observations for heavy hitter detection
Chao Wang, Qing Zhao, and Chen-Nee Chuah. Group testing under sum observations for heavy hitter detection. In 2015 Information Theory and Applications Workshop (ITA) , pp. 149–153. IEEE,
work page 2015
-
[2020]
On the paral- lel reconstruction from pooled data
Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, and Philipp Loick. On the paral- lel reconstruction from pooled data. In 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 425–435. IEEE,
work page 2022
-
[2021]
Esmaeil Karimi, Fatemeh Kazemi, Anoosheh Heidarzadeh, Krishna R Narayanan, and Alex Sprintson
URL https: //arxiv.org/abs/2106.02039. Esmaeil Karimi, Fatemeh Kazemi, Anoosheh Heidarzadeh, Krishna R Narayanan, and Alex Sprintson. Sparse graph codes for non-adaptive quantitative group testing. In 2019 IEEE Information Theory Workshop (ITW), pp. 1–5. IEEE,
Pith/arXiv arXiv 2019
-
[2022]
URL https://arxiv. org/abs/2212.06817. Nader H Bshouty. Optimal algorithms for the coin weighing problem with a spring scale. In COLT, volume 2009, pp. 82,
Pith/arXiv arXiv 2009
-
[2024]
Approximate Message Passing with Rigorous Guarantees for Pooled Data and Quantitative Group Testing
Nelvin Tan, Jonathan Scarlett, and Ramji Venkataramanan. Approximate message passing with rigorous guarantees for pooled data and quantitative group testing. arXiv preprint arXiv:2309.15507,
work page internal anchor Pith review Pith/arXiv arXiv
This paper was first reviewed by deepseek-v4-flash on August 5, 2026.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.