acceptodds
Under review as a conference paper at ICLR 2027

When a Known Answer Unlocks Search: Split–Localize Control for Structured One-Sided Search

Abstract

A query whose answer is already known can still be essential for efficient search. We study structured one-sided search in which targets must be explicitly localized before they leave the active query system. On an anchor family, exact one-step information gain and exact discovery gain require expected queries, while executing a zero-information localization first enables search. This motivates *split-localize control*, whose exact-posterior form admits an scored-query bound and a constant-factor total-query guarantee after certification costs are included. We introduce Fractional-SL as a scalable realization based on entropy-regularized action weights. Under fixed nested-prefix geometry, exact optimization, and order-aligned proposal spread , Fractional-SL uses total queries. A one-target family forces Fractional-SL to use queries, exposing its sensitivity to a loose target-count upper bound. With 10,000 tail candidates, Fractional-SL requires 19.63 queries on average versus 5,004.5 for the exact myopic policies. In informative-score multi-target experiments, enforcing the certified positive-set constraint saves 3.55-7.75 queries on average under a same-selector ablation.

Primary area:
learning theory
Keywords:
active search, adaptive querying, group testing, partial feedback, query complexity

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_sud5OpenReview ↗
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 KK 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 O(RKlog⁡n)O(RK\log n) bound on the number of queries is shown under nested-prefix and score assumptions, where RR depends on the score variation and the regularization parameter. The work also gives a lower bound of Ω(Klog⁡(n/K))\Omega(K\log(n/K)) for Fractional-SL, showing that the dependence on KK 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
  1. 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 O(RKlog⁡n)O(RK\log n) 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.

  2. 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
  1. 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.

  2. 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
  1. 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.

  2. 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?

  3. What is the best approximation ratio that can be obtained from Corollary 4 by optimizing the parameters α\alpha and λ\lambda? The paper gives a ratio of approximately 5.08 for α=1/3\alpha=1/3 and λ=1\lambda=1, 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?

  4. 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?

  5. 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
AuthorsOpenReview ↗

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\\{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,b], a>0a>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)O(H(\mu_0)+\bar k_0+1) expected total queries for arbitrary target-set priors under this condition. Here kˉ0\bar k_0 is the expected residual target count. Required execution makes kˉ0\bar 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.

AuthorsOpenReview ↗

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 α\alpha and λ\lambda]

Let hh be binary entropy in nats and cα,λ=min⁡h(α),λα,λ(1−2α)c_{\alpha,\lambda}=\min\\{h(\alpha),\lambda\alpha,\lambda(1-2\alpha)\\}. Lemma 8 proves that the factor (ln⁡2+λ)/cα,λ(\ln2+\lambda)/c_{\alpha,\lambda} 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 α\alpha, the minimizing λ\lambda is h(α)/min⁡α,1−2αh(\alpha)/\min\\{\alpha,1-2\alpha\\}; minimizing the resulting one-variable expression gives α=1/3\alpha=1/3. The corresponding bounds on expected total queries are:

Choice of λ\lambda (with α=1/3\alpha=1/3)No guards neededWith presence guards
Optimized: 3h(1/3)3h(1/3)E[T]≤4.08898,OPT\mathbb E[T]\le4.08898\\,\mathrm{OPT}E[T]≤5.08898,OPT+1\mathbb E[T]\le5.08898\\,\mathrm{OPT}+1
Experimental: 11E[T]≤5.07945,OPT\mathbb E[T]\le5.07945\\,\mathrm{OPT}E[T]≤6.07945,OPT+1\mathbb E[T]\le6.07945\\,\mathrm{OPT}+1

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.

α\alpha only sharpens the analysis. λ\lambda changes the policy: increasing it favors singleton execution over batch information. The optimized value gives the best bound from Corollary 4; the experiments retain λ=1\lambda=1 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 m=∣Ct∣m=|C_t|, let Δt\Delta_t be the score range, and let τ\tau be the entropy regularization parameter. Computing feasible weights within ℓ1\ell_1 error ρ\rho of the exact optimizer takes O(mlog⁡(2+mΔt/(τρ)))O(m\log(2+m\Delta_t/(\tau\rho))) real-arithmetic operations and O(m)O(m) storage. Scoring all eligible prefixes and singletons then takes O(m)O(m) 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 BtB_t. 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 BtB_t and the residual budget outside. This requires at most three scalar logistic root searches, followed by a linear scan for query selection.

With Rt=exp⁡(Δt/τ)R_t=\exp(\Delta_t/\tau), the per-step work at sufficient accuracy is Oλ(mlog⁡(2+mRtlog⁡Rt))O_\lambda(m\log(2+mR_t\log R_t)). Under Theorem 5's fixed-prefix assumptions, starting from an empty transcript and with Rt≤RR_t\le R throughout, the total-query bound remains Oλ(RKlog⁡(en))O_\lambda(RK\log(en)), 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.

AuthorsOpenReview ↗

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 n=128n=128 candidates for each k∈4,8k\in\\{4,8\\}, with all 5,120 records distinct. Controlled sampling guarantees the supplied bound K=8K=8; the realized kk 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:

kk (K=8K=8)Fractional-SLPeriodic-2Weighted-SplitBisection
411.9513.1523.8532.25
824.6030.7544.4559.85

The paired Weighted-Split-minus-Fractional differences are 11.90±1.4011.90\pm1.40 and 19.85±2.1919.85\pm2.19 queries (pointwise 95% Student-tt 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 K=k=8K=k=8, 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 K=k=8K=k=8, the paired increase is 7.75±1.457.75\pm1.45.

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 K=2K=2, the differences at K=4K=4 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.

Reviewer_L4QzOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to find hidden targets when the allowed queries change as targets are tested and removed. In this setting, testing a target whose location is already known can open up useful queries. For example, the authors show that testing and removing a known target first allows logarithmic search, while greedy methods need linearly many queries. Based on this observation, they propose Exact-SL and Fractional-SL, which choose between gathering new information and testing individual targets. They then prove bounds on the number of queries under specific assumptions and use controlled experiments to show when these methods improve on simpler approaches.

Critical strengths

(i) The main example is clear. It shows why testing a target can be useful even when the answer is already known. The greedy methods fail even with exact probabilities.

(ii) The paper gives guarantees for both methods. It also shows why a target-count bound that is too large can slow down Fractional-SL.

(iii) The experiments include useful baselines and a separate test of the positive-set constraints. The authors report both improvements and cases where their method performs worse, including computation time.

Critical weaknesses

(i) The Exact-SL proof appears close to the approach of Nikpey et al (https://arxiv.org/pdf/2412.17751). The new search setting and the Fractional-SL analysis seem to be the stronger contributions.

(ii) The main example requires every target to be tested individually and prevents queries from skipping a known target. A concrete application where both rules are needed would make the motivation stronger.

Questions for authors
  • Theorem 5 assumes that Equation (14) is solved exactly. Let FtF_t be its objective and xt⋆x_t^{\star} its exact optimizer. If a feasible numerical solution satisfies Ft(xt⋆)−Ft(x~t)≤εtF_t(x_t^{\star})-F_t(\tilde{x}_t)\leq\varepsilon_t, how small must εt\varepsilon_t be, in terms of τ\tau, RR, λ\lambda, and ∣Ct∣|C_t|, to preserve the bound T=Oλ(RKlog⁡(en))T=O_{\lambda}(RK\log(en))? Can you verify this condition for the reported runs?

  • In Proposition 6, the weights xv=K/mx_v=K/m lead to Ω(Klog⁡(n/K))\Omega(K\log(n/K)) queries even when k=1k=1. Could binary splitting from adaptive group testing remove this dependence on KK? Specifically, suppose every second scored query tests the first half of the smallest certified positive prefix BtB_t, or its sole element when ∣Bt∣=1|B_t|=1. Would this give T=O(klog⁡(en)+1)T=O(k\log(en)+1), including guards and singleton localizations? How would this variant compare with Fractional-SL on the instances in Table 1?

5 comments
AuthorsOpenReview ↗

Response to L4Qz Part 1: Finite-Accuracy Guarantees and Numerical Certification

Thank you very much for recognizing the known-answer separation and the theoretical and empirical contributions, and for the constructive questions that helped us strengthen the analysis. We now establish an explicit finite-accuracy guarantee with numerical certification, and prove and evaluate your proposed periodic-bisection variant. We also clarify Exact-SL’s relationship to prior work and provide a concrete diagnostic model explaining the two operational rules.

For Q1, the sufficient objective-gap tolerance depends on τ,λ,R\tau,\lambda,R, with no additional ∣Ct∣|C_t| factor. All 32,268 relevant solver states across the revised multi-target, scaling, and APS experiments satisfy it.

1. Dimension-independent tolerance [Q1: Accuracy required to preserve Theorem 5]

Let hh be binary entropy in nats, and let Rt=exp⁡((max⁡vθt(v)−min⁡vθt(v))/τ)≤RR_t=\exp((\max_v\theta_t(v)-\min_v\theta_t(v))/\tau)\le R, with the extrema over the active set CtC_t. Set η=min⁡1/20,h(0.44)/(4λ)\eta=\min\\{1/20,h(0.44)/(4\lambda)\\} and dt=min⁡1/100,η/(4Rt)d_t=\min\\{1/100,\eta/(4R_t)\\}. Under the fixed-prefix assumptions of Theorem 5, starting from an empty transcript, feasible weights satisfying the following condition at every scored state

Ft(xt⋆)−Ft(xt)≤ϵt≤2τdt2F_t(x_t^\star)-F_t(x_t)\le\epsilon_t\le 2\tau d_t^2

preserve the pathwise bound T=Oλ(RKlog⁡(en))T=O_\lambda(RK\log(en)), including guards and singleton executions. A uniform tolerance follows by replacing RtR_t with RR in dtd_t.

The key estimate is that an objective gap of ϵt\epsilon_t bounds both every coordinate error and every query-response surrogate error by ϵt/(2τ)\sqrt{\epsilon_t/(2\tau)}. Entropy regularization lower-bounds the objective gap by τ\tau times the sum of coordinatewise Bernoulli KL divergences. This sum is the KL divergence of two auxiliary product Bernoulli distributions. Pinsker’s inequality bounds the difference in their probabilities of the event that at least one variable in the queried set equals one. The resulting uniform error bound preserves the split-or-localize progress used in Theorem 5.

2. Numerical certification [Q1: Verification for the reported runs]

We verified every Fractional-SL and ordinary periodic-policy solve in the revised multi-target, scaling, and APS experiments. We implemented the specialized nested solver and checked feasibility by exact integer arithmetic on dyadic weights. An interval-evaluated dual upper bound then certifies the objective gap for the implemented inputs and weights.

The largest certified gap-to-tolerance ratio is 8.319×10−138.319\times10^{-13}; no refinement retry was needed. The Fractional-SL query counts in the original Table 1 are unchanged.

Revision: Theorem 5 now includes approximate optimization; Lemma 13 proves the dimension-independent surrogate bound; Proposition 17 gives the solver and certificate. Appendix E reports the numerical verification.

AuthorsOpenReview ↗

Response to L4Qz Part 2: Periodic Bisection and Matched Comparison

Your proposed periodic rule gives O(klog⁡(en)+1)O(k\log(en)+1) total queries, including guards and singleton executions. On the original Table 1 instances, Fractional-SL retains a lower mean query count in five of six cells. Below we give the bound and the matched comparison.

1. A realized-target guarantee [Q2: Removing the supplied-KK dependence]

Count scored rounds globally, excluding guards, and do not reset this counter after a target is executed. On every second scored round, query the first ⌊∣Bt∣/2⌋\lfloor|B_t|/2\rfloor elements of the smallest certified positive prefix BtB_t, or execute its singleton when ∣Bt∣=1|B_t|=1. From an empty transcript with n≥1n\ge1, the total query count obeys T≤2k(⌈log⁡2n⌉+1)+k+1.T\le 2k\bigl(\lceil\log_2 n\rceil+1\bigr)+k+1.

For the single-target family in Proposition 6, this gives T≤2⌈log⁡2n⌉+4T\le2\lceil\log_2n\rceil+4, regardless of the supplied KK.

Between two successful singleton executions, the smallest positive prefix cannot grow. Each forced split at least halves its size up to rounding, or immediately executes a target. Thus each such phase takes at most 2(⌈log⁡2n⌉+1)2(\lceil\log_2 n\rceil+1) scored rounds. There are at most kk phases, at most kk positive guards, and at most one terminal negative guard. This also covers k=0k=0. The bound is independent of scores and optimization accuracy.

2. Matched empirical comparison [Q2: Performance on the original Table 1 instances]

We evaluated exactly this rule with period two on the same n=128n=128 instances, informative scores, and 20 matched seeds per cell. All methods use the same targets, access order, updates, guards, and stopping rule. The table reports mean total queries; the last column is periodic minus Fractional-SL, with a pointwise 95% paired Student-tt interval.

KKkkFractional-SLPeriodicBisectionPaired difference
217.607.409.40−0.20±0.39-0.20\pm0.39
2212.9513.5516.40+0.60±0.44+0.60\pm0.44
4319.3520.2025.60+0.85±0.98+0.85\pm0.98
4424.0524.3532.30+0.30±1.21+0.30\pm1.21
8735.5037.3055.70+1.80±1.19+1.80\pm1.19
8840.9542.4562.70+1.50±0.85+1.50\pm0.85

Both scored policies use fewer queries than pure bisection in all six informative-score cells. In the corresponding six no-signal cells, the periodic variant lowers the mean query count relative to Fractional-SL in every cell. Scheduled bisection supplies the score-independent guarantee; the informative-score results show the query savings retained by scored choices.

With held-out risk scores learned from APS industrial measurements, Fractional-SL also uses 9.1% and 20.0% fewer queries on average than Periodic-2 at k=4k=4 and k=8k=8, respectively, under the same independently randomized access order (Appendix E.1, Table 18).

Revision: Proposition 16 proves the bound, including the general period-qq version. Section 5 states it in the main text; Section 6.2 and Appendix E discuss the comparison, with the full paired results in revised Table 11. Original Table 1 is Table 2 in the revision.

AuthorsOpenReview ↗

Response to L4Qz Part 3: Contribution and Application of the Operational Model

The central contribution is search in which executing a target changes future query access. Exact-SL gives an approximation guarantee for this operational task, and serial diagnosis provides a concrete model in which the two rules in W2 arise together.

1. Exact-SL’s contribution [W1: Relationship to Nikpey et al.]

The informative-test/high-marginal alternative has a clear predecessor in Nikpey et al. [1]; we now identify this connection beside the lemma. Our extension addresses two requirements of the operational model.

First, a chain of legal queries at each reached state suffices to produce an informative batch or a sufficiently likely singleton. The ordering may change across states, and the argument requires neither arbitrary pools nor complements. A known-positive singleton can therefore be selected for the access its execution creates.

Second, the analysis covers execution and certified completion, charging informative rounds to entropy and singleton rounds to executed targets. For initial posterior μ0\mu_0 and expected residual target count kˉ0\bar k_0, any policy with the same access rules and operational endpoint satisfies OPTtotal≥max⁡H(μ0)/log⁡2,kˉ0\mathrm{OPT}_{\mathrm{total}}\ge\max\\{H(\mu_0)/\log2,\bar k_0\\}. Theorem 3 and the guard accounting then give the constant-factor comparison in Corollary 4 for arbitrary target-set priors under the legal-chain condition. The target-count lower bound follows from required execution; Section 6.2 of [1] shows why it need not hold for identification alone.

This positions Exact-SL alongside the paper’s other contributions: the known-answer separation and Fractional-SL’s guarantee without posterior computation, now strengthened to cover finite optimization accuracy and arbitrary score order. Section 4, Appendix G, and Table 19 make the relationship to prior work explicit.

2. Serial fault diagnosis [W2: Why both operational rules arise together]

Consider a serial line with a fixed test source, selectable downstream readouts, and a local inspection-and-clear operation on each component. A source-to-readout test fails exactly when its path contains an uncleared fault. No bypassing follows from the path geometry: every downstream test traverses the upstream components. Individual execution follows from maintenance: inferring a fault does not clear it, and completing the repair task requires clearing each faulty component.

Omitting cleared and certified-healthy components from the active list makes the effective pooled tests exactly its prefixes. With a known fault aa before eight candidates containing one further fault, every pooled prefix initially fails because of aa. Clearing aa makes a test of the first four candidates informative. This is the mechanism in Figure 1, and the interface satisfies both the legal-chain and fixed-prefix conditions.

The model combines established diagnostic mechanisms: Ma et al. [2] study binary path failures under restricted probing; Simpson and Sheppard [3, pp. 51–52] describe repairing a fault and retesting to expose a hidden fault, termed peeling. The revised introduction and Appendix F.1 give the example and its model correspondence.

3. Identification-only separation [W2: Role of mandatory final execution]

New Corollary 11 keeps the same test-and-remove dynamics but permits termination once the target set is identified. The greedy policies still take Θ(m)\Theta(m) expected queries on the anchor instance, while executing the known anchor first gives at most 1+⌈log⁡2m⌉1+\lceil\log_2m\rceil, where mm is the number of tail candidates. Thus the linear-versus-logarithmic gap persists even when final individual execution is waived. Appendix C gives the proof.

Thank you again for your feedback.

References

[1] H. Nikpey, S. Sarkar, and S. Saeedi Bidokhti. Group Testing with General Correlation Using Hypergraphs. arXiv:2412.17751v2, 2025.

[2] L. Ma et al. On Optimal Monitor Placement for Localizing Node Failures via Network Tomography. Performance Evaluation, 2015.

[3] W. R. Simpson and J. W. Sheppard. System Testability Assessment for Integrated Diagnostics. IEEE Design & Test of Computers, 1992.

Reviewer_u3XgOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies the query complexity of unambigously identifying an unknown set of targets A⋆⊆VA^\star\subseteq V (and non-targets alike) within a given finite set VV via sequential interactions with a simple existential oracle Qt↦Yt=1A⋆∩Qt≠∅Q_t\mapsto Y_t = 1\\{A^\star \cap Q_t \neq \emptyset\\}, which, upon receiving an admissble query Qt⊆VQ_t \subseteq V at round tt chosen by a policy from a given set of admissible queries Qt(Ht)\cal{Q}_{t}(\cal{H}_t) as a fuction of the history Ht\cal{H}_t, answers whether there are any targets in QtQ_t (Yt=1)Y_t=1) or not (Yt=0Y_t=0).

The history-dependent set of admissible queries Qt(Ht)\cal{Q}_t(\cal{H}_t) imposes the structural requirements and rules on inquiry. The authors provide theoretical results on expected query complexity under different structural assumptions on the access rule.

Critical strengths

Despite reading it a number of time, I am unable to comprehend this paper other than my summary above.

Critical weaknesses

Despite reading it a number of time, I am unable to comprehend this paper other than my summary above. The presentation of this paper is highly inaccessible and poorly written. It took me multiple reads back and forth between the introduction and problem formulation to get at least a sense of what the paper is about. However, I am still puzzled and cannot assess the paper's stated claims or results.

Questions for authors
  1. nn appears as a key variable from abstract to the very end of the paper and yet I still don't know what it stands for as it is never defined.
  2. What does 'μt\mu_t is exact posterior on Ft\cal{F}_t" exactly mean? what is the prior?
  3. What does BnB_n stand for? What does the "anchor state" mean? I don't understand what to make of the ordering and prefixing.
  4. I don't understand what IG_t and DG_t actually stand for and how they come up.
  5. TT is defined before but I don't understand TMaxIGT_{MaxIG} and TMaxDGT_{MaxDG} stand for as they are never defined. Similarly, the phrases "stated score-order tie-breaking" and "myopic policies" are ambiguous and I don't understand what they are referring to.
  6. what is the residual budget? it was never introduced/defined before line 160. Also, it's unclear if "residual edges" refer to edges of some graph structure.
3 comments
AuthorsOpenReview ↗

Response to u3Xg Part 1: The Search Problem and the Known-Answer Example

Thank you very much for identifying the definitions that made the paper difficult to assess. We have rewritten the opening around a concrete example and defined the notation before using it. The key idea is: a known-answer query can change which informative tests are available next. We answer your questions directly below.

1. Candidates and actions [Q1; Q3: nn, targets, active order, and prefixes]

There are n=∣V∣n=|V| candidates and an unknown target set A⋆⊆VA^\star\subseteq V. A query returns one if it contains a target, and zero otherwise; each call costs one. A positive singleton also removes its target. A positive pooled test supplies evidence without removing targets. Knowing a target's identity does not itself remove it.

Active candidates exclude removed targets and certified non-targets, but may include a known target. An active order lists these candidates; a prefix contains its first several elements. In the example, all active singletons and pooled prefixes are legal. Deletion preserves the order of survivors. Completion means executing every target and certifying that none remain; TT counts calls through that endpoint.

2. The example, before and after removal [Q3: BnB_n and “anchor state”]

The original BnB_n is the set of tail candidates. We now write Bm=b1,…,bmB_m=\\{b_1,\ldots,b_m\\}, reserving nn for the total size. There is one known active target aa and one uniformly located target in BmB_m, ordered as a,b1,…,bma,b_1,\ldots,b_m. Thus n=m+1n=m+1. The “anchor” is aa: every pooled prefix contains it until it is removed.

With eight tail candidates:

  • Before removal: a,b1,…,b4\\{a,b_1,\ldots,b_4\\} is legal but always positive. The pooled tail set b1,…,b4\\{b_1,\ldots,b_4\\} is not a prefix.
  • Execute a\\{a\\}: its answer is already known, but this action removes aa.
  • After removal: b1,…,b4\\{b_1,\ldots,b_4\\} becomes a legal prefix, and its answer distinguishes the two halves. Tail singleton tests remain legal throughout.

The benefit is the informative test enabled by removal, not information in the anchor's answer.

3. Greedy policies and query counts [Q4–Q5: IG, DG, “myopic,” tie-breaking, and TT]

IG is the expected reduction in uncertainty from the next answer. For this deterministic oracle, IGt(Q)=h(pt(Q))\mathrm{IG}_t(Q)=h(p_t(Q)), where pt(Q)p_t(Q) is the posterior probability of a positive answer and hh is binary entropy. DG is the expected number of additional target identities logically certified by the next answer.

MaxIG and MaxDG maximize these respective values. They are myopic: they do not value access enabled for later queries. Ties favor singletons, then the fixed order a,b1,…,bma,b_1,\ldots,b_m; prefix ties favor shorter prefixes. This specifies the original “stated score-order tie-breaking.”

While aa remains, pooled prefixes and a\\{a\\} have zero IG and DG. Uncertain tail singletons have positive value, so both policies test tails individually. Their call counts from this state, excluding its construction, are TMaxIG(m)T_{\rm MaxIG}(m) and TMaxDG(m)T_{\rm MaxDG}(m). Theorem 1 gives expected total cost (m+3)/2(m+3)/2 for each, including target executions.

Removing aa first instead enables bisection, followed by at most one final singleton execution: at most 2+⌈log⁡2m⌉2+\lceil\log_2m\rceil calls. This proves linear expected greedy cost versus logarithmic optimal cost, even with exact probabilities.

Revision: The introduction and Figure 1 give the example first. Sections 2–3 define nn, the state, IG/DG, the policies, tie-breaking, and query-count notation.

AuthorsOpenReview ↗

Response to u3Xg Part 2: Probabilities, Residual Constraints, and Guarantees

Two representations serve different roles: feasible sets record what the observations allow; the posterior assigns probabilities to those possibilities. This distinction explains the remaining notation and the two algorithms.

1. Prior and exact posterior [Q2: μt\mu_t on Ft\mathcal F_t]

Ft\mathcal F_t contains remaining target sets consistent with the observations and supplied constraints. In the anchor state these are a,b1,…,a,bm\\{a,b_1\\},\ldots,\\{a,b_m\\}. The supplied prior μ0\mu_0 gives probabilities to the initially feasible alternatives, conditional on initial evidence. The example assigns each probability 1/m1/m; Exact-SL permits arbitrary target-set priors, including correlations.

After observing queries and answers, μt\mu_t is the conditional distribution of the remaining target set. “Exact posterior” means using this distribution without approximation. A negative query of b1\\{b_1\\} eliminates the first alternative and leaves probability 1/(m−1)1/(m-1) on each remaining one. Answers are deterministic given the query and actual target set; Bayesian uncertainty concerns which set is present.

2. Remaining target count [Q6: “Residual budget”]

KK is the supplied upper bound on target count. If LtL_t contains removed targets, then rt=K−∣Lt∣r_t=K-|L_t| bounds the number still remaining. This counts targets, not available queries: only a positive singleton execution decreases it. In the example it starts at two and becomes one after removing aa.

3. Positive sets [Q6: “Residual edges”]

An unresolved positive pooled test records a set that must contain a remaining target. These are the original “residual edges,” now explicitly defined as positive sets or hyperedges; they need not be graph-vertex pairs.

After removing aa, a positive test of b1,b2,b3,b4\\{b_1,b_2,b_3,b_4\\} records this set. A negative test of b1\\{b_1\\} shrinks it to b2,b3,b4\\{b_2,b_3,b_4\\}. A positive singleton b2\\{b_2\\} removes that target and discharges the constraint, because b2b_2 explains the earlier positive answer.

A feasible remaining target set must lie among active candidates, respect rtr_t, and intersect every unresolved positive set. These requirements define Ft\mathcal F_t in the upper-bound-only model.

Revision: Section 2 gives the definitions and updates under “Recording what the answers imply” and “Prior and posterior.”

4. From these definitions to the guarantees [W: Understanding the paper's claims]

Exact-SL compares information gain with the probability of executing a target. The known anchor has execution value one, despite zero IG and DG. Fractional-SL replaces the exact posterior with fractional weights constrained by the positive sets and target-count bound.

ResultAssumptions and guarantee
Exact-SL: Theorem 3 and Corollary 4Exact posterior, legal singletons, and a legal chain adding one candidate at a time at each reached state. Expected total cost is within a constant factor of the optimum under the same access and execution rules, plus one additive call when presence guards are used.
Fractional-SL: Theorem 5Fixed-order prefixes and singletons, bounded score spread, stated optimization accuracy, and an empty initial transcript. Total queries are Oλ(RKlog⁡(en))O_\lambda(RK\log(en)) for every target set of size at most KK. Here RR measures score spread relative to regularization; λ\lambda is a fixed selection parameter.

Presence guards query the full active set to check whether a target remains. Table 1 collects these guarantees and the known-answer separation. Sections 4–5 explain why the algorithms progress under their respective access conditions.

Thank you again for your feedback. We hope these clarifications and revisions address your concerns and make the paper’s contributions and guarantees clearer.

AuthorsOpenReview ↗

Follow-up to u3Xg on our responses and revision

Thank you again for your careful review and for identifying the points that made the paper difficult to follow. We would be grateful if you could let us know whether our responses and revisions address your concerns.

For ease of reference, Part 1 answers Q1 and Q3–Q5 through the before-and-after example, defining the candidates, legal queries, greedy policies, and query counts. Part 2 answers Q2 and Q6 with explicit prior/posterior and state-update examples, then summarizes the two algorithms’ assumptions and guarantees. The revised introduction and Figure 1 present the example before the formal definitions.

We greatly value the opportunity to discuss the work further with you and address any remaining concerns. If any definition, argument, or claim remains unclear, we would sincerely appreciate your guidance on the specific point and would be glad to provide a focused clarification. Thank you for your time and consideration.

Reviewer_vJnJOpenReview ↗
Rating
1
Confidence
1
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper works on a sequential query decision problem. The agent is required to determine query to be submitted at each round. The query must be selected from limited choices, which is dependent on the query history. After sending the query, the agent would observe a binary variable, suggesting that whether the submitted query contains an element belonging to the target set. The agent wants to identify all the elements int the target set, with as small query cost as possible. This paper constructs examples showing that querying with a deterministic response can still be useful. In addition, they design algorithms with performance guarantee on the expected total query number. Numeric experiments are conducted to validate the efficiency of their proposed algorithm.

Critical strengths
  1. The topic is interesting and meaningful. This paper provides a new case, showing that a query with deterministic information can still provide information.
  2. The paper has covered both theoretical analysis and numeric experiments to support their arguments.
Critical weaknesses

I admit I have difficulty in understanding the terminologies in the paper. It is highly possible that my concern is unreal. And I am willing to follow other reviewers who are able to evaluate the paper with a higher confidence.

  1. A clearer presentation is desired. Some terminologies are used without formal and rigorous definition.

    • Line 47-49: I don't have knowledge on the example "minimal anchor construction". What are "target", "active order", "prefix"? I can only have a random guess like the following.

      Assume the remaining unknown set is {i1, i2, ..., in}. The query must be formulated as {i1, i2, ..., im} for some m<= n. Thus, if the initial set is {a, i1, i2, ..., in}, where aa and one of {i1, i2, ..., in} are positive, we need to first use query {a} to remove the musk.

      But this guess doesn't make sense, as it cannot explain Θ(n)\Theta(n) or Θ(log⁡n)\Theta(\log n) queries. This example doesn't help me capture the intuition of the necessity of "A query with a deterministic response". It only makes me feel more confused.

    • Line 59: What is "presence-certified state"? Does it refer to some possible cases that an algorithm may encounter after sending some queries?

    • Line 111: What is Ht\mathcal{H}_t? Do you mean the sigma-field induced by the query and observation history Qs,Yss=1t−1\\{Q_s, Y_s\\}_{s=1}^{t-1}?

    • Line 119 to 120: This paper claims "This is stronger than merely identifying A∗A^* in a posterior or version space." What's the meaning of "stronger"? If we require the final output is exactly A∗A^*, then I think it is equivalent to identify all the elements in V∖A∗V\setminus A^*, leading to CT=∅C_T=\emptyset.

      I notice that line 122 to 129 is to present the dynamics of agent. What is the definition of "positive edges"? Do you mean (a,b)∈V2:a≠b;a,b∩A∗≠∅\\{(a,b)\in V^2:a\neq b; \\{a,b\\}\cap A^*\neq \emptyset\\}

    • Line 131: What is the "remaining target budget"? Do we have initial budget before any query is made? How do we consume the budget when we make a query?

    • Line 138: This paper denotes μt\mu_t be the posterior of Ft\mathcal{F}_t. I want to confirm what the prior distribution is. It seems the response YtY_t is deterministic regarding QtQ_t. It is confusing that the paper consider Bayesian setting.

    • Line 147: What are "guards"?

    • Line 168: What is the definition of "minimum expected query cost"? Do you mean the minimum total query number required to solve the problems presented by (5)(6)? Or do you mean cost of each query is different, depending on elements inside QtQ_t? What are Q(Ht)\mathcal{Q}(\mathcal{H}_t) in the problem described by (5)(6).

    • Line 173: What are TmaxIG(n),TmaxDG(n)T_{maxIG}(n), T_{maxDG}(n)?

    I didn't put all the points here. I doubt the ambiguity deeply affects my understanding of the paper, and I am unable to judge the contribution of the paper.

  2. I appreciate that the authors are willing to provide a short proof for each of Theorems in the main text. I expect more intuition on each of the main theorems.

Questions for authors

Please clarify the problem dynamics and terminologies mentioned in the subsection "Critical Weaknesses". I will increase my score if the authors are able to answer the concern in the section "Critical Weaknesses" and following questions. I will also hear the opinion from other reviewers.

  1. Is it reasonable to require mandatory singleton localization? It is possible that we never send query that only contains a single element, but we can still conclude a specific element must be in the target set. I want to know the motivation of requiring mandatory singleton localization. Can it help to ease difficulties in the analysis?

  2. At the line 114, the paper claims that "The set-valued map Q(Ht)\mathcal{Q}(\mathcal{H}_t) is part of the problem instance. It may encode prefixes of an active ordering, graph-supported pools, or other structured access rules, and it may change after localization".

    I want to confirm whether all the main theorems (Theorem 3, Corollary 4, Theorem 5) share the same Q(Ht)\mathcal{Q}(\mathcal{H}_t) formulation? Can we explicitly state the Q(Ht)\mathcal{Q}(\mathcal{H}_t) in each Theorem?

  3. I want to know whether we can create a table or a summary that present all the main upper and lower bounds occurred in the main text, which can be helpful for readers to follow the main progress and differences.

5 comments
AuthorsOpenReview ↗

Response to vJnJ Part 1: The Example and Why Target Removal Matters

Thank you very much for your detailed reading and specific questions. They helped us rewrite the introduction, define the actions and state explicitly, and separate the assumptions of the main results. Below we follow the terms in your review. The central distinction is: knowing a target's label does not execute its removal; that removal can make later tests informative.

1. The query interface [W1: “target”, “active order”, and “prefix”]

A target is an element of the unknown set A⋆A^\star. Active candidates exclude certified non-targets and targets already removed; they can include a known target. An active order lists these candidates, and a prefix contains its first several elements. A query reports whether its set contains a target.

In the example, the order is a,b1,…,bma,b_1,\ldots,b_m. Target aa is known; exactly one tail candidate is another target, uniformly distributed. Your interpretation of prefixes is correct. The key additional rule is that every active singleton is also legal, including bi\\{b_i\\}. Before removing aa, a pooled prefix a,b1,…,bj\\{a,b_1,\ldots,b_j\\} is legal, but the pooled tail set b1,…,bj\\{b_1,\ldots,b_j\\} for j≥2j\ge2 is not. A positive singleton tests and removes its target. A positive pooled query records evidence without removing targets.

2. Why the costs differ [W1: The linear–logarithmic gap and the known-answer query]

Greedy search. While aa remains, every pooled prefix returns one regardless of the tail target's location. Testing the known aa also supplies no information or new target identity. An uncertain tail singleton has positive information and discovery value, so both MaxIG and MaxDG test tail candidates individually.

If the target has rank j<mj<m in their fixed testing order, they make jj tail tests and one test of aa. If it is last, m−1m-1 negative tests identify it, but both it and aa still require execution: m+1m+1 calls. Averaging gives (m+3)/2(m+3)/2 total calls.

Remove aa first. One call makes tail prefixes legal. With eight tail candidates, b1,…,b4\\{b_1,\ldots,b_4\\} can now distinguish the two halves. Bisection identifies the target in at most ⌈log⁡2m⌉\lceil\log_2m\rceil calls, followed by at most one final singleton execution. Total cost is at most 2+⌈log⁡2m⌉2+\lceil\log_2m\rceil, with lower bound log⁡2m\log_2m.

The answer to a\\{a\\} carries no information; executing it enables informative tests that both greedy policies postpone.

Revision: The introduction and Figure 1 explain the example before the model. Section 3 defines both greedy policies and derives the costs above.

3. Knowing versus removing [W1: Why identifying A⋆A^\star need not give CT=∅C_T=\varnothing]

You are right that identifying A⋆A^\star also identifies every non-target. The distinction is the definition Ct=V∖(Lt∪Nt)C_t=V\setminus(L_t\cup N_t): LtL_t records targets already tested individually and removed; NtN_t records certified non-targets. A known target enters LtL_t only when its removal is executed.

For example, if aa is the known sole target and all other candidates are certified non-targets, then Ct=aC_t=\\{a\\} until a\\{a\\} is queried. Every label is known, but one action remains. Operational completion requires LT=A⋆L_T=A^\star and CT=∅C_T=\varnothing.

4. Why the local action is needed [Q1: Motivation for “mandatory singleton localization”]

In serial diagnosis, source-to-readout tests traverse prefixes, while a local action inspects and clears one component. Inferring an upstream fault does not repair it: it continues to mask downstream tests until cleared. Completing maintenance requires clearing every fault. This model combines binary path-failure tests under restricted probing [1] with repair and retesting to reveal hidden faults (“peeling”) [2, pp. 51–52].

We also separate the access mechanism from the final execution requirement. New Corollary 11 permits stopping once all target identities are known, while retaining the same test-and-remove dynamics. Greedy search still costs Θ(m)\Theta(m) in expectation; removing aa first costs at most 1+⌈log⁡2m⌉1+\lceil\log_2m\rceil. Thus the search separation persists even when final individual execution is waived.

Revision: Section 2 defines the distinction between knowing and removing; the introduction and Appendix F.1 give the diagnostic model; Section 3 and Appendix C give the identification-only result.

References

[1] L. Ma et al. On Optimal Monitor Placement for Localizing Node Failures via Network Tomography. Performance Evaluation, 2015.

[2] W. R. Simpson and J. W. Sheppard. System Testability Assessment for Integrated Diagnostics. IEEE Design & Test of Computers, 1992.

AuthorsOpenReview ↗

Response to vJnJ Part 2: State, Probabilities, and Query Costs

The remaining parts of W1 concern the information available to the policy and what each query changes. We still use the same terms as your review.

1. History and probabilities [W1: “sigma-field”, the prior, and deterministic responses]

History. Ht\mathcal H_t is the observed transcript ((Qs,Ys))0≤s<t((Q_s,Y_s))_{0\le s<t} together with initial evidence. Conditioning on it means conditioning on its generated sigma-field σ(Ht)\sigma(\mathcal H_t).

Prior and posterior. The supplied μ0\mu_0 is a distribution over initially feasible remaining target sets, conditional on initial evidence. In the example, each a,bi\\{a,b_i\\} has probability 1/m1/m. The family Ft\mathcal F_t records feasible remaining sets; μt\mu_t is the conditional distribution of A⋆∖LtA^\star\setminus L_t given the transcript.

Deterministic answers. The answer is fixed given both the query and actual target set; the policy does not know that set. With two equally likely target locations, querying one has positive-answer probability 1/21/2 despite a noiseless oracle. The randomness concerns which target set is present.

2. Evidence and target count [W1: “positive edges” and “remaining target budget”]

Positive edges. A positive pooled test of u,v,w\\{u,v,w\\} says at least one member is a target. Such a set can have any size: it is a hyperedge, not necessarily a vertex pair. Pt\mathcal P_t stores unresolved positive sets. A negative answer deletes tested candidates from them. A positive singleton removes its target and discharges every set containing it, since that target explains the earlier positive answer. Other sets remain constraints.

Remaining target budget. KK is the supplied target-count upper bound, and rt=K−∣Lt∣r_t=K-|L_t| bounds the number still remaining. A positive singleton decreases it by one; other queries leave it unchanged. It counts possible remaining targets, not remaining queries.

3. Presence and guards [W1: “presence-certified state” and “guards”]

A state is presence-certified when the evidence guarantees a remaining target; an unresolved positive set supplies this certificate. A guard queries the full active set when candidates remain but presence is uncertified. A negative answer certifies completion; a positive pooled answer supplies a positive set; a positive singleton executes its target. Every guard costs one query. Extra knowledge, such as an exact target count, can sometimes establish presence or completion directly.

4. Costs and policy notation [W1: “minimum expected query cost” and the TT variables]

Cost. Each call costs one, regardless of set size; a singleton's cost includes test-and-remove. The optimum minimizes expected calls under the same initial information, legal queries, and completion requirement. Expectation is over the target-set prior and any policy randomization. The anchor's legal queries are active singletons and active-order prefixes.

Policies. MaxIG maximizes information from the next answer; MaxDG maximizes the expected number of newly certified target identities. Their TT variables count calls from the anchor state, excluding its construction. Theorem 1 gives their expectations. Ties favor singletons, then the fixed candidate order; prefix ties favor shorter prefixes.

The original example used nn for tail size. The revision uses mm for that size and reserves n=∣V∣n=|V| for the total: here n=m+1n=m+1. Thus TMaxIG(m)T_{\mathrm{MaxIG}}(m) and TMaxDG(m)T_{\mathrm{MaxDG}}(m) refer to the original policies and costs with clarified notation.

Revision: Section 2 groups these definitions under “Recording what the answers imply,” “Prior and posterior,” and “Checking whether any target remains.” Section 3 defines the policies, costs, and tie-breaking; Appendix A gives the exact state and posterior updates.

AuthorsOpenReview ↗

Response to vJnJ Part 3: Query Assumptions, Proof Intuition, and Guarantees

The theorems use different access assumptions. Exact-SL needs a legal chain at each reached state; Fractional-SL uses one fixed order updated by deletion. Below we specify the families, explain the progress arguments, and collect the requested bounds.

1. Which queries must be legal [Q2: The query family for each theorem]

Theorem 3 and Corollary 4. Let Pt,jP_{t,j} be the first jj candidates of an ordering of CtC_t. At each presence-certified state, legal queries must include v:v∈Ct∪Pt,j:2≤j<∣Ct∣⊆Q(Ht)\\{\\{v\\}:v\in C_t\\}\cup\\{P_{t,j}:2\le j<|C_t|\\}\subseteq\mathcal Q(\mathcal H_t).

The ordering may change with the transcript; other legal queries may coexist. The guarded form of Corollary 4 also requires the full active set to be queryable when presence is uncertified.

Theorem 5. Fix an initial order and preserve the relative order of surviving candidates. The controller uses its active prefixes and all active singletons, including the full-active guard. Scores need not follow this order. The bound assumes bounded score spread and exact optimization or the feasible approximation accuracy now stated in the theorem.

The added APS experiment illustrates this fixed-order setting, with independently randomized access order and risk scores learned only from separate training data. At n=128n=128, K=k=8K=k=8, mean total queries are 24.60 for Fractional-SL, 30.75 for Periodic-2, 44.45 for Weighted-Split, and 59.85 for bisection. These simulated searches use held-out industrial measurements [1]; Appendix E.1/Table 18 gives the protocol and paired intervals.

2. Why the guarantees hold [W2: Intuition beyond the proof sketches]

Exact-SL. If no candidate has high target probability, adding candidates to a legal prefix one at a time must produce a balanced response probability. A chosen action thus either gains a definite amount of information or has a definite probability of executing a target. Initial entropy bounds cumulative information gain; expected target count bounds successful executions. Charging queries to these two forms of progress gives Theorem 3; counting completion checks gives Corollary 4.

Fractional-SL. A positive set must receive at least unit weight. With small weights, the chosen prefix progresses under either answer: a positive answer narrows the known-positive prefix, and a negative answer deletes candidates. With large weights, the selected batch is short or the remaining pool is small. Counting these reductions and executions gives the bound. The argument uses constrained weights, not an assumption that they equal posterior probabilities.

3. Upper and lower bounds [Q3: A summary table]

Write H=H(μ0)H=H(\mu_0) for initial entropy in nats, kˉ0\bar k_0 for expected remaining targets, kk for realized targets, and KK for the supplied bound. TT counts all calls; T+T_+ excludes guards. Let c=min⁡h(α),λα,λ(1−2α)c=\min\\{h(\alpha),\lambda\alpha,\lambda(1-2\alpha)\\}, where hh is binary entropy, 0<α<1/20 < \alpha < 1/2, and λ>0\lambda>0 weights singleton selection.

ResultConditionsBound
General lower boundIdentify and execute targets; certify completionOPT≥max⁡H/log⁡2,kˉ0\mathrm{OPT}\ge\max\\{H/\log2,\bar k_0\\}
Theorem 1Known anchor; one uniform tail target; prefixes and singletonslog⁡2m≤OPT≤2+⌈log⁡2m⌉\log_2m\le\mathrm{OPT}\le2+\lceil\log_2m\rceil; greedy mean (m+3)/2(m+3)/2
Theorem 3Exact posterior; legal chain at each reached stateE[T+]≤(H+λkˉ0)/c\mathbb E[T_+]\le(H+\lambda\bar k_0)/c
Corollary 4Same chain; full-active guardsE[T]≤(H+λkˉ0)/c+kˉ0+1\mathbb E[T]\le(H+\lambda\bar k_0)/c+\bar k_0+1; constant-factor comparison to OPT plus one call
Theorem 5Fixed prefixes; bounded spread RR; stated solve accuracy; empty initial transcriptT=Oλ(RKlog⁡(en))T=O_\lambda(RK\log(en))
Proposition 6Exact Fractional-SL; zero scores; λ=1\lambda=1; sole target lastT=Ω(Klog⁡(n/K))T=\Omega(K\log(n/K)) as n/K→∞n/K\to\infty
Proposition 16Fixed prefixes; bisection every q≥1q\ge1 scored rounds; empty initial transcriptT≤qk(⌈log⁡2n⌉+1)+k+1T\le qk(\lceil\log_2n\rceil+1)+k+1

Here n=∣V∣n=|V|, mm is the anchor's tail size, and RR bounds exp⁡((max⁡θt−min⁡θt)/τ)\exp((\max\theta_t-\min\theta_t)/\tau) over active candidates and scored states. Corollary 4's factor is (log⁡2+λ)/c(\log2+\lambda)/c without guards; guards add one to the factor and one additive call.

Revision: Table 1 presents this map of assumptions and results. Sections 4–5 now explain the legal queries and main proof ideas alongside each guarantee.

We thank you again for your detailed feedback.

Reference

[1] Scania CV AB. APS Failure at Scania Trucks. UCI Machine Learning Repository, 2016. DOI: 10.24432/C51S51.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.