Structured Transforms and the Power of Two Constraint

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 248 papers52 conceptsfrozen 2026-10-04

In high-performance computing and machine learning, there is a recurring "magic" number: $2^n$. Whether you are training a neural network, sorting a massive dataset, or encrypting private updates, the most efficient algorithms often demand that your data dimensions be an exact power of two.

This requirement isn't a mere preference; it is a fundamental byproduct of the "divide and conquer" strategy. When a problem can be split perfectly in half, and those halves can be split again, we unlock the $O(N \log N)$ complexity that makes modern scale possible. However, real-world data rarely arrives in neat, dyadic packages. This creates a persistent tension between mathematical elegance and practical overhead.

The Efficiency of Dyadic Symmetry

The core intuition behind structured transforms—like the Fast Fourier Transform (FFT) or the Fast Walsh-Hadamard Transform (FWHT)—is the exploitation of symmetry. By recursively decomposing a large matrix multiplication into smaller, identical operations, we can bypass the $O(N^2)$ cost of dense linear layers.

In ButterflyFlow, Chenlin Meng and Tri Dao utilize "butterfly matrices" to create invertible layers. These matrices mimic the structure of an FFT circuit, where data points "flutter" through a series of pairwise combinations. This structure is theoretically guaranteed to capture complex permutations and global dependencies with far fewer parameters than a standard linear layer.

Similarly, the ACDC architecture, proposed by Marcin Moczulski and Nando de Freitas, replaces wasteful fully-connected layers with a sequence of structured transforms. By alternating between diagonal matrices and fast transforms, they approximate any linear transformation in $O(N \log N)$ time.

The "why" behind the power-of-two constraint in these cases is simple: the recursion tree must be balanced. If you have 8 elements, you can split them into 4, then 2, then 1. If you have 9, the symmetry breaks, and the standard recursive logic fails.

The Padding Tax

When data dimensions do not align with these radix-2 constraints, researchers must pay what is often called a "padding tax." To use an FFT-based convolution, as explored by Michael Mathieu and Yann LeCun in Fast Training of Convolutional Networks through FFTs, an input of size 700 must be zero-padded to 1024.

This padding introduces several inefficiencies:

  1. Memory Overhead: You are storing and moving zeros that contribute no information.
  2. Computational Waste: The processor still performs multiplications and additions on those zeros.
  3. Stairwise Scaling: As noted in Faster Multiplication for Long Binary Polynomials by Ming-Shing Chen and colleagues, performance doesn't scale smoothly. A slight increase in data size (e.g., from 1024 to 1025) can lead to a sudden, nearly 2x jump in computational cost as the algorithm is forced to the next power of two.

Beyond Neural Networks: Sorting and Privacy

The power-of-two constraint extends far beyond deep learning. In Differentiable Sorting Networks, Felix Petersen and Christian Borgelt relax classical algorithms like Bitonic Sort into differentiable operations. Bitonic sort is inherently dyadic; it compares and swaps elements in a fixed, power-of-two pattern that is ideal for SIMD hardware but rigid in its input requirements.

In the realm of privacy, Peter Kairouz and Ken Liu demonstrate in The Distributed Discrete Gaussian Mechanism that applying unitary transforms (like the Hadamard transform) can flatten data distributions to prevent modular wrap-around errors in secure aggregation. However, because the Walsh-Hadamard transform requires power-of-two dimensions, standard model architectures must be heavily padded, leading to significant increases in communication bandwidth—a critical bottleneck in federated learning.

Hardware and Memory Layouts

The constraint is also baked into how we map data to physical hardware. Stephen Nicholas Swatman and Ana-Lucia Varbanescu explore this in Finding Morton-Like Layouts. Morton order (or Z-order) uses bit-interleaving to map multi-dimensional data into one-dimensional memory while preserving locality. This bit-manipulation trick only works seamlessly when array dimensions are powers of two. For arbitrary sizes, the result is memory over-allocation and "holes" in the address space.

Even at the compiler level, Keren Zhou and Jiarui Niu show in Linear Layouts that modeling tensor-to-hardware mappings using linear algebra over the finite field $\mathbb{F}_2$ is highly effective for power-of-two resources. Generalizing these formalisms to arbitrary shapes remains a difficult challenge because the underlying binary matrix logic relies on the clean divisibility of the power-of-two space.

The Path Forward

The research across these 44 papers suggests a shared trajectory: we are moving from "hard" constraints to "soft" adaptations. While early work like Fastfood by Quoc V Le and Alex Smola accepted padding as a necessary evil for log-linear kernel approximations, newer methods are seeking ways to maintain efficiency on arbitrary dimensions.

Whether through "deformable" butterfly structures or more flexible hardware index shifters like those in Sparse Stream Semantic Registers, the goal is to decouple the mathematical brilliance of $O(N \log N)$ transforms from the rigid geometric constraints of the power of two.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 32 papers
  2. Version 1 · 2026-10-04 · 48 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_power_of_two_dimensionality_constraint_a3984dca,
  title = {power-of-two dimensionality constraint},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/power-of-two-dimensionality-constraint/rdr_a3984dca4a0c40b1b86713156e0cff0e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_structured_transforms_and_the_power_of_t_a3984dca_v1,
  title = {Structured Transforms and the Power of Two Constraint},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/structured-transforms-and-the-power-of-two-constraint/rdr_a3984dca4a0c40b1b86713156e0cff0e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}