🤖 machine learning

Breaking chains with trees: Deep learning with $\mathcal{O}(\log N)$ parallel time complexity

This paper introduces Hierarchical Block-Local Learning (HBLL), a novel framework that decomposes deep neural networks into hierarchically linked blocks trained via local objectives to eliminate sequential backpropagation, thereby achieving $\mathcal{O}(\log N)$ parallel time complexity while maintaining competitive performance on vision and language tasks.

Original authors: Neeraj Mohan Sushma, Aditya Nagarsekar, Cabrel Teguemne Fokam, Robin Schiewer, Amit Kumar Pal, Anand Subramoney, David Kappel

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Neeraj Mohan Sushma, Aditya Nagarsekar, Cabrel Teguemne Fokam, Robin Schiewer, Amit Kumar Pal, Anand Subramoney, David Kappel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a massive team of 1,000 people how to solve a complex puzzle.

The Old Way (Backpropagation): The "Telephone Game" Bottleneck
Currently, most AI models are trained using a method called "Backpropagation." Think of this like a game of "Telephone" played in reverse.

The team solves the puzzle from start to finish (Forward pass).
They realize they made a mistake at the very end.
They must then whisper the correction back, one person at a time, all the way to the beginning (Backward pass).
The Problem: No one can change their strategy until the person before them has finished whispering the correction. If you have 1,000 people, the "whisper" takes a long time. This is called "locking." It means you can't speed things up by adding more computers because everyone is waiting for the person next to them. It's also like trying to fix a car engine while the car is still driving; you need to know exactly how the whole car works to fix one part.

The New Way (HBLL): The "Tree of Managers"
The paper introduces a new method called Hierarchical Block-Local Learning (HBLL). Instead of one long line of people waiting for a whisper, imagine organizing the team into a pyramid of managers.

The Structure: Instead of a single line of 1,000 workers, you have a tree. At the bottom, you have small teams. Above them, managers who oversee two teams. Above those, managers who oversee the managers, and so on, until you reach the CEO at the top.
The Training: When a mistake happens, the CEO doesn't need to whisper all the way to the bottom.
- The CEO tells the two top-level managers what went wrong.
- Those two managers tell their four sub-managers.
- Those tell their eight sub-managers.
- The Magic: Because the information splits down the tree, the message reaches the bottom very quickly. If you have 1,000 layers, the message only needs to travel about 10 steps (logarithmic time) instead of 1,000 steps.
Local Learning: Each small team (or "block") only needs to worry about its own immediate neighbors. They don't need to know the secrets of the entire company to do their job. They just need to make sure their local piece of the puzzle fits with the pieces above and below them.

Why This Matters (The "Breaking Chains" Analogy)
The paper claims this method breaks the "chains" of waiting.

Speed: Because the "whisper" travels down a tree rather than a line, the training time grows very slowly as the model gets bigger. The paper claims it can train deep networks in O(log N) time, meaning if you double the size of the network, you don't double the training time; you only add a tiny bit more.
No "Weight Transport": In the old way, the "backward whisper" needs to use the exact same wires as the "forward thinking." HBLL doesn't need this perfect symmetry. It's like being able to fix a road without needing to drive the exact same path you took to get there.

What They Tested
The authors tested this "Tree of Managers" approach on several difficult tasks:

Recognizing Digits (MNIST): They showed it works even on very deep networks where the old method (Backpropagation) failed to learn anything useful.
Recognizing Objects (CIFAR-10 & 100): They used it on "Vision Transformers" (AI that looks at pictures). It performed just as well as the standard method, even when the images were missing pieces or had noisy labels.
Writing Text (WikiText-103): They used it to teach an AI to predict the next word in a sentence. It did a good job, proving this method works for language too.
Time Sequences (RNNs): They adapted it for tasks that happen over time (like reading a sentence word-by-word). They found a way to train these models in parallel (like the tree) but still run them sequentially (like a normal sentence) when using them.

The Hidden Superpower: Flexible Inference
One cool side effect of this tree structure is that the AI implicitly learns many different "sub-networks."

Imagine the AI has a "Full Path" (using all 1,000 layers) for difficult puzzles.
But it also has "Short Paths" (using only the top few layers) for easy puzzles.
This means you can use the same trained model to do a quick, simple job or a deep, complex job without retraining it. It's like having a Swiss Army knife where you can pop out just the screwdriver or use the whole tool, depending on the task.

In Summary
The paper proposes a way to train AI that stops everyone from waiting in line. By organizing the learning process into a hierarchical tree where local teams fix their own small problems, the AI can learn much faster in parallel. It achieves results comparable to the standard method but removes the "locking" bottleneck, making it possible to train massive models more efficiently.

Technical Summary: Breaking Chains with Trees (HBLL)

Problem Statement

Modern deep neural networks (DNNs) rely on error backpropagation (BP), a paradigm that introduces two fundamental limitations:

The Locking Problem: Layer-wise updates are strictly interdependent. A full forward pass followed by a full backward pass is required before any parameters can be updated, preventing parallel training across layers and limiting hardware utilization.
The Weight Transport Problem: Exact gradient computation requires symmetric forward and backward pathways, which is biologically implausible and computationally expensive to implement in hardware.

These constraints result in a sequential time complexity of $O(N)$ for training $N$ layers, creating bottlenecks for scalability, memory efficiency, and communication overhead in large-scale models. While local learning methods have been proposed to relax global error propagation, they have historically struggled to scale to large network sizes or complex architectures like Transformers and Recurrent Neural Networks (RNNs).

Methodology: Hierarchical Block-Local Learning (HBLL)

The authors propose Hierarchical Block-Local Learning (HBLL), a framework that decomposes deep networks into hierarchically linked blocks trained via local objectives derived from variational principles, eliminating the need for full end-to-end backpropagation.

Theoretical Foundation

The approach reinterprets the chain of operations in a DNN ( $x \to z_1 \to \dots \to z_{N-1} \to y$ ) as a first-order Markov chain. To overcome the $O(N)$ sequential dependency, the authors introduce a tree-structured factorization of the posterior distribution over intermediate representations.

Divide-and-Conquer: By introducing intermediate variables at multiple hierarchy levels (e.g., $z_{N/2}$ , $z_{N/4}$ ), the chain is decomposed into smaller subproblems.
Theorem 1: The authors prove that the posterior distribution over intermediate representations admits an equivalent tree-structured decomposition. This reduces the computational path from $O(N)$ to $O(\log N)$ , enabling the first parallel algorithm for training deep networks with this complexity.

Variational Learning Framework

HBLL employs a variational formulation to define local learning objectives:

Objective: The global log-likelihood loss is replaced by an auxiliary loss involving the Kullback-Leibler (KL) divergence between a variational distribution $q$ (defined by the tree structure) and the true posterior.
Local Updates: The expectation in the variational loss is decomposed into local terms associated with each block. Each block learns to align its variational conditional distribution $q(z_n | \text{parents})$ with the forward model $p(z_n | z_{n-1})$ .
Implementation: Using Monte Carlo sampling and assumptions of exponential family distributions, gradients are computed using local statistics (means and variances) without global gradient propagation.
Algorithm: Training proceeds in parallel across blocks at the same hierarchy depth. The process iterates from the root (deepest level) down to the leaves, with each step taking $O(\log N)$ parallel time.

Extension to Recurrent Architectures (HBLL-RNN)

The framework is extended to sequential models by interpreting the hierarchy over time indices.

Causality: To ensure causal inference, the lowest-depth cell consumes only the previous hidden state and current input.
Consistency Correction: To address the exposure bias mismatch between tree-based training (where nodes see "clean" predecessors) and autoregressive rollout (where errors compound), the authors introduce a parallel consistency stage. This iteratively refines the recurrent cell's states using self-generated predecessors without requiring a full sequential rollout during training.

Key Contributions

HBLL Framework: A novel method for training deep neural networks by decomposing them into hierarchically organized blocks optimized with local objectives, removing the need for full end-to-end backpropagation.
$O(\log N)$ Parallel Complexity: The first algorithm capable of training deep networks with $O(\log N)$ parallel time complexity, significantly improving upon the $O(N)$ complexity of standard backpropagation.
Probabilistic Interpretation: A principled probabilistic framework derived from variational principles that enables distributed and parallel training while maintaining effective information propagation.
Flexible Inference: The method implicitly defines a family of subnetworks corresponding to different hierarchical paths, allowing for flexible inference with varying effective depths and computational budgets.
Recurrent Extension: The formulation of HBLL-RNN, a hierarchical local-learning approach for training sequential models that avoids backpropagation through time (BPTT).

Experimental Results

The authors evaluated HBLL on vision classification, autoregressive language modeling, and recurrent sequence modeling tasks, comparing it against standard backpropagation (BP) and Contrastive Forward-Forward (CFF+M) baselines.

MNIST (MLP): HBLL achieved competitive accuracy across depths 2, 3, and 4. Notably, at depth 4, while BP performance collapsed to near chance levels, HBLL maintained high accuracy (97.09% vs. 11.32% for BP), demonstrating its ability to train deeper hierarchical models effectively.
CIFAR-10 & CIFAR-100 (Vision Transformers):
- HBLL achieved competitive performance on CIFAR-10 (87.30% vs. 88.98% for BP) and CIFAR-100 (86.09% vs. 85.96% for BP).
- Robustness: HBLL showed superior robustness to missing data and label noise compared to BP.
- Subnetworks: Shorter paths through the hierarchy (fewer Transformer blocks) remained competitive with full-depth baselines, validating the flexible inference capability.
WikiText-103 (Language Modeling): HBLL achieved competitive perplexity (22.22 vs. 18.17 for BP) on the autoregressive language modeling task, demonstrating applicability to sequence modeling without full gradient propagation.
Sequential MNIST (RNNs): HBLL-RNN remained competitive with BPTT on sequential and permuted-sequential MNIST. The tree readout remained stable across depths, while the deployed sequential chain showed expected degradation at large depths. HBLL-RNN achieved up to a 3.6x speedup in training time at depth 8 compared to BPTT.

Significance and Claims

The paper claims that HBLL represents a significant step toward scalable, parallelizable deep learning. By breaking the sequential dependency of backpropagation, HBLL addresses the locking problem and reduces inter-layer dependencies, enabling efficient distributed training.

The authors emphasize that HBLL is the first algorithm to achieve $O(\log N)$ parallel time complexity for training deep networks. They argue that the method provides a theoretically grounded, probabilistic alternative to backpropagation that scales to modern architectures (Transformers, RNNs) and complex tasks (vision, language). While acknowledging a performance gap with fully backpropagated models at very large scales, the authors position HBLL as a viable approach that offers a trade-off between computational efficiency and model performance, while also providing inherent robustness and flexible inference capabilities.