REVIEW 2 major objections 5 minor 18 references
Soft-Decision Decoding for LDPC Code-Based Quantitative Group Testing
T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read This paper introduces a belief-propagation decoder with purely soft messages for LDPC-code-based quantitative group testing, and shows by simulation that it lowers the misdetection rate relative to the hard-decision peeling decoder, with…
desk verdict A clean, modest extension of belief propagation to quantitative group testing, with a real but untested caveat: all reported gains come from feeding the true prevalence only to the proposed decoder. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the bipartite factor graph of the assignment matrix, with $n$ variable nodes for items and $r$ constraint nodes for tests, together with the two message-update rules. The constraint-node update (equation 5) computes the belief that an item is defective by summing over all assignments of the other neighbors whose total equals the observed test outcome minus the item's candidate state, which is the step that extracts soft information from the exact count. The variable-node update (equation 3) is the product of the prevalence prior and all incoming constraint messages except the one on the edge being updated. Because the constraint sum ranges over all configurations with a given count, the update complexity is $O(2^{d_c-1})$, exponential in the check-node degree.
What would settle it
Run the soft decoder on a $(3,6)$ regular graph with $n=1024$ and true prevalence $\delta=0.3$, but with the decoder using a fixed prior $\delta=0.1$, and compare its misdetection rate with the peeling decoder; if the soft decoder no longer reaches the $10^{-3}$ target while the peeling decoder does, the claimed advantage depends on perfect prior knowledge.
Extended reading notes
Core claim
The central claim is that a belief-propagation decoder with purely soft messages strictly improves the misdetection rate of LDPC-code-based quantitative group testing compared with the hard-decision peeling decoder of [15]. The decoder models each test outcome as a constraint that the sum of the states of the items in the pool equals the observed count, and it computes each constraint-to-variable message by summing over all configurations of the other pool members consistent with that count. The variable-node update multiplies the incoming constraint beliefs by a Bernoulli prior set by the prevalence $\delta$. Simulations on regular $(3,6)$ and $(3,9)$ assignment graphs with population sizes from 128 to 16,384 show consistent gains that grow with population size, and the soft update rules reduce to the peeling decoder's declarations as extreme cases.
Load-bearing premise
The decoder assumes the prevalence $\delta$ is known exactly and uses it as the prior in every variable-node update; all simulations feed the true $\delta$, so a mismatched estimate could reduce or erase the reported gains.
Editorial extensions
If this is right
- At a fixed number of tests, the soft decoder can operate at a higher prevalence while meeting the same misdetection target, which lowers the cost of screening populations with more defective items.
- For the regular graphs tested, the prevalence gain over the hard-decision decoder grows with the population size, from about 0.02 at $n=128$ to roughly 0.14-0.18 at $n=16{,}384$.
- The decoder is compatible with irregular LDPC assignments as well as the regular graphs used in the simulations.
- Because the messages are soft probabilities, the authors expect a natural extension to noisy test outcomes by replacing the exact constraint with the conditional test distribution, a route that hard-decision peeling cannot take directly.
- The exponential check-node complexity bounds practical use to pools of small degree, so the reported gains apply in the low-degree regime.
Reading between the lines
- The reported gains assume the decoder knows the true prevalence $\delta$; if $\delta$ must be estimated from imperfect data, the advantage over hard-decision decoding may shrink, and the paper does not test that sensitivity.
- The same message-passing structure could be augmented with an expectation-maximization step to estimate $\delta$ on the fly, producing a self-calibrating decoder.
- Since the decoder outputs an approximate posterior for each item, thresholds can be tuned to reflect asymmetric costs of false positives and false negatives, an option the paper does not explore.
- The monotone improvement with $n$ hints at a finite-length threshold phenomenon similar to LDPC decoding, where performance sharpens once the graph becomes locally cycle-free.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a belief-propagation (BP) decoder for LDPC-code-based noiseless non-adaptive quantitative group testing. The decoder exchanges soft messages between variable nodes (items) and constraint nodes (tests), with the constraint-node update performing exact marginalization over the test constraint. The authors derive the variable-node and constraint-node update rules in Section IV, provide a computational complexity analysis, and present Monte Carlo simulations in Section V showing that the proposed soft decoder achieves lower misdetection rate than the hard-decision peeling decoder of Mashauri et al. [15] for regular graphs with (dv,dc) = (3,6) and (3,9), for population sizes ranging from n=128 to n=16384. The reported gain in prevalence δ at PMD ≈ 10^-3 ranges from about 0.02 (short lengths) to 0.17 (moderate lengths).
Significance. If the claimed improvement is robust, the proposed decoder is a useful contribution to quantitative group testing: it is a natural, correctly derived belief-propagation adaptation of the LDPC framework, and the exact constraint-node update (5) is a sound marginalization for the noiseless adder-channel constraint. The paper is clearly written and the algorithm is straightforward to implement. However, the central claim is currently supported only by simulations that are confounded by an asymmetry in side information and that lack statistical error characterization. The authors do not provide code, number of Monte Carlo trials, or sensitivity analysis, so the magnitude of the reported gains is not yet established. The work has potential, but the evidence as presented is insufficient to fully validate the central outperformance claim.
major comments (2)
- [Section V, Algorithm 1, Eq. (3)] The comparison between the proposed decoder and the peeling decoder of [15] is confounded: the BP decoder is given the true prevalence δ as the prior in the VN update (3) and as an input to Algorithm 1, while the peeling decoder baseline does not use δ. The paper never tests sensitivity to a mismatched prior, so the reported gains in δ (0.02–0.17) may partly or entirely stem from this extra information rather than from the soft-information update rule. To substantiate the claim that the proposed decoder outperforms the hard-decision decoder, the authors should add experiments with a misspecified prior, provide a baseline decoder that also knows δ, or explicitly state and justify the assumption that δ is known exactly.
- [Section V, Figs. 3–5] The numerical results are presented without error bars, confidence intervals, or any statement of the number of Monte Carlo trials. Since the target PMD values are as low as 10^-3, the plotted points are estimates of rare-event probabilities and their reliability is unclear. Without a statistical characterization, the claimed prevalence gains (e.g., 0.14–0.18 for moderate lengths) cannot be assessed for significance. Please specify the number of simulation runs, the simulation procedure, and add error bars or confidence bands to the figures.
minor comments (5)
- [Section II] The notation [x] is defined as the set {1,...,x}, but square brackets are also used for citations throughout the text; this dual use is confusing and should be disambiguated (e.g., use a different symbol for the set).
- [Abstract and author affiliation] The abstract mentions 'Mashauri et al.' without a citation number, and the first author's affiliation contains a typo ('T echnical'). Please fix these presentation issues.
- [Section IV-B, second bullet] The quantity r_i^(ℓ) in the second bullet point is used but never defined; please define it explicitly or rephrase the sentence.
- [Section V, first paragraph] The footnote says that slightly fewer iterations yield similar performance, but the paper does not report how the performance degrades with L. Since L is a free parameter, a small experiment varying L would help the reader understand the sensitivity of the results to this choice.
- [Figures 3–5] The legends in the figures repeat the same n values for both the solid and dashed curves, which makes the figures hard to read. Please use a combined legend entry (e.g., 'BP, n=128' and 'Peeling, n=128') or otherwise clarify the correspondence.
Circularity Check
No circularity: the claimed gain is established by direct simulation of a standard belief-propagation decoder against a re-implemented hard-decision baseline; no parameter is fitted from the data and no load-bearing premise is imported from self-citations.
full rationale
The derivation chain is self-contained. Algorithm 1 and Eq. (3) use the prevalence δ as a prior, but δ is part of the stated probabilistic model in Section III (Pr_Di(b) = (1−δ, δ)), not a parameter fitted to the test outcomes; the decoder's PMD is measured by simulation in Section V, not derived from the prior by construction. The constraint-node update in Eq. (5) is an exact marginalization of the constraint in Eq. (4), so the message-passing rule does not encode the target result. The comparison to [15] is a direct re-simulation of the peeling decoder, so [15] is a baseline rather than an unverified self-citation; [18] is cited only as a related constraint and [4] as an application, neither carrying load. The only substantive caveat is that the simulations always feed the true δ to the proposed decoder while the peeling baseline does not use δ; this is an informational asymmetry that could affect the size of the reported gain under mismatched or unknown δ, but it is a robustness/fairness concern, not circularity, because no equation or fitted value forces the outcome. Under the paper's stated assumption of known δ, the claimed improvement is an independent empirical result.
Assumptions & free parameters
free parameters (1)
- L (number of iterations) =
100
assumptions (4)
- domain assumption Items are i.i.d. Bernoulli with probability delta of being defective.
- domain assumption Test outcomes are noiseless and exactly equal to the sum of the defective items in the pool.
- domain assumption The assignment matrix is a regular LDPC code with given column and row weights.
- domain assumption Belief propagation converges to a good approximation of the MAP solution after L iterations.
Cite this review
Pith. "Pith review of Soft-Decision Decoding for LDPC Code-Based Quantitative Group Testing." pith.science (2026). https://pith.science/paper/ZRCYSLCR
@misc{pith2026250112167,
author = {Pith},
title = {Pith review of: Soft-Decision Decoding for LDPC Code-Based Quantitative Group Testing},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZRCYSLCR}},
note = {Machine review of arXiv:2501.12167}
}
read the original abstract
We consider the problem of identifying defective items in a population with non-adaptive quantitative group testing. For this scenario, Mashauri et al. recently proposed a low-density parity-check (LDPC) code-based quantitative group testing scheme with a hard-decision decoding approach (akin to peeling decoding). This scheme outperforms generalized LDPC code-based quantitative group testing schemes in terms of the misdetection rate. In this work, we propose a belief-propagation-based decoder for quantitative group testing with LDPC codes, where the messages being passed are purely soft. Through extensive simulations, we show that the proposed soft-information decoder outperforms the hard-decision decoder Mashauri et al.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[15]
Low- density parity-check codes and spatial coupling for quantitative g roup testing,
M. M. Mashauri, A. Graell i Amat, and M. Lentmaier, “Low- density parity-check codes and spatial coupling for quantitative g roup testing,” in IEEE Int. Symp. Information Theory (ISIT) , pp. 1860–1865, 2023
work page 2023
-
[18]
Asymptotic analysis and spatial coupling of counter braids,
E. Rosnes and A. Graell i Amat, “Asymptotic analysis and spatial coupling of counter braids,” IEEE Transactions on Information Theory , vol. 64, no. 11, pp. 7242–7263, 2018
work page 2018
-
[1]
The detection of defective members of large populations,
R. Dorfman, “The detection of defective members of large populations,” The Annals of Mathematical Statistics , vol. 14, no. 4, pp. 436–440, 1943
1943
-
[2]
Group testing : An information theory perspective,
M. Aldridge, O. Johnson, and J. Scarlett, “Group testing : An information theory perspective,” 2019
work page 2019
-
[3]
Group testing against covid- 19,
C. Gollier and O. Gossner, “Group testing against covid- 19,” tech. rep., EconPol Policy Brief, 2020
work page 2020
-
[4]
FedGT: Identification of malicious clients in federated le arning with secure aggregation,
M. Xhemrishi, J. ¨Ostman, A. Wachter-Zeh, and A. Graell i Amat, “FedGT: Identification of malicious clients in federated le arning with secure aggregation,” 2023
work page 2023
-
[5]
Q uantitative group testing in the sublinear regime,
O. Gebhard, M. Hahn-Klimroth, D. Kaaser, and P . Loick, “Q uantitative group testing in the sublinear regime,” 05 2019
work page 2019
-
[6]
Quantitative group testing-ba sed overlapping pool sequencing to identify rare variant carriers,
C. Cao, C. Li, and X. Sun, “Quantitative group testing-ba sed overlapping pool sequencing to identify rare variant carriers,” BMC bioinformatics , vol. 15, p. 195, 06 2014
work page 2014
Show all 18 references
-
[7]
Group testing schemes from code s and designs,
A. Barg and A. Mazumdar, “Group testing schemes from code s and designs,” IEEE Transactions on Information Theory , vol. 63, no. 11, pp. 7131–7141, 2017
2017
-
[8]
Saffron: A fast, efficient, and robust framework for group testing bas ed on sparse- graph codes,
K. Lee, K. Chandrasekher, R. Pedarsani, and K. Ramchandr an, “Saffron: A fast, efficient, and robust framework for group testing bas ed on sparse- graph codes,” IEEE Trans. Signal Processing , vol. 67, pp. 4649–4664, Sept. 2019
2019
-
[9]
An analysis on non-adaptive group testing based on sparse pooling graphs,
T. Wadayama, “An analysis on non-adaptive group testing based on sparse pooling graphs,” in 2013 IEEE International Symposium on Information Theory , pp. 2681–2685, 2013
2013
-
[10]
Group te sting using left-and-right-regular sparse-graph codes,
A. V em, N. T. Janakiraman, and K. R. Narayanan, “Group te sting using left-and-right-regular sparse-graph codes,” CoRR, vol. abs/1701.07477, 2017
2017 arXiv
-
[11]
Optimal dec oding of linear codes for minimizing symbol error rate,
L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal dec oding of linear codes for minimizing symbol error rate,” IEEE Trans. Inf. Theory , vol. 20, no. 2, pp. 284–287, 1974
1974
-
[12]
Optimum detection o f defective elements in non-adaptive group testing,
G. Liva, E. Paolini, and M. Chiani, “Optimum detection o f defective elements in non-adaptive group testing,” in Annu. Conf. Information Sciences and Systems (CISS) , (Baltimore, MD), 2021
2021
-
[13]
Sparse graph codes for non-adaptive quantit ative group testing,
E. Karimi, F. Kazemi, A. Heidarzadeh, K. R. Narayanan, a nd A. Sprintson, “Sparse graph codes for non-adaptive quantit ative group testing,” in IEEE Information Theory W ork. (ITW) , 2019
2019
-
[14]
Non-adaptive quantitative group testing using irregular sparse graph codes,
E. Karimi, F. Kazemi, A. Heidarzadeh, K. Narayanan, and A. Sprintson, “Non-adaptive quantitative group testing using irregular sparse graph codes,” pp. 608–614, 09 2019
2019
-
[16]
Quantitative group testing and the rank of random matrices,
U. Feige and A. Lellouche, “Quantitative group testing and the rank of random matrices,” CoRR, vol. abs/2006.09074, 2020
2006 arXiv
-
[17]
Compressed sensing,
D. Donoho, “Compressed sensing,” IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289–1306, 2006
2006
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.