On the Architectural Complexity of Neural Networks

Nicholas J. Cooper, François G. Meyer, Michael L. Roberts, Carlos Zapata-Carratalá, Lijun Chen, and Danna Gurari present a combinatorial theory for neural networks that models architectures as rank-5 hierarchical complexes built from elements, generalized tensors, mode maps, tensor operations, and full network diagrams. The key technical move is to represent tensor operations explicitly rather than hiding them behind high-level layer abstractions, which lets the authors define architectural complexity through five signatures: operation complexity, tensor complexity, arity complexity, order complexity, and coupling-arity complexity. Using this framework, they analyze eight canonical architectures over 40 years and show that major jumps, such as from ResNet to Transformer, align with the first appearance of higher arity operations; in their encoding, a single-head self-attention block has Cop 3, CT 7, Cα 3, CO 4, and CA 2, while a residual block has Cop 3, CT 6, Cα 2, CO 6, and CA 2. They then systematically generate 3,028 novel higher-complexity architectures, evaluate them on CIFAR-10, CIFAR-100, and Tiny Imagenet, and find that some small sampled blocks are highly parameter efficient: one highlighted CIFAR-100 model reaches 65.52% accuracy with fewer than 200,000 parameters, surpassing MobileNetV2’s 64.29% with an order of magnitude fewer parameters, and the same model reaches 66.32% after 120 epochs. The paper also introduces a neural-network engine and a tensor-operation calculus, including tensor operation matrices and tensor equation matrices, to make these constructions executable and searchable.