acceptodds
Under review as a conference paper at ICLR 2027

Disagreement Has a Depth: Fail-Safe Consensus over Label Hierarchies

Abstract

Coordinated failures can flip a majority vote, yet sources that disagree on a label often agree on its ancestors: disagreement has a depth. We ask for the most specific statement that stays consistent with a strict majority of the uncorrupted sources, right or wrong, when up to of sources are corrupted. For label reports, the finest such rule, even among set-valued rules and rules that see the whole stream of examples, returns the deepest subtree holding more than reports. We derive its exact loss of depth, with a barrier at , and its exact risk under per-example and persistent adversaries, certifiable from i.i.d. labelled held-out data. For probability reports, backing off from the likeliest label to its first ancestor with mean probability at least is safe exactly when . Calibration to 95% coverage crosses this threshold on all four datasets, human labels included. Safe backing off is never finer than the finest safe subtree-valued rule for probability reports, so backing off matched to that rule's clean error crosses the threshold on all three machine-source datasets, with 1.2 to 2.7 times the rule's per-example worst-case error for two or three of ten corrupted sources. Safety costs abstentions and buys little against the non-adaptive failures we tested.

Primary area:
learning theory
Keywords:
Byzantine robustness, robust aggregation, label hierarchies, hierarchical classification, selective prediction, abstention, certified robustness, ensembles, crowdsourcing, worst-case risk

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_CRoROpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how to aggregate predictions on a fixed label hierarchy when up to f sources can be arbitrarily corrupted. It defines safety relative to the majority subtree of the uncorrupted sources and characterizes the finest safe output for label reports. It derives exact specificity losses and worst-case error events, extends the approach to probability reports, and establishes a safety threshold for hierarchical selective classification. Experiments on image classification, cell annotation, and human labels examine the trade-off between adversarial error and prediction specificity, together with the conditions under which statistical risk certificates transfer.

Critical strengths
  • S1: The paper gives a precise answer to a useful aggregation question: how much specificity can be retained while respecting the majority information in every possible uncorrupted subset. The contribution extends beyond a supermajority threshold to a characterization of the finest safe output, exact corruption costs, and a probability-report safety boundary. It carefully distinguishes this guarantee from correctness against ground truth.
  • S2: The empirical study examines the error-specificity trade-off with substantial controls. The probability-rule comparison uses the same reports and matches clean validation error. Under these matched conditions, the probability rule achieves lower worst-case error than HSC across the evaluated machine-source datasets. Safe-threshold baselines, specificity curves, persistent failures, and negative results help delimit the benefit rather than suggesting universal superiority.
Critical weaknesses
  • W1: The operational value of the retained coarse answers remains less established than the formal guarantee. The paper identifies an operating regime and measures specificity, but does not connect that specificity to a downstream decision or task-specific cost of abstention. On Aircraft, the probability rule at f=2 has clean normalized depth 0.17, and 94.2% of examples admit an attack forcing complete abstention. This is an attack-existence statistic, not an observed deployment abstention rate. In PBMC, the ten sources are feature-panel models, so losing one entire modality corrupts five sources and falls outside the regime that preserves unanimous answers. These disclosed limitations make the practical benefit depend strongly on a justified failure budget and the value of a coarse prediction.
  • W2: The empirical certification protocol only partly supports direct deployment of the reported risk bounds. The main validation split also selects model hyperparameters or temperatures, while the statistical guarantee assumes a fixed rule and independent certification data. The disjoint-selection check is reassuring for the label rule on the image tasks, but an equivalent check is not reported for the probability rule. Separately, the PBMC label-rule top-level bound is 1.3% while the test worst-case error is 3.6% under donor shift. The paper acknowledges this failure and explains that its warning requires uncorrupted reports and does not repair the certificate. This limits deployment assurance and empirical coverage claims, without refuting the conditional theorem.
Questions for authors
  • Q1: Could you work through one of the evaluated applications with a justified corruption budget and a concrete downstream decision or cost model? Showing when a coarse output is useful, when abstention is acceptable, and how the resulting utility compares with HSC would clarify the practical significance of the existing error-specificity results.
  • Q2: Could you report the probability rule's certificates using data disjoint from all model and temperature selection, and distinguish these results from certificates affected by validation reuse? This would clarify how much empirical support remains for the deployable guarantee once its sampling conditions are enforced.
2 comments
AuthorsOpenReview ↗

New: certificates on data disjoint from all model and temperature selection (every all-error bound still holds), and a worked decision-cost analysis on PBMC with a justified corruption budget

Thank you for two precise deployment questions. We ran both analyses; the results are in the revised PDF (changes in blue).

Q2. Certificates on data disjoint from every selection step. For the image datasets we retrained the ten probes with weight decay and temperature chosen on one half of the validation split (stratified) and certified on the other half (2,500 CIFAR-100 images, 1,700 aircraft). The PBMC networks never see the validation donor, whose cells were used only to fit temperatures; we refitted the temperatures on one half and certified on the other (5,017 cells). One-sided 95% Clopper-Pearson bounds at f=2f=2, all errors (top-level errors in parentheses), in %:

boundexact test worst case
CIFAR-100, Q2pQ^p_212.2 (7.1)9.6 (5.7)
CIFAR-100, Q2Q_217.0 (9.8)14.8 (8.6)
FGVC-Aircraft, Q2pQ^p_24.5 (3.7)3.8 (3.0)
FGVC-Aircraft, Q2Q_219.3 (13.5)18.5 (12.4)
PBMC, Q2pQ^p_213.3 (1.5)10.1 (3.7)
PBMC, Q2Q_217.3 (1.4)14.4 (3.6)

Every all-error bound covers the exact test worst case for both rules on all three datasets, and also at f=3f=3. The top-level bounds hold on the image datasets and fail on PBMC exactly as before, because its test cells come from other donors. Reusing the split for selection had moved the bounds by at most 1.0 point. The remaining failure is therefore the i.i.d. assumption under donor shift, not validation reuse; the label-free warning flags it but does not repair it, as the paper says. (New Table 27; Section 5.4.)

Q1. A worked application with a cost model. PBMC cell typing at f=2f=2. Each source reads one gene or antibody panel, so two independent panel failures (for example a failed antibody lot and a mis-pooled gene panel) corrupt two sources. Losing a whole modality corrupts five sources, beyond any safe rule (M≤3fM\le 3f), as Section 6 states and as you note. Cost per cell: a wrong label costs λw\lambda_w, an abstention at the root (the cell goes to manual gating) costs 1, and a correct but coarser label at depth dd costs 0.5(1−d/L)0.5(1-d/L). Under attack, the adversary picks for every cell the corruption that maximizes its cost (a wrong label if it can, else the root, else the coarsest correct label); this is exact for Q2Q_2 and Q2pQ^p_2 and a lower bound for HSC, which favours HSC. HSC at θc+\theta_c^+ climbs at the safe threshold, just above θc=12+f2M\theta_c=\frac12+\frac f{2M}. Expected cost per cell (Table 28 rounds to two decimals):

clean, λw=2\lambda_w=2clean, 10panel dropout, 10attack, 2attack, 10
Q2pQ^p_20.1920.3710.2920.4611.250
HSC at θc+\theta_c^+ (safe)0.1870.3140.2860.4811.271
HSC calibrated to Q2pQ^p_20.1850.3870.2950.4951.608
HSC calibrated to Q2Q_20.2060.6360.4180.6102.623
abstain on every cell11111

When a wrong label is cheap, the more specific calibrated rule is best without an adversary. Under attack, the two safe rules are best as soon as a wrong label costs two abstentions; they differ by at most 0.06 in every column. The attack column is the worst case, with every cell attacked: at λw=10\lambda_w=10 abstaining on every cell is then cheaper than any rule, which is when abstention is the right call. If a random share of cells is attacked, the safe rules beat abstaining up to a 72% share, against 50% for HSC calibrated to Q2pQ^p_2 and 18% for HSC calibrated to Q2Q_2. The image datasets show the same pattern (new Tables 28 and 29).

On the 94.2% for FGVC-Aircraft. It is the share of images for which some corruption of two sources can force Q2pQ^p_2 to the root, not an observed abstention rate. Without any attack, Q2pQ^p_2 already abstains on 76% of the images (the vote rule Q2Q_2 on 51%), because the weak aircraft sources disagree at the top level. Safety is expensive there, and the paper says so; on PBMC and CIFAR-100 the clean abstention rates of Q2pQ^p_2 are 6% and 23%.

Thank you; these two analyses make the deployment conditions of the guarantee explicit.

Thank you for the helpful response. The certificates computed on data disjoint from model and temperature selection address my concern about validation reuse. The worked PBMC cost analysis also clarifies when coarse predictions are useful. These additions strengthen my positive assessment, and I would like to keep my current score, which is already positive.

Reviewer_nTrPOpenReview ↗
Rating
3
Confidence
3(+2)
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies how to combine several sources (models, annotators) that label an example within a taxonomy, when up to ff of the MM sources may be adversarial. It calls an output safe if it never contradicts or overstates what the honest majority supports, whoever the corrupted sources are. The most specific safe output is the deepest node backed by more than (M+f)/2(M+f)/2 sources. The paper characterizes how much specificity and accuracy this costs and gives a held-out certificate. For probability outputs, it derives the threshold above which hierarchical selective classification (HSC) stays safe, and shows that standard calibration lands below it on four datasets.

Critical strengths
  • This seems like a relevant question with a clear answer. Combining models, annotators or agents over a taxonomy under failures is common, and falling back to a coarser label is a sensible alternative to all-or-nothing abstention. The honest-majority notion of safety is well chosen: anchoring to the truth would force abstention, and certifying the clean output would tolerate fewer failures. The paper makes both comparisons.
  • The proofs seems to be correct, and every closed-form result is also verified.
  • The paper is candid about its limitations, which makes the paper easy to assess. It acknowledges the overlap with classical quorum results, states where safety does not pay, and reports the certificate failing under distribution shift.
  • The key empirical claim is tested directly. Replacing the taxonomy with a random one removes most of the gain, which shows the benefit comes from the hierarchy itself. Further controls (correlated sources, retrained pools, a separate selection split) support robustness.
Critical weaknesses
  • As far as i can see, the novelty is narrower than the abstract suggests. This matters because the abstract presents classical results as new and leads with its least substantive ones. The rule is majority-rule consensus of trees with a Byzantine-quorum threshold, which the paper acknowledges in the body but not in the abstract. The optimality results the abstract emphasizes (over set-valued and stream-aware rules) follow in a few lines from the definition of safety. The genuinely new parts, the safety notion for hierarchies and the HSC threshold, should lead.

  • The experiments support the threshold, not the new rule. This matters because the headline result (1.2–2.7× lower worst-case error) is presented as an advantage of the proposed rule. That comparison calibrates HSC to a point the theory itself shows must be unsafe. Run above the safe threshold, HSC matches the proposed rule's worst case at nearly the same specificity (Tables 6, 9), and vote-share climbing likewise matches the vote rule. The practical message is therefore "keep HSC above the safe threshold".

  • Some comparisons favor the method by construction which inflates the apparent advantage. Fig. 1b, the first result shown, includes baselines that never abstain, and it compares votes with averaged probabilities, which the paper itself notes mixes two effects. On the full trade-off curves (Fig. 3), the advantage at permissive settings comes from using votes rather than probabilities. At intermediate settings it holds only against the paper's own loose bounds for the baselines; by actual attack, robust averaging does as well or better in parts of the range.

Questions for authors
  1. Beyond the construction in Theorem 1(ii), which result do you consider technically non-trivial?
  2. What does the proposed probability rule offer in practice over HSC run above the safe threshold?
  3. Apart from label-aware attacks and collusion, is there a failure mode where safety reduces error at matched specificity? If not, the operating envelope in §6 should be the headline.
2 comments
AuthorsOpenReview ↗

We agree that the threshold, not the rule, is the main practical message: abstract reordered to lead with safety and the threshold, safe HSC added to Table 1, Figure 1b on the same reports, and the envelope stated

Thank you for a precise reading. We agree with your central point and have revised the paper accordingly (changes in the revised PDF are shown in blue).

1. The practical message is the threshold. Safe climbing is never finer than the finest safe subtree-valued probability rule QfpQ^p_f (Proposition 1(iv)), and above θc\theta_c HSC matches its exact worst case. The abstract, the contributions and Section 5.2 now say this, and Table 1 now includes the safe HSC row (f=2f=2; worst-case error % / mean depth; θc+\theta_c^+ is just above θc\theta_c):

CIFAR-100FGVC-AircraftPBMC
Q2pQ^p_29.4 / 0.684.0 / 0.179.9 / 0.77
HSC at θc+\theta_c^+ (safe)9.4 / 0.664.0 / 0.159.9 / 0.75
HSC calibrated to Q2pQ^p_2's clean error11.7 / 0.696.5 / 0.1713.9 / 0.78

So the 1.2 to 2.7 ratios measure what common calibration costs, not an advantage over safe HSC. The abstract now leads with the safety notion and the threshold, names the majority-rule consensus tree at a Byzantine-quorum threshold as classical, keeps the optimality over set-valued and stream-aware rules to one clause, and ends with the envelope.

2. Comparisons by construction. Figure 1b now shows, on the same probability reports and for every ff on PBMC, QfpQ^p_f, safe HSC and calibrated HSC; the never-abstaining baselines and the votes-against-probabilities comparison are gone from it. Safe HSC coincides with QfpQ^p_f, while calibrated HSC rises to 13.9%, 24.0% and 39.0% at f=2,3,4f=2,3,4, against 9.9%, 13.0% and 16.9%. We also agree with your reading of Figure 3, and Section 5.2 now states it: the advantage at permissive settings comes from votes rather than probabilities, and at intermediate depths the probability quorum beats the certified bounds of the climbing rules, not their attack values. Separately, a stronger search at the matched operating points (new Table 34) raises the robust-averaging attack values by 0.7 to 3.6 points on CIFAR-100 and PBMC and by 6 to 19 points on FGVC-Aircraft; we did not rerun it along the whole frontier, so your reading at intermediate depths stands.

3. Your questions.

  • Which result is technically non-trivial? Theorem 3: the exact error event against the truth, attained per example, its persistent version (equal to the error of the honest majority of the other sources) and its label-free part, which together give the held-out certificate. And Proposition 1: for probability reports the finest safe subtree is the deepest one that keeps a strict majority after removing any j≤fj\le f largest contributions, which yields the if-and-only-if threshold and the certified bounds of Proposition 3. The proofs are short; their value is exactness and a falsifiable prediction, not the length of the arguments.
  • What does QfpQ^p_f offer over safe HSC? In expected cost, little: in a new decision-cost analysis safe HSC is within 0.03 of Q2pQ^p_2 under attack and cheaper without attack in five of six cases when a wrong label costs ten abstentions. QfpQ^p_f is the reference that defines the threshold (θc\theta_c is where climbing starts to contain QfpQ^p_f on every profile) and the standard to audit other aggregators against: a trained DeepSet aggregator (Dhasade et al., 2026; new run) followed by climbing matched on held-out data to the clean error of Q2pQ^p_2 does not contain it, hence is unsafe, on 10% to 28% of test profiles. QfpQ^p_f also keeps slightly more depth at the same worst case. We recommend either rule.
  • Failure modes where safety helps at matched specificity. No, beyond the ones you name: the only other case in our tests is an adaptive persistent pair that steers a learned reliability model, and it too uses the labels. Safety does not help under the non-adaptive failures we tested or under bandwagon collusion. Section 6 now opens with this envelope, and the abstract ends with it.

Thank you; the revised framing now matches what the experiments show.

Thank you for the honest response, the additions and the new framing.

While smaller points, few things are still not clear to me - In Fig. 3 the stronger attack was run only at the matched points, so along the rest of the curve the comparison is still against the baselines’ loose bounds, is it right ?
The vote-share result in your reply to 344B (Q6) supports the vote-rule half of my second weakness, but is not tied to it.

Since my score was already on the accept side and the revised claims are relatively narrower in scope, I am keeping my score and updating my confidence.

Reviewer_JBt6OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies voting when the possible answers form a hierarchy. Each of M sources reports one label for the same example. Up to f individual sources may be corrupted and report arbitrary labels. We know the assumed limit f, but not which sources are corrupted.

The goal is to give the most specific answer guaranteed to have support from more than half of all uncorrupted sources. This majority is always measured over all uncorrupted sources; moving down the hierarchy does not restrict the comparison to voters within that branch.

For example, suppose ten sources identify a dog's breed from the same blurry photograph. These are the observed votes, which may already include corrupted reports:

  • Dog: 10 votes
    • Retriever: 8 votes
      • Labrador retriever: 6 votes
      • Golden retriever: 2 votes
    • Spaniel: 2 votes
      • Cocker spaniel: 1 vote
      • Springer spaniel: 1 vote

Each source votes for one breed, and that vote also supports its ancestors. Suppose we require protection against at most two corrupted sources. Since their identities are unknown, we consider the worst possibility for each proposed answer, which is that exactly two of its supporters are corrupted:

Proposed answerIf two of its supporters are corruptedStrict majority of the eight honest sources?
Labrador retrieverFour honest supporters remainNo: 4/8 is exactly half
RetrieverSix honest supporters remainYes: 6/8
DogEight honest supporters remainYes: 8/8

Labrador still beats every other individual breed, but that is insufficient for this guarantee. Retriever and dog both qualify, so the rule returns "retriever", the more specific answer.

In general, the rule selects the deepest category with more than (M + f)/2 observed votes. The paper proves that no safe rule can be more specific, even one that may return a set of labels, knows which source sent which report, or sees the whole stream of examples. Corruption only costs specificity, but once f reaches M/3, the adversary can force every safe rule back to the root, even when all honest sources agree. The guarantee concerns support among uncorrupted sources, not factual correctness: those sources can still be mistaken. The paper also computes how often the rule can be made wrong, meaning that its answer excludes the true label. On a given example, an adversary who knows the true label can make the rule wrong exactly when some wrong category already has more than (M − f)/2 votes from the uncorrupted reports: moving f votes into that category lifts it above the (M + f)/2 quota. In the dog example with M = 10 and f = 2, that threshold is 4. If the ten votes were uncorrupted and the dog really were a Labrador, no wrong category would have more than 2 votes, so two corrupted sources could make the answer less specific but never wrong. If the dog were a golden retriever, the 6 Labrador votes would let them push the rule to "Labrador retriever".

The worst-case error is the share of examples where such a wrong category exists. This is exact, not a bound, and it is attained. If the same sources are corrupted on every example, as with a poisoned model, the worst-case error is lower or equal, and it equals the error of the remaining honest sources' majority. Knowing which sources are corrupted would then buy specificity but not accuracy.

Because this condition can be checked on uncorrupted reports, the worst-case error can be estimated from a labelled held-out set and turned into an upper bound that holds with high probability (a one-sided Clopper-Pearson bound), provided the held-out examples are drawn from the same distribution as the deployment data. Part of the condition needs no labels: an example is always vulnerable if two non-overlapping categories each have more than (M − f)/2 votes. The share of such examples can be monitored in deployment, and a change from the held-out value warns that the data have shifted, though not why. In the experiments the bound held on every dataset except the top level of the blood-cell data, where the test cells came from different donors than the held-out cells, and there the label-free warning fired.

Critical strengths

The work appears correct and the results are natural.

Critical weaknesses

In my view, the results are not sufficiently novel for a venue like ICLR. The proofs use standard counting arguments, and the thresholds are folklore in distributed computing: the M > 3f barrier for keeping unanimous honest answers is the condition for Byzantine dissemination quorums, and the M > 4f condition for the clean-anchored rule matches masking quorums, as the paper itself acknowledges (line 151). The improvement over stability certificates, from M > 4f to M > 3f, comes from protecting the honest majority instead of the clean output, a weaker requirement whose threshold was already known. Writing down the theorems is a reasonable contribution, and I have not found them stated in prior work, but I do not think the step beyond existing results is large enough for a top-tier conference.

The most serious weakness is the presentation, which is very dense and hard to follow. For instance, the standing assumptions (A1) to (A3) are defined inside a paragraph in lines 158 to 161 but are then referenced in the statements of the theorems. Please set them out as a separate itemized list so they are easy to find. The problem statement in the introduction is especially dense, and it took me considerable effort to understand what was meant. This is why I restated the problem in my summary above, with some help from GPT and Claude. A clear problem statement is central to a good paper, and this one would benefit greatly from a more accessible one.

Questions for authors

See weaknesses.

2 comments
AuthorsOpenReview ↗

Problem statement rewritten around a worked example, assumptions itemized; the classical thresholds are acknowledged, and what is new is stated precisely

Thank you for the careful reading and for restating the problem with the dog-breed example; the revision follows that restatement. Changes in the revised PDF are shown in blue.

1. Presentation (changed in the revision).

  • Assumptions. (A1) to (A3) are now an itemized list in Section 3, before Definition 1, so the theorems point to a visible list.
  • Problem statement. The second paragraph of the introduction now works through an example the way your summary does, on the cell of Figure 1a: "Suppose at most two sources are corrupted and we do not know which. The subtype is not a safe answer: if two of its six supporters are the corrupted ones, only four of the eight working sources back it, which is not a strict majority. The cell type is safe: wherever the two corrupted sources are, at least five of the eight working sources back it. (The majority is always counted over all working sources, not within a branch.)" The rule, the honest-majority anchor and the fact that safety is not correctness follow in plain words, before any formal definition.
  • Theorem 3, the densest statement, is now followed by a plain-language reading: an attack can make the rule wrong exactly when a wrong subtree already holds more than (M−f)/2(M-f)/2 clean reports.
  • Figure 1b now compares rules on the same probability reports, so the first result shown is easy to read.

2. Novelty. We agree with the facts you list. The abstract now calls the rule the classical majority-rule consensus tree at a Byzantine-quorum threshold, and the introduction names every classical ingredient before any result: (M+f)/2(M+f)/2 and M>3fM>3f are the quota and availability condition of Byzantine dissemination quorums, M>4fM>4f is the masking-quorum condition, QfQ_f is the majority-rule consensus tree at level 12+f2M\frac12+\frac f{2M}, and the gain from M>4fM>4f to M>3fM>3f comes from anchoring to the honest majority rather than to the clean output. We do not claim that the counting is hard.

What these classical results do not give, and the paper does:

  1. Error against the truth. Quorum theory is silent about ground truth. Theorem 3 gives the exact, attained error event per example and under a persistent corrupted set, separates a part that needs no labels, and Corollary 2 certifies the error from held-out data.
  2. Probability reports. Proposition 1 gives the finest safe subtree-valued rule and shows that hierarchical selective classification (HSC; Goren et al., NeurIPS 2024), run on averaged probabilities, is safe if and only if its threshold exceeds 12+f2M\frac12+\frac f{2M}.
  3. A per-profile reference. Quorum overlap shows that a given rule is safe; Theorem 1 and Proposition 7 show that on every observed profile no safe rule says more, even one that outputs a set of labels, uses source identities or sees the whole stream. The proof is short; its use is that any aggregator can be audited against QfQ_f.

These results make predictions about methods in current ML use that could have failed. Standard calibration of HSC lands below the threshold on all four datasets; calibrated to the safe rule's clean error, HSC crosses it on all three machine-source datasets with 1.2 to 2.7 times that rule's exact worst-case error, and above the threshold it matches it (Figure 1b, Table 1). The trained robust aggregator of Dhasade et al. (ICLR 2026; new run), followed by climbing, does not contain the finest safe output, and is therefore unsafe, on 10% to 28% of test profiles. The held-out certificate covers the exact test worst case on every machine-source dataset except for top-level errors on PBMC, whose test cells come from new donors, and there the label-free warning fires. New runs with nine sources (new Table 26) also make the integer structure visible: with nine sources Q2Q_2 and Q3Q_3 are different rules with the same worst-case error, with ten they are one rule with different errors.

We see the contribution as an exact answer to a question that arises whenever models or annotators are combined over a taxonomy, with testable consequences for current ML aggregation rules. The revised contribution list now marks which parts are classical.

Thank you for the clarifications and the adjustments.

My main concern that led to me giving the paper a rating of 2 was insufficient novelty, but by reading the other reviews and your rebuttal I am increasing my score to 3.

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

The paper asks what can be asserted safely when M sources report labels from a hierarchy and up to f of them are corrupted, and answers that the most specific statement consistent with a strict majority of the honest sources is the deepest subtree holding more than (M+f)/2 reports, Q_f, so that corruption removes depth before it forces contradiction (Definition 1, Theorem 1, p. 4). It proves Q_f is the finest f-safe rule even against set-valued and stateful rules (Theorem 1(iii), Proposition 7), derives its exact loss of depth with a barrier at f = M/3 (Theorem 2), its exact worst-case error under per-example and persistent adversaries with a held-out Clopper-Pearson certificate and a label-free warning (Theorem 3, Corollary 2), and, for probability reports, shows that hierarchical selective classification is f-safe iff its climbing threshold exceeds θ_c = 1/2 + f/2M (Proposition 1(iii)). The evaluation uses four datasets (CIFAR-100, FGVC-Aircraft, PBMC CITE-seq, CIFAR-10H human labels) with M = 10 sources and f = 2, 3 across per-example, persistent and label-free threat regimes, against HSC, conformal climbing, Byzantine-robust averaging, Dawid-Skene and stability certificates (Section 5). Common calibrations land below θ_c and carry 1.2 to 2.7 times the worst-case error of the finest safe rule, no overclaims occur above θ_c, and the certificate transfers except under donor shift, where the warning fires (Figure 2, Tables 1 and 3). The authors also find that safety costs abstention, with Q_2 reaching the root on 21% to 76% of examples (Table 1), and gives no advantage under the non-adaptive failures tested (Tables 2 and 21), and they conclude that practitioners should report Q_f or Q^p_f at the budget of their threat model, certify it on held-out data, and never calibrate climbing below θ_c (Section 6).

Critical strengths

S1. The problem construct is new: asking which statement survives every admissible corruption of an observed profile is not posed by consensus-tree theory (no adversary) or Byzantine quorums (overlap, not per-profile output). Anchoring to the honest majority and pricing the gap to the truth separately (Theorem 3) is the right decomposition.

S2. Optimality is proved over a large class: no set-valued, identity-aware or stateful rule can be finer (Theorem 1(iii), Proposition 7). This is what goes beyond ℓ-majority consensus (Margush and McMorris, 1981), which the authors acknowledge Q_f coincides with (Section 2, Table 5).

S3. The prices in depth and error are exact and attained rather than bounded (Theorems 2 and 3, Corollary 1), Corollary 2 certifies them from held-out data, and every closed form is verified by enumeration (Appendix C, e.g., 999,126 profile-corruption pairs for Theorem 1(i)).

S4. The θ_c prediction about a deployed rule (HSC, Goren et al. 2024) is falsifiable and confirmed: zero overclaims above θ_c on all four datasets (Figure 2), and for HSC matched to Q^p_f the certified bound equals the attack, so the 1.2 to 2.7 ratios are exact (Table 1 caption, Section 5.2, Table 9).

S5. Experimental design is thorough and self-critical: permuted-hierarchy control (Section 5.1), correlated-source control, retrained pools (Table 15), varying M (Table 17), certificate tested where it fails (Table 3), negative results stated in the abstract.

Critical weaknesses

W1. The novelty delta is narrower than the framing and is left for the reader to reconstruct. Q_f is the ℓ-majority consensus tree at ℓ = 1/2 + f/2M; τ_f and the M > 3f barrier are Malkhi and Reiter's dissemination quorum (Section 2, p. 3); coarsening instead of abstaining under a certificate exists for single models (Anani et al., ICML 2024); Theorems 1 and 2 are Lemma 1 plus counting (App. B). The new layers are the set-valued/stateful optimality, the exact certified risk and θ_c. The contribution list (p. 2) should state this delta explicitly.

W2. The strongest current robust aggregator is not compared. Dhasade et al. (ICLR 2026) show robust averaging alone is insufficient and obtain their best results from a trained DeepSet composition; the paper evaluates only their robust averaging followed by climbing (Section 2). For the aggregators that are included, the comparison is not certified: trimmed-mean bounds are up to 2.5 times the attack, the geometric median has no bound and sits at 0.97 to 1.33 times Q^p_f by attack (Section 5.2, Table 1 caption, Tables 11 and 12).

W3. Only two distinct quorum rules are effectively evaluated on the machine-source datasets: with M = 10, τ_2 = τ_3 (Section 3), so the f = 2 and f = 3 results (Tables 3, 8 and 9) are the same rule under different attack budgets. All machine-source experiments use M = 10 and at most three levels; larger M appears only for CIFAR-10H human reports (Table 23) and the synthetic timing check (App. D).

W4. The practical envelope is narrow by the authors' own numbers: Q_2 is driven to the root on 32.8%, 75.9% and 21.0% of examples (Table 1); under the non-adaptive failures no rule dominates and HSC is more accurate on most CIFAR-100 failures (Section 5.3, Table 21); bandwagon collusion gives ratios 1.01, 1.19, 0.99 (Table 2, Table 10). Section 6 says so; the title and abstract read more broadly.

W5. The human-label result carries little evidence: 95% conformal calibration gives θ = 0 on CIFAR-10H because human reports are 94.9% to 99.3% accurate (Figure 2 caption; App. D), worst-case errors are 1.2% to 2.1% (Table 3), and regime B does not apply.

W6. Related work omits Guo and Kong (WWW 2024, robust aggregation with adversarial experts, flat labels) and taxonomy-grounded aggregation of classifiers (arXiv 1512.0355, 2015).

Questions for authors

Q1. Please state which claims in Theorems 1 to 3 do not follow from majority-rule consensus trees and Byzantine dissemination quorums combined, beyond Theorem 1(iii), Proposition 7 and Corollary 2, and revise the contribution list accordingly (W1).

Q2. Can you add the trained DeepSet aggregator of Dhasade et al. (2026), or explain why Proposition 1(i) makes that comparison unnecessary in practice rather than only in the worst case (W2)?

Q3. Can you tighten the geometric-median and trimmed-mean comparisons, either with a certified bound for the geometric median or a stronger attack (Section 5.2; Tables 11 and 12) (W2)?

Q4. Can you report M = 9 or 11 on the machine-source datasets so that f = 2 and f = 3 correspond to distinct rules and the step structure of the price in depth and error is visible (W3)?

Q5. When f is unknown, what rule do you recommend, and how does the 21% to 76% no-answer share interact with it (Section 6, Table 1) (W4)?

Q6. Is there a calibration target under which the CIFAR-10H experiment is informative about θ_c, and can a persistent-annotator regime be built from a common annotator subset (W5)?

Q7. App. B states a set of labels can be safe and strictly finer than Q^p_f for probability reports. How large is that gap empirically, and does it affect the "never finer" claim for safe climbing (abstract, Proposition 1(iv))?

2 comments
AuthorsOpenReview ↗

All seven questions answered, with new runs: nine sources, DeepSet-TM, a stronger attack on robust averaging, CIFAR-10H coverage sweep and persistent panels, smallest safe sets; classical parts named in the abstract and introduction

Thank you for a precise review. Every analysis below is in the revised PDF, in blue.

Q1 (delta). Classical, and now named in the abstract and introduction: the quota and τf\tau_f, the M>3fM>3f and M>4fM>4f of dissemination and masking quorums, and QfQ_f as the ℓ\ell-majority consensus tree; single-model coarsening under a certificate is Anani et al. (2024). Beyond Theorem 1(iii), Prop. 7 and Cor. 2, what does not follow from them combined: Theorem 1(ii), that on every observed profile some admissible placement of the corrupted sources makes the honest-majority ball equal QfQ_f (overlap gives safety, not per-profile tightness); Theorem 2(ii) and Cor. 1, the exact attained depth for every honest or clean profile; and Theorem 3, the error against the truth (exact attained event per example, its persistent version, its label-free part), on which quorum theory is silent. Theorem 1(i) and 2(iii) are quorum overlap and availability, as the contributions now say.

Q2 (DeepSet-TM). Our reimplementation follows Dhasade et al. (adversarial training, f=2f=2) and is trained on half of the validation split; the climbing threshold is matched on the other half to the clean error of Q2pQ^p_2. Attacked by our point-mass and gradient searches (lower bounds), in %:

f=2f=2, testoutput not containing Q2pQ^p_2clean / depthworst caseQ2pQ^p_2: clean / depth / worst
CIFAR-10010.34.1 / 0.7013.13.3 / 0.68 / 9.4
FGVC-Aircraft19.70.9 / 0.305.80.7 / 0.17 / 4.0
PBMC27.67.9 / 0.8925.92.2 / 0.77 / 9.9

Where its output does not contain Q2pQ^p_2 it is unsafe (Prop. 1(i)). It buys depth (0.30 against 0.17 on FGVC-Aircraft) at 1.4 to 1.5 times the worst case of Q2pQ^p_2 on the image datasets; on PBMC (2.6 times) the matched threshold also fails to transfer to the test donors. Prop. 1 says no subtree-valued rule, trained or not, is both safe and finer than QfpQ^p_f, not that a trained one is worse on average; its clean leaf error is 0.4 to 1.5 points above the plain mean's, and we did not test it under non-adaptive failures.

Q3 (robust averaging). A stronger search (new Table 34) raises every attack value, by 0.7 to 3.6 points on CIFAR-100 and PBMC and by 6 to 19 on FGVC-Aircraft (geometric median at f=3f=3: 34.7 to 54.0%; Q3Q_3: 33.5%). Relative to QfQ_f, the trimmed mean and median now sit at 1.3 to 1.9 times (were 1.2 to 1.6) and the geometric median at 1.1 to 1.6 (was 0.97 to 1.33), so none is below QfQ_f any more, and the trimmed mean's certified bound is within 2.0 times its attack value (was 2.5). All stay lower bounds, which favours them; the geometric median has no certified bound.

Q4 (M = 9). All ten leave-one-out subsets (means), exact worst-case error of QfQ_f in %:

MM, ff (τf\tau_f)CIFAR-100AircraftPBMCroot share, CIFAR-100
10, 2 (7)14.618.614.432.8
10, 3 (7)21.833.522.245.3
9, 2 (6)19.027.819.231.1
9, 3 (7)19.027.819.2100

The rule moves with ⌊(M+f)/2⌋\lfloor(M+f)/2\rfloor and the error with ⌊(M−f)/2⌋\lfloor(M-f)/2\rfloor (one rule, two error levels at M=10M=10; two rules, one error level at M=9M=9, where f=3f=3 meets M=3fM=3f). HSC matched to QfpQ^p_f crosses θc\theta_c in all 90 dataset, subset and budget cases (ratios 1.08 to 4.12).

Q5 (unknown f). Set fmax⁡f_{\max} from the threat model (the most sources that can fail together) and report the chain Q0⊆⋯⊆Qfmax⁡Q_0\subseteq\dots\subseteq Q_{f_{\max}}; each element is safe at its own budget. The no-answer share of QfQ_f grows with ff (CIFAR-100: 17.5, 32.8, 45.3% at f=1,2,3f=1,2,3) and counts examples where some corruption forces the root, not abstentions. New decision costs (Table 28): under attack Q2pQ^p_2 is the cheapest rule once a wrong label costs two (FGVC-Aircraft, PBMC) or five (CIFAR-100) abstentions, safe HSC within 0.03; without attack the more specific rules win when errors are cheap. The abstract now ends with this envelope (W4).

Q6 (CIFAR-10H). Yes: 99.5% coverage. At 95%, 98% and 99%, vote-share climbing stays below the one-hot safe threshold 0.6 in every draw (2.2 to 2.7% overclaims; worst case 2.7 to 3.2% against 1.2% for Q2Q_2); at 99.5% it lands just above 0.6 and the overclaims vanish. On 145 persistent panels (ten annotators who labelled the same 200 images), the worst corrupted pair gives 1.25% against 1.35% for the per-example oracle. With clean errors near 0.4%, CIFAR-10H tests the threshold and the regimes, not large error gaps.

Q7 (sets). The smallest safe set Vf(s)=⋃∣Z∣≤fC(s−Z)V_f(s)=\bigcup_{|Z|\le f}C(s_{-Z}) is strictly smaller than Qfp(s)Q^p_f(s) on at most 0.2% of test profiles, and mean specificity moves by at most 0.001; for label reports Vf=QfV_f=Q_f always. "Never finer" concerns subtree-valued rules, which climbing is.

W6. Added and contrasted (Section 2, Table 5): Guo and Kong (Web Conference 2025) and Saha et al. (2015).

Reviewer_344BOpenReview ↗

Retaining my assessment

Thank you for author for putting a good efforts in trying to address the issues. But I'll be retaining my initial assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.