acceptodds
Under review as a conference paper at ICLR 2027

From Ranking Quality to Query Complexity: Exact-AUC Minimax Recovery with Ordinal Predictions

Abstract

We characterize the minimax adaptive-query complexity of every exact-AUC class in noiseless group testing with a known number of positives. For positives among items, let . The complexity is for ; the classes with are singletons and require no queries when AUC is known. The curve exhibits a regime in which candidate counting is insufficient: for , log-cardinality is , yet recovery requires OR queries. We obtain matching lower bounds by constructing hard families at every prescribed rank sum. One explicit algorithm, given neither AUC nor a candidate class, attains all these class-wise rates up to universal constants and an additive constant. The characterization also identifies how ranking accuracy must scale with sparsity to permit query budgets. Within the same exact-AUC class, however, supports recoverable by this algorithm in queries can coexist with subfamilies requiring queries in the worst case. Certified finite-class budgets and numerical constructions illustrate the query obstruction and the within-class separation.

Primary area:
learning theory
Keywords:
adaptive group testing, query complexity, ranking quality, side information, support recovery

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_UkbbOpenReview ↗
Rating
2(+1)
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies asymptotic minimax complexity for detecting positives from a set of items under the group testing framework. The authors also provide tight lower bounds by constructing hard instances and also study the complexity tradeoff under sparsity as well.

Critical strengths

This paper characterizes the number of queries required to identify a positive set of size ss, given that its ranks ρ1<⋯<ρs\rho_1<\cdots<\rho_s have a prescribed total displacement D=∑i=1s(ρi−i)D=\sum_{i=1}^{s}(\rho_i-i) from the top ss positions. All ranks are measured with respect to a total order qq fixed before querying.

Critical weaknesses

I divide my criticism of the paper into three parts. a) Lack of connection to machine learning and b) Presentation and clarity issues.

Lack of connection to machine learning

I tried to read this paper carefully but I could find only minimal connection to machine learning, nor did the authors try to make any connection to machine learning community apparent in the paper. This seemed to me like a paper that might go into an Algorithms conference provided the writing and presentation issues are fixed in the paper.

Clarity issues

I found the paper quite hard to read and I feel that a lot of notations and terminologies are not set up the way they should be set up actually. Let me point a few of these below.

In section 3.2, the authors actually try to give the construction of a lower bound without being explicit about it. From section 3.2, the authors use terms like common active set, mutually disjoint negative pairs and the notion of a tree is never defined here at all actually. This makes the paper very hard to read without defining these technical terms. This problem remains throughout the paper.

Questions for authors

Please refer to the weakness section above.

5 comments
AuthorsOpenReview ↗

Response to Ukbb Part 1: What a learned ranking guarantees about downstream recovery

Thank you very much for identifying where the ML connection and mathematical setup needed clearer explanation. Your comments prompted us to make the prediction-to-measurement connection explicit and revise the exposition across Sections 2–5. Our question is: how much can a learned ranking reduce the measurements needed to identify all positives?

1. From ranking evaluation to downstream measurement cost [W1: connection to ML].

A model ranks candidates before screening, while their true labels remain unknown. A pooled OR measurement asks whether a selected group contains a positive. The recovery algorithm uses the ranking and known positive count s to choose its tests.

Of the s(d−s)s(d-s) positive-negative pairs, let D be misordered. Empirical AUC is then 1−D/[s(d−s)]1-D/[s(d-s)]. This D also equals the total displacement of positive ranks from the first s positions: fixing the rank sum specifies exactly the possible labelings at a given AUC.

AUC evaluates pairwise ordering; our question is how that predictive quality translates into the cost of acquiring the remaining labels. When a learned ranking guides pooled screening, its operational value depends on the measurements it saves. The exact-AUC curve makes this connection quantitative: it gives the optimal worst-case recovery budget guaranteed by each quality level and shows how the required accuracy changes with sparsity.

This provides a task-dependent interpretation of ranking performance. A high AUC alone can conceal whether the prediction improves the recovery order; the characterization identifies when it does. The recovery algorithm receives only the ranking and s, not AUC, so the quality measure defines the performance benchmark without becoming an additional input required to exploit the prediction.

2. What this tells us about learned predictions [W1: implications for ML].

  • Accuracy must scale with sparsity. On the high-AUC side, an O(s)O(s) class-wise budget is attainable exactly when AUC error is O(s/(d−s))O(s/(d-s)). Even AUC 0.99 can leave worst-case recovery at the same query order as unranked search when positives become sparse.
  • Equal AUC permits different recovery costs. At 524,288 items and identical AUC and positive count, inference-wrapped U takes 151 queries on the easy support versus 664.96 on average over 48 uniform hard-family draws. AUC determines the class envelope; positive-rank geometry captures variation within it.
  • Quality need not be supplied to be exploited. One explicit algorithm attains every AUC-aware class rate, up to constants and an additive constant, using the ranking directly.

Revisions: The Introduction now opens with this prediction-to-measurement problem. Section 3.4 develops the sparsity-dependent accuracy requirement; Sections 6.2–6.3 evaluate learned HIV/PCBA rankings and same-AUC recovery costs. Our second response explains the changes to definitions and proofs.

AuthorsOpenReview ↗

Response to Ukbb Part 2: Clarifying the setup, algorithm, and lower-bound construction

We revised Section 3.2 to state its lower-bound objective, start with a concrete example, and define the decision tree before deriving the bound. We also clarified the surrounding setup and algorithm descriptions. The key argument is self-contained below.

1. What the sets and pairs mean [W2: candidate sets and terminology].

A support is the set of positive ranks; a candidate support is one possible labeling at the prescribed positive count and AUC. To lower-bound the entire class, it suffices to construct a hard subfamily.

Take s=6s=6, D=4D=4, and d≥12d ≥ 12. Let W be the first eight ranks, with later ranks negative:

CandidatePositive ranksDeleted pair
S11, 2, 4, 5, 6, 73, 8
S21, 2, 3, 5, 6, 84, 7
S31, 2, 3, 4, 7, 85, 6

The original “common active set” W contains every candidate support. Each candidate deletes one pair, making that pair negative. “Mutually disjoint” means no rank belongs to two listed pairs. Every pair sums to 11, so each support has rank sum 36−11=2536-11=25 and displacement 25−21=425-21=4, hence identical AUC.

2. Why pooling cannot split this family evenly [W2: meaning of disjoint negative pairs].

An OR query is positive if its pool contains a positive item. Testing rank 3 gives a negative answer only for S1. Testing ranks 3 and 4 together is positive for all three candidates and reveals nothing.

A query is informative when its answer differs across remaining candidates. For a negative answer, every queried rank inside W must lie in the true deleted pair. Disjointness therefore allows at most one candidate to answer negatively; a positive answer retains all the others. Equal pair sums keep AUC fixed; disjointness restricts discrimination.

3. From this obstruction to a query lower bound [W2: decision tree and lower-bound objective].

A deterministic adaptive procedure is a binary decision tree: internal nodes specify queries, branches specify answers, and leaves output supports. Each informative negative branch isolates at most one candidate; the positive branch continues. A depth-t tree can therefore be correct on at most t+1t+1 candidates.

For a randomized procedure with uniform budget t, fix its seed and apply the same bound. Averaging over m equally likely candidates and then over the seed gives average success at most (t+1)/m(t+1)/m. Per-candidate success of at least 2/3 requires t≥2m/3−1t ≥ 2m/3-1.

Our general construction gives m proportional to D at every 2≤D≤s2 ≤ D ≤ s, with all candidates at exactly that displacement. This proves the linear-in-D lower bound.

4. Clarifications throughout the main text [W2: clarity beyond Section 3.2].

Beyond the example and tree argument in Section 3.2, we made these changes:

  • Section 2: define support and rank coordinates, and distinguish instance cost TA(S)T_A(S) from the class-wide uniform budget M(d,s,D)M(d,s,D).
  • Section 3: map the upper bounds and three lower-bound constructions before developing them.
  • Section 4: explain the boundary window and rank-band fallback before the pseudocode; spell out generalized binary splitting and the scheduling rule.
  • Section 5: describe the relevant classes through bandwise positive counts and common displacement.

We sincerely hope our revisions and responses address the concerns you raised and provide a clearer basis for reassessing the paper's contribution and relevance to the ML community.

Thank you again for your feedback. For details, please refer to the revised paper.

AuthorsOpenReview ↗

Follow-up to Ukbb on our response

Thank you again for taking the time to explain your concerns. We hope the clearer ML connection, revised definitions, and worked example address the issues you raised. Could you let us know whether any concerns remain? We would greatly appreciate your updated assessment and the opportunity to discuss them further with you.

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

This paper studied the problem of ranking quality and query complexity for exact-AU in noiseless group testing with a known number of positives. The authors analyzed the query complexity of positive items and also constructed matching lower bounds. The authors also developed an explicit AUC-oblivious algorithm, given neither AUC nor a candidate class, attains all the class-wise rates up to universal constants and an additive constant. The authors also identified how ranking accuracy must scale with sparsity under query budget constraints. The authors also conducted numerical experiments to illustrate and verify their theoretical results.

Critical strengths
  1. This paper studies a fundamental problem in AUC-based ranking quality and query complexity.

  2. This paper is theoretically deep and provides tight upper and lower bounds for the problem.

  3. The authors provided numerical experiments in addition to theoretical studies.

Critical weaknesses
  1. The paper is not reader-friendly for non-specialist in this area.

  2. The numerical study is inadequate.

Questions for authors
  1. The presentation of the paper can be improved. Although easy to follow in general, this paper can benefit from providing more background and using some simple illustrative examples to highlight their key ideas.

  2. Also related to the previous point, right now the authors only provided their main theoretical results without discussing the related work and current state of the art in the literature. It is unclear what are the current gaps and state of the art results. Could the authors provide more in-depth discussions on the novelty of this paper, the major challenges in proving the upper and lower bounds, and the key idea in their proofs and analysis?

  3. The current experiments only use d=4,…,9d=4,\ldots,9 and s∈[0,⌊d/2⌋]s\in[0,\lfloor d/2 \rfloor], which is very small scale, although I understand the major contributions of this work are theoretical. Nonetheless, could the authors conduct larger-scale experiments to further verity their theoretial results?

5 comments
AuthorsOpenReview ↗

Response to fAJv Part 1: The contribution, proof mechanisms, and a concrete example

Thank you very much for recognizing the theoretical depth and tight bounds, and for requesting clearer examples, a fuller comparison with prior work, and larger experiments. These thoughtful suggestions helped us clarify the proof mechanisms and extend evaluation to 524,288 items. We address the theory and exposition here; our second response presents the numerical evidence.

1. The gap resolved by the characterization [Q2: novelty and prior work].

General group-testing results analyze recovery over candidate families or hypergraphs [1,2]. Our contribution determines the complexity of families specified by a standard ranking metric: matching rates in population size, positive count, and AUC at every feasible displacement, attained by one algorithm without receiving AUC.

The curve has three regimes: linear in displacement near a perfect ordering, a plateau of order s, and logarithmic growth at larger displacement. For 2≤D≤s2 ≤ D ≤ s, log-cardinality is of order D\sqrt{D}, yet recovery requires linearly many queries in D. The challenge is to realize this query obstruction at every prescribed rank sum and obtain matching constructions across the remaining regimes. Candidate counting alone cannot supply the curve.

2. A concrete example of the lower-bound mechanism [W1: accessibility; Q1: illustrative example].

An OR test is positive exactly when its pool contains a positive item. Take s=6s=6, D=4D=4, and d≥12d ≥ 12. Delete one pair from the first eight ranks; all later ranks are negative:

CandidateDeleted ranksTest rank 3Test ranks 3 and 4
S13, 8NegativePositive
S24, 7PositivePositive
S35, 6PositivePositive

Each pair sums to 11, leaving positive-rank sum 36−11=2536-11=25 and displacement 25−21=425-21=4. Thus AUC is identical. Testing rank 3 identifies S1 on a negative answer; pooling ranks 3 and 4 reveals nothing.

More generally, an informative OR query can be negative only when its tested ranks within the first eight lie in the deleted pair. Disjointness allows at most one candidate to answer negatively. For m such candidates, a depth-t decision tree can be correct on at most t+1t+1: each negative branch isolates one, while the positive branch continues. Fixing the seed of a randomized algorithm with uniform budget t gives the same bound. Average success over a uniform candidate is at most (t+1)/m(t+1)/m, so per-candidate success of at least 2/3 requires a linear budget.

3. How the bounds cover every quality level [Q2: proof challenges and key ideas].

For the lower bounds, equal-sum deleted pairs give the boundary regime. Shifting this construction produces the order-s plateau while preserving the prescribed displacement. At larger displacement, symmetric positive-rank pairs generate enough supports at exactly the required sum for a matching counting bound.

For the upper bounds, small displacement forces a positive prefix and negative suffix, confining uncertainty to a short window. At larger displacement, rank-sum counting and weighted candidate search [1] give the matching rate. The explicit algorithm attains these rates through top-s verification, expanding boundary windows, and rank-band recovery in both directions, without candidate enumeration.

Revisions: The Introduction and Appendix D explain the gap and related work. Sections 2–4 clarify the setup, introduce the worked example and query tree, and separate class-aware bounds from the AUC-oblivious algorithm.

[1] E. Triesch. A group testing problem for hypergraphs of bounded rank. Discrete Applied Mathematics, 1996.

[2] M. Gonen, M. Langberg, and A. Sprintson. Group testing on general set-systems. ISIT, 2022.

AuthorsOpenReview ↗

Response to fAJv Part 2: Large-scale experiments expose the three regimes and same-AUC separation

We added 18,590 verified recovery runs, reaching 524,288 items, to examine the three regimes and growing same-AUC separation. The small-class computations remain as exact finite-budget benchmarks.

1. Recovery across regimes and scales [W2: numerical evidence; Q3: larger scales].

At (d,s)=(4096,16),(16384,32),(65536,64)(d,s)=(4096,16),(16384,32),(65536,64), a fixed displacement grid spans both orientations, both transitions, and the center: 69 distinct class-orientation settings. Supports instantiate the proof constructions: deleted-pair families are enumerated; symmetric-pair families use 48 independent uniform draws.

We compare U, rank-band recovery, and generalized binary splitting (GBS) under predicted and random orders, with eight random permutations per support. The GBS variants differ only in input order; grouping, splitting, inference, and stopping rules are identical.

Inference-wrapped U uses fewer mean queries than both GBS variants in 66/69 settings, including all 30 with Δ≤sΔ ≤ s. Perfect forward/reverse rankings take one/two queries. GBS is cheaper at the three central settings. These results locate the boundary savings and show that they persist with scale. Figure 2 reports the comparison; Appendix F.3 also plots costs relative to the theoretical rate and family-specific lower bounds.

2. Same AUC, widening cost separation [W2: evidence for separation; Q3: scaling].

Each row pairs an easy support with a hard family at exactly the same positive count and rank sum. Both cost columns use inference-wrapped U; the hard mean averages 48 uniform draws.

Items dPositives sShared AUCEasy costHard meanHard-family budget LB
1,02480.9094494063.3525
8,192160.95401270135.2373
27,648240.96915796214.81129
65,536320.976795121298.81190
221,184480.984480138476.04319
524,288640.988341151664.96457

At the largest size, the difference is 4.40-fold; the hard-mean 95% bootstrap interval is [660.10, 669.88]. The last column is algorithm-independent: exact family counts lower-bound the uniform budget of any algorithm succeeding with probability at least 2/3 on every member, even when told the family. Its 457-query bound exceeds the easy-support cost by more than threefold. Figure 3 and Appendix F.4 report the separation, exact counts, and uniform sampler.

3. Exact finite budgets complement the scaling evidence [W2: numerical validation].

We retain certified optima for 156 exact-AUC classes, checked through integer decision-tree witnesses and rational probability certificates. Separately, exact partition counts and the deleted-pair budget expose the entropy gap: at D=s=2048D=s=2048, d=4096d=4096, full-class log-cardinality is about 153.67 bits, but the subfamily requires a 683-query budget.

All 18,590 added runs recover exactly. The recovery generators and inference rules are unchanged; only query-mask construction was accelerated and checked against the submitted implementation.

Revisions: Sections 6.2–6.3 and Figures 2–3 present the scale experiments; Appendices F.3–F.4 give protocols and uncertainty estimates. The supplementary package includes sampled supports, per-run costs, and reproduction code.

Thank you again for your feedback. For details, please refer to the revised paper.

AuthorsOpenReview ↗

Follow-up to fAJv on our response

We appreciate your suggestions, which helped improve both the presentation and numerical evaluation. We hope the worked example, fuller discussion of related work and proof ideas, and larger-scale experiments address your concerns. We would welcome your thoughts on the revised paper and the chance to discuss any further questions you may have.

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

This work studies a special case of group testing whether the uknown S has s positive elemnts and their sum is equal to R. The learner has access to an oracle Y(Q) that for a chosen query set Q, Y(Q) returns true if Q intersects with the target set S and false if they are disjoint. The authors show that the query complexity for this adaptive group testing problem is roughly min(\Delta, s) + s \log (1 + \Delta/s^2) where \Delta is the displacement measure, i.e., if the elements of S have positions \rho_1, \ldots, \rho_s then D = \sum_{i=1}^s (\rho_i - i) and \Delta is min(D, s(d-s) - D) (minimum over both original and reverse order of elements). Since \Delta is at most s(d-s)/2, the query complexity given in this work is always at least as good as generic group testing (without the additional sum = R structure) and in the worst case we get back to the standard s \log(d/s) query complexity.

Critical strengths
  1. I think studying the adaptive query complexity for the class of fixed sum sets is clean and interesting. The adaptive group-testing complexity for fixed-cardinality, fixed-sum supports provides a precise way to analyze the recovery value of an ordinal ranking.

  2. The given theoretical results give a tight characterization of the query complexity for the problem. The provided matching bounds cover every feasible displacement.

  3. The algorithm doesn't require knowning the displacement D and efficiently attains the best possible rates.

Critical weaknesses
  1. I am not sure how relevant this is to a broader ML audience as the setting seems somewhat specialized. Moreover, the practical implementation of the algorithm seems to underperform in some of the experiments presented in this work. In the held-out HIV/PCBA study (see Table 4), the method seems to underperform both GBS baselines in all settings, requiring 13.7%–47.5% more mean queries than random-order GBS.
Questions for authors

How does this model and work compare to other query-complexity characterizations such that given in [1]?

[1] https://arxiv.org/abs/2405.07937

5 comments
AuthorsOpenReview ↗

Response to BGqK Part 1: ML relevance and relation to Kontonis et al. [1]

Thank you very much for recognizing the tight bounds and AUC-oblivious attainment. Your insightful questions helped us sharpen the ML connection and comparison with [1]; your empirical concern motivated the guarded variant in our second response. The central question is: what recovery budget does a learned ranking's quality guarantee?

1. Ranking quality as a resource for recovery [W1: relevance to ML].

A learned model orders candidates before screening; pooled measurements then identify the positives. We characterize how ranking quality controls this measurement cost, without requiring calibrated probabilities or a particular ranker.

On the high-AUC side, an O(s)O(s) class-wise query budget is attainable exactly when the AUC error is O(s/(d−s))O(s/(d-s)). Thus even AUC 0.99 can leave the worst-case recovery order unchanged as positives become sparse. This gives a sparsity-dependent accuracy requirement for downstream savings. Corollary 2 extends the characterization to classes specified by a lower bound on AUC.

2. What the characterization adds to [1] [Q1: relation to the general query framework].

Kontonis, Ma, and Tzamos study how query-language complexity controls labeling complexity. Their Appendix D, Theorem 38, gives general query-dimension bounds for a fixed hypothesis class and query family. Our exact-AUC problem fits this framework; our contribution resolves the complexity of these ranking-quality classes explicitly.

AspectKontonis et al. [1]Our work
ObjectHypothesis classes and region-query familiesExact-AUC classes under fixed OR queries
BoundsGeneral bounds through VC and query dimensionsMatching rates in population size, positive count, and AUC at every feasible displacement
AlgorithmLearning for specified hypothesis and query classesExplicit attainment of all class rates without receiving AUC or enumerating candidates

The technical challenge is to obtain matching bounds at every prescribed rank sum. For 2≤D≤s2 ≤ D ≤ s, log-cardinality is of order D\sqrt{D}, yet OR-query complexity is linear in D. Our constructions realize this obstruction at each displacement and connect it to the plateau and logarithmic regimes.

3. The same family separates query mechanisms [Q1: role of query expressiveness].

Take m supports obtained by deleting one of m disjoint, equal-sum pairs from a common set. An informative OR query can be negative for at most one candidate; its positive answer retains all the others. Recovery therefore requires linearly many queries, even with bounded error.

If arbitrary all-positive region queries are available, select one representative from each of half the remaining deleted pairs and ask whether all selected items are positive. The answer is negative exactly when the true deleted pair belongs to that half. Binary search then identifies the support in logarithmically many queries. The linear obstruction thus comes from the fixed OR mechanism on an exact-AUC class.

Revisions: The Introduction states the prediction-to-measurement connection; Section 3.4 develops the sparsity and threshold guarantees; Appendix D.2 compares [1], including the same-family separation.

[1] V. Kontonis, M. Ma, and C. Tzamos. Active Learning with Simple Questions. COLT 2024.

AuthorsOpenReview ↗

Response to BGqK Part 2: Controlling the observed overhead without losing the exact-AUC guarantee

We addressed the observed adaptation overhead with a baseline-guarded variant, H9H_9, that shares measurements with generalized binary splitting (GBS). On the same 36,000 HIV/PCBA pools, mean-query overhead over random-order GBS falls from 13.74%–47.45% to 1.01%–3.67%, while preserving the simultaneous exact-AUC class-wise order.

1. Where the original ranking gains are lost [W2: source of empirical overhead].

On PCBA-2551, standalone rank-band recovery uses 58.49 mean queries versus 65.20 for random-order GBS. Forward boundary exploration adds 5.00 queries and bidirectional scheduling another 10.67, raising U's cost to 74.16. PCBA-588342 shows the same pattern: rank-band costs 60.70 versus GBS's 65.20, but U costs 76.71. This paired ablation motivates guarding the quality-adaptive search against its finite exploration and scheduling costs.

2. A baseline guarantee without losing quality adaptation [W2: controlling adaptation overhead].

H9H_9 schedules one private U request followed by nine private GBS requests. A private request would require a physical oracle call when that inference-wrapped algorithm runs alone. Each simulation retains its own inference state; a shared state reuses measurements. Requests answered by shared inference still consume their scheduled slots.

For any support and fixed GBS order, let u and g be the standalone physical costs of inference-wrapped U and GBS. Then TH9≤(10/9)g+1.T_{H_9} ≤ (10/9)g+1.

It also uses at most 10u−910u-9 queries, preserving O(1+M(d,s,D))O(1+M(d,s,D)) simultaneously for every D. Thus the guard controls GBS overhead while retaining quality adaptation. Neither procedure receives AUC. Corollary 3 gives the tunable version; Appendix B.5 provides the schedule and proof.

3. Paired evaluation on the original pools [W2: held-out performance].

We fixed the ratio at 1:9 and evaluated all twelve settings with the original rankings, pools, and eight GBS permutations per pool unchanged.

MethodMean-query overhead over random-order GBS
Original inference-wrapped U13.74%–47.45%
Independent 1:9 schedule, exact-cost controlApproximately 11%–13%
Shared-information H9H_91.01%–3.67%

The shared guard adds only 1.01–1.18 queries per pool on average and beats ranked GBS in nine of twelve settings. The independent-schedule control isolates the benefit of sharing: most subsequent private U requests are answered from measurements already acquired by GBS.

On the prescribed-sum scaling grid, H9H_9 also beats both GBS variants in all 30 boundary settings (Δ≤sΔ ≤ s). All 288,000 added real-pool runs and 13,520 synthetic runs recover exactly and satisfy the instance-wise bounds.

Revisions: Section 6.2 reports the guarded results; Appendix G.5 and Figure 11 give the paired comparison and protocol. The supplementary code includes all per-run records.

Thank you again for your feedback. For details, please refer to the revised paper.

AuthorsOpenReview ↗

Follow-up to BGqK on our response

Thank you again for your thoughtful feedback. We hope our clarification of the ML connection, comparison with Kontonis et al., and new baseline-guarded results have addressed your concerns. We would be grateful to hear your assessment of these revisions and would welcome the opportunity to discuss any remaining questions with you.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions and discussion

We thank the Area Chair for considering our submission and all three reviewers for taking the time to revisit the paper. We appreciate the continued support of BGqK and fAJv. We were also glad to hear from Ukbb that the worked example and decision-tree explanation addressed their technical questions and that our response clarified the connection to ML.

1. What does ranking quality guarantee?

Even when AUC tends to one, finding every positive can still require as many queries in the worst case, up to constant factors, as searching without a ranking. For noiseless pooled testing with a known positive count, we characterize the optimal worst-case query budget at every feasible AUC. One explicit algorithm attains the entire curve, up to constant factors and an additive constant, without being told the AUC.

2. A clearer proof and a larger test of the theory.

Section 3.2 now starts with three candidate supports at identical AUC. The example illustrates why counting candidates is insufficient: an informative OR test isolates one candidate on a negative answer but retains all the others on a positive answer. Appendix D.2 compares this construction with the framework of Kontonis et al.: on the same family, queries that ask whether all selected items are positive permit binary search.

In response to fAJv’s request for larger-scale evidence, we extended the same-AUC experiment from 8,192 to 524,288 items. At the largest size, our algorithm recovers one support in 151 queries. At exactly the same AUC and positive count, any algorithm that succeeds with probability at least two-thirds on every member of the hard family needs a worst-case budget of at least 457 queries (Figure 3).

3. What changed on learned rankings.

BGqK drew our attention to the gap on learned rankings: the original algorithm used more queries on average than random-order generalized binary splitting (GBS) in all twelve settings. That observation motivated a new variant that shares measurements with GBS. On the same 36,000 held-out HIV/PCBA pools, it brings the mean overhead down to 1.01–1.18 extra queries per pool, depending on the setting. The same fixed variant retains the guarantee for every exact-AUC class and, in each of the 30 synthetic boundary settings, uses at least 63% fewer queries on average than the better of the two GBS baselines (Corollary 3; Appendix G.5).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.