{"id":"7ab0c3ec-c579-4e05-8a86-422ccae816ee","arxiv_id":"2412.15276","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"QEDG improves data-free hard-label model stealing by generating boundary-hugging synthetic samples and reusing a single query to create multiple augmented training examples, beating prior methods with fewer queries.","lead":"A new model-stealing method, QEDG, trains a substitute model using synthetic samples generated near the target's decision boundary and adds unqueried augmented samples as extra supervision, reducing queries on MNIST and other benchmarks. A security researcher or MLaaS provider would read it because it shows how few black-box label queries are needed to clone a classifier.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The query-complexity proof assumes R repeated queries per synthetic point, but Algorithm 1 queries each point exactly once and never re-queries; the claimed guarantee does not follow.","rationale":"The reader's weakest_assumption identifies exactly the most load-bearing concern in this paper. The empirical claim of better performance with fewer queries is plausible and directly supported by the reported tables, so I do not see a reason to reject or downgrade it on those data alone. The theoretical section, however, is internally mismatched with the algorithm: the proof requires R repeated queries for majority voting over imperfect feedback, while Algorithm 1 makes one query per synthetic feature and never repeats a query. The paper's own text acknowledges the role of R in Eq. (31) for the Chernoff bound, so the gap is not a subtle interpretation issue but a concrete proof-protocol mismatch. This concern matters because the theorem is the stated basis for 'query efficient' and for adopting the consistency-rate metric; if the theorem is unsupported, that portion of the contribution is not established, even though the empirical comparison may stand on its own. The reader's CONDITIONAL verdict already captures the necessary repair: either fix the proof so it matches Algorithm 1, or clearly scope the theorem to a repeated-query variant that is not the method being evaluated. I therefore agree with the reader's assessment and recommend no change to the verdict. The concrete test above would settle whether the theorem can be salvaged: re-deriving the bound with R=1 is a direct analytical check that determines whether the stated query complexity follows from the actual protocol.","tokens_in":14442,"tokens_out":6697,"duration_ms":65135,"concrete_test":"Re-derive the query-complexity claim with R fixed to 1 in Eqs. (25)-(31), matching Algorithm 1's single-query-per-generated-sample protocol, and recompute the Chernoff bound in Eq. (30). If the resulting success probability is no longer at least 1-2δ for Q = 8·q(ε,δ)·ln(q(ε,δ)/δ)/(1-2max_x φ)^2, then the theorem does not apply to the implemented method, and the theoretical section must either be revised or explicitly scoped to a repeated-query protocol that QEDG does not use.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The theoretical section claims that QEDG achieves the query complexity in Eq. (33), but the proof only works under a repeated-query protocol. Eq. (25) fixes the size of the labeled set as R times the active-learning complexity q(ε,δ), and Eqs. (26)-(31) define τ_g = Σ_{r=1}^R τ_g^r as R independent noisy observations of the same x_g, using a Chernoff majority-vote bound to suppress the feedback error φ. Algorithm 1, however, queries the target once per generated x_g, stores {(x_g, ŷ_g)} in the memory bank, and never queries the same x_g again. The 'query-free augmentation' produces new samples x'_g from x_g, but these are not queried against the target; they are assigned the original label ŷ_g, so they are not independent repeated feedback about x_g. Consequently, the R in Eq. (31) has no counterpart in the algorithm, and the probability bound in Eq. (30) cannot be instantiated for QEDG as described. This is a load-bearing gap in the paper's argument because the theorem is offered as the theoretical justification for query efficiency and for the consistency-rate metric. The empirical tables may still be correct, but the theoretical guarantee stated in Eqs. (22)-(23) is unsupported by the presented proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes QEDG, a data-free model stealing method for hard-label black-box classifiers. The method trains a generator with a classification loss, a harmony loss based on the variance of the substitute model's prediction vector, and a diversity loss, then queries the target model once per generated sample and stores the pair in a memory bank. For samples on which the substitute already agrees with the target, QEDG applies augmentations and reuses the target label without additional queries. The paper also introduces a consistency-rate metric and presents a theoretical query-complexity theorem based on active learning with imperfect feedback. Experiments compare QEDG with HEE, DaST, DFME, IDEAL, and DFTA on MNIST, FMNIST, SVHN, CIFAR-10, CIFAR-100, and a Microsoft Azure MLaaS scenario, reporting accuracy, consistency, and transfer attack success rates.","tokens_in":14699,"tokens_out":10528,"duration_ms":100817,"significance":"If the empirical results are reproducible, QEDG would be a useful contribution to query-efficient hard-label model stealing: it reports reducing the query budget by a factor of 4-10 relative to IDEAL/DFTA while matching or exceeding accuracy, consistency, and attack transfer rates, and it includes a real MLaaS evaluation. The evaluation uses external test sets and standard metrics, so the reported gains are not an artifact of a fitted-value-as-prediction loop. The main weakness is that the theoretical guarantee does not match the algorithm as written, and the empirical claims lack variance reporting and a controlled baseline comparison. Because the theorem is presented as the formal justification for query efficiency, the gap between the proof and Algorithm 1 is load-bearing and needs to be resolved before the paper's central claims can be accepted.","major_comments":[{"comment":"The query-complexity theorem is not established for the algorithm as written. Eq. (25) sets the collected labeled set size to R times q(epsilon, delta); Eqs. (26)-(29) define tau_g as the sum of R independent noisy observations of the same x_g; and Eq. (31) chooses R via a Chernoff majority-vote argument. Algorithm 1, however, queries each generated x_g exactly once, stores (x_g, yhat_g) in the memory bank, and never re-queries that x_g. The query-free augmentation creates new samples x'_g and assigns them the original label yhat_g without asking the target, so these are not independent repeated observations of f*(x_g). Consequently, the R appearing in Eq. (31) has no counterpart in the algorithm, and the probability bound in Eq. (30) cannot be instantiated for QEDG as described. This is load-bearing because the theorem is offered as the theoretical justification for the query efficiency and for the consistency-rate metric; either the proof must be adapted to a single-query protocol, or the algorithm must be changed to re-query samples R times with the query budget increased accordingly.","section":"Theoretical Analysis, Eqs. (25)-(33) vs. Algorithm 1"},{"comment":"The central empirical claim 'better performance with fewer queries' is not yet statistically supported. Tables 1-3 report single-run results without standard deviations or the number of seeds, and several differences are small, for example MNIST FGSM untargeted: Ours 41.37 vs. HEE 40.09, and CIFAR-10 PGD untargeted: Ours 78.64 vs. DFTA 78.16. In addition, the baseline numbers appear to be taken from earlier papers at different query budgets and possibly different training protocols; for example, Table 2 compares Ours at 30K queries with DFTA/IDEAL at 50K and HEE at 1000K on SVHN, and similar asymmetries appear on the other datasets. The authors should report mean and standard deviation over multiple seeds and rerun or clearly mark baselines under an identical target/substitute architecture and training protocol before claiming a consistent advantage.","section":"Experiments, Tables 1-3"},{"comment":"The formal loss in Eq. (14) does not match Algorithm 1. Eq. (14) assigns weight gamma to any sample for which S(x_g, theta_S^(t-1)) != yhat_g, but Algorithm 1 applies the weighted update only in the else branch for the original stored sample; for a non-disputed sample, the algorithm augments x_g and trains on (x'_g, yhat_g) with an unweighted loss L(x'_g, yhat_g). It is not specified whether the condition in Eq. (14) is evaluated on x_g or on x'_g, and the augmentation branch is not reflected in the equation. Please state the exact loss for each branch or modify Eq. (14) so that it corresponds to the pseudocode.","section":"Algorithm 1, Eq. (14)"},{"comment":"Even apart from the repeated-query issue, the theorem's formal setting does not match the hard-label model-stealing problem. In the threat model, the target's feedback yhat = T(x) is deterministic, so if f* is defined as the target's decision function then phi(f*, x) = 0 for every x and the noise condition max_x phi < 1/2 is vacuous; if f* is instead a ground-truth function, then the adversary wants to match T, not f*, and feedback errors relative to f* are irrelevant. The theorem should be stated as a generic active-learning-with-noise bound, or the model should be reformulated so that the noise models a concrete defense mechanism while f* remains the target function. In its current form the theorem does not explain the query-efficiency mechanism of QEDG.","section":"Theoretical Analysis, Eqs. (21)-(23)"}],"minor_comments":[{"comment":"The 'Theoretical Analysis' section appears twice with essentially the same theorem text; the proof in Eqs. (24)-(33) appears after Related Work rather than as a clearly labeled appendix. Consolidate or label the sections to avoid duplication.","section":"Paper structure"},{"comment":"Algorithm 1 says 'while q <= Q' with q initialized to 0, so the loop runs Q+1 times; additionally, the pseudocode uses xg as a single sample while Eqs. (10)-(11) operate on a batch of N synthetic features. Clarify whether one query or one batch is spent per iteration and how q is incremented.","section":"Algorithm 1"},{"comment":"Eq. (20) defines Cohen's kappa correctly, but the adjacent text swaps the roles: po is the observed agreement and pe is the expected agreement, not 'accidental consistency'.","section":"Eq. (20) and surrounding text"},{"comment":"The implementation details state 'For both MNIST and FMNIST, the perturbation bound is respectively set to 0.3, 0.2, and 0.1'; since there are two datasets, specify which bound is used for each dataset.","section":"Implementation details"},{"comment":"The ablation in Table 4 is performed on CIFAR-10 only; given that the loss-scale hyper-parameters alpha and beta are dataset-dependent and Table 2 shows different gains per dataset, please state whether the component contributions are qualitatively consistent on at least one additional dataset.","section":"Ablation study, Table 4"},{"comment":"The claim that the generated samples 'closely and uniformly align with the target model's decision boundary' is stronger than what L_harm and L_div implement: these losses use the substitute model's prediction variance, not the target model's boundary. Please rephrase the claim or provide evidence that substitute-boundary closeness translates to target-boundary closeness.","section":"Introduction and Proposed Framework"},{"comment":"Eq. (1) writes T and S as real-valued functions with one-dimensional output, whereas Eq. (2) and the experiments treat them as classifiers returning labels. Use consistent notation for K-class outputs.","section":"Threat model, Eq. (1)"},{"comment":"The related-work text says 'we used more queries on both datasets' when three datasets (SVHN, CIFAR-10, CIFAR-100) are introduced at that point; fix the wording.","section":"Related Work"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the empirical core is real: the harmony and diversity losses plus the query-free augmentation give strong gains at low query budgets, and the consistency-rate metric is a good addition. Second, the theory section does not match the algorithm. The theorem's proof assumes R repeated queries of each synthetic point with majority voting; Algorithm 1 queries each point once. The R never materializes, so the stated query-complexity bound is unsupported. That is not a minor typo, it is the paper's main theoretical claim.\n\nWhat the paper does well: it re-examines the cooperative-game stealing setup and identifies that existing generators produce overconfident samples. The two new losses are simple and plausible: variance of the softmax vector pushes samples toward decision boundaries, and pairwise cosine distance spreads them out. The query-free augmentation reuses labels for augmented non-disputed samples, which is a neat trick. The ablation on CIFAR10 is careful and shows each component contributes, with the full combination best. The real MLaaS demo with Azure is a nice sanity check.\n\nWhere it is soft, in proportion: the proof gap is the big one, as above. Also, all tables are single runs without error bars; baseline numbers are taken from prior papers at different query budgets. These are common in this literature but they do weaken the magnitude claims. The sensitivity analysis is only on MNIST, so we do not know if the hyperparameters transfer.\n\nWho this is for: anyone working on model stealing or black-box attacks. The method is a plausible step forward and the consistency-rate metric is worth adopting even if the theory never gets fixed.\n\nMy recommendation: send it to peer review. A serious referee can push for the theory to be aligned with the algorithm, or for the claim to be scoped down to a repeated-query protocol the method does not implement. I would also require code and seeds. If the empirical results hold after those changes, this is a useful contribution.","headline":"Solid empirical stealing method with a new loss pair and metric, but the proof assumes repeated queries the algorithm never makes.","tokens_in":15235,"tokens_out":2619,"would_cite":true,"duration_ms":27589,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Data-free model stealing can be made far more query-efficient by generating synthetic samples on the decision boundary of the substitute model and reusing each query's label through light augmentations.","keywords":["data-free model stealing","hard label setting","query efficiency","decision boundary","model extraction","query-free augmentation","consistency rate","adversarial transferability"],"falsifier":"A direct test would count, during training, the fraction of generated samples for which the substitute and target disagree; if decision-boundary generation does not raise this disputed-sample rate well above the plain classification-loss baseline, the proposed losses are not the source of the query savings. A second test would replace the harmony and diversity losses with uniform sampling from the substitute's decision boundary and compare accuracy, consistency, and attack success at the same query budget.","tokens_in":14228,"feed_emoji":"🕵️","tokens_out":10848,"duration_ms":87234,"temperature":0.7,"pith_summary":"The paper tries to establish that data-free model stealing—cloning a black-box classifier that only returns top-1 labels—can be made dramatically more query-efficient. It proposes QEDG, which generates synthetic samples on and spread around the substitute model's decision boundary, and recycles each query's label through light augmentations that preserve the label. The claim is that this yields a substitute model with higher accuracy, higher consistency with the target, and higher transfer attack success than existing methods, using a fraction of the queries—typically one quarter to one tenth of the strongest baselines' budgets. If true, deployed MLaaS models are cheaper to clone and attack, weakening the protection offered by hard-label APIs.","feed_headline":"Black-box models stolen with a fraction of the queries","feed_subtitle":"Two loss functions plus label-preserving augmentation slash the query cost of cloning deployed classifiers.","key_machinery":"The generator objective is $L_G = L_{clf} + \\alpha\\, \\mathrm{Var}(S(x)) - \\beta\\, d(x_i,x_j)$, where $\\mathrm{Var}(S(x))$ is the variance of the substitute's output scores across classes (the harmony loss) and $d$ is cosine dissimilarity (the diversity loss). Minimizing the variance pushes synthetic samples toward the substitute's decision boundary; maximizing pairwise distance spreads them uniformly along it. The query-free augmentation completes the machinery: non-disputed samples are given light flips or rotations, their target labels are kept, and the augmented pairs are used to train the substitute at zero additional query cost. The paper's theorem supplies a query-complexity bound for stealing with imperfect feedback, $Q = \\frac{8}{(1-2\\max_x \\phi)^2} q(\\epsilon,\\delta) \\ln\\frac{q(\\epsilon,\\delta)}{\\delta}$, which motivates the consistency-rate evaluation metric.","core_discovery":"The central discovery is that the generator's objective is the bottleneck: minimizing the substitute's classification loss on synthetic samples produces overconfident samples on which the substitute and target already agree, so queries are wasted. QEDG replaces that objective with a combined loss: a harmony loss that minimizes the variance of the substitute's class scores to drive samples onto its decision boundary, and a diversity loss that maximizes inter-sample distance to cover the boundary uniformly. Queries to the target are then made on these boundary samples, so many land in the disputed area where the substitute and target differ; the resulting 'pessimistic' samples give strong learning signal. Query-free augmentation multiplies this signal: non-disputed samples are lightly transformed and their target labels reused, adding supervised information at zero query cost. The paper also gives a theorem bounding the query complexity of stealing with imperfect feedback, showing only a logarithmic overhead over clean active learning, and introduces consistency rate/Cohen's kappa as a more faithful evaluation metric.","pith_inferences":["The theorem's repeated-query assumption does not match the single-query algorithm, so an interesting next question is whether a single-query variant can be analyzed under a different feedback model; the empirical results suggest it can still work, but the guarantee is not yet proven.","The decision-boundary sampling idea transfers naturally to other label-only problems—such as query-efficient adversarial example search or model inversion—where hitting the disputed region is exactly what reveals useful information.","The query-free augmentation relies on the stability of hard labels under light transforms for non-disputed samples; on high-resolution or fine-grained classification tasks this stability may weaken, which would shrink the method's advantage over stronger augmentation pipelines.","Because the generator only ever sees the substitute model's boundary, the method's efficiency may depend on the substitute architecture being rich enough to represent the target's decision surface; a wider capacity gap could lower the disputed-sample hit rate."],"forward_implications":["With a few thousand to a few hundred thousand hard-label queries, an attacker can train a substitute that matches the target's accuracy on five datasets and exceeds the accuracy of baselines that use up to ten times more queries.","Adversarial examples transferred from the substitute achieve higher or comparable attack success rates at much lower query budgets, so the stolen model is a better weapon.","Substitute fidelity measured by consistency rate and Cohen's kappa tracks the query-efficiency gains better than accuracy alone, which should change how model-stealing defenses are evaluated.","Because the method needs so few queries, existing query-based defenses and anomaly detectors that raise alarms after many queries give less protection than assumed."],"supporting_citations":[{"why":"DaST, the first data-free substitute training method, whose cooperative-game formulation and generator are the starting point QEDG modifies.","marker":"Zhou et al. 2020"},{"why":"DFTA, the query-efficient baseline QEDG compares against; it stores generated samples and uses a cooperative game objective.","marker":"Zhang et al. 2022"},{"why":"IDEAL, the other query-efficient baseline that QEDG must beat, also built on the cooperative game framework.","marker":"Zhang, Chen, and Lyu 2022"},{"why":"HEE, the memory-bank stealing baseline whose strong data augmentation QEDG contrasts with its label-preserving augmentation.","marker":"Yuan et al. 2024"},{"why":"PRADA, the detection mechanism that motivates limiting query counts to avoid being flagged.","marker":"Juuti et al. 2019"},{"why":"Supplies the query-synthesis active learning model and complexity definition the theorem uses.","marker":"Alabdulmohsin, Gao, and Zhang 2015"},{"why":"StyleGAN, the generator architecture adopted for synthesizing the query images.","marker":"Karras, Laine, and Aila 2019"}],"fun_headline_variants":["Boundary samples slash query cost for model stealing","Steal models with fewer queries using boundary-aware generation","Data-free model stealing with query-efficient boundary sampling","QEDG: cut queries for data-free model stealing","Model stealing with reduced queries via boundary-focused generation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the query-complexity bound assumes the attacker queries each synthetic sample several times and takes a majority vote, while Algorithm 1 queries every generated sample exactly once, so the theoretical guarantee does not follow from the argument as written and the claimed efficiency rests on the empirical comparisons.","fun_headline_variants_meta":{"raw":{"variants":["Boundary samples slash query cost for model stealing","Steal models with fewer queries using boundary-aware generation","Data-free model stealing with query-efficient boundary sampling","QEDG: cut queries for data-free model stealing","Model stealing with reduced queries via boundary-focused generation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0005,"raw_usage":{"total_tokens":2464,"prompt_tokens":979,"completion_tokens":1485,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":595,"completion_tokens_details":{"reasoning_tokens":1411}},"tokens_in":595,"tokens_out":1485,"duration_ms":10233,"temperature":1.0,"reasoning_tokens":1411,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:06:27.238524+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct test would count, during training, the fraction of generated samples for which the substitute and target disagree; if decision-boundary generation does not raise this disputed-sample rate well above the plain classification-loss baseline, the proposed losses are not the source of the query savings. A second test would replace the harmony and diversity losses with uniform sampling from the substitute's decision boundary and compare accuracy, consistency, and attack success at the same query budget.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"DaST, the first data-free substitute training method, whose cooperative-game formulation and generator are the starting point QEDG modifies."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"HEE, the memory-bank stealing baseline whose strong data augmentation QEDG contrasts with its label-preserving augmentation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"PRADA, the detection mechanism that motivates limiting query counts to avoid being flagged."},{"cited_title":"M.; Gao, X.; and Zhang, X","cited_arxiv_id":null,"evidence_quote":"Supplies the query-synthesis active learning model and complexity definition the theorem uses."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"StyleGAN, the generator architecture adopted for synthesizing the query images."}],"review_version":1}