Technical Summary: Algorithmic Simplification of Neural Networks with Mosaic-of-Motifs

Problem Statement

Large-scale deep learning models have demonstrated superior performance across domains such as computer vision, multi-modal learning, and reinforcement learning, largely driven by scaling laws. However, this scaling incurs substantial costs in memory, compute, and energy. While compression techniques like pruning, quantization, and knowledge distillation have successfully reduced model sizes by exploiting redundancy, a fundamental question remains: Why are deep neural networks inherently suited for compression?

Existing complexity measures often focus on parameter counts or computational footprints but fail to capture the structural organization of learned parameters. The authors hypothesize that the answer lies in algorithmic complexity. They posit that while random initialization yields parameters with high algorithmic complexity (requiring long descriptions), the optimization process induces structure and repeatability, resulting in solutions with lower algorithmic complexity. Current compression methods often treat compressibility as a post-hoc property or optimize for specific objectives (like sparsity), rather than shaping the optimization domain to inherently favor algorithmically simpler solutions.

Methodology: Mosaic-of-Motifs (MoMos)

To investigate and induce this simplicity, the authors propose Mosaic-of-Motifs (MoMos), a constrained parameterization method that restricts the hypothesis class of model weights.

Core Concept

MoMos partitions the flattened weight vector $w \in \mathbb{R}^n$ into $m$ blocks of size $s$. Instead of allowing each block to be an arbitrary vector, MoMos restricts each block to be selected from a fixed set of $k$ reusable motifs ($Z = \{z_1, \dots, z_k\}$). The arrangement of these motifs across the blocks is defined by a mosaic (reuse pattern) $M \in [k]^m$.

The resulting parameterization $\hat{w}$ is constructed as:
$$\hat{w} = \psi^{-1}(z_{M(1)}, \dots, z_{M(m)})$$
where $\psi$ is a slicing operator and $\psi^{-1}$ reconstructs the full weight vector.

Theoretical Framework

The method is grounded in Kolmogorov complexity, $K(w)$, defined as the length of the shortest program that outputs $w$.

1. Unconstrained Bound: For arbitrary weights, the worst-case description length is bounded by the bit-length of the weights: $K(w) \leq nq + O(1)$.
2. MoMos Bound: For the MoMos hypothesis class $\mathcal{H}_{s,k}$, the authors prove a tighter worst-case upper bound:
   $$K(\hat{w}) \leq ksq + m \lceil \log_2 k \rceil + \zeta$$
   Here, $ksq$ represents the bits required to describe the $k$ motifs, and $m \lceil \log_2 k \rceil$ represents the bits for the mosaic pattern.
3. Optimization Geometry: The MoMos hypothesis class decomposes into a union of linear subspaces. The richness of the optimization domain is determined by the number of distinct subspaces, which relates to Stirling numbers of the second kind. The authors show that smaller block sizes ($s$) allow for a richer optimization domain (more distinct subspaces) for a fixed capacity, while larger blocks enforce greater regularity but restrict the search space more severely.

Implementation

The optimization proceeds by alternating between updating the dense weights via standard gradient descent and projecting them onto the MoMos structure. At each step, the current weights are sliced into blocks, and a set of $k$ motifs is sampled (or updated) to minimize the reconstruction error (distortion) between the dense blocks and their motif-based representation.

Key Contributions

1. MoMos Parameterization: Introduction of a constrained parameterization that enforces repeatability and reuse, providing a theoretically justified bias toward algorithmically simpler solutions.
2. Complexity Guarantees: A formal proof that MoMos guarantees a lower worst-case algorithmic complexity compared to unconstrained parameterization, controlled by the block size $s$ and motif count $k$.
3. Empirical Validation: Demonstration that MoMos drives learned weights toward more algorithmically regular and compressible parameterizations (measured via proxies like Block Decomposition Method, BDM) while preserving performance comparable to unconstrained baselines.
4. Optimization Domain Analysis: An analysis showing that the optimization domain under MoMos is a union of linear subspaces, and that the trade-off between algorithmic simplification and domain richness can be tuned via block size and capacity.

Experimental Results

The authors evaluated MoMos on various architectures (MLP, ResNet20, Tiny-ViT, Swin-B, SmolLM2) and datasets (CIFAR-10, Tiny ImageNet, WikiText-103).

• Performance vs. Complexity: MoMos achieves baseline-level accuracy (or perplexity for LLMs) with significant reductions in algorithmic complexity. For instance, on Tiny-ViT with a block size $s=2$ and capacity $c=5\%$, the model achieves 86.99% accuracy (vs. 86.56% baseline) with a Relative Algorithmic Simplification (RAS) of 3.02.
• Granularity Trade-offs: Smaller block sizes (e.g., $s=2, 4$) preserve accuracy even at low capacities, whereas larger blocks require higher capacities to recover performance. This suggests that fine-grained reuse is more effective for maintaining function multiplicity.
• Concentration of Structure: During training, motif assignments become highly concentrated; a small fraction of motifs accounts for the majority of block assignments, while many motifs remain unused. This confirms that the optimization process naturally selects a sparse set of reusable patterns within the dense parameter space.
• Distortion and Loss: The distortion between dense weights and their MoMos reconstruction decreases alongside the validation loss, indicating that the imposed regularity does not hinder the model's ability to learn.
• Comparison to Baselines: MoMos outperforms or matches standard compression baselines (Vector Quantization, Product Quantization, Soft Weight Sharing, Quantization-Aware Training) in terms of the trade-off between accuracy and complexity reduction, often with lower training-time overhead.

Significance and Claims

The paper claims to provide the first work that offers guarantees on the algorithmic complexity of learned parameters by constraining the model class itself, rather than treating compressibility as a post-training property.

• Induced Redundancy: The work demonstrates that redundancy and structure can be induced from the optimization domain rather than just observed after training. By shaping the hypothesis class, the authors show that models can be made inherently more compressible without significant performance degradation.
• Dense Simplicity: A key insight is that models can become algorithmically simpler without becoming sparse. The learned structures remain dense (few zero motifs), but the reuse patterns create the compressibility.
• Theoretical Insight: The results support the hypothesis that learning induces structure, reducing the algorithmic complexity of the solution compared to random initialization. This aligns with the view that neural networks are biased toward functions of lower Kolmogorov complexity.
• Limitations: The authors note that while the theoretical bounds are tight, the current hardware does not yet support fast, reusable block operations, meaning the theoretical compression does not immediately translate to hardware efficiency. They also acknowledge that current complexity proxies (like BDM) are approximations and may be misleading for high-dimensional objects.

In conclusion, MoMos offers a novel perspective on model compressibility, suggesting that the "need" for massive parameter counts in deep learning may be partially replaced by structured reuse, thereby offering a path to more efficient and theoretically grounded neural network design.