acceptodds
Withdrawn from ICLR 2027

What Response Marginals Miss: Adaptive Query Complexity of Functional Backdoor Recovery

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Functional backdoor recovery finds any trigger whose attack success rate is at least a given threshold rather than to recover the planted trigger. We study the minimum number of queries required for this task under label feedback which returns the predicted class label. We construct two finite families of victim models that have exactly the same attack success rate for every victim and trigger candidate. The distribution of returned labels for every query is also identical under a uniformly chosen victim. These families form an explicit counterexample that despite the matched quantities, their optimal adaptive query complexities are and where is the number of possible victims. The difference arises because the same non-target labels are associated with different sets of victims, so successive queries eliminate possible victims at different rates. This separation disappears when the response is reduced to binary feedback, which reports only whether the target label is returned. The separation also persists for every fixed failure probability below one. Finally, we realize the same recovery problems with trained CIFAR-10 ResNet-18 classifiers and verify the predicted optimal query budgets. These results show that attack success rate and the distribution of returned labels for each query are insufficient to determine the query complexity of functional backdoor recovery.

Primary area:
learning theory
Keywords:
backdoor attacks, functional backdoor recovery, trigger recovery, black-box model queries, adaptive query complexity

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_qCssOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the optimal adaptive query complexity of functional backdoor recovery: finding any admissible trigger whose attack success rate meets a prescribed threshold. Its main contribution is a constructive separation between two finite model families with identical victim–candidate attack-success tables and identical per-query label marginals under a uniform prior over models. Despite these matched statistics, their optimal worst-case query budgets under label feedback grow logarithmically and linearly, respectively, with the number of possible models. Under binary target/non-target feedback, the two families become indistinguishable. Extensions establish that the separation persists with bounded error and overlapping successful-trigger sets, where exact model identification is unnecessary. The authors implement the constructed response structures in CIFAR-10 ResNet-18 models, exhaustively verifying the prescribed fixed-source response tables and thresholded success sets while maintaining clean accuracy. Supplementary experiments compare binary and label feedback for a specified search heuristic on conventional backdoor models, finding no consistent benefit from retaining non-target labels. Overall, the paper demonstrates that attack-success statistics and individual-query response marginals do not determine adaptive recovery difficulty; relationships among responses across queries also matter.

Critical strengths

1.A precise separation under strong matching conditions. The paper constructs families with identical victim–candidate attack-success tables and identical per-query label marginals, yet proves logarithmic versus linear optimal adaptive query complexity. Matching both statistics makes the result consequential: even detailed measurements of trigger effectiveness and individual-query responses can miss essential aspects of recoverability. The bounded-error and overlapping-success-set extensions further establish that the separation persists beyond zero-error recovery and exact model identification. This provides a rigorous foundation for considering the relationships among query responses when assessing recovery difficulty. 2.Controlled neural-network validation of the theoretical construction. The CIFAR-10 ResNet-18 experiments exhaustively verify the prescribed fixed-source response tables and check the corresponding thresholded success sets while retaining strong clean accuracy. Together with the transfer proposition, these checks support the claimed optimal budgets for the restricted experimental problems. This strengthens the contribution by demonstrating that the constructed response structures can coexist with normal classification performance in trained neural networks.

Critical weaknesses

1.Limited coverage of broader recovery interfaces. The exact separation concerns a prescribed finite query space, and the neural realization certifies it under a fixed-source interface. The paper does not establish whether the separation persists when source images or candidate transformations can be selected more freely. This limits the result’s implications for broader black-box recovery settings, while leaving the stated existence theorem intact. 2.Limited empirical characterization of the relevant response structure. The neural experiments establish that the designed response tables are realizable. However, Appendix D evaluates a particular search policy without directly measuring how cross-query dependencies contribute to recovery difficulty in conventional backdoors. Consequently, the paper provides limited evidence about when the identified information structure matters outside the constructed examples, constraining its broader explanatory significance.

Questions for authors

1.Clarification of the neural realization’s scope. Were the prescribed non-target response patterns checked on source images beyond the single audited image? If such results are already available, how consistently do the FAST/SLOW response structures persist across images? This would help assess whether source-image selection could substantially change the observed separation. 2.Clarification of the supplementary evidence. Do any existing analyses or search logs from Appendix D indicate whether non-target labels provide additional information about successful candidates after conditioning on the previous query history and target/non-target outcomes? Can the available evidence distinguish between uninformative additional feedback and a search policy that fails to exploit useful information? Such evidence would help assess whether the mechanism identified by the theoretical construction also matters in the conventional-backdoor experiments.

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

This paper studies functional backdoor recovery in black-box settings and investigates whether ASR and per-query response marginals are sufficient to characterize adaptive query complexity. The authors construct two problems, FAST and SLOW, with identical ASR and response marginals, yet prove that their optimal query complexities are �0��0� and �1��1�, respectively, showing that recovery difficulty depends on structural information not captured by response marginals. The authors further demonstrate the realizability of these theoretical constructions using ResNet-18 models trained on CIFAR-10.

Critical strengths
  1. The paper identifies a clean and non-trivial limitation of commonly used summary statistics for functional backdoor recovery. The central counterexample is conceptually strong: the FAST and SLOW families are constructed to have identical ASR for every victim–trigger pair and identical per-query response marginals under a uniform victim prior, yet their optimal adaptive query complexities differ from �0��0� to �1��1�. This cleanly demonstrates that marginal response statistics alone do not characterize black-box recoverability; the association between responses and latent victims across successive queries matters.

  2. The theoretical separation is carefully controlled and supported by several useful extensions. The paper goes beyond a single zero-error counterexample: the separation persists under fixed non-zero failure probability, the authors consider a variant where recovery does not require exact victim identification, and the separation disappears under binary feedback. In particular, the binary-feedback result helps isolate the source of the separation to information contained in non-target labels rather than simply differences in trigger success rates.

  3. The paper makes a meaningful effort to connect the abstract construction to trained neural networks. Rather than leaving FAST/SLOW as purely combinatorial response tables, the authors instantiate them using trained CIFAR-10 ResNet-18 classifiers and verify all victim-query responses and functional trigger sets. For H=12,24,48H=12,24,48, the learned models exactly reproduce the prescribed finite recovery problems, allowing the theoretical query budgets to transfer without approximation.

Critical weaknesses
  1. There remains a gap between the theoretical FAST/SLOW constructions and practical backdoor attacks. The core complexity separation in this paper is established using artificially designed FAST/SLOW response tables. In Section 5, the experiments explicitly assign target labels to triggered samples so that the trained models reproduce the predefined OhF(q)O_h^F(q) and OhS(q)O_h^S(q). Therefore, these experiments provide strong evidence that the theoretical constructions can be realized by neural networks, but they do not establish whether similar response structures and complexity separations arise naturally in standard backdoor attacks.

  2. The additional experiments on standard backdoor attacks provide limited empirical support for the practical significance of the core theoretical finding. Appendix D further compares binary feedback and label feedback on BadNet, GRASP, and BELT+. Under the LinUCB search policy used in the experiments, retaining the full class labels does not consistently improve recovery performance: at the largest query budget, label feedback yields a slight improvement for BadNet, a slight decrease for GRASP, and no successful recovery for BELT+ under either feedback setting. Therefore, the current empirical results do not yet clearly demonstrate how much the label-response structure identified in the main theoretical analysis affects backdoor recovery in practical settings.

Questions for authors
  1. Do the response structures revealed by FAST/SLOW naturally arise in existing backdoor attacks? The paper constructs two recovery problems, FAST and SLOW, and shows that even when they have identical ASR and identical per-query response marginals, their optimal adaptive query complexities can differ by an order of magnitude. However, the theoretical constructions rely on carefully designed response tables, and the experiments in Section 5 realize these structures by explicitly assigning training labels to triggered samples. Could the authors further analyze the response structures of standard backdoor attacks such as BadNet, GRASP, or BELT+ to examine whether similar complexity separations arise naturally? This would help clarify the practical relevance of the theoretical findings to real-world backdoor recovery.
  2. How do the authors interpret or characterize the key information beyond response marginals that determines recovery complexity? The paper shows that identical ASR and per-query response marginals can still lead to substantially different optimal recovery complexities, and attributes this difference to the association between response labels and hidden victims, as well as to how successive queries partition the remaining victim space. Could the authors further clarify, within the existing theoretical framework, how this additional structural information should be understood, and what specific property of the FAST/SLOW constructions leads to the θ(log⁡H)\theta(\log H) versus θ(H)\theta(H) complexity separation?
Reviewer_Y6jcOpenReview ↗
Rating
1
Confidence
3
Informativeness
3
Presentation
3
Soundness
1
Read review
Paper summary

This paper investigates the adaptive query complexity of functional backdoor recovery under black-box label feedback. The authors examine whether attack success rates (ASR) and marginal response distributions are sufficient to characterize the minimum number of queries required to recover an effective trigger. To address this question, they construct two families of victim models, FAST and SLOW, that share identical ASR values and response marginals but exhibit optimal query complexities of (Θ(log⁡H)\Theta(\log H)) and (Θ(H)\Theta(H)), respectively, where (HH) denotes the number of candidate victim models. The authors further extend the theoretical results to nonzero failure probabilities and binary feedback settings. Finally, they train CIFAR-10 ResNet-18 classifiers to reproduce the constructed response patterns and verify the predicted query budgets. The results demonstrate that marginal response statistics alone are insufficient to characterize the complexity of adaptive functional backdoor recovery.

Critical strengths

Rigorous Theoretical Analysis. The paper provides a mathematically rigorous construction demonstrating that identical attack success rates and response marginals do not necessarily imply similar adaptive query complexities. The theoretical results are supported by formal proofs, including extensions to nonzero failure probabilities and binary feedback.

Clear and Controlled Experimental Validation. The experiments systematically instantiate the theoretical FAST and SLOW constructions using trained ResNet-18 classifiers. By verifying both the prescribed response mappings and functional trigger sets, the authors establish a clear correspondence between their theoretical results and the trained models.

Critical weaknesses

Oversimplified and Discretized Trigger Search Space. The paper assumes a finite, predefined set of trigger candidates, whereas practical backdoor recovery typically involves searching a high-dimensional, continuous trigger space. In such settings, neither FAST nor SLOW can generally guarantee exact identification of the underlying model or trigger with finitely many black-box queries without additional structural assumptions. Consequently, the proposed complexity separation primarily characterizes identification within an artificially discretized hypothesis space, rather than the fundamental difficulty of recovering triggers in realistic settings. The authors should clarify whether their findings extend to continuous trigger spaces and what assumptions would be required.

Limited Theoretical Novelty. The proposed complexity separation largely resembles classical results in adaptive hypothesis identification and decision-tree theory. FAST exploits informative partitions of the hypothesis space, while SLOW relies on queries that eliminate candidates individually. The paper does not sufficiently clarify what new theoretical insights are established beyond these well-understood principles, particularly in the context of backdoor security.

**Unrealistic Knowledge Assumptions. ** The analysis assumes that the defender knows the complete candidate victim family and its query-response mappings. In particular, the logarithmic complexity of FAST relies on prior knowledge of how query responses encode victim identities. Such information is generally unavailable in realistic black-box settings, and acquiring it may itself require substantial effort or queries. This raises concerns about the operational relevance of the proposed complexity bounds.

Questions for authors

What practical backdoor inspection scenarios motivate the assumption that the defender knows the complete family of possible victim models and their query-response mappings?

How does the resulting family-level query complexity inform the recoverability of a trigger from a single unknown backdoored model?

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

Related papers

Discussion (0)

Sign in to comment.