🤖 machine learning

Toy Combinatorial Interpretability Models Reveal Lottery Tickets in Early Feature Space

This paper demonstrates that in a combinatorial toy setting, winning lottery tickets correspond to families of compatible feature-space locations that are already proximal to final codes at initialization, suggesting that the lottery ticket phenomenon is governed by hidden feature-space geometry rather than specific weight-space subnetwork identities.

Original authors: Alon Bebchuk, Nir Shavit

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alon Bebchuk, Nir Shavit

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, crowded library (a dense neural network) filled with millions of books. The "Lottery Ticket Hypothesis" is the idea that hidden inside this giant library is a tiny, perfect subset of books (a sparse subnetwork) that, if you took them out, put them back on the shelf exactly as they were when the library first opened, and started reading only those, you could still tell the same stories as the whole library.

For a long time, scientists asked: How do we find this tiny subset? Most tried to look at the books based on how "heavy" or "important" they looked on the shelf (weight magnitude).

This paper asks a different, more mechanical question: What is actually inside that tiny subset that makes it work?

The authors built a "toy library" (a simple, mathematically transparent model) where they can actually see the "stories" (features) being written inside the machine. Here is what they found, explained simply:

1. The Library Isn't Just Books; It's a Map

Think of the neural network not just as a pile of weights, but as a map of a city.

The Dense Network: A city where every street is crowded with traffic.
The "Ticket": A specific set of streets that, if you cleared out all the other traffic, would still allow you to get from Point A to Point B perfectly.

The paper argues that the "winning ticket" isn't just a random collection of heavy books or strong streets. Instead, it's a pre-existing map that was already drawn in the city's layout before the traffic even started moving.

2. The "Precursor" Neighborhoods

When the network starts training (the city starts building), the dense traffic (standard training) does two things:

It amplifies the good spots: It turns certain empty lots into perfect, well-organized neighborhoods (called "codes").
It rejects the crowded spots: If two neighborhoods are trying to build on the same tiny plot of land, the system rejects one to avoid a traffic jam.

The "winning ticket" is the set of empty lots that were already close to becoming perfect neighborhoods right from the start. They didn't need to be built from scratch; they just needed the right amount of traffic to finish the job.

3. The Magic of "Rewinding"

Here is the surprising part. When you take the "winning ticket" (the sparse set of streets) and rewind it to the very beginning (before any traffic), you might expect it to look like a tiny, broken version of the big city.

But it doesn't.

Because the streets are connected in a specific way, removing 75% of the "traffic" (weights) actually clears the fog. Suddenly, the remaining streets look much more organized and closer to the final perfect neighborhoods than the original messy city did. The act of pruning (removing weights) changes the map itself, revealing a hidden, clean structure that was waiting to be seen.

4. It's About the "Family," Not the "Address"

The paper found that the winning ticket doesn't care about exactly which street corner a neighborhood is on.

Old view: "We need the exact same street corner (row) to work."
New view: "We just need the type of neighborhood (the code family) to exist somewhere."

If the system needs a "4-Positive" neighborhood, it doesn't matter if it ends up on Street 2 or Street 5. As long as the family of neighborhoods is there and compatible with each other, the system works. The ticket preserves the blueprint for the family, not the specific address.

5. Better Detectors

The authors tried to find these tickets using two different detectors:

The Weight Detector: Looks at how "heavy" or strong the connections are. (This is like judging a book by its cover weight).
The Feature Detector: Looks at the "distance" to the perfect neighborhood on the map. (This is like looking at the actual layout of the streets).

They found that the Feature Detector was much better at finding the winning tickets early on. It could see the "near-perfect neighborhoods" before the heavy traffic even started. The Weight Detector only became good later, once the training had already organized the city enough that the heavy books started to look like the right ones.

The Bottom Line

The paper concludes that a "Lottery Ticket" isn't just a lucky set of numbers or a mask of weights. It is a hidden scaffold in the feature space.

Think of it like this: When you buy a house, you aren't just buying the bricks (weights); you are buying the potential of the land (feature space). The winning ticket is the land that was already shaped like a perfect house foundation before you even started building. The training process just finishes the construction.

Important Note: The authors are very clear that this was tested on a "toy" model (a small, simplified computer program designed to solve logic puzzles). They are not claiming this works exactly the same way in giant, real-world AI models yet. They are saying: "If you are a small, logical machine, this is how your lottery tickets work. Figuring out if this applies to the big, complex machines is the next step."

Technical Summary: Toy Combinatorial Interpretability Models Reveal Lottery Tickets in Early Feature Space

Problem Statement

The Lottery Ticket Hypothesis (LTH) posits that dense neural networks contain sparse subnetworks ("winning tickets") that, when rewound to their initial weights and retrained in isolation, match the performance of the full model. While prior work has established the existence of these tickets and refined the conditions for their discovery (e.g., rewinding to slightly later checkpoints), a mechanistic question remains unanswered: What internal object does a winning ticket preserve?

Existing explanations suggest tickets preserve a "lucky" set of weights, a specific mask, or a favorable optimization basin. However, in standard deep networks, the hidden representations are too opaque to determine exactly what structural object the mask corresponds to. This paper asks whether the ticket preserves a specific feature-space scaffold that allows sparse training to rebuild the necessary computation.

Methodology

The authors investigate this question using a combinatorial, clause-structured toy setting based on a Disjunctive Normal Form (DNF) detector. This setting is chosen because it admits an interpretable feature-space representation with well-defined combinatorial distances between features.

Model Architecture and Feature Space

Setup: The model consists of a learnable linear projection $C_0$ followed by a hidden layer $W_1$ and output layer $W_2$ . The network computes $z = W_2 \cdot \text{ReLU}(W_1 C_0 x + b_1) + b_2$ .
Feature Space ( $C_1$ ): The core object of analysis is $C_1 = W_1 C_0$ . This matrix represents the network's computation in feature space, disentangling features from the input embedding.
Codes: The task involves detecting positive and negative evidence for DNF clauses. The model learns specific local sign patterns (codes):
- 4P: $(+1, +1, +1, +1)$ for positive evidence.
- 3N1P: One positive and three negative signs for negative evidence.
Metrics: The authors define combinatorial distances ( $d_\tau$ ) and margins ( $m$ ) to measure how close a local vector is to these canonical code families.

Experimental Design

Ticket Cycle: The authors simulate the full LTH cycle: dense training $\to$ masking (pruning) $\to$ rewinding to initialization $\to$ sparse retraining.
Feature-Space vs. Weight-Space: They analyze how applying a mask to the initial weights changes the initial feature-space state ( $C_1$ ). They demonstrate that pruning is not merely a visual restriction of weights but fundamentally alters the row patterns in feature space.
Probes: The paper introduces "mechanism-inspired" detectors that rank feature-space locations based on:
- Static Distance: Proximity to canonical code families.
- Motion: Finite-difference movement toward codes during early dense training.
- Compatibility: Avoiding overcrowded rows (superposition).
Comparisons: These feature-space rules are compared against standard weight-space baselines (SNIP, GraSP, SynFlow, Early-Bird magnitude) and random sparse expansions.

Key Contributions

1. The Ticket is a Feature-Space Scaffold, Not Just a Mask

The paper argues that a winning ticket is not a fixed set of weights but a family of compatible feature-space locations.

Family-Level Recovery: Sparse retraining often recovers the correct clause/template family (e.g., 4P) but on a different row than the dense model. Therefore, the preserved object is the code family, not the microscopic row identity.
Precursor Locations: Winning tickets correspond to precursor locations in the initial feature space that are already near (at initialization) to the final feature-channel codes.

2. Mechanism of Dense SGD and Superposition

Dense SGD acts as a selector in feature space:

Amplification: It drives selected precursor locations toward exact canonical codes.
Rejection: It rejects other plausible early locations, particularly those on "crowded" rows (rows with high load).
Competition: This indicates that ticket formation involves resolving competition under superposition, where multiple features share limited representational dimensions. A ticket is a set of locations that balances proximity to final codes with low inter-feature interference.

3. Pruning Alters the Initial Feature State

Applying a mask to the initial weights ( $W_1$ ) changes the entire initial feature-space state ( $C_1$ ).

Zeroing coordinates outside the mask changes the whole row pattern in $C_1$ .
Consequently, the "sparse initialization" is a new projected feature-space state, not just a subset of the dense initial state.
A winning ticket is a family of locations in this new state that leaves enough degrees of freedom for sparse SGD to reconstruct compatible codes.

4. Diagnostic Probes Outperform Weight-Based Methods

The authors propose lightweight probes based on feature-space distance and motion.

Results: In the toy setting, these feature-space probes frequently outperform established weight-based ticket discovery methods (like SNIP or magnitude) in both accuracy and exact code recovery, particularly in the early stages of training.
Limitation: While feature-space rules identify the correct locations, there remains a "translation problem" of implementing these locations with a sparse set of weight-space coordinates.

Results

Structure Preservation: OBS (Optimal Brain Surgeon) tickets preserve significantly more of the dense model's code geometry (approx. 53-54% same-site recovery) compared to random sparse expansions (approx. 20%).
Precursor Proximity: In the masked initial state, OBS tickets place a much higher fraction of eventual final code sites at distance 0 or 1 from their target templates compared to random masks. For example, in the epoch-10 rewind state, 78.9% of eventual final code sites were within one defect, compared to 54.6% for random sparse.
Superposition Dynamics: Rejection of candidate codes is concentrated on heavily loaded rows, confirming that dense SGD resolves competition among candidate carriers.
Probe Performance: Feature-space diagnostics (static distance + dynamic motion) lead in exact code recovery and perform competitively in accuracy against weight-space baselines, validating the hypothesis that early ticket structure is visible as geometry in feature space rather than raw weight saliency.

Significance and Claims

The paper positions itself as a model-organism study rather than a completed theory for all neural networks.

Modest Scope: The authors explicitly state that their findings are grounded in a toy setting (small networks computing Boolean formulae). They draw an analogy to Judah Folkman's cancer research: "if you are a mouse and you have cancer, we can probably cure you." Similarly, "if you are a small neural network computing Boolean formulae, then we can probably understand your lottery tickets."
Core Insight: The primary contribution is a shift in perspective: the lottery ticket structure is governed by hidden feature-space geometry rather than weight-space subnetwork identity.
Future Directions: The paper suggests that extending these ideas to larger models may require approximate feature dictionaries or sparse autoencoder-style decompositions. It highlights an open "translation problem" between selecting feature-space locations and implementing them with sparse weights.
Interpretability: The work suggests a new path in interpretability research where feature-space measurement is possible, moving beyond opaque weight-space analysis to understand the "scaffold" that sparse training rebuilds.

In summary, the paper provides a mechanistic explanation for the Lottery Ticket Hypothesis in a controlled setting, demonstrating that winning tickets preserve a feature-space scaffold of precursor locations that are already near the solution, and that dense training serves to select and refine this scaffold by resolving superposition competition.