Compiling Trained Networks into Frozen Random Ones: Sign-Aware Transport for Training-Free Strong Tickets

A randomly initialized neural network that is wide enough already contains a subnetwork that performs well. You find it by deciding which connections to keep, without ever changing a weight. This is the "strong lottery ticket" claim, and it is backed both by existence proofs and by practical search methods. Those methods still pay close to the price of ordinary training, though. Edge-popup, for example, learns a score for every frozen weight with full backpropagation, and a network found this way is a Wide ResNet-50 that uses 30% of its weights and reaches about 73% top-1 on ImageNet (What's Hidden in a Randomly Weighted Neural Network?). We propose to skip that search when a trained model already exists. The trained model is "compiled" into a frozen random network one layer at a time, with no gradient steps. The only difficulty is deciding which random neurons will imitate which trained neurons. That is an assignment problem between two unordered sets of neurons, and entropic optimal transport solves it at the scale of modern layers.

The mechanism rests on one constraint that the sign-preservation literature has made precise. A mask can keep or drop a weight, but it cannot flip the weight's sign. Evidence from lottery tickets says signs carry most of the information in a good sparse network, and exact magnitudes carry little. Tickets retrain fine when magnitudes are resampled with signs held fixed (Deconstructing Lottery Tickets), and any initialization becomes a winning ticket once it is given the right signed mask (Find A Winning Sign). Our claim follows from this. The success of a frozen random subnetwork should be governed by one measurable quantity: how much of the trained network's weight mass has a matching-sign connection available in the random pool once neurons are aligned. Optimal transport is the natural tool for choosing an alignment that maximizes this quantity.

Core Claim

Given a trained network and a frozen random network of the same depth that is $k$ times wider, a layer-by-layer, sign-aware transport assignment followed by greedy subset selection can produce a strong ticket. We claim this ticket matches edge-popup accuracy at a small fraction of edge-popup's compute. We further claim that the remaining gap to the trained network is explained by sign unavailability rather than by magnitude mismatch.

The second claim can be tested directly. It also answers a question left open by Strong Lottery Ticket Hypothesis with ε-perturbation. That paper showed that letting random weights move within an $\epsilon$-ball before mask search raises MNIST accuracy from around 0.82 to close to 0.98. It did not check whether this gain comes from flipping the signs of near-zero weights or from shifting magnitudes. We predict it is mostly sign flips.

How the Compilation Works

The procedure moves forward one layer at a time. At layer $l$, each teacher neuron (from the trained network) must be imitated by $k$ student neurons (from the random network). Assume the previous layer has already been assigned, so every teacher input $u$ has a known group of student "replicas." Student neuron $j$ can then stand in for teacher neuron $i$ only if, for the important incoming weights $W_{iu}$, $j$ has at least one frozen incoming edge from $u$'s replicas whose sign matches $W_{iu}$. We score this with a sign-availability cost: $$C_{ij} = -\sum_u |W_{iu}|\, s_{j}(u, \mathrm{sign}(W_{iu})),$$ Here $s_j(u,\sigma)=1$ if student neuron $j$ has a frozen incoming edge of sign $\sigma$ from a replica of teacher input $u$, and $0$ otherwise. The cost reduces to a pair of matrix products over sign indicators, so it runs efficiently on a GPU.

The assignment is then the entropic transport problem $$\min_{P \ge 0,\; P\mathbf{1} = k\mathbf{1}_n,\; P^\top \mathbf{1} \le \mathbf{1}_{kn}} \langle P, C \rangle - \epsilon H(P),$$ The symbols are as follows. $P$ is the coupling between the $n$ teacher neurons and the $kn$ student neurons. Its row constraint gives each teacher neuron exactly $k$ replicas, and its column constraint uses each student neuron at most once. $H$ is entropy, and $\epsilon$ controls smoothing. Sinkhorn scaling solves this with GPU matrix-vector products in near-quadratic time (Altschuler et al.; Fast Computation of Wasserstein Barycenters). We round $P$ to a hard assignment. Exact assignment by linear programming costs cubic time, which rules it out for transformer-width layers. The Sinkhorn step is what keeps the method tractable.

Once neurons are assigned, each student neuron keeps a subset of its matching-sign incoming edges. The subset is chosen greedily so that the neuron's pre-activation, measured on a small probe batch, fits the teacher neuron's pre-activation up to a positive scale. This is the subset-sum construction behind the existence proofs (Proving the Lottery Ticket Hypothesis; Logarithmic Pruning is All You Need), carried out approximately and driven by data. Batch-normalization and head parameters stay frozen, exactly as in edge-popup. The cost is one probe-batch forward pass, one Sinkhorn solve, and one greedy fit per layer, with no backpropagation. An optional second stage uses the compiled mask to initialize edge-popup scores and runs a short search.

Relation to Prior Work

The motivating evidence comes from the sign literature. Deconstructing Lottery Tickets shows that signs are what matter for retraining tickets, and that heuristic supermasks built from sign and magnitude cues reach only 41% on CIFAR-10. Sign-In to the Lottery proves that sparse networks cannot easily push weights across zero, and that no continuous reparameterization fully fixes this. Masks, Signs, And Learning Rate Rewinding shows that learning-rate rewinding beats iterative magnitude pruning precisely by keeping early sign corrections. A frozen random network is the limiting case of these results: zero sign flips are allowed. That is why we make sign availability, rather than magnitude, the quantity the alignment optimizes.

Find A Winning Sign is the closest sign-based method, and we differ from it in two ways. It overwrites signs on a fresh initialization and then trains, and it finds its signed masks through multi-cycle learning-rate rewinding. We change no weight and train nothing.

The method comes from transport-based pruning. Towards Meta-Pruning via Optimal Transport uses a transport map to fuse pruned neurons into survivors within one trained network. CPOT ranks channels by Wasserstein distance to a layer barycenter. SWAP recasts post-training pruning as entropic Wasserstein regression solved with Sinkhorn. All three prune a trained network in place. None of them transports structure from one network into a different, frozen, random one, and none treats sign as a feasibility constraint.

The constraint comes from strong-ticket search. Edge-popup (What's Hidden in a Randomly Weighted Neural Network?) and trained supermasks both need full backpropagation over scores. What's Hidden in a One-layer Randomly Weighted Transformer? documents the same overhead for transformers. That overhead is what we try to remove.

Research Program

The work has three parts.

The first is a diagnostic study. We rerun the $\epsilon$-perturbation setup, a 4-layer MLP with 500 hidden units per layer on MNIST, and log every weight whose sign changes under the projected-gradient step. We then rerun mask search with only those sign changes applied and magnitudes reset. If most of the gain from 0.82 to 0.98 survives, sign availability is confirmed as the bottleneck.

The second is building the compiler and measuring its accuracy against width multiplier $k$ on MNIST and CIFAR-10. We also report sign-availability coverage, meaning the fraction of teacher weight mass with a matching-sign edge after alignment, as a predictor of accuracy.

The third is scaling the compiler to ImageNet. There, a trained ResNet-50 is compiled into a frozen random Wide ResNet-50-2, which has the same depth and twice the width. This setting lets us compare directly against edge-popup's reported network. A final sign-budget experiment lets the compiler flip a small fraction $\rho$ of the frozen weights. We then measure how much accuracy each percent of flips buys, which tells us how close the frozen-sign constraint is to the whole story.

Baselines

The naive reference points are a random mask at matched sparsity and the heuristic supermask of Deconstructing Lottery Tickets, which reports 86% on MNIST and 41% on CIFAR-10. Both cost essentially nothing to compute, so any compiled ticket must clear them by a wide margin to justify even one Sinkhorn solve.

The strongest competitor is edge-popup (What's Hidden in a Randomly Weighted Neural Network?). It optimizes continuous scores over frozen weights with a straight-through estimator, and it reports about 73% top-1 on ImageNet for a Wide ResNet-50 using 30% of its weights. On CIFAR-10, the trained supermask of Deconstructing Lottery Tickets reports 65.4%. For the edge-popup CIFAR-10 figure with the specific architecture we use, no reported result was found on Lacuna, so we will run it ourselves.

For fairness, we run edge-popup on the same frozen random networks, with the same seeds, the same sparsity, and the same data. We give it a tuning budget equal to the one used for the compiler's $\epsilon$, probe-batch size, and $k$. We report accuracy as a function of wall-clock GPU time, both with and without the one-time cost of training the teacher, because edge-popup does not need a teacher and hiding that cost would be unfair.

We count the compiler as beating edge-popup under either of two conditions. The first is that it reaches edge-popup's accuracy within one point using less than 10% of edge-popup's search compute. The second is that compiler-plus-short-search beats edge-popup at equal total compute. We also report the $\epsilon$-perturbation method at its reported MNIST figure of close to 0.98 with $\epsilon=0.3$. It is not a like-for-like competitor, because it modifies weights. It serves as the reference for the sign-budget experiment.

The ablation that isolates our key ingredient replaces the transport assignment with a fixed index assignment, where student neurons $jk$ through $jk+k-1$ imitate teacher neuron $j$. Everything else stays identical. A second ablation keeps transport but uses a sign-blind cost, namely activation-profile distance. The upper bound on everything is the teacher's own accuracy.

Why not just…?

Why not just run edge-popup with a distillation loss against the teacher? This is a real threat, because local distillation losses may speed score learning enough to erase our compute advantage. We include it as an additional baseline, run under the same compute-matched protocol. If it matches our accuracy-per-GPU-hour, the contribution shrinks to the diagnostic claim about signs, and we will say so.

Why not just assign replicas by index, since the random network is symmetric anyway? The network is symmetric in distribution, but a particular draw is not. Which student neurons happen to have matching-sign edges from which inputs is a property of the realized random weights, and an index assignment ignores it. The fixed-assignment ablation settles this. If coverage and accuracy do not improve over index assignment at small $k$, transport is unnecessary and we will drop it. We expect the gap to close as $k$ grows, and the width sweep will show where it closes.

Why not just quantize the teacher to ternary weights if the goal is a compact model? If the goal is storage, ternary quantization probably wins. A mask over a $k$-times-wider network costs more bits than roughly 1.6 bits per teacher weight, and Quantization vs Pruning frames this very tradeoff. We therefore do not claim a storage advantage. Our claims concern search cost in settings where the random weight pool is fixed and regenerated from a seed, as in seed-based image codecs (LotteryCodec), and a constructive test of how much width sign constraints demand in practice. We will report bits per model for both approaches so readers can judge.

Why not just use A Winning Sign's signed mask? It overwrites signs and retrains from a fresh initialization, which violates the frozen-weight setting. Its discovery also runs on iterative rewinding. It is the right tool when training is allowed, and our sign-budget experiment measures exactly how far a small amount of that freedom moves the frozen result.

Decisive Checks

Four results would decide the outcome.

The first is the MNIST sign-attribution experiment. If replaying only the sign changes from the $\epsilon$-perturbation method recovers most of the 0.82 to 0.98 gain, the core premise holds. If magnitude shifts account for most of the gain, the sign-aware cost is the wrong objective.

The second is the rank correlation, across seeds and widths on CIFAR-10, between sign-availability coverage and final compiled accuracy. A strong correlation would validate coverage as the quantity to optimize.

The third is the ImageNet comparison: compiled Wide ResNet-50-2 accuracy and GPU time against edge-popup's roughly 73% at 30% weights. Low accuracy at $k=2$ would tell us that practical compilation needs more width than this architecture offers, which is itself useful evidence about the gap between logarithmic bounds and practice.

The fourth is the sign-budget curve. If flipping 1% of weights closes most of the remaining gap to the teacher, frozen signs are the dominant obstacle to strong tickets, and that would redirect how the field searches for them.