acceptodds
Under review as a conference paper at ICLR 2027

Batch Active Evidence Acquisition via Submodular Utility Coverage across Hypotheses

Abstract

Decision systems in clinical diagnosis, fraud review, industrial monitoring, and tool use must choose which costly evidence to acquire before making a prediction. Sequential acquisition selects one action, observes its outcome, and then chooses the next. Test panels, imaging protocols, and related workflows instead require the complete action batch to be selected before any outcome is available. We study this one-shot batch active evidence acquisition setting, where an action can reveal a feature, an image patch, or the answer to a diagnostic question. Without the observation loop, the policy cannot re-estimate the value of the remaining actions after each acquisition, and directly maximizing the expected downstream-loss reduction of a batch is intractable. We introduce hypothesis utility coverage (HUC). Given a partial observation, HUC retrieves similar completed instances to represent plausible completions, transfers their precomputed explanation-derived action utilities, and applies diminishing returns to the utility already covered within each completion. The surrogate is monotone submodular by construction, so greedy selection carries the classical guarantee on the surrogate under a cardinality budget without assuming anything about the data, and a conditional bound separates its gap from the ideal objective into retrieval, saturation-fit, and utility-estimation terms. On a controlled synthetic benchmark, a matched control shows that the gain over ranking actions by posterior-averaged importance comes from this set-dependent saturation rather than from rescoring individual actions. On diagnostic question acquisition (DDXPlus) HUC improves over a fixed acquisition path at every plotted budget, on real image and tabular datasets the gains are small or absent, and under the reported implementations it is competitive with direct batch scoring at a fraction of the selection cost.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Active Feature Acquisition, Batch Acquisition, Submodular Optimization, Retrieval-Based Prediction, Shapley Values, Cost-Sensitive Learning

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_2ur4OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

Paraphrasing a bit here...

This paper studies "batch active querying". Suppose X is the set of queries and Y is the set of outcomes, this work assumes we have observed some queries: M = {(x1,y1) ... (xm,ym)}. This work decides next batch of queries to issue S_query = {x^1, ... , x^k}. It then goes and get the outcome for those queries, S = {(x^1, y^1), ..., (x^k, y^k)}, and combine the observations SEEN = S \cup M. It then uses SEEN to predict the outcomes for the rest of the queries, and compute some loss on 1) the prediction accuracy itself perhaps, or 2) downstream usage of the predictions.

Generally, computing S_query from M is intractable as it is a combinatorial optimization problem. So the author made some relaxations until submodular happened and the proofs are happy. Empirical results look promising too, but maybe done on too few domain and a bit archaic (like who still do cifar in 2026 lol, but maybe that's beside the point)....

Critical strengths

Good problem statement and logical decomposition into the 3 apprximation steps. Relaxed a whole bunch and actually got to sub-modular surrogate and the proof works out. Nice work.

Although checking the proof is beyond my ability, as I don't work on sub-modular proofs, so I leave it to the other reviewers who can validate the proof itself.

But at the end of the day, the empirical results looked pretty good, and the proposed method seemed very general.

Critical weaknesses

Section 5 in experiment, what are the metrics we're comparing? Is it how well a network can predict patches of the full CIFAR images when observing SEEN ? Or is it how well a network can predict the classification label of the CIFAR image given only SEEN ?

In Section 5 you are also missing a figure visualizing the patches queried for by your algorithm, vs that of baselines, vs that of random. Like show a CIFAR image, show the M, and show the SEEN, for all these baseliens. Something like (https://arxiv.org/pdf/1711.03243 Figure 2) . Because while the performance plot shows your method is good in aggregate, the reader would like to intimately know what your algorithm actually does on a concrete instance. So you want to always have a "gallery" figure, showing specific instances of how your algorithms work on a set of concrete input, so the reader goes "yeah okay I trust you" and then show the plot which demonstrate to the reader that "oh yeah I see the plot, it works on thousands of inputs like the ones you just showed me".

Figure1 you want to also report (approximate) oracle results. If you were to select a large number of subsets (like 1M possible different subsets) for S_query within the budget, and have an oracle pick the best one, you'd get a very good performance right? How far is the proposed method from this oracle? Having random is great as it esbalishes a lower bound, I'd like to see the upper bound too with the oracle.

Have some figures to explain your experiment setup would be nice, as the broader audience would benefit from a more hand-holdy explanation. Like can you have a coverstory of sorts? something like . . . "we're looking for oil, we have drilled into the ocean at these coordinates and taken their readings, and we can send down a submarine to drill at these additional coordinates to see if theres oil" iono some intuitive to understand story, that motivates why observations must be taken in batch, what real-life problems have that flavor, etc. Like what's the point of observing patches of CIFAR ( ? )

Questions for authors

this work reminded me of a prior line of works by Pu.Y that do query selection in the non-batch setting. https://arxiv.org/abs/1704.06131 , https://arxiv.org/pdf/1711.03243 . They also have notion of interpolating (neighborhood of) past observations to make predictions on future queries. See if there's some interesting connections.

another thing, this part: "the predictor f and encoder g are one masked network, trained once per dataset and seed with uniformly random masks and then frozen. "

So the predictor f is trained over uniformly random masks, but at test time, the observations it gets to use is the SEEN set. Now the patches in SEEN is nothing but random no? So this is actually somewhat off-distribution. Have you thought about training "f" alongside a distribution of the SEEN set, and see if performans can be better? I'm just so curious haha

minor:

  • maybe we can drop the l(f(x_M),y) term from equation 1, as that's a constant no?

anyways I like the paper and want to champion it, it's a breath of fresh air after all the auto-research slop on my stack . . . but you gotta make it more accessible. It was not easy to read . . .

3 comments
AuthorsOpenReview ↗

Response to Reviewer 2ur4 (1/2)

Thank you for the concrete suggestions and the kind words. We added the galleries, the hindsight oracle, the fine-tuning run, the cover story and the setup figure you asked for. Each is below with its location.

W1: Which metric does Sec. 5 compare?

The class label. On CIFAR, the frozen classifier sees the central patches M plus the acquired patches S, with all other patches masked, and outputs the class. We report its top-1 accuracy, and no patch is ever reconstructed. Every dataset works this way, with the class, the cancer subtype or the diagnosis as the label. Figure 2 plots each method's accuracy minus that of the fixed path, which is the zero line. The fixed path is a baseline that acquires the same patches for every image. Sec. 5 and the Figure 2 caption now say this.

W2: A figure of the patches each method queries.

Added to App. A.8 as Figure A8.2. It shows eight CIFAR-10 test images. Six are drawn at random, and two are chosen among images where HUC is correct and TOPK is wrong, as the caption says. For each image it shows the full image, the initial patches M, and for each method the patches it adds, the visible input and the prediction. The methods are HUC, random selection, the fixed path, TOPK and AACO-greedy. TOPK ranks actions by their average utility, and AACO-greedy re-scores candidate batches with the predictor. App. A.8 also shows four random Synthetic cases, where the generator tells which question carries the class signal. At five features the true class's question is in HUC's batch for 64% of test cases and in TOPK's for 40% (Table A8.8). For DDXPlus, App. A.8 lists the questions each method asks for six random and three chosen patients. One chosen patient is an 82-year-old man with a cough. His similar records point most often to pharyngitis, COPD and upper respiratory tract infection (URTI). TOPK and the fixed path ask three pain questions, which among these three diagnoses concern only pharyngitis and URTI. HUC asks one pain question, one about COPD and one about past asthma attacks. The correct diagnosis is an acute COPD exacerbation, and only HUC gets it right. In the revision: App. A.8, Figures A8.1 and A8.2 and Tables A8.8 to A8.10.

W3: Oracle results.

Added as the hindsight oracle (Table A8.6). On DDXPlus and Synthetic, HUC closes more of the gap between the fixed path and the oracle than TOPK and AACO-greedy at every budget.

Gap closed = (method - fixed path) / (hindsight oracle - fixed path), in % (higher = closer to the oracle)HUCTOPKAACO-greedy
DDXPlus, 1 / 3 / 5 / 7 questions13 / 35 / 47 / 509 / 24 / 36 / 385 / 27 / 44 / 49
Synthetic, 5 / 10 / 15 / 20 / 25 features48 / 70 / 74 / 82 / 8628 / 50 / 65 / 80 / 8546 / 62 / 67 / 67 / 67

For every test case, the oracle uses the true label to pick from a pool of batches the one with which the predictor does best. The pool holds up to 10,000 random batches of the same size and the batches of HUC, TOPK, CS and the fixed path. It is correct for 98 to 100% of DDXPlus patients, against 84 to 95% for HUC, and for every Synthetic case. That is more than the 87% the same predictor reaches on Synthetic with every feature observed, because the label picks a batch on which the predictor happens to be right. The new Table A8.6 in App. A.8 covers all five datasets.

W4: A cover story and a setup figure.

Added. Sec. 1 now names cases where all actions must be chosen at once. A patient fills in an intake questionnaire before a visit, or a clinician orders a panel of laboratory tests at the same time. Every question or test is chosen before any answer arrives. Your oil-survey example has the same structure. The drilling sites are fixed before any reading returns, and the image patches in our CIFAR experiments play the role of sites in a controlled setting. In plain words, HUC looks up similar completed records and notes which questions mattered for each of them. It then picks a set that covers what most of them need, and it gives less credit to a question whose job is already done for a record. The new setup figure (Figure 1) shows this on a small example with three similar records that need different actions. TOPK's three picks serve only two of the records, while HUC's serve all three. Sec. 1 now adds the clinical example and the setup figure (Figure 1).

AuthorsOpenReview ↗

Response to Reviewer 2ur4 (2/2)

Q1: Connection to Pu et al.

Both papers are now cited (Sec. 2). Like HUC, they use past observations to model new ones. Pu et al., UAI 2017 learn a model that predicts the outcome of a candidate observation from the outcomes seen so far. They pick, one at a time, the observation whose outcome is most uncertain. Pu et al., ICML 2018 pick a small set of input-output examples for a program synthesizer. Each time, they add the example their model finds least likely given those already chosen. HUC differs in its goal and in when it commits. An action earns credit by how much it matters for a downstream label predictor under each similar record, not by how uncertain its value is. The whole batch is fixed before any value is seen. In the revision: Sec. 2 cites both papers.

Q2: Training f on the distribution of the SEEN sets.

Yes, on Synthetic it helps, and HUC stays ahead of TOPK by about as much as before. We fine-tuned one copy of the predictor on the feature sets HUC actually acquires and one on TOPK's. The similar records and their utilities stay fixed, so the picks do not change:

Synthetic, 1,600 new test cases, three training seeds (accuracy points)5 features10152025
HUC, fine-tuned minus original predictor+1.1+1.6+1.2+1.3+0.9
HUC minus TOPK, original predictors+15.0+16.1+7.3+1.9+0.3
HUC minus TOPK, each fine-tuned on its own feature sets+15.7+16.6+7.1+1.7+0.3

In the revision: App. A.8, Table A8.7.

M1: Dropping ℓ(f(xM),y)\ell(f(x_M), y) from Eq. 1.

Yes. The term varies across cases but is constant in SS for a fixed xMx_M, so dropping it leaves the best batch unchanged. We keep it so that G(∅∣xM)=0G(\varnothing \mid x_M) = 0 and GG reads as the benefit of acquiring SS. Dropping it would shift the objective and change the form of its multiplicative approximation bound. Sec. 3 now says this after Eq. 1.

AuthorsOpenReview ↗

Follow-up on the added items

Thank you again for the kind words, and for the concrete suggestions, which made the paper easier to follow. Each item you asked for is already in the revised PDF, and all of them stay in the final version.

  • The metric is the class label, now stated in Sec. 5 and the Figure 2 caption.
  • Sec. 1 has the clinical cover story and a setup figure (Figure 1), and we rewrote the parts that were hard to follow.
  • App. A.8 has the Synthetic and CIFAR-10 galleries (Figures A8.1 and A8.2) and DDXPlus examples (Tables A8.9 and A8.10).
  • The hindsight oracle uses the true label to pick the best of many candidate batches (Table A8.6). On DDXPlus and Synthetic, HUC closes more of the gap between the fixed path and this oracle than TOPK and AACO-greedy at every budget. TOPK ranks actions by their average utility, and AACO-greedy re-scores candidate batches with the predictor.
  • Fine-tuning the predictor on the acquired sets raises HUC's accuracy on Synthetic by 0.9 to 1.6 points, and its lead over TOPK stays about the same (Table A8.7).
  • Sec. 2 cites both papers by Pu et al., and Sec. 3 says why Eq. 1 keeps its first term.

We would be glad to clarify anything before the discussion closes.

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

This paper studies the problem of one-shot batch active evidence acquisition, where an action can reveal a feature, an image patch, or the answer to a diagnostic question. The authors introduce Hypothesis Utility Coverage (HUC), which retrieves similar completed instances to represent plausible completions, transfers their precomputed explanation-derived action utilities, and applies diminishing returns to the utility already covered within each completion. The resulting surrogate function is monotone submodular by construction, allowing greedy selection to achieve the classical (1-1/e) approximation guarantee for the surrogate objective.

Critical strengths
  1. The paper is well written, clearly organized, and easy to follow.
  2. The paper addresses an important problem. The idea of using hypothesis utility coverage as a surrogate for one-shot batch active evidence acquisition is interesting. The authors also provide theoretical guarantees based on the proposed surrogate objective, which adds rigor to their approach.
  3. The experimental results demonstrate the effectiveness of the proposed method.
Critical weaknesses
  1. The overall novelty is somewhat incremental. Conceptually, using submodular functions to capture the diminishing marginal returns of selecting additional features is a well-established idea. While the proposed hypothesis utility coverage formulation is interesting, its underlying principle is closely related to existing submodular coverage approaches. The paper could better clarify what fundamentally distinguishes the proposed formulation from prior work on submodular optimization and feature selection.
  2. The theoretical contributions are relatively limited. The proposed surrogate belongs to the well-known concave-over-modular family of submodular functions, and its submodularity follows directly from standard results. Similarly, the final approximation bound is derived by combining approximation errors with the classical greedy approximation guarantee. Given the extensive literature on submodular optimization and approximate submodular objectives, these theoretical results appear to be relatively straightforward extensions of existing studies.
Questions for authors

The paper could better clarify what fundamentally distinguishes the proposed formulation from prior work on submodular optimization and feature selection.

3 comments
AuthorsOpenReview ↗

Response to Reviewer ecJ4

Thank you for pressing us on what is new relative to submodular coverage and on what the theory adds. The revision now states both precisely.

W1 / Q1: What distinguishes HUC from prior submodular optimization and feature selection?

What distinguishes HUC is what its submodular function covers. It keeps the utility profile of each similar completed record separate and weights each record by its similarity to the case. For one test case, HUC scores a batch SS by

F(S)=∑kαkψa(∑j∈Suk(j)),ψa(z)=log⁡(1+az),F(S) = \sum_k \alpha_k \psi_a\Big(\sum_{j \in S} u_k(j)\Big), \qquad \psi_a(z) = \log(1 + a z),

with one term per similar record kk, similarity weight αk\alpha_k and nonnegative action utilities uk(j)u_k(j) derived from that record's precomputed attributions. An action therefore earns less once the batch covers that record's utility. This set dependence is what pays off. CS scores each action alone with the same function. With matched inputs, HUC is 16.1 points above CS at 5 and 10 features on Synthetic (Table 5) and 2.0 to 3.6 points above it at 3 to 7 questions on DDXPlus (Table A8.1).

HUC also chooses differently from the closest acquisition methods. EC2 (Golovin et al., NeurIPS 2010) and DiRECt (Chen et al., AAAI 2015) use specified relationships between hypotheses and test outcomes. They choose tests adaptively, after observing earlier results. GenEx (Asgaonkar et al., AAAI 2024) uses a feature generator and classifiers trained for separate data groups. HUC selects its whole batch from the transferred profiles, without generating feature values or evaluating hypothetical outcomes with the predictor. It is 3 to 250 times faster than AACO-greedy, which re-scores candidates with the predictor (Table 1). We agree that the concave-over-modular form itself is standard (Stobbe & Krause, NeurIPS 2010; Wei et al., ICML 2015), so submodularity and the greedy factor are inherited. In the revision: a new related-work paragraph and the two citations above (Sec. 2), and a reworded contribution 1 (Sec. 1).

W2: The theoretical contribution is limited.

We agree that the structural result is standard, and the revision says so. For nonnegative utilities and weights, HUC's surrogate FF is normalized, monotone and submodular. Greedy selection therefore attains (1−1/e)(1 - 1/e) under equal costs, and under unequal costs with the standard partial-enumeration variant (Sec. 4.4). What the analysis adds is the link to the predictor's expected loss reduction GG (Eq. 1), which need not be submodular for a fixed predictor. HUC optimizes FF, which is exactly submodular, and a standard uniform-error transfer argument relates FF to GG. Under the assumptions of Lemmas 1 to 3, for a budget of bb actions, Theorem 1 gives, with high probability over the reference records,

G(SHUC∣xM)≥(1−1/e)G(S⋆∣xM)−(2−1/e)(ε1+ε2+ε3),G(S_{\mathrm{HUC}} \mid x_M) \ge (1 - 1/e) G(S^\star \mid x_M) - (2 - 1/e)(\varepsilon_1 + \varepsilon_2 + \varepsilon_3),

where SHUCS_{\mathrm{HUC}} is HUC's batch and S⋆S^\star the best batch of the same budget. The three errors concern retrieval, saturation fit and utility estimation. Krause & Guestrin, UAI 2005 is a related precedent. Their information-gain objective is submodular under stated conditional-independence assumptions, and their analysis includes additive error from approximate marginal evaluations. Our analysis also shows when HUC and TOPK, which ranks actions by average utility, pick the same batch. This happens with proportional utility profiles, an equal-cost budget and matched inputs. On DDXPlus, the gain from set dependence is larger where the records disagree (Table A8.2). In the revision: Theorem 1 (Sec. 4) now cites Krause & Guestrin and points to a direct check that HUC's score tracks the realized gain (App. A.8, Table A8.3).

I would like to thank the authors for their clarification, which has addressed some of my concerns. However, I still have reservations regarding the significance of the technical contribution.

AuthorsOpenReview ↗

Response to Reviewer ecJ4’s Follow-up Comment

Thank you for the follow-up, and for telling us that the response addressed some of your concerns.

We agree that the function class, the greedy factor and the error transfer in Theorem 1 are standard. The revision states this in contribution 1 and relates Theorem 1 to Krause & Guestrin (UAI 2005) in Sec. 4.4. What we claim is how the function is built for each case, and the evidence for when this helps. Three contrasts show what the construction changes.

  • In summarization (Lin & Bilmes, ACL 2011) and data subset selection (Wei et al., ICML 2015), every candidate item is observed, so its contribution to each target is computed from the item itself. In HUC the candidates' values are not yet observed. The targets are similar records retrieved for the case, and the contributions come from those records' precomputed attributions.
  • Feature selection chooses which features a model should use, from data in which every feature is observed. Instance-wise selectors such as L2X (Chen et al., ICML 2018) and INVASE (Yoon et al., ICLR 2019) choose, for each fully observed example, the features most informative for its prediction. HUC chooses which features, image patches or questions to acquire for a new case before any of their values is seen.
  • EC2 and DiRECt (Golovin et al., NeurIPS 2010; Chen et al., AAAI 2015) also work with hypotheses. Their objectives add up the weight of the hypothesis pairs that a test's outcome separates, so they need a model of each test's outcome under each hypothesis. HUC's objective instead measures, for each retrieved hypothesis, how much of the fixed predictor's utility the batch covers. It gives an action less credit once that hypothesis's needs are covered, and it needs no outcome model.

On DDXPlus, removing only this discount removes the whole gain over ranking actions by their average utility. This holds from three questions on, in every training seed, with the same records and utilities for both methods. On METABRIC, CIFAR-10 and CIFAR-100 the discount helps in all 13 settings, by 0.1 to 0.9 points (Table A8.1).

The natural alternative is to run greedy on an estimate of the true objective, calling the predictor on retrieved completions of every candidate batch. AACO-greedy does this. It is no more accurate than HUC in 18 of the 22 plotted settings, and it takes 3 to 250 times longer to select a batch (Tables 1 and 4). HUC calls no predictor once the similar records are found.

We hope this makes the scope of our contribution clearer, and we would be glad to expand on any of these points.

Reviewer_tTb6OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary
  • The paper studies one-shot batch active evidence acquisition, where a learner selects a set of additional features before observing any of their values.

-The available features are known, but only some feature values are initially observed. The task is to select the set which gives the highest expected improvement in the classification rate while not overrunning the expenditure budget.

  • The authors propose Hypothesis Utility Coverage (HUC), which retrieves similar completed examples to represent plausible completions of the current partial observation and uses their precomputed importance scores to estimate the utility of candidate acquisition actions. HUC applies diminishing returns to the utility already covered in each of the plausible completion sets. It thus encourages the batch to attend to different information needs, and gives a monotone surrogate objective with greedy guarantees under the budgeted rule.
Critical strengths
  • The problem is well formulated and the proposed method is well described.

  • The central sub-modularity proof in Theorem 1 seems correct under the stated conditions. The authors distinguish the surrogate objective from the true predictive objective and identify the assumptions needed to connect them. The method also distinguish equal-cost selection from unequal-cost selection: achieving the same approximation factor with heterogeneous costs requires the additional enumeration procedure, beyond ordinary gain-per-cost greedy selection.

  • HUC can construct a batch without repeatedly running the predictor over hypothetical outcomes. The reported timings show that this can substantially reduce selection latency compared with predictor-based rescoring.

Critical weaknesses
  • The error decomposition is useful because it identifies what must go right. Nevertheless, without estimating the errors, the resulting lower bound may be too loose to say anything useful about predictive performance.

  • A feature can be important in explaining a prediction on a complete example while adding little information to the current partial observation. For example, its value may already be predictable from what is known. Similarly, transferring an attribution from a neighboring case assumes that the neighbor’s information needs are relevant to the current query. That can fail when the retrieved case differs in an important unobserved way.

  • The synthetic control establishes that set dependence matters in that synthetic environment. The other experiments leave the mechanism less clear.

  • While authors mention the direct competitor method GenEx, they do not compare against the method in their experiments.

  • The main results use three seeds, with error bars showing the half range across seeds. These are not confidence intervals. The synthetic mechanism experiment separately reports paired bootstrap intervals.

-The concave-over-coverage construction and its greedy approximation guarantee are established machinery. Earlier work uses concave functions to impose diminishing returns and encourage coverage across different targets. While the paper is interesting study, I am not convinced about significant novelty presented.

Questions for authors
  1. Why are the gains much larger on synthetic data than on real datasets? What characteristics of a problem make HUC more useful than simply ranking features by their importance?

  2. How does HUC compare with GenEx, the closest existing method for batch acquisition? Could you include this comparison to clarify HUC’s advantages and limitations?

  3. Does a higher HUC score reliably mean better predictions? Could you show how closely the score matches the actual improvement obtained after acquiring a batch?

3 comments
AuthorsOpenReview ↗

Response to Reviewer tTb6 (1/2)

Thank you for the precise questions on where HUC's gain comes from, on GenEx and on whether the score tracks real gains. Each now has its own analysis in App. A.8, and we summarize them point by point below.

Q1: Why are the gains larger on Synthetic, and when does HUC beat ranking by importance?

HUC can beat ranking only where the similar records disagree about which actions matter, and Synthetic is built so that they do. If all similar records agree up to a scale factor, HUC returns exactly the batch of TOPK, which ranks actions by their average utility (Sec. 4.2). This holds with the same inputs and equal action costs. On Synthetic the useful question depends on the case's class, which is not observed (App. A.1.1). The generator tells which question carries the class signal, so the effect can be counted:

Synthetic, five featuresHUCTOPK
Test cases whose batch includes the true class's question64%40%
Picks that repeat a question already in the batch4%42%

On DDXPlus the same pattern holds within one dataset. Among patients of similar difficulty, the gain from set dependence is 2 to 4 points larger when the similar records disagree more. App. A.8 now adds Table A8.8 and Figure A8.1 for Synthetic and Table A8.2 for DDXPlus.

W3: Is the mechanism clear outside Synthetic?

Yes, on DDXPlus. From three questions on, the whole gain over ranking comes from set dependence, in every training seed. CS keeps HUC's own score for each action but scores each action alone, which removes set dependence:

DDXPlus, accuracy points (higher = better)1 question357
HUC minus TOPK+0.7+1.4+1.3+1.4
CS minus TOPK+0.7-0.6-1.6-2.3

CS falls below TOPK from three questions on, while HUC stays above it. With one question, set dependence cannot act, so HUC and CS pick the same question. On CIFAR-10, CIFAR-100 and METABRIC, set dependence helps in all 13 settings we ran, by 0.1 to 0.9 points. In the revision: Sec. 6 reports this control on all five datasets (App. A.8, Table A8.1).

Q2 / W4: Comparison with GenEx.

HUC beats a GenEx-style baseline at every budget on DDXPlus. DDXPlus is the dataset closest to GenEx's own disease-prediction benchmark, where symptoms are the features and diseases are the classes.

HUC minus the GenEx-style baseline (points; higher = HUC better)
DDXPlus, 1 / 3 / 5 / 7 questions+2.2 / +1.7 / +0.9 / +0.5

HUC is ahead in every training seed at 1 to 5 questions. The baseline follows GenEx's selection design. Cases are split into groups by random hyperplanes, as in GenEx, and each group gets one batch chosen greedily on validation data with the true labels. The baseline uses our predictor, because with GenEx's per-group classifiers it scored 3 to 7 points lower on DDXPlus. We did not run GenEx itself. Its public code carries no license, and its pipeline needs a generative model and a classifier for every data group, trained inside its greedy search (Sec. 2). HUC needs neither a generator nor any training per group. Sec. 2 now points to this baseline in its GenEx paragraph (App. A.8, Table A8.5).

Q3 / W1: Does a higher HUC score mean better predictions?

Yes, on DDXPlus and Synthetic. Among the candidate batches for one case, the ones HUC scores higher tend to improve the prediction more (Table A8.3):

Rank correlation between HUC's score and the realized gain, averaged over test cases (1 = perfect, 0 = none)
DDXPlus, 25 batches per case (HUC's, the baselines' and 20 random ones)0.71 to 0.77
DDXPlus, the 20 random batches alone0.52 to 0.63
Synthetic, 23 batches per case0.31 to 0.45

Theorem 1 links HUC's score to this gain. Under the assumptions of Lemmas 1 to 3, with high probability over the reference records, HUC's batch reaches at least (1−1/e)(1 - 1/e) of the best batch's expected loss reduction, minus (2−1/e)(2 - 1/e) times the sum of three error terms. The terms measure how far the similar records are from the case, how far the concave credit is from the real diminishing returns, and how far the estimated utilities are from the ideal ones. Evaluating these terms needs quantities we cannot observe, such as the ideal utilities, so we checked the link directly. Sec. 4 now points to this check right after Theorem 1.

W5: Confidence intervals.

Added for DDXPlus. Per-seed 95% paired bootstrap intervals over the test patients exclude zero at every budget and seed. This holds for HUC minus TOPK and for HUC minus the fixed path, a baseline that acquires the same batch for every patient. The smallest lower bounds are +0.5 and +1.9 points. These intervals describe uncertainty over patients within one trained run. The half-range bars describe variability across seeds. Table 5 already gives per-seed intervals for the Synthetic control. In the revision: App. A.8, Table A8.4.

AuthorsOpenReview ↗

Response to Reviewer tTb6 (2/2)

W2: Attributions from complete examples.

HUC conditions on the observed part through retrieval and scores only the actions not yet observed. As you note, the attributions themselves are not conditioned on the observed values, and Theorem 1 keeps this gap as its utility-estimation term ε3\varepsilon_3. On DDXPlus the transferred utilities still rank each case's candidate batches well, with a rank correlation of 0.71 to 0.77 (Q3). For the two failure modes you describe:

  • A neighbor that differs in an unobserved way. Each similar record stays a separate hypothesis, weighted by how well it matches the observed part. A mismatched neighbor therefore counts in proportion to its weight, and its extra credit drops once the batch covers its needs. It still matters when it carries a large weight or when most similar records share it, which is the retrieval term of Lemma 1.
  • A feature that adds little given what is known. The SHAP attributions we use average a feature's contribution over subsets of the other features, so evidence that overlaps with other features gets less credit. For overlap among the acquired actions, set dependence already discourages repeated picks (Q1). App. A.5 also offers an optional pairwise redundancy penalty, which keeps HUC's score submodular.

App. A.1.2 now states that the image explainers are not conditioned on the observed patches, and Table A8.3 checks HUC's score against the realized gain.

W6: Novelty.

We agree that the concave-over-modular form and its greedy guarantee are established results. HUC's contribution is the acquisition formulation. It keeps the utility profile of each similar record separate and applies the concave credit within each profile. The same-input controls above show that this set dependence is where most of the gain over ranking comes from (Q1, W3). In the revision: contribution 1 (Sec. 1) and a new related-work paragraph (Sec. 2). Point 1 of the general response and our reply to Reviewer ecJ4 discuss novelty in more detail.

AuthorsOpenReview ↗

Follow-up on the added analyses

Thank you again for your detailed review and for highlighting HUC’s substantially lower selection latency compared with predictor-based rescoring. Like you, Reviewers ecJ4 and 2ur4 found the problem well posed. Your questions led to four analyses in App. A.8, and we summarize their DDXPlus results below.

  • GenEx. HUC beats a GenEx-style baseline at every budget, by 2.2 points at one question and by 0.5 at seven (Table A8.5). The baseline follows GenEx's selection design and splits cases into groups by random hyperplanes, as GenEx does.
  • Where the gain comes from. TOPK ranks actions by their average utility, and set dependence is HUC's lower credit for an action once a similar record's needs are covered. A same-input control shows that from three questions on, the whole gain over TOPK comes from set dependence in every training seed (Table A8.1).
  • Score and realized gain. Across each case's candidate batches, HUC's score has a rank correlation of 0.71 to 0.77 with the realized gain (Table A8.3).
  • Confidence intervals. Per-seed 95% paired bootstrap intervals for HUC minus TOPK exclude zero at every budget and seed (Table A8.4).

If any point is still open, please tell us before the discussion closes at 11:59 pm AoE on November 18, so that we can answer it in time.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response

We thank the reviewers for their concrete requests. Below we answer three questions that concern the whole paper and then list the new analyses and the changes.

1. What does HUC add beyond standard submodular coverage? (tTb6, ecJ4)

HUC uses the attribution profiles of similar records to choose which features, image patches or diagnostic answers to acquire together. It keeps each record's profile separate: an action's contribution decreases as the batch covers more utility for that record. HUC selects the entire batch SS before observing any new values, using

F(S)=∑kαkψa(∑j∈Suk(j)),ψa(z)=log⁡(1+az),F(S) = \sum_k \alpha_k \psi_a\Big(\sum_{j \in S} u_k(j)\Big), \qquad \psi_a(z) = \log(1 + a z),

where αk\alpha_k is the retrieval weight of record kk and uk(j)u_k(j) is the utility of action jj, derived from that record's precomputed attributions. This set dependence accounts for most of HUC's gain over ranking. Concave singleton (CS) uses the same records and utilities but scores actions individually. HUC outperforms CS by 16.1 percentage points on Synthetic at 5 and 10 features (Table 5) and by 2.0 to 3.6 points on DDXPlus at 3 to 7 questions (Table A8.1). The submodular form of FF and the (1−1/e)(1 - 1/e) greedy guarantee for the surrogate under equal action costs are standard. Contribution 1 (Sec. 1) and the new related-work paragraph (Sec. 2) now distinguish these results from our acquisition formulation. After retrieval, HUC selects the batch without calling the predictor. It is 3 to 250 times faster than AACO-greedy, which re-scores candidate batches with the predictor (Table 1).

2. Does the mechanism hold beyond the synthetic benchmark? (tTb6)

Yes on DDXPlus, where the gains are largest after Synthetic. There, from three questions on, the whole gain over TOPK comes from set dependence in every training seed. TOPK ranks actions by their average utility. The gain from set dependence is also larger for patients whose similar records disagree more. On CIFAR-10, CIFAR-100 and METABRIC, set dependence helps in all 13 settings we ran, by 0.1 to 0.9 points. In the revision: Sec. 6 and App. A.8 report this control on all five datasets.

3. Readability (2ur4)

We rewrote the parts that were hard to follow. Sec. 1 now names cases in which all actions must be chosen at once, and a new setup figure shows the procedure on a small example (Figure 1). Sec. 5 and the Figure 2 caption state that the predictor outputs the class label on every dataset. Each method now has one name throughout, while this results figure used to call HUC "Submod" and TOPK "Top-K". App. A.8 shows what each method picks on CIFAR-10 images, Synthetic cases and DDXPlus patients. In the revision: Sec. 1 with Figure 1, Sec. 5 with the Figure 2 caption and Table 1, and App. A.8.

Analyses added for the reviewers (App. A.8)

AnalysisAsked byResult
TOPK, CS and HUC with the same inputs on four more datasetstTb6Set dependence carries the gain on DDXPlus from 3 questions on and helps in all 13 settings on METABRIC, CIFAR-10 and CIFAR-100
GenEx-style baselinetTb6HUC ahead at every budget on DDXPlus, by 0.5 to 2.2 points
HUC's score against the realized gaintTb6Rank correlation 0.71 to 0.77 on DDXPlus
Per-seed bootstrap intervalstTb6HUC minus TOPK and minus the fixed path exclude zero at every budget and seed on DDXPlus
Hindsight oracle2ur4HUC closes more of the gap than TOPK and AACO-greedy on DDXPlus and Synthetic
Fine-tuning on the acquired features2ur4HUC +0.9 to +1.6 points on Synthetic, lead over TOPK about the same
Galleries and DDXPlus examples2ur4What each method picks, on random and on chosen cases

Changes in the revision (blue). Sec. 1 adds a clinical example and the setup figure (Figure 1) and rewords contributions 1 and 2. Sec. 2 adds a related-work paragraph on EC2, DiRECt, Krause & Guestrin, VOILA and the two papers by Pu et al., and two citations for the standard concave-over-modular construction (Stobbe & Krause, 2010; Wei et al., 2015). Its GenEx paragraph now points to the GenEx-style baseline. Sec. 3 adds two sentences after Eq. 1. In Sec. 4, Theorem 1 cites Krause & Guestrin and points to the direct check of the score. Sec. 5 adds the prediction target and one name per method. Sec. 5 and App. A.1.2 correct the description of the image explainers. No reported number changes. Sec. 6 and the Conclusion report the new controls, and Sec. 6 points to App. A.8. App. A.2 says how the DDXPlus utilities are transformed, and Figure 3 in App. A.5 uses the method names of the text. The new App. A.8 holds the analyses above, the galleries and the DDXPlus examples.

AuthorsOpenReview ↗

Summary of the discussion for the program and area chairs

HUC chooses the whole batch of features, image patches or questions for each case before any value is seen, from similar completed records and their attributions. Its gain over ranking comes from set dependence, on Synthetic and on DDXPlus from three questions on, and it is competitive with predictor-based batch scoring at a fraction of the selection cost.

The reviews highlighted the importance of the problem and the clarity of its formulation. Reviewer tTb6 noted that the submodularity argument appeared correct under the stated conditions and recognized HUC’s lower selection latency compared with predictor-based rescoring. Reviewer ecJ4 acknowledged the rigor of the guarantees and the empirical effectiveness of the method. Reviewer 2ur4 also found the experimental results promising and noted the generality of the approach.

During the discussion we added the analyses the reviewers asked for (App. A.8, marked in blue).

  • On DDXPlus, set dependence carries the gain over ranking. From three questions on, the whole gain over TOPK comes from it in every training seed (Table A8.1, added for tTb6).
  • On DDXPlus, HUC's score tracks the realized gain, with a rank correlation of 0.71 to 0.77 across each case's candidate batches (Table A8.3, added for tTb6).
  • On DDXPlus, HUC beats a GenEx-style baseline that splits cases into groups by random hyperplanes, as GenEx does, at every budget (Table A8.5, added for tTb6). Per-seed bootstrap intervals for HUC minus TOPK exclude zero at every budget and seed (Table A8.4, added for tTb6).
  • HUC is competitive with predictor-based batch scoring at a fraction of its cost. AACO-greedy is no more accurate than HUC in 18 of the 22 plotted settings. It takes 3 to 250 times longer to select a batch (Tables 1 and 4, in our answer to ecJ4).
  • HUC's construction differs from standard coverage functions, feature selection and EC2 / DiRECt, as our answer to ecJ4 details. The function class, the greedy factor and the error transfer are standard, and the revision says so.
  • For Reviewer 2ur4, the revision states the metric and adds a cover story with a setup figure (Figure 1) and galleries (Figures A8.1 and A8.2). It also adds a hindsight oracle (Table A8.6), fine-tuning on the acquired sets (Table A8.7) and the link to Pu et al. (Sec. 2), and it rewrites the parts that were hard to follow. The final version keeps all these additions and adds the contrasts from our answer to ecJ4 to Sec. 2.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.