{"id":"fc9740ee-f36f-4570-89af-5d4ba2110249","arxiv_id":"2509.01723","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"An adaptive Decision Transformer policy, trained on heuristic-generated trajectories, is claimed to beat the non-adaptive query-count bound for quantitative group testing.","lead":"A team at UCSD trains a Decision Transformer to choose adaptive subset-sum queries for quantitative group testing, after reducing the n-item problem to a k-dimensional integer recovery task. They report, for the first time, average query counts below the non-adaptive information-theoretic bound, but the comparison mixes average performance with worst-case bounds.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central claim compares average adaptive query counts to a worst-case non-adaptive lower bound; the inference that adaptivity beats the bound does not follow.","rationale":"The paper's most positive finding is that a Decision Transformer can imitate expensive entropy-guided query strategies at much lower inference latency (Table 2), and the DT-Entropy numbers in Table 1 may be a real empirical observation about the reduced k-dimensional subproblem. But the central claim in the abstract and conclusion goes beyond that: it asserts a first-ever demonstration that adaptivity beats the non-adaptive information-theoretic bound for QGT. That inference has two independent weaknesses. First, and most decisive, the comparison is between an average and a worst-case quantity. Eq. (1) is a minimax lower bound; any zero-error adaptive procedure with variable stopping time can have an expected query count below it, so exceeding it on average is not evidence of surpassing the bound. The paper does not report worst-case stopping times or an average-case non-adaptive baseline. Second, even if the metric were fixed, Section 4's end-to-end query count log2(n/k)m+k assumes the subproblem query-cost distribution is identical at every splitting stage, justified only by an initial random shuffle. The shuffle makes coordinates exchangeable within a stage, but it does not make the distribution of upper bounds and feasible vectors across stages identical, since group sizes shrink and the conditioning changes at each depth; the paper provides no empirical or analytic check of this invariance. The reader's weakest assumption flags the second point; we agree it is a real problem, but we view the metric mismatch as the more load-bearing flaw because it invalidates the central claim even if all Table 1 numbers are reproduced. A concrete check is to report the full distribution of end-to-end stopping times (and the average of an optimal non-adaptive scheme under the same prior) for small n,k. Absent that, the claim should not be accepted.","tokens_in":8837,"tokens_out":11854,"duration_ms":145243,"concrete_test":"Re-run the end-to-end algorithm for small n,k (e.g., n=16, k=2 and n=32, k=3) with the described DT policies and, for every x in B_{n,k}, record the stopping time; report both the maximum (worst-case) and the mean. Compare the worst-case to the Djackov bound in Eq. (1), and compare the mean to the mean of the best non-adaptive scheme under the same uniform prior (obtainable by exhaustive search for these sizes). If the worst-case is not below Eq. (1), or if a non-adaptive scheme has a lower mean, the central claim is an artifact of comparing average to worst-case.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline claim ('reduces the average number of queries below the well-known non-adaptive information-theoretic bound') is not established by the reported experiments. Equation (1) is a worst-case lower bound: it lower-bounds the number of tests any non-adaptive scheme must use to identify every x in B_{n,k}. Table 1, however, reports the mean number of queries of a zero-error adaptive policy averaged over random instances. Because the stopping time can be small on easy instances, an average can fall below a worst-case lower bound without any reduction in worst-case query complexity. Section 7 then multiplies the Table 1 mean by log2(n/k) and compares the result to Eq. (1), so the comparison mixes metrics: average adaptive versus worst-case non-adaptive. To demonstrate that adaptivity reduces query complexity, the comparison must hold metric-for-metric—e.g., worst-case adaptive versus worst-case non-adaptive, or expected adaptive versus expected non-adaptive under the same prior. The paper provides neither. This is independent of the further unverified assumption in Section 4 that the per-stage mean m is identical across all log2(n/k) stages; even if that assumption held, the central 'first time surpassing the non-adaptive bound' claim would still not follow.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":9102,"tokens_out":10232,"duration_ms":118765,"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":[{"comment":"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":"Section 7, Eq. (1), Table 1"},{"comment":"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.","section":"Section 4, paragraph on total query complexity"},{"comment":"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":"Table 1, row 'Lower Bound'"},{"comment":"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.","section":"Section 6, Tables 1 and 2"}],"minor_comments":[{"comment":"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":"Section 6, after 'challenging.'"},{"comment":"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.","section":"Section 6, Table 2 reference"},{"comment":"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.","section":"Table 1"},{"comment":"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":"Throughout"},{"comment":"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.","section":"Section 4, 'query budget of k'"}],"recommendation":"reject","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, here is my take. The central claim of this paper—that a Decision Transformer beats the non-adaptive information-theoretic bound for quantitative group testing—is not established by the experiments. Table 1 reports mean query counts for a small reduced problem, and the total is computed as that mean times log(n/k). The non-adaptive bound in Eq. (1) is a worst-case lower bound for all instances. An average can fall below a worst-case bound without any demonstration that adaptivity reduces query complexity. You need a metric-for-metric comparison. So the 'first time surpassing the non-adaptive bound' is an overstatement, as the stress-test notes.\n\nWhat is genuinely new: the reduction of QGT to an integer-vector recovery problem of dimension k, which makes the search space tractable for sequence models. The binary splitting itself is classical, but the formal setup with upper bounds is clean. Applying Decision Transformers to learn adaptive query policies from two types of expert trajectories is a reasonable engineering contribution. The experiments consistently show that the DT can imitate covariance- and entropy-guided heuristics with much lower latency, which is a practical win for deploying these strategies at scale.\n\nSoft spots: The assumption in Sec. 4 that the expected per-stage query count m is the same across all log(n/k) stages is unverified and implausible; the upper bounds shrink as groups split, so the subproblem distribution changes. Random shuffling of coordinates does not fix that. Also, there are no error bars, no code or data, and the 'lower bound' row in Table 1 is not derived. The DT is trained on the same expert heuristics it then reproduces, so the numbers are an imitation result, not a new algorithmic bound.\n\nWho is this for? A reader in group testing who is open to learning-based policies, or an ML researcher interested in applying sequence models to small combinatorial problems. It deserves a serious referee because the reduction is useful and the empirical method is competent, but the paper needs major revision: reframe the claim as average-case improvement under a fixed prior, validate the per-stage invariance, and release artifacts.\n\nRecommendation: send it to peer review with a requirement for the authors to address the comparison issue and provide code/data. I would not cite it in its current form.","headline":"Useful reduction, competent imitation, but the central claim compares averages to a worst-case bound and doesn't hold.","tokens_in":9575,"tokens_out":5251,"would_cite":false,"duration_ms":59787,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"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","keywords":["quantitative group testing","adaptive querying","subset-sum queries","decision transformer","offline reinforcement learning","binary splitting","integer-vector recovery","information-theoretic lower bound"],"falsifier":"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","tokens_in":8711,"feed_emoji":"🧪","tokens_out":20572,"duration_ms":208961,"temperature":0.7,"pith_summary":"The paper targets quantitative group testing: locating exactly k defective items in a collection of n by asking for subset sums of chosen pools, each answer costing one query. It claims that adaptivity — letting each question depend on earlier answers — can finally deliver the query savings that information theory has promised but no algorithm had achieved. The route is a reduction that shrinks the n-dimensional problem to a sequence of k-dimensional integer-vector recovery subproblems, solved by a Decision Transformer trained offline on expert query trajectories. In experiments the total average query count falls below the classic non-adaptive bound for every k from 2 to 8, and for k=2 it reaches the information-theoretic lower bound exactly. If the result holds up, it turns a long-open theoretical gap into a practical, sparsity-scaled recipe for pooled-data recovery.","feed_headline":"Adaptive queries beat the non-adaptive bound at last","feed_subtitle":"A decision transformer learns which pools to ask, hitting the optimal average for k=2 defectives.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Decision Transformer sequence-modeling architecture that the paper adapts to choose queries; the whole learning method is built on it.","marker":"(Chen et al., 2021)"},{"why":"States the non-adaptive information-theoretic lower bound m0 that the paper's algorithm is claimed to beat.","marker":"(Djackov, 1975)"},{"why":"Provides the best prior adaptive algorithm (the baseline it must beat) and the counting argument for the adaptive lower bound.","marker":"(Bshouty, 2009)"},{"why":"The integer-programming solver used as the identifiability oracle that decides when the reduced integer vector is uniquely determined.","marker":"Gurobi Optimization, LLC (2024)"},{"why":"The transformer architecture whose self-attention is the backbone of the sequence model used for query prediction.","marker":"(Vaswani et al., 2017)"},{"why":"The GPT-style causal transformer implementation adopted as the Decision Transformer's model.","marker":"(Radford et al., 2018)"}],"fun_headline_variants":["First adaptive QGT algorithm beats info bound","Decision transformer crushes non-adaptive query bound","Adaptive group testing finally breaks non-adaptive bound","AI asks smarter queries, beats non-adaptive bound"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["First adaptive QGT algorithm beats info bound","Decision transformer crushes non-adaptive query bound","Adaptive group testing finally breaks non-adaptive bound","AI asks smarter queries, beats non-adaptive bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001002,"raw_usage":{"total_tokens":4063,"prompt_tokens":721,"completion_tokens":3342,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":465,"completion_tokens_details":{"reasoning_tokens":3282}},"tokens_in":465,"tokens_out":3342,"duration_ms":27206,"temperature":1.0,"reasoning_tokens":3282,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T12:15:14.834966+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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","supporting_citations":[],"review_version":1}