{"id":"2d13687a-3cc0-4eb4-bbb3-18852ccef51f","arxiv_id":"2411.14498","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"Delta-NAS encodes pairs of one-edit-away architectures as sparse differences and learns to predict the accuracy gap, using that predictor to guide evolutionary search.","lead":"Delta-NAS predicts the accuracy difference between two similar network designs instead of predicting each design's raw accuracy. The authors argue this difference-based encoding lets architecture search scale to very large design spaces at low computational cost.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The exponential-to-linear complexity claim is a category error: Theorems 3-5 bound the number of difference-encoding types, not the query complexity of Algorithm 2, so the central contribution is unsupported.","rationale":"The reader's REJECT verdict is warranted, but my primary reason differs from the reader's designated weakest assumption. The reader focused on the unvalidated Zen-Score proxy; I focus on the complexity claim, which is the paper's stated strongest contribution. The two concerns are independent: the complexity issue would remain even if the proxy were perfectly calibrated. I credit the paper for a plausible difference-encoding idea and for reporting predictor correlation numbers in Table 1, but Algorithm 2's complexity is never analyzed, and Theorem 4 is a statement about encoding-set cardinality, not algorithmic cost. A clear restatement of the scaling claim and a convergence analysis would be needed to salvage the contribution. Since this reinforces, rather than changes, the existing rejection, the verdict should remain unchanged.","tokens_in":10173,"tokens_out":11722,"duration_ms":112160,"concrete_test":"Re-derive the total number of difference-predictor evaluations per run of Algorithm 2 as Q = P * T * |D1(p)|, with |D1(p)| = O(nr). For the paper's hyperparameters (P=256, T=96k) on NASBench101, this is over 300 million queries, far exceeding the roughly 432k architectures in |A|. Then run the algorithm with n scaled from 3 to 6 cell nodes, keeping P and T fixed, and measure T* needed to reach 95% of the global optimum. If T* grows with n, the end-to-end complexity is not linear in n; if T* is flat, the claim should be restated as O(log|A|) for a fixed budget, not linear in search-space size.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline contribution, 'reducing computational complexity from exponential down to linear with respect to the size of the search space,' is not established by the theory. Theorem 4 computes |D1| = rn and contrasts it with |A| = r^n, but |D1| is the cardinality of the set of one-edit difference encodings, not the running time of Algorithm 2. Algorithm 2 enumerates the one-edit neighbors of each population member: per generation it makes O(|P| * n * r) difference-predictor queries, repeated for T generations. The theorems say nothing about how large T must be to find a near-optimal architecture, and on an arbitrary accuracy landscape a one-edit hill-climber can require exponentially many steps (e.g., a needle-in-a-haystack optimum). Moreover, n = log_r |A|, so a per-generation cost that is polynomial in n is logarithmic in |A|, not linear in |A| as the abstract claims. The 'linear to exponential' phrasing conflates the size of a compressed encoding dictionary with the cost of search. Even if the proxy experiments were perfect, this gap invalidates the central theoretical claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"Delta-NAS proposes to perform neural architecture search by predicting the accuracy difference between pairs of nearby architectures, rather than predicting the absolute accuracy of an architecture. The paper contributes a set of cardinality theorems for 'difference of architecture' (DoA) encodings, a predictor trained on Zen-Score accuracy differences, and an evolutionary algorithm that repeatedly moves a population to the most promising one-edit neighbor according to the difference predictor. The authors claim that this difference projection reduces computational complexity 'from exponential down to linear' with respect to the size of the search space, and they report predictor correlation results (Table 1) and convergence plots (Figures 4-5) on NASBench101, NASBench201, TransNASBench, and NASBench301.","tokens_in":10398,"tokens_out":8720,"duration_ms":80025,"significance":"If the central claim were correct, Delta-NAS would be a substantial advance: it would make fine-grained search feasible on very large architecture spaces at an apparent low cost, and the difference encoding idea is a plausible way to exploit locality in NAS. The manuscript does contain a correct elementary analysis of the size of the one-edit difference encoding for block-based spaces (Theorem 4 and Theorem 5 are simple but valid under their definitions). However, the headline complexity claim is not established: the theorems count encoding types, not the query complexity of the search algorithm, and one of the baseline cardinality theorems is mathematically wrong. The empirical evaluation is also incomplete because the proxy-based training signal is never validated against true benchmark accuracies and the convergence plots are not accompanied by numeric final-accuracy tables. The contribution as presented is therefore not ready for publication.","major_comments":[{"comment":"The abstract and conclusion claim that Delta-NAS reduces computational complexity 'from exponential down to linear with respect to the size of the search space.' This does not follow from the theorems. Theorem 4 merely counts the number of one-edit difference types: |D1| = rn. It says nothing about how many predictor queries Algorithm 2 makes or how many generations T are needed to approach an optimal architecture. Algorithm 2 makes O(|P| * n * r) predictor queries per generation and is run for T generations; none of Theorems 1-5 bound T or the query complexity. Since n = log_r |A| for block-based spaces, a cost polynomial in n is logarithmic in |A|, not linear in |A| as stated. The paper also does not address the fact that a one-edit hill-climber can take exponentially many evaluations on an adversarial accuracy landscape, so the claimed 'exponential to linear' reduction is unsupported.","section":"§3, Theorem 4 and Algorithm 2"},{"comment":"The claimed cardinality |A| = n(n-1)/2 * r^n for cell-based spaces is incorrect. The upper-triangular adjacency matrix contains n(n-1)/2 binary edge variables, so the number of distinct adjacency matrices is 2^{n(n-1)/2}; with r operations per node the correct cardinality is 2^{n(n-1)/2} r^n. The paper appears to confuse the dimension of the edge-encoding space with its cardinality. As a concrete check, for NASBench101 (5 nodes, 3 operations) the formula gives 10 * 3^5 = 2430 architectures, whereas the benchmark contains 423k architectures. This error invalidates the comparison with |D1| for cell-based spaces. In addition, the paper never specifies what a 'one edit' means in a cell-based space (operation change, edge toggle, or both), so |D1| = rn cannot be directly applied to cell-based search spaces without further clarification.","section":"§3, Theorem 2"},{"comment":"The DoA predictor is trained on accuracy differences computed with the zero-cost Zen-Score proxy, not on the ground-truth accuracies available in the tabular benchmarks. The paper never validates that Zen-Score differences correctly rank true accuracy differences on NASBench101, NASBench201, or TransNASBench. If the proxy's local differences do not match real accuracy differences, Algorithm 2 will be guided by a misleading score and the convergence improvements shown in Figures 4-5 would not reflect genuine NAS performance. In addition, Table 1 does not specify how Kendall's Tau is computed for a difference predictor: the DoA model outputs pairwise differences, not absolute accuracies, so the comparison with encodings trained for absolute-accuracy prediction (ADJ, Path, ZCP, Arch2Vec, CATE, FLAN) is ambiguous unless the evaluation protocol for pairwise ranking is stated explicitly.","section":"§4.1 and §5.2, Table 1"},{"comment":"The central empirical claims--faster convergence and 'significantly higher sample efficiency' over SEP and other baselines--are supported only by convergence plots. No tabulated final test accuracies, standard deviations, or statistical significance measures are reported for any benchmark, and the text repeatedly asserts superiority without giving the reader numeric evidence. The broken reference to 'Appendix ??' for the TransNASBench results means those results are not available in the manuscript. To substantiate the stated claims, the paper needs tables of final accuracy (with runs, means, and variances) for each method and each benchmark, not only curves.","section":"§5.3, Figures 4-5"}],"minor_comments":[{"comment":"The manuscript contains numerous typos and grammatical errors, including 'key roll' (abstract), 'dubed', 'carnality' (Section 4.1), 'imediately' (Section 5.1.2), 'evalutation' (Section 2), 'Graph Convoulional' (Section 2.1), 'cardinally' (Section 3), and 'hyperparammeter' (Section 5.1.2); a careful proofreading pass is needed.","section":"Throughout"},{"comment":"The text cites 'FLAN [1]' and describes a 'flow attentive hybrid encoder', but reference [1] is Akhauri and Abdelfattah, 'Encodings for prediction-based neural architecture search', which does not appear to match the cited method; the reference should be checked and corrected.","section":"Section 2.3, Reference [1]"},{"comment":"The text states that NASBench301 is 'the largest space we consider with 1021 architectures', which is inconsistent with Table 1's header reporting percentages of '9k samples'; the relationship between the search-space size and the number of samples should be clarified.","section":"Section 5.1.1 and Table 1"},{"comment":"The symbol n is overloaded: Definition 1 sets n as the number of nodes or depth of a network, but Section 4.1 also uses n for 'the number of samples for each difference encoding'; using a different symbol for the sample count would remove ambiguity.","section":"Section 4.1"},{"comment":"The y-axis label 'predictor loss' is not defined in the text; the paper should state which loss function is plotted, on which dataset it is evaluated, and whether the loss is for the DoA predictor only.","section":"Figure 3"}],"recommendation":"reject","confidential_remarks":"I concur with the reader's assessment. The theoretical section is the main advertised contribution, and its central claim is a category error: the cardinality of D1 is definitional, not a bound on the search algorithm's complexity, and Theorem 2 is numerically wrong. The empirical sections, as presented, do not compensate because the proxy is unvalidated and no final-accuracy tables are given. If the authors substantially reframe the work as an empirical study of difference encodings with rigorous validation and corrected claims, a future submission could be reconsidered, but the current manuscript is not publishable in its present form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The interesting nugget here is the difference-of-architecture encoding and the local difference predictor. That is genuinely new relative to BRP-NAS, which learns pairwise rankings rather than accuracy gaps, and I don't know of prior work using sparse difference encodings for NAS. The method is plausible: predicting how a one-edit change affects accuracy seems like a reasonable way to guide evolutionary search, and Table 1 shows the DoA encoding has competitive predictor correlations. The paper also positions itself honestly against SEP and other evolutionary baselines.\n\nBut the central claim, repeated in the abstract and conclusion, is not established. Theorems 3–5 count the cardinality of difference-encoding sets. |D1| = rn is the size of the set of one-edit encodings, not the running time of Algorithm 2. Algorithm 2 enumerates all one-edit neighbors of each population member, so each generation costs O(|P|·n·r) predictor queries, repeated for T generations. The paper never analyzes how large T must be to find a near-optimal architecture, and on a needle-in-a-haystack landscape a one-edit hill-climber can need exponentially many steps. Phrasing the contribution as 'exponential down to linear with respect to the size of the search space' is a category error: n is logarithmic in |A|, so polynomial-in-n cost is logarithmic in |A|, not linear. The theorems are correct but they support the encoding size, not the search cost.\n\nThe second soft spot is the training signal. The difference predictor is trained on Zen-Score accuracy differences, not on true trained accuracies. The paper never validates that Zen-Score's local differences rank true accuracy differences correctly. If the proxy is misleading, the evolutionary search is guided by noise and the benchmark gains could be artifacts. This needs direct validation before the method can be trusted.\n\nThe experiments are also underreported. There are no final accuracy tables, no error bars, the Table 1 protocol is unclear (what exactly is being compared, and what are the baselines' hyperparameters?), and there is no code. Figures 4–5 are suggestive but not sufficient to support the 'state-of-the-art' claim.\n\nWho is this paper for? Researchers working on predictor-based NAS and zero-cost proxies might find the difference-encoding concept worth exploring, but they should not cite it as evidence for linear scaling. It deserves a serious referee because the core idea is salvageable, but the current version needs major revision: a rigorous complexity analysis, a validation of the proxy, and complete benchmark reporting. I would send it to review with the expectation of heavy revision, but I would not accept it as is.","headline":"The difference-encoding idea is genuinely new and the cardinality theorems are correct, but the exponential-to-linear complexity claim does not follow from them, and the zero-cost proxy is never validated against true accuracies.","tokens_in":10931,"tokens_out":3021,"would_cite":false,"duration_ms":30213,"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":"Delta-NAS claims that predicting accuracy differences between neighboring architectures cuts NAS search complexity from exponential to linear, with benchmark results supporting it.","keywords":["neural architecture search","difference encoding","predictor-based NAS","evolutionary search","zero-cost proxy","Zen-Score","NAS benchmarks","sample efficiency"],"falsifier":"On NASBench201, compute the rank correlation between Zen-Score accuracy differences and true validated-accuracy differences over many one-edit neighbor pairs; if the correlation is not clearly positive on a substantial fraction of pairs, the predictor's training signal is misaligned and $\\Delta$-NAS's reported search gains would not demonstrate improvement in true accuracy.","tokens_in":9932,"feed_emoji":"🧠","tokens_out":11044,"duration_ms":102213,"temperature":0.7,"pith_summary":"$\\Delta$-NAS is a neural architecture search method built on a change of prediction target: rather than estimate a network's final accuracy, the system predicts the accuracy difference between a network and a nearby variant exactly $k$ edits away. The paper argues that this difference projection maps an exponentially large architecture space onto a sparse difference space of size $|D_k| = r^k \\binom{n}{k}$, and for the default $k=1$ this is $rn$ instead of $r^n$ (block-based) or $\\frac{n(n-1)}{2}r^n$ (cell-based). The difference predictor is trained on accuracy differences estimated with a zero-cost proxy, and the search then evolves a population by repeatedly moving each network to its most promising one-edit neighbor. On NASBench101, NASBench201, NASBench301, and TransNASBench the method reports higher predictor correlation, faster convergence, and better final accuracy than the listed baselines at a fraction of the sampling cost. If correct, this would make fine-grained search practical on architecture spaces large enough to defeat current methods.","feed_headline":"Predicting accuracy gaps, not accuracies, makes NAS scale linearly","feed_subtitle":"Delta-NAS learns the impact of one-edit changes, cutting predictor search space from exponential to linear growth.","key_machinery":"The load-bearing object is the difference-of-architecture encoding and its paired difference predictor. Each training example is a pair $(a_i, a_j)$ of architectures at edit distance $k$; the input is the sparse difference of their adjacency and operation representations, and the target is the difference in their predicted accuracies. Because close architectures cancel out most of their structure, the encoding lives in a space of size $|D_k| = r^k\\binom{n}{k}$, and for the chosen $D_1$ the predictor sees only single-change differences. The same many-to-one encoding is also the mechanism behind the search: at every generation the evolutionary loop queries the predictor over one-edit neighbors and steps to the one with the largest predicted accuracy gain, repeating until convergence.","core_discovery":"The central claim is that accuracy-difference prediction, not accuracy prediction, is the right representation for scalable NAS. For a block-based space with $n$ nodes and $r$ choices per node, the architecture set has size $|A|=r^n$; for cell-based spaces with adjacency choices, $|A| = \\frac{n(n-1)}{2} r^n$. When the predictor is restricted to one-edit neighbor pairs, the difference encoding has size $|D_1| = rn$, and in general $|D_k| = r^k \\binom{n}{k}$, so the exponential dependence on depth is replaced by polynomial (in fact linear for $k=1$) growth. The paper further claims that the many-to-one nature of the encoding removes graph-isomorphism ambiguity and lets multiple samples per encoding compensate for the noise of the zero-cost proxy. The search algorithm greedily follows the predicted best neighbor, and the reported results position $\\Delta$-NAS as the first method whose search cost scales linearly as the candidate count grows exponentially.","pith_inferences":["The complexity reduction is about the encoding space, not necessarily the runtime: the evolutionary loop still evaluates a neighborhood of neighbors per individual per generation, so the practical speedup depends on how cheaply the difference predictor can be evaluated and on the proxy being reliable.","A direct test of the method's foundation would be to rerun the NASBench201 experiments using true validated-accuracy differences instead of Zen-Score differences as training targets; if search quality changes little, the difference encoding is robust to the proxy, and if it changes a lot, the reported gains are partly a property of the proxy rather than the encoding.","The paper reports per-task TransNASBench results as available in an appendix, but the appendix reference is left as 'Appendix ??' in the manuscript, so those per-task numbers cannot currently be checked from the text.","Because the difference predictor is trained per search space, a practical extension would be to test whether a predictor trained on one space transfers to another space with the same operation set; the paper does not report such transfer experiments."],"forward_implications":["With $k=1$, the predictor's input space shrinks from $r^n$ (block-based) or $\\frac{n(n-1)}{2}r^n$ (cell-based) to $rn$ encodings, so the number of distinct difference patterns grows linearly with network depth.","Because the difference encoding is many-to-one, multiple architecture pairs can share one training example; the paper uses this to average the zero-cost proxy over several samples, reducing proxy noise without extra training.","The evolutionary search needs no absolute-accuracy predictor: it only ranks one-edit neighbors, so the per-generation cost is the population size times the size of a one-edit neighborhood, which grows linearly with network size rather than with the whole search space.","On the benchmarks tested, the paper reports both higher Kendall's tau for the predictor and faster convergence to near-optimal architectures than regularized evolution with shortest edit path crossover, with the gap widening on larger search spaces."],"supporting_citations":[{"why":"Supplies the zero-cost proxy (Zen-Score) whose accuracy differences are used as training labels for the difference predictor.","marker":"[12]"},{"why":"Provides the 432k-architecture cell-based NASBench101 benchmark used for predictor evaluation and search convergence tests.","marker":"[30]"},{"why":"Provides the 15.6k-architecture NASBench201 benchmark with full training curves, used for predictor comparison and search.","marker":"[7]"},{"why":"Provides the multi-task TransNASBench benchmark used to test generality across tasks.","marker":"[22]"},{"why":"Provides the large block-based NASBench301 surrogate benchmark used to test the method on depth-20 operation stacks.","marker":"[32]"},{"why":"Gives the shortest edit path crossover evolutionary baseline whose hyperparameters Delta-NAS reuses and whose performance it compares against.","marker":"[17]"},{"why":"Provides the FLAN encoding baseline compared in the predictor correlation experiments.","marker":"[1]"},{"why":"Provides the CATE encoding baseline compared in the predictor correlation experiments.","marker":"[28]"},{"why":"Provides the Arch2Vec encoding baseline compared in the predictor correlation experiments.","marker":"[29]"}],"fun_headline_variants":["Delta-NAS: predict accuracy gaps, not values, to scale NAS","Accuracy-difference encoding turns exponential NAS search linear","Predicting deltas, not absolutes, scales NAS to linear cost","NAS speedup: predict accuracy differences, not whole networks","One-edit neighbor pairs make NAS search linear, not exponential"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The difference predictor is trained on accuracy differences estimated by the Zen-Score zero-cost proxy, and the paper does not check that proxy differences rank true trained-accuracy differences correctly on the benchmarks before letting them guide the search.","fun_headline_variants_meta":{"raw":{"variants":["Delta-NAS: predict accuracy gaps, not values, to scale NAS","Accuracy-difference encoding turns exponential NAS search linear","Predicting deltas, not absolutes, scales NAS to linear cost","NAS speedup: predict accuracy differences, not whole networks","One-edit neighbor pairs make NAS search linear, not exponential"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000187,"raw_usage":{"total_tokens":1305,"prompt_tokens":901,"completion_tokens":404,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":517,"completion_tokens_details":{"reasoning_tokens":318}},"tokens_in":517,"tokens_out":404,"duration_ms":3744,"temperature":1.0,"reasoning_tokens":318,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:52:36.819884+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On NASBench201, compute the rank correlation between Zen-Score accuracy differences and true validated-accuracy differences over many one-edit neighbor pairs; if the correlation is not clearly positive on a substantial fraction of pairs, the predictor's training signal is misaligned and $\\Delta$-NAS's reported search gains would not demonstrate improvement in true accuracy.","supporting_citations":[{"cited_title":"Zen-nas: A zero-shot nas for high-performance deep image recognition, 2021","cited_arxiv_id":null,"evidence_quote":"Supplies the zero-cost proxy (Zen-Score) whose accuracy differences are used as training labels for the difference predictor."},{"cited_title":"Nas-bench-201: Extending the scope of reproducible neural architecture search, 2020","cited_arxiv_id":null,"evidence_quote":"Provides the 15.6k-architecture NASBench201 benchmark with full training curves, used for predictor comparison and search."},{"cited_title":"Surrogate nas bench- marks: Going beyond the limited search spaces of tabular nas benchmarks, 2022","cited_arxiv_id":null,"evidence_quote":"Provides the large block-based NASBench301 surrogate benchmark used to test the method on depth-20 operation stacks."},{"cited_title":"Shortest edit path crossover: A theory-driven solution to the permutation prob- lem in evolutionary neural architecture search","cited_arxiv_id":null,"evidence_quote":"Gives the shortest edit path crossover evolutionary baseline whose hyperparameters Delta-NAS reuses and whose performance it compares against."},{"cited_title":"Abdelfattah","cited_arxiv_id":null,"evidence_quote":"Provides the FLAN encoding baseline compared in the predictor correlation experiments."},{"cited_title":"Cate: Computation-aware neural architecture encoding with trans- formers, 2021","cited_arxiv_id":null,"evidence_quote":"Provides the CATE encoding baseline compared in the predictor correlation experiments."},{"cited_title":"Does unsupervised architecture representation learning help neural architecture search?, 2020","cited_arxiv_id":null,"evidence_quote":"Provides the Arch2Vec encoding baseline compared in the predictor correlation experiments."}],"review_version":1}