- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper studies an adaptive search problem in which an unknown set of at most targets must be identified using queries that test whether a subset contains at least one target. The set of queries allowed is adaptive, and may depend on previous answers. An important assumption is that identifying a target from the available information is not by itself sufficient, that is each target must also be confirmed by a positive singleton query before it can be removed from the search space.
The work first establishes a lower bound on the expected number of queries required by any algorithm, in terms of the entropy of the prior distribution and the expected number of targets. It then proposes two algorithms. Exact-SL uses the exact posterior distribution to choose between subset queries and singleton queries that confirm targets, and it achieves a constant-factor approximation to the optimal expected number of queries under a nested-chain condition on the allowed queries. A second algorithm, Fractional-SL, avoids computing the posterior, and instead solves an entropy-regularized convex optimization problem that assigns fractional weights to candidate targets, subject to constraints from previous answers. For this algorithm a bound on the number of queries is shown under nested-prefix and score assumptions, where depends on the score variation and the regularization parameter. The work also gives a lower bound of for Fractional-SL, showing that the dependence on in the upper bound is relevant. The experimental evaluation includes an example demonstrating the limitations of greedy strategies, comparisons with optimal adaptive policies on small instances, and synthetic experiments with multiple targets.
Critical strengths
-
The paper provides rigorous performance guarantees for both proposed algorithms. Exact-SL achieves a constant-factor approximation to the optimal expected number of queries under a nested-chain condition, while Fractional-SL achieves an query bound without requiring the computation of posterior probabilities. There is also a general entropy-based lower bound for any algorithm, and a lower bound on the query complexity of Fractional-SL, though they are both non-tight. The paper also presents an experimental analysis to complement the theoretical findings.
-
The paper considers a search setting in which identifying a target is not sufficient: targets must be explicitly confirmed, and their removal can change the set of admissible queries. This introduces an additional decision into adaptive search, namely how and when to gather information. The resulting problem is interesting from an algorithmic perspective and has potential applications, although its practical relevance depends on the justification of the model assumptions
Critical weaknesses
-
The paper is unnecessarily difficult to follow, in many places. The introduction uses obscure terminology, introduces algorithms and parameters before properly explaining them, and mixes the problem setting with the contributions. Even the relatively simple motivating example is obscured by unnecessarily complicated language. The introduction needs substantial restructuring, starting with a clear explanation and motivation of the model and its assumptions. Moreover, the discussion of related work is insufficient, with important classical results on search and entropy missing (works by Mehlhorn, Knuth etc). The paper does not clearly explain how its theoretical guarantees compare with previous results, what improvements they provide, or which aspects are genuinely new. These shortcomings make it difficult to assess the significance of the contributions.
-
The theoretical guarantees rely on rather certain assumptions on the admissible queries, particularly the nested-chain condition for Exact-SL and the prefix setting for Fractional-SL. It is not clear how broadly these assumptions apply, or which concrete applications abide by these settings. The example in Section 3 also depends heavily on a specially constructed restriction on the queries. Furthermore, the experimental evaluation is entirely synthetic, and does not convincingly establish a consistent advantage over simpler search strategies. It is thus rather difficult to assess the broader applicability and practical significance of the proposed methods. An informative conclusion section would have helped, instead of merely a repetition of the results.
Questions for authors
-
Could you provide concrete applications in which targets must be explicitly confirmed by singleton queries before they can be removed, and in which the admissible queries have the restrictions considered in the paper? In particular, how natural are the nested-chain and nested-prefix assumptions? The separation in Section 3 seems to depend critically on the restricted query family.
-
Could you please explain more more precisely how their theoretical results compare with existing results on adaptive search and correlated group testing, particularly the entropy-based approaches discussed in the related work? Which aspects of the approximation analysis for Exact-SL are new, and what improvements, if any, are obtained over previous guarantees?
-
What is the best approximation ratio that can be obtained from Corollary 4 by optimizing the parameters and ? The paper gives a ratio of approximately 5.08 for and , but these values do not appear to be optimal. Can the authors clarify the best guarantee implied by their analysis and the trade-offs involved in choosing these parameters?
-
Fractional-SL is presented as a scalable alternative to Exact-SL, but Theorem 5 bounds the number of queries rather than the computational cost of selecting them. Is it possible to provide a running-time bound for solving the fractional optimization problem and selecting a query at each step?
-
I have some concerns about the experimental evaluation which appears to rely on synthetic settings that are may favor the proposed approach. In particular, the multi-target experiments use syntetically generated scores that are correlated with the true targets. Are these scores consistent with previous work. Moreover, it appears that in the absence of informative scores, simple prefix bisection performs better than Fractional-SL, and the comparison with Weighted-Split gives mixed results. Can the authors clarify in which settings Fractional-SL is expected to offer a substantial advantage over simpler alternatives, and provide evidence that these settings arise naturally rather than being specific to the chosen experimental construction?
Additional comments for further improvement
- In their AI usage statement, the authors mention using AI tools to improve the wording and flow of the paper. In my opinion, the result has been the opposite. Much of the text, particularly in the introduction, has become unnecessarily obscure, with excessive jargon and convoluted expressions that make relatively simple ideas difficult to understand. I strongly encourage the authors to rewrite these parts in clear, direct language, removing what appears to be automated polishing.
5 comments
Response to sud5 Part 2: Optimized Guarantees and Per-Query Computation
Optimizing Corollary 4 improves its guard-free factor from approximately 5.08 to 4.089. We also derive an explicit per-query computation bound for Fractional-SL at a finite accuracy sufficient to preserve its query guarantee.
1. Best guarantee and parameter trade-off [Q3: Optimizing and ]
Let be binary entropy in nats and . Lemma 8 proves that the factor is globally minimized at $ \alpha^{\star}=\frac{1}{3},\ \lambda^{\star}=3h(1/3)\approx1.90954,\ C^{\star}=3+\frac{\ln 2}{h(1/3)}\approx4.08897. $
For fixed , the minimizing is ; minimizing the resulting one-variable expression gives . The corresponding bounds on expected total queries are:
| Choice of (with ) | No guards needed | With presence guards |
|---|---|---|
| Optimized: | ||
| Experimental: |
The first column of bounds applies when every reached nonterminal state already has certified target presence. Otherwise, full-active guards check whether a target remains, adding at most one call per executed target and one final negative call. OPT uses the same initial information, access rules, and execution requirement.
only sharpens the analysis. changes the policy: increasing it favors singleton execution over batch information. The optimized value gives the best bound from Corollary 4; the experiments retain and correspond to the second row.
Revision: Corollary 4 states both guarantees; Lemma 8 proves the parameter optimum.
2. Cost of computing and selecting a query [Q4: A running-time guarantee for Fractional-SL]
Proposition 17 supplies the computational guarantee. Let , let be the score range, and let be the entropy regularization parameter. Computing feasible weights within error of the exact optimizer takes real-arithmetic operations and storage. Scoring all eligible prefixes and singletons then takes operations. Elementary-function evaluations are counted as unit-cost operations.
The key simplification is that nested positive-set constraints reduce to one inequality on the smallest positive prefix . Solve the budget-only problem first. If its solution meets this inequality, it is optimal; otherwise the constraint binds, separating the problem into mass one inside and the residual budget outside. This requires at most three scalar logistic root searches, followed by a linear scan for query selection.
With , the per-step work at sufficient accuracy is . Under Theorem 5's fixed-prefix assumptions, starting from an empty transcript and with throughout, the total-query bound remains , including guards and target executions. Thus the computation bound explicitly accounts for the accuracy needed by the query analysis.
Revision: Section 5 and Proposition 17 (Appendix D.3) give the solver, accuracy requirement, and complexity proof. Figure 2 and Table 15 report measured decision time and the separate numerical-certification cost.
Response to sud5 Part 3: Real-Data Risk Scores and the Source of Query Gains
We now directly test whether the gains persist when scores come from a predictor trained on real measurements. On held-out APS truck-failure data, Fractional-SL reduces mean queries by 49.9% and 44.7% relative to Weighted-Split in the two tested target-count settings, using identical inputs and an access order independent of scores. Controlled experiments separately test the roles of access order and positive-set constraints.
1. Learned scores on held-out industrial data [W2; Q5: Evidence beyond synthetic scores]
We use the official APS Failure at Scania Trucks dataset [1]. A histogram gradient-boosting classifier is fitted on 48,000 records, with 12,000 for validation, all from the official training file. On the separate 16,000-record test set, average precision is 0.9149 and ROC-AUC is 0.9948. Scores are the classifier's log-odds outputs. Model settings, score transformation, and search parameters are fixed before test evaluation; test labels do not generate or tune the scores.
For simulated prefix/singleton search, we construct 20 groups of candidates for each , with all 5,120 records distinct. Controlled sampling guarantees the supplied bound ; the realized is withheld from policies. Candidate order is independently randomized. All methods share scores, legal queries, state updates, and stopping conditions. Mean total queries, including guards and target execution, are:
| () | Fractional-SL | Periodic-2 | Weighted-Split | Bisection |
|---|---|---|---|---|
| 4 | 11.95 | 13.15 | 23.85 | 32.25 |
| 8 | 24.60 | 30.75 | 44.45 | 59.85 |
The paired Weighted-Split-minus-Fractional differences are and queries (pointwise 95% Student- intervals over the 20 groups). All 160 runs complete correctly. The query advantage thus persists with held-out predictions from real measurements.
Revision: Section 6.2 and Appendix E.1/Table 18. The supplement includes the original data, fixed protocol, trained predictor, predictions, and complete query records.
2. Separating access and positive evidence [W2; Q5: Does the construction favor Fractional-SL?]
Active search uses predictive scores to guide discovery [2]. Our original Gaussian-score experiments control signal strength; the APS experiment supplies learned scores. In both, access can be fixed independently of score ranking. In the controlled physical-order experiment at , Fractional-SL uses 44.05 queries versus 54.30 for Weighted-Split and 59.55 for bisection. The gain therefore does not require arranging the available prefixes by risk score.
The No-Cover ablation changes only the positive-set inequalities, retaining the scores, objective, query selector, positive-evidence filter, and state updates. Removing these constraints increases mean cost in all six informative-score settings by 3.55–7.75 queries; at , the paired increase is .
The constraint assigns at least unit weight to a set known to contain a target, changing subsequent splits and their competition with singleton execution. This isolates the benefit of retaining positive-test evidence beyond the predictive scores themselves.
3. When simpler strategies are competitive [Q5: No-signal results and mixed Weighted-Split comparisons]
The strongest gains occur with informative scores and several targets, where scores and accumulated positive evidence jointly guide the next action. In the controlled experiments, Weighted-Split is slightly cheaper at , the differences at are smaller, and bisection is cheaper in all six no-signal score-order settings. The added APS results test the informative-score regime using an independently trained predictor.
The periodic variant reserves every second scored round for bisection. It lowers Fractional-SL's mean cost in all six no-signal settings; original Fractional-SL is cheaper in five of six controlled informative-score settings and in both APS settings above. This identifies the trade-off between exploiting informative scores and reserving calls for guaranteed splitting progress.
Revision: Tables 12–13 report physical-order comparisons, Table 2 the constraint ablation, and Table 11 the controlled periodic comparison.
Thank you again for your feedback.
References
[1] Scania CV AB. APS Failure at Scania Trucks. UCI Machine Learning Repository, 2016. DOI: 10.24432/C51S51.
[2] R. Garnett et al. Bayesian Optimal Active Search and Surveying. ICML, 2012.
Response to sud5 Part 1: The Model, Its Contribution, and Clearer Presentation
Thank you very much for recognizing the theoretical guarantees and identifying where the presentation obscured them. We have rewritten the introduction, specified a diagnostic model and the relation to prior work, and added learned scores from industrial data. Removing a known target can enable informative tests that remain blocked while it is active. Parts 2 and 3 present the stronger guarantees and new evidence.
1. Actions before terminology [W1; Additional comments: Unclear introduction and excessive jargon]
The introduction opens with a diagnostic situation: a known faulty component makes every group containing it test positive; repairing it can reveal other faults. We then state the query rule and give the example in Figure 1. Querying a removes the known target; the first four of eight remaining candidates can then be tested to distinguish the two halves. Algorithms and contributions follow this explanation.
We replaced unexplained labels with the actions they describe. Section 2 distinguishes knowing a target from removing it, defines positive sets and remaining target count, and explains deterministic answers under a prior. Table 1 pairs results with assumptions. The conclusion explains what the results establish about information gained and access enabled.
2. Why the access and removal rules occur together [W2; Q1: Concrete application and naturalness of the assumptions]
Consider serial diagnosis with a fixed test source, downstream readouts, and local inspection-and-clear actions. A source-to-readout test fails if any component on its path is faulty. Every downstream test traverses upstream components, so a known upstream fault masks later tests until cleared. Inferring the fault does not perform that action; completing maintenance requires clearing each fault.
After cleared and certified-healthy components are omitted from the active list, the effective path tests are active prefixes. Individual actions remain available. This interface satisfies both the legal-chain and fixed-prefix conditions. It combines binary path failures under restricted probing [5] with repair and retesting to expose hidden faults, termed peeling [6, pp. 51–52].
Exact-SL permits the legal chain to change at each reached state. Fractional-SL uses a fixed order under deletions, with risk scores in any order. New Corollary 11 also allows stopping as soon as the target set is identified: the linear–logarithmic separation persists. The separation therefore does not depend on requiring all final target executions.
3. What extends classical search and correlated group testing [W1; Q2: Prior guarantees and new analysis]
Knuth and Mehlhorn [1–3] establish optimal and probability-balanced search trees and their relation to entropy. After the blocking target is removed, our one-target continuation is ordinary binary search. The new issue is which action makes those comparisons available.
Nikpey et al. [4] provide the closest predecessor of the informative-test/high-marginal argument. Their setting permits arbitrary pools and ends at identification. In the extended version, Theorem 4.9 has a target-size-ratio factor when supported sizes lie in [a,b], a>0; Theorem 4.11 gives an alternative with error tolerance.
Our analysis produces a legal progress action from a chain and singletons at each reached state, without arbitrary pools or complements. Charging informative tests to entropy and individual tests to executed targets yields O(H(μ0)+kˉ0+1) expected total queries for arbitrary target-set priors under this condition. Here kˉ0 is the expected residual target count. Required execution makes kˉ0 an unavoidable cost, giving a constant-factor comparison with the optimum under the same access and completion rules. Corollary 4 states this operational guarantee; Part 2 gives its optimized constants.
Revision: Introduction, Sections 2 and 4, Appendix F.1 (diagnostic model), and Appendix G/Table 19 (prior-work comparison).
References
[1] D. E. Knuth. Optimum Binary Search Trees. Acta Informatica, 1971.
[2] K. Mehlhorn. Nearly Optimal Binary Search Trees. Acta Informatica, 1975.
[3] K. Mehlhorn. A Best Possible Bound for the Weighted Path Length of Binary Search Trees. SIAM Journal on Computing, 1977.
[4] H. Nikpey et al. Group Testing with General Correlation Using Hypergraphs. arXiv:2412.17751v2, 2025.
[5] L. Ma et al. On Optimal Monitor Placement for Localizing Node Failures via Network Tomography. Performance Evaluation, 2015.
[6] W. R. Simpson and J. W. Sheppard. System Testability Assessment for Integrated Diagnostics. IEEE Design & Test of Computers, 1992.