Hierarchical Compositionality and the Efficiency of Depth

This direction is merged into another direction: depth-width efficiency tradeoff. Its last version stays readable and citable here.

Version 1 of 195 papers142 conceptsfrozen 2026-10-04

The fundamental question of deep learning is not whether deep networks can learn complex functions—the Universal Approximation Theorem tells us that even a single hidden layer can represent any continuous function—but rather why they are so much more efficient at doing so than shallow ones.

Research into the expressive power of deep architectures suggests that the "magic" of deep learning lies in a structural alignment between the network and the world. This alignment, often called the blessing of compositionality, allows deep networks to bypass the "curse of dimensionality" that plagues traditional statistical methods.

The Curse of Breadth

To understand why depth matters, we must first look at why breadth fails. In a shallow architecture, every input variable is treated as globally related to every other variable. To approximate a high-dimensional function, a shallow network must essentially "brute-force" the representation.

Olivier Delalleau and Yoshua Bengio demonstrated this using Sum-Product Networks (SPNs). They proved in Shallow vs. Deep Sum-Product Networks that deep architectures can represent certain functions with a linear number of units, while shallow versions of the same functions require an exponential number of units. Without depth, the network cannot keep expressions in a nested, factorized form, leading to an "exponential explosion" of terms when the function is flattened into a single layer.

The Blessing of Compositionality

The reason deep networks are so effective is that the functions we care about in the real world—vision, language, and physics—are rarely "flat." Instead, they are compositional: they are built from a hierarchy of local interactions.

Tomaso Poggio and Hrushikesh Mhaskar argue in Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality that deep networks mirror the directed acyclic graph (DAG) structure of these functions. By restricting interactions to small subsets of variables at each layer (hierarchical locality), deep networks reduce the complexity of the approximation task.

In this framework, the number of parameters required scales with the maximum number of inputs to any single internal node, rather than the total number of global input variables. As M. D. Fraser notes in Compositional sparsity of learnable functions, this "compositional sparsity" transforms an exponential high-dimensional problem into a linear summation of simpler, low-dimensional tasks.

Exponential Efficiency through Reuse

Depth provides a "compact language for complexity" by leveraging the recursive reuse of intermediate results. David Rolnick and Max Tegmark illustrate this with the example of multiplying variables. In The power of deeper networks for expressing natural functions, they show that while a shallow network requires $2^n$ neurons to multiply $n$ inputs, a deep architecture can achieve this with $O(n)$ neurons by building a binary tree of multiplications.

This efficiency isn't limited to standard neural networks. It appears across various architectures:

Structural Alignment and Generalization

The success of deep learning is ultimately a result of structural alignment. When a network's hierarchical layers match the intrinsic steps of a process, it achieves optimal convergence rates with fewer parameters. Guohao Shen and colleagues demonstrate in Deep Quantile Regression that by calibrating depth and width to match the smoothness of individual functions within a compositional hierarchy, models can overcome the curse of dimensionality in regression tasks.

This efficiency also explains why deep networks generalize so well. By representing complex functions with significantly fewer parameters than shallow networks, deep architectures have a lower "effective capacity," which Poggio et al. argue minimizes the risk of overfitting and reduces the number of training samples required to reach a target accuracy. In essence, depth acts as a structural prior that matches the compositional nature of the physical world.

Papers in this version

Showing 60 of 95 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_hierarchical_compositionality_and_the_ef_a5d316f9,
  title = {Hierarchical Compositionality and the Efficiency of Depth},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hierarchical-compositionality-and-the-efficiency-of-depth/rdr_a5d316f981a44911a30bcb3d90b7754e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_hierarchical_compositionality_and_the_ef_a5d316f9_v1,
  title = {Hierarchical Compositionality and the Efficiency of Depth},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hierarchical-compositionality-and-the-efficiency-of-depth/rdr_a5d316f981a44911a30bcb3d90b7754e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}