When Does Blockwise Additivity Break? Diagnosing and Repairing the Additive Assumption in Distillation-Based Architecture Search

When Does Blockwise Additivity Break? Diagnosing and Repairing the Additive Assumption in Distillation-Based Architecture Search

arXiv:2611.07487v1 [cs.NI] 5 Nov 2026

Yuefeng Xu Jun Yu Niigata University xyf20070623@gmail.com Yujun@ie.niigata-u.ac.jp

Abstract Blockwise distillation methods for architecture search and compression, such as DNA, DONNA, LANA and Puzzle, score every candidate replacement block in isolation. They then assemble a child network by solving an integer program whose objective is the sum of the perblock scores. The additive assumption behind this step is rarely tested. We study it on DeiT-S and DeiT-B with a library of seven replacement blocks per layer, seven block-latency budgets from 70% to 40% of the parent’s, and three fine-tuning seeds per searched network, using paired bootstrap confidence intervals. (i) At mild compression the additive integer linear program (ILP) is close to a pairwise integer quadratic program (IQP) that models block interactions. The post-fine-tuning accuracy gap widens sharply as the budget decreases from 60% to 55%: at budgets of 55%–40% the additive search trails the IQP by 3.3–16.6 top-1 percentage points on ImageNet-100. A separate DeiT-B experiment at 70%–60% shows that the smaller mild-budget gaps remain significant after 10,000 fine-tuning steps. (ii) We split the KL additivity error into a metric component, which arises because the KL is a non-linear function of the summed logit changes, and a functional component, which captures the score-level effect of non-additive logit changes. The metric component can be computed from cached single-block logits without additional network evaluations. It accounts for most of the mean error on DeiT-S (59–65%), whereas the functional component dominates on DeiT-B (73–76%). (iii) A hybrid search ranks candidate moves with the logit-sum predictor and measures only the best ones. It needs no dedicated pair measurements and costs 13–27% of the IQP’s pair stage in forward images. On ImageNet-100 it significantly outperforms the IQP in 7 of 14 settings; the difference is not significant in 6, and the hybrid significantly underperforms in 1. Equal-cost random and evolutionary searches suggest that direct evaluation of complete structures accounts for a substantial part of this gain. On ImageNet-100, further reductions of the pre-fine-tuning KL do not consistently improve fine-tuned accuracy, and scoring after a short fine-tune does not help. Experiments on the full ImageNet-1k with 1000-class fine-tuning reproduce the sharp widening of the gap between the 60% and 55% budgets (5.8–17.5 points at 55%–40%), the model-dependent error decomposition, and the hybrid’s advantage over the IQP (significantly better in 13 of 14 settings, no significant difference in the remaining one). The stronger-search and fine-tuning-aware scoring studies are restricted to ImageNet-100.

1

Introduction

Blockwise distillation is an attractive recipe for turning a large pretrained network into a faster one. Each block of the parent is given a set of cheaper alternatives, for example fewer attention heads, a pruned or low-rank MLP, or no block at all. Every alternative is trained locally to mimic the parent block’s output and is scored once in isolation. A child network is then assembled by choosing one alternative per layer so that a summed per-block score is minimal under a latency or 1

memory budget. The resulting integer program solves in seconds. The approach underlies DNA [6], DONNA [9], LANA [8] and, at the scale of large language models, Puzzle [1]. The price of this speed is an additivity assumption: the damage done by a set of replacements is taken to be the sum of the damage of each replacement alone. The assumption is plausible when few blocks change. It is far less obvious when half of the network is replaced, which is exactly the regime of aggressive latency budgets. If additivity fails there, an additive search systematically picks combinations that look harmless one block at a time but interact badly. The quality of the result then depends on fine-tuning to repair the damage. This paper asks three questions. Q1 How wrong is the additive assumption, at which compression level does it start to matter, and does the damage survive fine-tuning? Q2 Where does the additivity error come from? Q3 Can it be repaired cheaply, without measuring all block pairs? Contributions. 1. A controlled, statistically tested study of additivity in blockwise replacement search. It covers two vision transformers and seven latency budgets and compares an additive integer linear program (ILP) with a pairwise integer quadratic program (IQP) after fine-tuning with three seeds (Sec. 4). The gap is small and roughly constant down to 60% latency and jumps between 60% and 55%. The main experiments are repeated on the full ImageNet-1k with 1000-class fine-tuning (Sec. 7). 2. A decomposition of the KL additivity error into a metric component and a functional component, with a second-order explanation of the metric component (Sec. 5). On DeiT-S most of the mean error is metric curvature of the score; on DeiT-B most of it is attributed to the functional component. 3. A logit-sum predictor and a hybrid search that uses it only to rank candidates for real evaluation. The hybrid requires no dedicated pair measurements (Sec. 6). It is compared against equal-cost random and evolutionary searches, and against a stronger online-corrected variant. Together these suggest that, among the structures found by these searches, further gains are limited by the fidelity of the pre-fine-tuning score rather than by the search. Scores computed after a short fine-tune do not help (Sec. 6.5).

2

Related work

Blockwise distillation search. DNA [6] trains supernet blocks with block-wise knowledge distillation. DONNA [9] builds a block library by blockwise distillation and fits a linear accuracy predictor over block-level scores. LANA [8] trains alternative operations by layer-wise feature-map distillation and selects them with an integer linear program under a latency constraint. Puzzle [1] applies the same pipeline to large language models with a mixed-integer program and global distillation. All of these rely, explicitly or through a linear predictor, on per-block scores that combine additively. Our study tests this assumption directly.

2

Interaction-aware compression. Hessian-based mixed-precision quantization (HAWQ [3]) assigns bit-widths from per-layer sensitivities. CLADO [2] is the closest prior work: it argues that per-layer quantization errors are not independent, estimates pairwise cross-layer terms on a small data subset, and solves an integer quadratic program. Our pairwise IQP baseline is the blockreplacement analogue of this idea. We go further in three ways. We study when additivity breaks as a function of the budget. We separate the part of the cross term that is only metric curvature from true interaction. And we show that pair measurements can be replaced by ranking plus a small number of real evaluations. Predictor-based and evolutionary search. Performance predictors are widely used to make neural architecture search cheap [13]. Regularized evolution [10] is a strong, simple search baseline. We use it on measured scores as an equal-cost baseline for our hybrid search.

3

Experimental setup

Models and data. The parent models are DeiT-S and DeiT-B [12] pretrained on ImageNet1k, taken from timm [14] and used without retraining. We work on ImageNet-100, formed from every 10th ImageNet-1k class in the standard label order (labels 0, 10, . . . , 990) [11]. The last fifty training images of each class in file-name order (5,000 images, calib) are held out. They are used for every score and every search decision. The remaining training images are used for blockwise distillation and fine-tuning. Section 7 repeats the main experiments on the full ImageNet-1k. In the ImageNet-100 experiments we report top-1 accuracy on two sets: • val100 : the 5,000 official validation images of the 100 classes, 100-way, obtained by restricting the argmax to the 100 class logits. This is the main metric. • val1k: the full 50,000-image ImageNet-1k validation set, 1000-way. This is a secondary metric that probes how far a child generalizes beyond the classes it was fine-tuned on. The parents reach 95.76% / 79.87% (DeiT-S) and 96.30% / 81.97% (DeiT-B) on val100 / val1k. Block library. At each of the 12 layers, the search chooses between the original block and seven replacement options: • half of the attention heads (attn_heads_half); • no attention (attn_skip); • an MLP retaining 50% or 25% of its hidden units (mlp_prune50, mlp_prune25); • a low-rank MLP with 50% of the parameters (mlp_lowrank50); • no MLP (mlp_skip); • no block at all (block_skip). The search space therefore has 812 ≈ 6.9×1010 structures. Alternatives are initialized from the parent’s weights. Each is trained for 3,000 steps (batch 128, AdamW, learning rate 3 × 10−4 ) to reproduce the parent block’s output from the parent block’s input. With x the token features entering the block, fp the parent block and fc the candidate, the loss is ∥fc (x)−fp (x)∥2 / max(∥fp (x)−x∥2 , 10−8 ) (means over the batch), which normalizes by the residual update. block_skip has no parameters and is not trained; for attn_skip and mlp_skip the remaining sub-layer is trained. 3

Scores. The score of a structure is the mean KL(pparent ∥ pchild ) over the 1000-way softmax on calib. We measure: • all 12 × 7 = 84 single replacements; • 1,389 pairs: all 49 candidate pairs for the 21 layer pairs at distance ≤ 2, plus 8 sampled candidate pairs for each of the 45 farther layer pairs; • 400 random structures with 2–6 replaced blocks, used only for analysis. Latency. A per-block latency table was measured on an RTX 5090 (batch 64, 20 warm-up and 100 timed runs). A budget of x% means that the summed block latency of the child is at most x% of the parent’s summed block latency. For 20 random structures, the summed table has a mean absolute relative prediction error of 1.2% (maximum 2.8%). We also timed every final structure end to end; there the mean absolute relative error is 0.8% (DeiT-S; maximum 2.7%) and 2.5% (DeiT-B; maximum 6.0%). Because the patch embedding and the classifier head are not replaced, the end-to-end latency fraction is a few points above the budget (Appendix A). Searches.

All searches use the same scores and latency table.

• Additive ILP minimizes

i s(i, ci ) under the budget, as in LANA and Puzzle.

P

• Pairwise IQP adds a measured interaction term K(i, ci , j, cj ) = s(i, ci , j, cj ) − s(i, ci ) − s(j, cj ) for every measured pair. The products are linearized in the standard way. • Greedy starts from the parent and repeatedly applies the single replacement with the smallest increase in additive score per unit of latency saved until the budget is met. It serves only as a starting point below. Both integer programs are solved with HiGHS [5] through SciPy with a 120 s time limit. Every solve reported here terminated with an optimal status within HiGHS’s default relative MIP gap of 10−4 , after at most 16 s. Fine-tuning and statistics. Each searched child is fine-tuned by global distillation from the parent: a KL loss on the 1000-way softmax, 2,000 steps, batch 128, AdamW, learning rate 5 × 10−5 , weight decay 0.05, 100 warm-up steps. This is done with three seeds. Differences between two searches are reported as the seed-averaged top-1 difference with a 95% paired bootstrap confidence interval over images (10,000 resamples, per-image correctness averaged over seeds [4]). The bootstrap resamples validation images while holding the three trained seed realizations fixed, so the intervals quantify image-sampling uncertainty conditional on these runs; they do not capture the variability of retraining. Each search is run once per budget; random and evolutionary searches use one fixed seed. A difference is called significant (∗ ) when its interval excludes zero, and we make no adjustment for multiple comparisons. In win/tie/loss (W/T/L) counts, a tie denotes a difference whose interval includes zero; it does not establish equivalence. For the IQP − ILP comparisons we also ran exact McNemar tests per seed [7]. At budgets of 55% and below every seed is significant on both datasets (p < 10−13 ). At 70%–60% individual seeds on ImageNet-100 are sometimes not significant (p up to 0.37), in line with the small gaps there.

4

Table 1: Additivity of single-block KL scores on 400 random structures with k = 2..6 replaced blocks (80 per k; calib). “Super-additive” means that the measured KL exceeds the sum of the single scores (add). MAE is the mean absolute difference between the measured KL and add. model

Kendall τ (sum) τ (+ pair terms) super-additive median act./add MAE k=2 MAE k=6

DeiT-S DeiT-B

0.894 0.894

0.952 0.956

90% 79%

1.16 1.09

IQP − ILP top-1 (pts)

0.228 0.246

ImageNet-1k val (100-class fine-tuning)

ImageNet-100 val DeiT-S DeiT-B

15

0.027 0.003

20

10 10

5 0

70

65 60 55 50 45 40 block-latency budget (% of parent)

0

70

65 60 55 50 45 40 block-latency budget (% of parent)

Figure 1: Top-1 gain of the pairwise IQP over the additive ILP after fine-tuning (mean of three seeds, 95% paired bootstrap interval). The gain is about one point or less down to 60% latency and jumps between 60% and 55% (shaded) for both models.

4

How additive are block scores? (Q1)

Before fine-tuning. Table 1 shows that the sum of single scores ranks random structures reasonably well (Kendall τ = 0.89). However, the error grows quickly with the number of replaced blocks, and it is biased: 79–90% of the structures are worse than predicted. Adding the measured pair terms raises τ to 0.95. Interaction is concentrated between nearby layers. On DeiT-S the mean relative pair term, |K(i, ci , j, cj )|/|s(i, ci ) + s(j, cj )|, is 0.167 at layer distance ≤ 2 and 0.030 beyond. After fine-tuning. Figure 1 and Table 2 compare the two searches after fine-tuning. At 70%– 60% latency the interaction-aware search is ahead by at most 1.2 points on val100. The difference is significant in four of six settings, but it is small. Between 60% and 55% the gap jumps, for both models, to 3.6–4.1 points. It grows to 11–17 points at 40%. The val1k gap shows the same transition, from 1.6–3.1 points to 8.8–26.9 points. This is consistent with the additive children losing much of their accuracy on the 900 classes not seen during fine-tuning. Longer fine-tuning. A natural objection is that a short fine-tuning budget exaggerates the gap. We therefore fine-tuned the DeiT-B children at the three mild budgets for 10,000 steps (two seeds; Table 3). The gap shrinks only slightly and stays significant at all three budgets. In these three mild-compression settings, extending fine-tuning to 10,000 steps does not eliminate the gap. We did not run the longer schedule at the aggressive budgets.

5

Table 2: IQP − ILP top-1 accuracy difference after fine-tuning (percentage points; three seeds; 95% paired bootstrap interval; ∗ : interval excludes 0). For val1k only point estimates are shown; all val1k intervals exclude 0 and are at most 0.8 points wide. The DeiT-B 70% val100 interval has a lower bound of 0 (to numerical precision) and is not counted as significant. budget

DeiT-S val100

70% 65% 60% 55% 50% 45% 40%

+0.77 [+0.32, +1.21] +0.69 [+0.26, +1.11]∗ +0.34 [−0.11, +0.81] +3.57 [+2.95, +4.21]∗ +3.33 [+2.65, +4.02]∗ +3.45 [+2.71, +4.19]∗ +16.55 [+15.47, +17.64]∗ ∗

DeiT-B val100

DeiT-S val1k

DeiT-B val1k

+0.33 [0.00, +0.67] +1.03 [+0.65, +1.43]∗ +1.15 [+0.71, +1.59]∗ +4.13 [+3.51, +4.76]∗ +3.89 [+3.23, +4.54]∗ +8.17 [+7.38, +8.99]∗ +11.32 [+10.40, +12.25]∗

+3.09 +1.98∗ +2.32∗ +24.56∗ +26.88∗ +21.15∗ +26.04∗

+1.65∗ +2.07∗ +2.75∗ +11.76∗ +8.79∗ +16.74∗ +19.19∗

∗

Table 3: DeiT-B, 10,000-step fine-tuning (two seeds), val100 top-1.

5

budget

ILP

IQP

IQP − ILP [95% CI]

70% 65% 60%

95.66 95.03 94.65

95.99 95.62 95.33

+0.33 [+0.01, +0.67]∗ +0.59 [+0.23, +0.95]∗ +0.68 [+0.29, +1.09]∗

Where does the additivity error come from? (Q2)

Let z ∈ R1000 be the parent’s logits on an image, sm the softmax, and δi the change in logits caused by the replacement selected at layer i alone (measured with the other blocks original; strictly δi,ci ). For a structure A we compare three quantities: add(A) =

i∈A KL sm(z) ∥ sm(z + δi ) ,

P

lin(A) = KL sm(z) ∥ sm(z +

i∈A δi ) ,

P

act(A) = KL sm(z) ∥ sm(zA ) ,

each averaged over calib. Here zA are the measured logits of the child. The additivity error splits exactly into act − add = (lin − add) + (act − lin) . (1) |

{z

metric

}

|

{z

functional

}

The metric part would be present even if the blocks did not interact at all, that is, if their logit changes simply added up. It is a property of the score, not of the network. The functional part is the difference between the KL of the actual child logits and that of the summed-logit approximation. It captures the score-level effect of non-additive logit changes. A functional part of zero does not prove that the logits are additive, since different logits can have the same KL. Why the metric part is often positive. A second-order expansion of the KL around the parent logits gives KL(sm(z) ∥ sm(z + δ)) ≈ 12 δ ⊤ F δ, where p = sm(z) and F = diag(p) − pp⊤ is the P Fisher matrix of the softmax. With δ = i δi , lin(A) − add(A) ≈

X

δi⊤ F δj .

(2)

i<j

The metric part is therefore approximately a Fisher-weighted cross term. Individual terms can be negative; the sum is positive when the logit changes of different blocks are, on aggregate, positively 6

Table 4: Decomposition of the additivity error (calib): measured pairs and 400 random structures. Components are signed and averaged over the pairs or structures; the metric share is the mean metric part divided by the mean of act − add, so it is not a decomposition of an absolute error and need not lie in [0, 1] in general. “Acc. drop” uses the 100-way top-1 drop (percentage points) instead of KL as the score. model

set

τ add

τ lin

act − add

metric part

metric share

DeiT-S

pairs, KL structures, KL pairs, acc. drop structures, acc. drop

0.924 0.894 0.811 0.825

0.931 0.911 0.875 0.897

0.0171 0.0694 0.255 1.256

0.0102 0.0454 0.094 0.446

59% 65% 37% 36%

DeiT-B

pairs, KL structures, KL pairs, acc. drop structures, acc. drop

0.934 0.894 0.820 0.781

0.952 0.932 0.882 0.874

0.0143 0.1095 0.195 1.748

0.0038 0.0267 0.034 0.282

27% 24% 17% 16%

aligned under F , for example when several of them lower the parent’s top-class logit. This is one mechanism for the super-additivity of most structures (Table 1). The predictor lin evaluates the summed-logit KL without a Taylor approximation, from the cached logits of the 84 single-block runs; subtracting add gives the exact metric part. Results.

Table 4 shows a clear difference between the two models.

• On DeiT-S, 59–65% of the mean KL additivity error is metric. Much of what an interactionaware search “learns” from pair measurements is curvature of the score rather than functional interaction. • On DeiT-B, the metric share is only 24–27%. Most of the mean error of the wider model is attributed to the functional component once several blocks are replaced. In both models the lin predictor ranks structures better than the plain sum (higher τ ). This holds even for the accuracy-drop score, where the metric share is smaller. The difference between the models predicts the behavior of the cheap repair in the next section.

6

Cheap repairs (Q3)

6.1

Search on the logit-sum predictor

The lin predictor needs only the 84 single-block runs. Unlike the additive score, it is not linear in the choices, so we optimize it by steepest-descent local search. The moves change one layer or two layers at once within the budget, and the search starts from the ILP and greedy solutions. We call the result lin. • On DeiT-S, lin substantially improves over the ILP at most budgets and its mean accuracy exceeds the IQP’s at five of seven budgets, without dedicated pair measurements (Table 5). It equals the ILP at 65%, where both select the same structure. • On DeiT-B, lin helps at mild budgets but falls 1.05, 4.32 and 5.58 points behind the IQP at 50%, 45% and 40%. This is the regime where the functional part dominates (Sec. 5): lin selects structures whose real KL is far above its prediction (Fig. 3). 7

top-1 after fine-tuning (%) top-1 after fine-tuning (%)

95 90 85 80 75 70

DeiT-S, ImageNet-100 val

DeiT-B, ImageNet-100 val 95 90

Additive ILP Logit-sum (lin) Pairwise IQP Hybrid (ours)

70

65

60 55 50 45 DeiT-S, ImageNet-1k val

85 80 40

70

65

70

65 60 55 50 45 40 block-latency budget (% of parent)

80

60

60 55 50 45 DeiT-B, ImageNet-1k val

40

60

40 40

20 70

65 60 55 50 45 40 block-latency budget (% of parent)

Figure 2: Top-1 after fine-tuning for the four searches (three seeds). Top: val100; bottom: val1k.

6.2

Hybrid search: rank cheaply, measure the best

The hybrid search uses lin only as a ranker and uses directly measured calibration KL to select moves. 1. Start from the best of {lin, ILP, greedy}, judged by real KL on a 1,000-image subset of calib (every fifth image). 2. At each step, rank all feasible one- and two-layer moves by lin. Measure the real subset KL of the 12 best moves not yet measured. 3. Move to the best of them if it improves on the current structure, and re-rank from the new structure. Otherwise measure the next 12, up to four chunks, and then stop. Measured structures are cached and never re-measured; the evaluation count includes the starting structures. The hybrid requires no dedicated pairwise measurements or precomputed pair table. Accuracy. After fine-tuning (Fig. 2, Table 5), the hybrid is significantly better than the IQP in 7 of 14 settings, not significantly different in 6, and significantly worse in one (DeiT-B 45%, −1.09). It is significantly better than the additive ILP in 13 of 14 settings; the remaining one, DeiT-B 70%, is borderline. On val1k the picture is more mixed. The hybrid is ahead of the IQP in 7 settings and behind in 6, mostly the mild DeiT-B budgets.

8

calibration KL (before fine-tuning)

Table 5: val100 top-1 after fine-tuning (three seeds) and hybrid − IQP with 95% paired bootstrap interval. model

budget

ILP

lin

IQP

hybrid

hybrid − IQP

DeiT-S

70% 65% 60% 55% 50% 45% 40%

93.59 93.11 92.27 88.99 87.42 85.32 70.73

94.47 93.11 93.16 92.85 90.62 90.27 88.27

94.36 93.80 92.61 92.56 90.75 88.77 87.27

94.27 93.93 93.11 92.75 92.49 90.05 88.99

−0.09 [−0.53, +0.34] +0.13 [−0.24, +0.49] +0.51 [+0.09, +0.94]∗ +0.19 [−0.23, +0.61] +1.74 [+1.19, +2.30]∗ +1.29 [+0.71, +1.87]∗ +1.71 [+1.13, +2.30]∗

DeiT-B

70% 65% 60% 55% 50% 45% 40%

95.39 94.61 93.71 89.71 89.02 85.11 78.77

95.59 94.99 94.91 93.45 91.86 88.96 84.51

95.72 95.64 94.87 93.84 92.91 93.28 90.09

95.71 95.39 94.72 94.57 93.58 92.19 91.98

−0.01 [−0.31, +0.29] −0.25 [−0.59, +0.09] −0.15 [−0.55, +0.25] +0.73 [+0.27, +1.19]∗ +0.67 [+0.19, +1.16]∗ −1.09 [−1.65, −0.54]∗ +1.89 [+1.29, +2.48]∗

DeiT-S

DeiT-B

Additive ILP Logit-sum (lin) Pairwise IQP Hybrid (ours)

4 × 1000 3 × 10 2 × 100

100

100 6 × 10−1 4 × 10−−11 3 × 10 2 × 10−1

10−1 70

65 60 55 50 45 40 block-latency budget (% of parent)

70

65 60 55 50 45 40 block-latency budget (% of parent)

Figure 3: Calibration KL of the selected structures before fine-tuning (log scale).

Cost. Beyond the 84 single runs shared by all methods, the IQP needs 1,389 pair measurements on 5,000 images, which is 6.9 M forward images. The hybrid measured 930 structures (DeiT-S) and 1,843 structures (DeiT-B) on 1,000 images over all seven budgets. That is 13.4% and 26.5% of the IQP pair stage (Table 6). This comparison counts image-level network evaluations beyond the shared single-block stage. It excludes predictor computation, logit storage and solver time and is not a measured wall-clock speed-up. The hybrid’s cost grows with the number of budgets, whereas the IQP’s pair table is reused. Assuming that the mean hybrid cost per budget stays unchanged, its cumulative cost reaches that of the IQP pair stage after about 26–52 budgets.

6.3

Is the ranking needed? Equal-cost baselines

The hybrid differs from the IQP in two ways: it ranks with lin, and it measures real structures. To separate the two effects we ran two baselines with exactly the same number of real evaluations per budget, the same subset and the same starting points. • Random: the best of the starts and feasible structures sampled uniformly (each layer’s option 9

Table 6: Search cost beyond the 84 single-block evaluations, in forward images (all seven budgets). model

IQP pair stage

hybrid

ratio

DeiT-S DeiT-B

1389 × 5000 = 6.95 M 1389 × 5000 = 6.95 M

930 × 1000 = 0.93 M 1843 × 1000 = 1.84 M

13.4% 26.5%

Table 7: Hybrid versus equal-cost searches on measured KL (top-1 difference after fine-tuning; ∗ : 95% interval excludes 0). Bottom: counts of significant wins / ties / losses of the hybrid over the 14 settings. budget 70% 65% 60% 55% 50% 45% 40%

DeiT-S val100 hyb − random hyb − evolution −0.19 +0.29 −0.05 −0.10 +1.87∗ −0.21 +0.72∗

DeiT-B val100 hyb − random hyb − evolution +0.67∗ +0.29 −0.10 +0.33 +0.76∗ +0.38 +2.12∗

−0.02 +0.03 −0.05 −0.10 +0.63∗ +0.48 +0.72∗

+0.46∗ −0.26 −0.11 +0.19 −0.49 −0.74∗ +0.16

W / T / L over 14 settings: val100 — vs. random 5/9/0, vs. evolution 3/10/1; val1k — vs. random 11/0/3, vs. evolution 12/0/2.

drawn uniformly, rejected if over budget). • Evolution: regularized evolution [10] with population 24, tournament size 6, and mutations of one or two layers. Table 7 summarizes these comparisons. On val100, equal-cost evolution on measured KL is not significantly different from the hybrid in 10 of 14 settings (3 wins, 1 loss). Random sampling is slightly weaker (5 wins, no loss). On DeiT-S, random and evolution often kept the lin start, so part of their strength there is inherited from lin. These results suggest that direct evaluation of complete structures accounts for a substantial part of the improvement over the IQP. Because all baselines share starting points that include lin, this comparison does not isolate the full contribution of the logit-sum predictor. The ranking appears to matter for generalization. On val1k the hybrid beats evolution in 12 of 14 settings. On DeiT-B the margin is +3 to +9 points at six of seven budgets. Proposing moves that are good under the logit-sum model appears to favor structures whose errors are small across all 1000 classes, not just on the measured subset.

6.4

A stronger search lowers KL without consistently improving fine-tuned accuracy

Since evolution matched the hybrid on val100, we tried to combine the two: hybrid v2. • It runs regularized evolution with the same budget of real evaluations. • Each generation proposes 48 random mutations plus the 8 best lin moves of the parent. Only the candidate with the best surrogate score is measured. • The surrogate is log lin(A) plus a ridge regression on log[act(A)/lin(A)] fitted online to all measured structures (both KL values clipped below at 10−6 ). Its 1,113 features are one-hot (layer, option) indicators and option pairs of layers at distance ≤ 2. 10

DeiT-S

DeiT-B 95.0 92.5 90.0 87.5 85.0 82.5 80.0

90 85 80 75 70

45% 50% 55% 60% 65%

10 calibration KL before fine-tuning

100

−1

calibration KL before fine-tuning Additive ILP Logit-sum (lin)

Pairwise IQP Random (real KL)

40%

block-latency budget

top-1 after fine-tuning (%)

95

Evolution (real KL) Hybrid

100

70%

Hybrid v2

Figure 4: Calibration KL before fine-tuning versus val100 top-1 after fine-tuning for all seven searches and budgets (color). Across budgets, lower calibration KL is generally associated with higher fine-tuned accuracy. Within a budget, the high-performing structures found by the real-evaluation searches have similar scores, and their order after fine-tuning is only weakly related to their KL.

Hybrid v2 did find structures with lower pre-fine-tuning KL. On DeiT-B it is below the hybrid at six of seven budgets, for example 0.22 vs. 0.32 at 55% and 0.68 vs. 1.05 at 45%. After fine-tuning, however, it shows no consistent gain. • On val100 it is significantly better than the hybrid in 2 of 14 settings and significantly worse in 2. Against evolution it is likewise 2 / 10 / 2 (W/T/L). • On val1k it is significantly worse than the hybrid in 9 of 14 settings, by up to 11.3 points (DeiT-B 45%). Figure 4 explains why. Across budgets and across clearly different structures, the pre-finetuning KL predicts the fine-tuned accuracy well. This is why the additive ILP is so easy to beat. Among the high-performing candidate structures found by the six non-additive searches, however, the within-budget Kendall τ between −KL and fine-tuned top-1 ranges from −0.57 to +1.00 on DeiT-S, where it is negative at three of seven budgets. On DeiT-B it ranges from +0.20 to +0.87. Among these structures, lower pre-fine-tuning KL does not consistently predict higher post-finetuning accuracy. This suggests that, in the present setup, the fidelity of the score rather than the search limits further gains; the remaining differences between good searches are typically below one point.

6.5

Does a fine-tuning-aware score help?

A natural fix for the score bottleneck is to score a structure after a short fine-tune. We tested this on the distinct final structures of the seven searches at the seven budgets: 39 on DeiT-S and 49 on DeiT-B (structures selected by several searches are counted once). 11

Table 8: Fine-tuning-aware scores. Mean within-budget Kendall τ with fine-tuned val100 top-1 over the seven budgets (minimum in parentheses), and the mean top-1 difference when the structure with the best score among the six non-additive searches is selected instead of the hybrid’s. Two proxy seeds. Rows marked “50–500 steps” give the range of these means over the four checkpoints. The cross-seed agreement row reports the correlation between one fine-tuning seed and the mean of the other two, an empirical reference for cross-seed agreement. score calib KL, 0 steps (used so far) calib KL, 50–500 steps calib top-1, 0 steps calib top-1, 50–500 steps calib top-1, 200 steps (fixed) cross-seed agreement

τ

DeiT-S select − hyb

τ

DeiT-B select − hyb

+0.22 (−0.57) 0.00 to +0.14 +0.54 (0.00) +0.48 to +0.70 +0.70 (+0.33)

−0.10 −0.20 to −0.14 +0.09 −0.03 to +0.06 +0.06

+0.52 (+0.20) +0.56 to +0.62 +0.62 (+0.33) +0.50 to +0.60 +0.50 (+0.07)

+0.17 +0.15 to +0.24 +0.19 +0.09 to +0.19 +0.09

+0.73

—

+0.85

—

• Each structure gets a 500-step global-KD fine-tune with the recipe of Section 3, with the schedule compressed to 500 steps. The data order is identical for all structures. • Calibration KL and calibration top-1 are recorded after 0, 50, 100, 200 and 500 steps, with two seeds. The proxy fine-tunes use the training split of Section 3; the proxy scores are computed only on the held-out calib images, which are excluded from proxy training. • The cost is 24 s (DeiT-S) and 59 s (DeiT-B) per structure and seed on one RTX 5090. As before, we report the within-budget Kendall τ between each score and the 3-seed fine-tuned val100 top-1, over the six non-additive searches. We also report the effect of using each score to select one of the six structures per budget. The proxy variant to carry forward, calibration top-1 after 200 steps (τ = 0.80), was chosen by its correlation with val100 accuracy on the first DeiT-S proxy seed; the remaining runs, in particular DeiT-B, serve as a subsequent check. The DeiT-S entries of Table 8 average both proxy seeds and therefore include the seed used for this choice; the DeiT-B entries do not depend on it. Table 8 shows a negative result. • Short fine-tuning does not make the KL a better score. On DeiT-S it becomes worse, with τ near zero after every checkpoint. On DeiT-B it improves only slightly, from 0.52 to about 0.6. • The variant selected on the first DeiT-S seed, top-1 after 200 steps, does not improve the ranking on DeiT-B. Its τ of 0.50 is below that of calibration top-1 before fine-tuning. • The only consistent finding needs no additional forward passes. Among the evaluated candidate structures, calibration top-1 measured before fine-tuning ranks better than calibration KL (τ 0.54 vs. 0.22 on DeiT-S, 0.62 vs. 0.52 on DeiT-B). Selecting structures by this score among the outputs of the six searches yields mean gains of only 0.09 (DeiT-S) and 0.19 (DeiT-B) percentage points over the hybrid. These gains are small, but we have not assessed them with paired comparisons, so we do not claim that they are explained by noise. The imperfect cross-seed agreement (0.73 / 0.85) suggests that fine-tuning variability contributes to the remaining ranking uncertainty, so that at this fine-tuning budget structures differing by a few tenths of a point are hard to order reliably. 12

Table 9: Full ImageNet-1k: top-1 (%) on the 50,000 validation images after fine-tuning on all 1000 classes (mean of three seeds; seed standard deviation 0.03–0.16). Gap: IQP − ILP with 95% paired bootstrap interval; every interval excludes 0. Boldface marks the highest mean in each row; it does not indicate statistical significance. The parents reach 79.87% (DeiT-S) and 81.97% (DeiT-B). model

7

budget

ILP

IQP

lin

70% 65% 60% DeiT-S 55% 50% 45% 40%

74.28 73.34 72.83 63.21 58.19 56.52 42.96

75.45 74.93 74.23 73.29 72.04 72.88 70.24 71.41 67.85 69.26 63.06 65.85 60.46 58.57

74.89 73.05 72.83 71.41 69.26 65.85 58.57

74.89 73.50 72.83 71.41 69.26 65.85 61.83

75.77 +1.17 [+0.95, +1.40] 74.53 +0.90 [+0.66, +1.13] 73.21 −0.79 [−1.04, −0.53] 71.30 +7.03 [+6.71, +7.34] 69.34 +9.66 [+9.34, +9.99] 66.27 +6.54 [+6.21, +6.88] 62.27 +17.50 [+17.11, +17.89]

70% 65% 60% DeiT-B 55% 50% 45% 40%

79.27 77.15 75.50 69.76 66.13 54.95 49.21

79.88 78.62 77.11 75.55 74.45 71.05 63.83

77.68 78.88 75.14 74.72 70.19 70.92 64.73

79.16 78.88 77.26 75.13 72.51 70.30 67.17

80.07 +0.61 [+0.43, +0.77] 78.88 +1.47 [+1.27, +1.67] 77.82 +1.61 [+1.38, +1.84] 76.71 +5.79 [+5.52, +6.07] 74.29 +8.32 [+8.03, +8.62] 72.13 +16.10 [+15.75, +16.45] 65.54 +14.62 [+14.27, +14.96]

79.27 78.88 78.29 74.65 69.81 62.88 53.00

random evolution hybrid

IQP − ILP [95% CI]

Full ImageNet-1k

The experiments above fine-tune the children on 100 classes, so val1k could only be a secondary metric. We therefore repeated the main pipeline on the full ImageNet-1k for both models, with no change of method or hyperparameters. The block library is distilled on the full training set. Five training images per class (5,000 images) are held out as calib. We measure all 84 single replacements, the same set of 1,389 replacement pairs defined in Section 3, and 400 random structures. All six searches (ILP, IQP, lin, hybrid, random, evolution) are run at the seven budgets. Every child is fine-tuned on all 1000 classes with the recipe of Section 3 and three seeds, and is evaluated 1000-way on the 50,000 official validation images. This is now the only metric. Additivity and its decomposition. The calib statistics are similar to those obtained on ImageNet-100. On the 400 random structures, the plain sum ranks with Kendall τ of 0.887 on DeiT-S and 0.886 on DeiT-B, and adding pair terms raises τ to 0.951 and 0.954. Of the structures, 95% and 92% are super-additive, with median act./add ratios of 1.22 and 1.21. Interaction is again local: the mean relative pair term is 0.19 at layer distance ≤ 2 and 0.03–0.04 beyond. The KL decomposition reproduces the contrast of Table 4. The metric share is 63% (pairs) and 67% (structures) on DeiT-S, against 36% and 34% on DeiT-B, so on the larger model most of the mean error is again attributed to the functional component. The transition. Table 9 shows the same break as on ImageNet-100. Down to 60% latency the IQP and the ILP differ by at most 1.6 points. On DeiT-S the ILP is even 0.8 points ahead at 60%. Between 60% and 55% the gap jumps to 7.0 (DeiT-S) and 5.8 points (DeiT-B), and it reaches 6.5–17.5 points at 50–40%. The jump is larger than on val100 of ImageNet-100 (3.6–4.1 points at 55%); this larger gap is observed when the children are fine-tuned and evaluated on all 1000 classes.

13

Table 10: Full ImageNet-1k: significant wins / ties / losses of the hybrid over each other search (95% paired bootstrap interval over the 50,000 validation images; seven budgets per model). A tie means that the interval includes 0. vs. ILP

vs. IQP

vs. lin

vs. random

vs. evolution

DeiT-S DeiT-B

7/0/0 7/0/0

7/0/0 6/1/0

5/2/0 5/1/1

5/2/0 6/1/0

5/2/0 5/1/1

total (14)

14/0/0

13/1/0

10/3/1

11/3/0

10/3/1

Cheap repairs. The behavior of lin again follows the decomposition. On DeiT-S, where most of the error is metric, lin’s mean accuracy is 1.2–2.8 points above the IQP’s at 55%–45% without dedicated pair measurements. On DeiT-B, where most of the error is functional, lin falls 4.6–10.8 points behind the IQP at 50%–40%. The hybrid removes this weakness (Table 10). It significantly outperforms the IQP in 13 of 14 settings, with no significant difference in the 14th (DeiT-B, 50%). Across the eight settings at budgets of 55%–40%, it recovers 98–149% of the IQP’s advantage over the ILP, computed as 100 (ahybrid − aILP )/(aIQP − aILP ). It is also significantly better than equalcost random sampling in 11 settings and evolution in 10, with one significant loss (DeiT-B, 40%, −1.63 points). On ImageNet-100 the hybrid and evolution were mostly not significantly different on val100 but the hybrid was clearly ahead on val1k (Table 7). With 1000-class fine-tuning that advantage now appears on the main metric. On DeiT-S, random and evolution often keep the lin start, as on ImageNet-100, which explains the ties at 55% and 50%.

8

Discussion and limitations

Practical guidance. At budgets of 70%–60%, the IQP’s advantage over the additive ILP is at most 1.2 percentage points on ImageNet-100 val100 and 1.6 points on full ImageNet-1k; whether this is acceptable depends on the application. At more aggressive budgets the additive ILP falls far behind, whether the interactions are metric or functional. If most of the error is metric, as on DeiT-S, the logit-sum predictor accounts for it without additional network evaluations, using the logits cached from the single-block runs. In general, spending a modest budget of real evaluations on candidates ranked by the logit-sum predictor removes the need for dedicated pair measurements and, on full ImageNet-1k, improves validation accuracy relative to the evaluated baselines in most settings. Limitations. • We study two models of one family. The full analysis uses ImageNet-100; the main comparisons are repeated on the full ImageNet-1k (Section 7), but the follow-up studies of Sections 6.4 and 6.5 are not. • Fine-tuning is short except for the 10k-step check of Table 3. On ImageNet-1k, 2,000 steps are about a fifth of an epoch, and the children at 70% latency stay 1.9–5.6 points below their parents. • Latency is measured on one GPU type. • In the ImageNet-100 experiments, val1k is secondary because the children are fine-tuned on 100 classes only. 14

• The hybrid’s cost grows with the number of budgets, while the IQP’s pair table can be reused across budgets. • Each search is run once per budget, and the confidence intervals are conditional on the three fine-tuning runs and are not adjusted for multiple comparisons. • The fine-tuning-aware scores of Section 6.5 use one short-fine-tune recipe and two seeds. Scores trained to predict fine-tuned accuracy, or longer proxy fine-tunes, may behave differently.

9

Conclusion

Across DeiT-S and DeiT-B, the post-fine-tuning accuracy gap between the additive ILP search and the pairwise IQP search widens sharply as the block-latency budget decreases from 60% to 55%, on both ImageNet-100 and full ImageNet-1k. We decompose the KL additivity error into a metric component, which can be computed from cached single-block logits without additional network evaluations, and a functional component that captures the score-level effect of non-additive logit changes. The metric component accounts for most of the mean KL additivity error on DeiT-S, whereas the functional component dominates on DeiT-B. The hybrid search eliminates the dedicated pair-measurement stage and significantly outperforms the IQP in 7 of 14 ImageNet-100 settings and 13 of 14 full ImageNet-1k settings; it significantly underperforms in one ImageNet-100 setting. The ImageNet-100 follow-up experiments show that further reductions in pre-fine-tuning KL do not consistently improve fine-tuned accuracy. Under the tested proxy fine-tuning recipe, short finetuning before scoring provides no consistent selection advantage, while calibration top-1 measured before fine-tuning ranks the evaluated candidate structures more accurately than calibration KL.

References [1] A. Bercovich, T. Ronen, et al. Puzzle: Distillation-based NAS for inference-optimized LLMs. arXiv preprint arXiv:2411.19146, 2024. [2] Z. Deng, X. Wang, S. Sharify, and M. Orshansky. Mixed-precision quantization with cross-layer dependencies. arXiv preprint arXiv:2307.05657, 2023. [3] Z. Dong, Z. Yao, A. Gholami, M. W. Mahoney, and K. Keutzer. HAWQ: Hessian AWare quantization of neural networks with mixed-precision. In ICCV, 2019. [4] B. Efron and R. J. Tibshirani. An Introduction to the Bootstrap. Chapman & Hall, 1993. [5] Q. Huangfu and J. A. J. Hall. Parallelizing the dual revised simplex method. Mathematical Programming Computation, 10(1):119–142, 2018. [6] C. Li, J. Peng, L. Yuan, G. Wang, X. Liang, L. Lin, and X. Chang. Block-wisely supervised neural architecture search with knowledge distillation. In CVPR, 2020. [7] Q. McNemar. Note on the sampling error of the difference between correlated proportions or percentages. Psychometrika, 12(2):153–157, 1947. [8] P. Molchanov, J. Hall, H. Yin, J. Kautz, N. Fusi, and A. Vahdat. LANA: Latency aware network acceleration. In ECCV, 2022. 15

[9] B. Moons, P. Noorzad, A. Skliar, G. Mariani, D. Mehta, C. Lott, and T. Blankevoort. Distilling optimal neural networks: Rapid search in diverse spaces. In ICCV, 2021. [10] E. Real, A. Aggarwal, Y. Huang, and Q. V. Le. Regularized evolution for image classifier architecture search. In AAAI, 2019. [11] O. Russakovsky, J. Deng, H. Su, et al. ImageNet large scale visual recognition challenge. International Journal of Computer Vision, 115(3):211–252, 2015. [12] H. Touvron, M. Cord, M. Douze, F. Massa, A. Sablayrolles, and H. Jégou. Training dataefficient image transformers & distillation through attention. In ICML, 2021. [13] C. White, A. Zela, R. Ru, Y. Liu, and F. Hutter. How powerful are performance predictors in neural architecture search? In NeurIPS, 2021. [14] R. Wightman. PyTorch pytorch-image-models, 2019.

A

image

models.

https://github.com/huggingface/

Measured latency of the selected structures

Table 11: End-to-end latency of the structures selected in the ImageNet-100 experiments, as a fraction of the parent (RTX 5090, batch 64). Each timing is the median of 100 runs after 20 warm-up runs, as for the block table; the value shown is the median of three such timings. Parent: 5.84 ms (DeiT-S), 16.84 ms (DeiT-B).

B

budget

ILP

DeiT-S IQP hybrid

ILP

DeiT-B IQP hybrid

70% 65% 60% 55% 50% 45% 40%

73.5% 68.2% 64.1% 59.0% 54.4% 49.5% 44.8%

73.0% 67.9% 64.0% 59.4% 54.6% 50.0% 45.0%

71.1% 66.6% 61.8% 56.9% 51.6% 47.6% 42.5%

72.0% 67.2% 62.8% 57.3% 52.2% 47.8% 42.4%

73.0% 68.8% 64.2% 59.5% 54.8% 49.7% 44.3%

71.9% 66.6% 62.0% 57.3% 52.8% 48.0% 42.7%

Hybrid v2: full comparison

Table 12: Hybrid v2 versus the other searches: counts of significant wins / ties / losses of hybrid v2 over the 14 settings (two models × seven budgets; ImageNet-100). A tie means that the 95% interval includes 0.

val100 val1k

vs. ILP

vs. IQP

vs. hybrid

vs. evolution

vs. random

13/1/0 13/0/1

7/4/3 4/3/7

2/10/2 3/2/9

2/10/2 10/0/4

5/8/1 8/0/6

16

Related documents

• Delta-Based Neural Architecture Search: LLM Fine-Tuning via Code Diffs#158578
• Model-Free Surrogate-Assisted Neural Architecture Search for Evolving Variable-Length Dense Blocks#924342
• Model-Free Surrogate-Assisted Neural Architecture Search for Evolving Variable-Length Dense Blocks#920111
• Distillation-based training for multi-exit architectures#449032
• LLM as a Tool, Not an Agent: Code-Mined Tree Transformations for Neural Architecture Search#1400892