Making a large language model shallower means deleting whole attention or feed-forward blocks. The safe way to do it today is slow. You remove one block, re-measure the model's quality on held-out text, remove the next least harmful block, and repeat. The slowness exists because blocks interact: two blocks can each be harmless to drop alone and catastrophic to drop together, so a single ranking of blocks cannot be trusted. Wireless broadcast coding faced the same shape of problem twenty years ago. Serving one receiver per transmission was safe but slow, and the fix was to find, in each time slot, the largest group of receivers that one coded packet could satisfy at once. That group is a clique, a set of nodes that are all pairwise connected, in a "compatibility graph" whose edges mark pairs of requests that do not conflict.
This note proposes to carry that scheduling idea over to pruning. We measure, once per round, how much damage each pair of blocks does when removed jointly. We draw an edge between two blocks when their joint removal is safe. We then delete an entire maximum-weight clique of mutually safe blocks before re-measuring. If this works, the number of sequential validation rounds falls from roughly the number of removed blocks to a handful. The method also protects against the "fine alone, fatal together" failure that one-shot ranking ignores.
Core Claim
The claim is that pairwise-verified clique selection removes many blocks per round with no loss in quality relative to one-by-one greedy removal, at a fraction of its sequential cost. The clique constraint, which requires every pair in the removed set to be individually checked as safe, is the ingredient that makes multi-block removal reliable. A cheaper additive pairwise score cannot replace it. A second, falsifiable claim comes straight from the coding literature. Instantly Decodable Network Codes for Real-Time Applications showed that clique-based coding beats uncoded repetition by up to 3.8× at moderate loss but converges to it when erasures exceed 65%, because when almost everything is missing, trivial choices serve everyone. The pruning analogue predicts that clique selection should match simple ranking at low pruning ratios, where nearly all candidate blocks are harmless. Its advantage should appear only at intermediate-to-aggressive depth ratios, where safe blocks are scarce and their interactions matter.
What Carries Over From Coding, and What Does Not
The coding work supplies the method. In Instantly Decodable Network Codes for Real-Time Applications, vertices are (receiver, wanted packet) pairs, edges mark pairs decodable from a single XOR, and the best transmission is a maximum clique. The graph is rebuilt every slot as receivers' caches change. We reuse that per-round rebuild: after each removal round, the pruned model's pair damages are re-measured. Douik et al. replace raw clique size with weighted cliques, with weights encoding uncertain feedback in Partially Blind Instantly Decodable Network Codes for Lossy Feedback Environment and accumulated delay in On Minimizing the Maximum Broadcast Decoding Delay for Instantly Decodable Network Coding. We borrow weighting in two ways. Vertex weights encode the compute saved by removing a block. Edge admission accounts for noise in damage estimates from a small calibration set, analogous to the lossy-feedback case.
A Graph Model for Opportunistic Network Coding supplies a useful constraint. It restricts coding to order-2 combinations because pairwise adjacency conditions stay polynomial while higher orders explode. We make the same bet: verify interactions exactly at order 2, and catch any rare higher-order failure with one cheap verification pass of the whole chosen set per round. If that pass fails, we back off by dropping the lowest-weight vertex. The conflict-graph colouring in Rate-Distortion-Memory Trade-offs in Heterogeneous Caching Networks is the complementary formulation and motivates the conflict-graph view of depth pruning, though it was applied only to video delivery.
One worry from coding does not transfer: NP-hardness. A 7B–14B model has at most a few dozen attention submodules, so exact maximum-weight clique search on graphs of under 100 vertices takes negligible time. The cost lies entirely in measuring edges, and that is where the overhead accounting must be honest.
On the pruning side, the motivating evidence is 2SSP: A Two-Stage Framework for Structured Pruning of LLMs. It prunes feed-forward neurons in one shot and then removes attention submodules one at a time by perplexity impact. It reports a two-order-of-magnitude pruning-time gain over iterative layer-removal methods and remains sequential in its second stage. That second stage is exactly what we replace. Till the Layers Collapse motivates the interaction problem from the other direction. It shows that naive layer dropping collapses BERT while a principled analytical criterion removes 10 of 12 layers within 6% accuracy. Removal decisions therefore cannot be made by independent scores. The learned-mask methods MaskLLM and LEAP constrain the design space. They show that end-to-end optimization beats layer-wise proxies, with LEAP reaching 13.16 versus 50.55 perplexity for ADMM on Qwen-2.5 0.5B at 60% unstructured sparsity, but they cost 276 to 1,280 GPU-hours and operate on weights rather than blocks. We do not compete with them on fine-grained sparsity. We target the structured depth-pruning regime where gradient-free, forward-pass-only selection is the goal.
Research Program
We gate each prunable unit $i$ (an attention submodule or a full block) and measure two quantities on a small calibration set: its solo damage $d_i$, the increase in calibration loss when it alone is removed, and its pair damage $d_{ij}$ when $i$ and $j$ are removed together. Vertex $i$ enters the graph only if $d_i \le \tau_1$. Edge $(i,j)$ exists if
$$d_{ij} \le \tau_2 \quad\text{and}\quad d_{ij} - d_i - d_j \le \epsilon,$$
where $\tau_2$ caps joint damage and $\epsilon$ caps super-additive interaction, the "fatal together" signature. Each vertex carries weight $w_i$, equal to the parameters or measured latency it saves. A round removes the maximum-weight clique and runs one verification pass on the whole set. The graph is then rebuilt on the pruned model, as an IDNC scheduler rebuilds after each slot. The thresholds are set by bisection so that the schedule reaches the target depth reduction.
Edge measurement costs one forward pass over the calibration set per surviving pair. For $B$ candidate units that is at most $B(B-1)/2$ passes, but the vertex filter shrinks $B$ and the passes are independent, so they batch in parallel. One-by-one greedy removal of $k$ units, by contrast, requires $k$ sequential rounds of up to $B$ evaluations each. We will report both total forward-token cost and the number of sequential rounds, because the claimed saving is mainly in sequential depth and wall-clock time, not necessarily in total FLOPs. We will also build a cheaper edge estimator from gate-gradient outer products, which costs one backward pass, so that the value of exactly measured pairs can be tested directly.
Baselines
The naive reference point is one-shot solo ranking. Every unit is scored by $d_i$ once, and the $k$ lowest-damage units are removed together. It uses the same calibration data and the same $d_i$ measurements our method computes, so any gain over it is attributable to pairwise information. Beating it means lower WikiText-2 perplexity and higher mean zero-shot accuracy at matched depth reduction. We expect to beat it only at moderate and high pruning ratios, as the coding analogy predicts.
The strongest existing method is 2SSP (2SSP), run with its own feed-forward width stage unchanged. Only its iterative attention-removal stage is replaced by clique scheduling, so the comparison isolates the depth-selection step. Both methods use the same calibration sequences and the same evaluation harness. The reference number is 2SSP's reported 58.92% average zero-shot score on Phi-3 14B at 37.5% sparsity, against 50.23% for the next best competitor. Beating 2SSP means matching or exceeding its zero-shot score at the same sparsity with substantially fewer sequential evaluation rounds and lower wall-clock pruning time on the same GPU. For the stand-alone one-by-one greedy removal it is compared against, no reported wall-clock pruning time was found on Lacuna, so we will measure it ourselves.
We also run a compute-matched iterative greedy baseline, which is one-by-one removal given exactly the same total number of calibration forward passes our method spends on edges. It answers whether spending the pair budget on more careful sequential search would do just as well.
Two ablations isolate the key ingredient. The first, the quadratic-greedy ablation, feeds the identical measured $d_{ij}$ matrix into a greedy minimizer of the additive score $\sum_i d_i + \sum_{i<j}(d_{ij}-d_i-d_j)$ with no clique constraint. The second, the estimated-graph ablation, builds edges from gradient outer products instead of measured pairs. A random-clique control of matched size checks that graph structure, not removal count, drives the results.
Why not just…?
Why not just rank blocks once by individual damage and drop the lowest k? This is free once solo damages are known. The lottery-ticket evidence shows that one-shot removal of large fractions causes a quality crash because interdependencies are ignored (The Lottery Ticket Hypothesis), and Till the Layers Collapse shows naive layer dropping collapsing BERT. Still, at low pruning ratios we expect ranking to tie with our method. We state this as a prediction rather than hiding it, and the sweep over depth ratios will show where the crossover lies.
Why not just keep 2SSP's one-by-one removal, since it is already fast? 2SSP is fast relative to older iterative methods, but its attention stage still requires one sequential round per removed module, and those rounds cannot be parallelized. Clique scheduling converts most of that work into independent pair evaluations. If the compute-matched iterative baseline equals our quality at equal wall-clock time, the case for clique scheduling reduces to parallelism alone, and we will report it that way.
Why not just optimize the pairwise quadratic score greedily, without any clique? This is the most serious threat, because it uses the same pair measurements. It differs in one way: an additive score lets one strongly interacting pair be outweighed by many small savings, whereas the clique forbids any unsafe pair outright. Near collapse, damage is far from additive, so we expect the hard constraint to matter most at aggressive ratios. The quadratic-greedy ablation settles this directly. If it matches our method everywhere, the honest conclusion is that the contribution is the round-based pair measurement and re-scheduling, not the clique formulation itself.
Proposed Experiments
The main study prunes attention submodules and full blocks in LLaMA-2 7B and Phi-3 14B. It evaluates WikiText-2 perplexity and the seven-task zero-shot suite used by An Efficient Pruner for Large Language Model with Theoretical Guarantee, at 2SSP's sparsity levels and a sweep of depth reductions. Calibration uses 128 sequences, the convention in this literature, with a 32-sequence subset for pair measurement. We report quality, total forward-token cost, sequential rounds, and wall-clock time.
The first decisive check is an exhaustive-search optimality test on Qwen-2.5 0.5B. With 24 attention submodules and 6 removed, all 134,596 subsets can be evaluated on a small calibration set. This shows how close clique scheduling, ranking, quadratic greedy, and one-by-one greedy each come to the true best subset. It also measures how often order-2 verification misses a higher-order failure, which tests the order-2 bet borrowed from A Graph Model for Opportunistic Network Coding.
The second decisive check is the degeneracy curve: the clique method's advantage over ranking, plotted against pruning ratio. If the advantage is flat or absent at intermediate ratios, the coding analogy has failed and the method has no reason to exist. If the advantage rises from zero, peaks, and falls again when no safe cliques remain, the curve will reproduce the regime structure that Instantly Decodable Network Codes for Real-Time Applications found in broadcast coding.
References
- Instantly Decodable Network Codes for Real-Time Applications
- Partially Blind Instantly Decodable Network Codes for Lossy Feedback Environment
- On Minimizing the Maximum Broadcast Decoding Delay for Instantly Decodable Network Coding
- A graph model for opportunistic network coding
- Rate-Distortion-Memory Trade-Offs in Heterogeneous Caching Networks
- 2SSP: A Two-Stage Framework for Structured Pruning of LLMs
- Till the Layers Collapse: Compressing a Deep Neural Network Through the Lenses of Batch Normalization Layers
- MaskLLM: Learnable Semi-Structured Sparsity for Large Language Models
- LEAP: Learnable End-to-End Adaptive Pruning of Large Language Models
- The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
- An Efficient Pruner for Large Language Model with Theoretical Guarantee