Extraction Propagation

Stephen Pasteris, Chris Hicks, Vasilios Mavroudis

Abstract: Running backpropagation end to end on large neural networks is fraught with difficulties like vanishing gradients and degradation. In this paper we present an alternative architecture composed of many small neural networks that interact with one another. Instead of propagating gradients back through the architecture we propagate vector-valued messages computed via forward passes, which are then used to update the parameters. Currently the performance is conjectured as we are yet to implement the architecture. However, we do back it up with some theory. A previous version of this paper was entitled "Fusion encoder networks" and detailed a slightly different architecture.

Introduction

Training massive neural networks is often compared to steering a giant ship from the engine room using a series of complex, leaky pipes. In deep learning, these "pipes" are gradients. As networks grow deeper, the signal often vanishes or degrades before it can reach the early layers, making optimization increasingly difficult.

In a new theoretical framework from researchers at The Alan Turing Institute, Extraction Propagation (Xprop) is proposed as a radical alternative. Instead of pushing gradients backward through a monolithic architecture, Xprop decomposes the network into a colony of small, interacting neural networks that communicate via forward-pass "messages."

The Extraction Network Architecture

The fundamental unit of this system is the Extraction Network (exnet). An exnet is structured as a Directed Acyclic Graph (DAG), typically a binary tree. This hierarchical organization allows the model to process information at multiple scales, from local features at the leaves to global representations at the root.

Hierarchical structure of an Extraction Network (exnet) showing primary propagators ($ϕ$) and a root trainer ($ψ$).

Within this graph, three distinct types of "mini" neural networks operate at the nodes and arcs:

  1. Primary Propagators ($ϕ$): These move information "up" from the input (leaves) toward the root, compressing local data into a "primary extraction."
  2. Complementary Propagators ($ϕ^\dagger$): These move information "down" or "sideways," taking context from the rest of the network to provide a "complementary extraction" to specific nodes.
  3. Trainers ($ψ$): These are local decision-makers that combine primary and complementary extractions to make predictions.

Localized Learning via Message Passing

The core innovation of Xprop is replacing global backpropagation with a three-phase local update cycle. This cycle relies on vector-valued messages (extractions) rather than chain-rule gradients.

Interaction between primary ($ϕ$), complementary ($ϕ^\dagger$), and trainer ($ψ$) networks via upward ($μ$) and downward ($μ'$) messages.

The Xprop Algorithm operates as follows:

  • The Up Pass: Data is tokenized at the leaves and pushed toward the root via forward passes of the primary propagators ($ϕ$).
  • The Down Pass: Starting from the root, complementary extractions are pushed back down the tree using the complementary propagators ($ϕ^\dagger$).
  • The Update: Every mini-network is updated using standard backpropagation, but only on its own local scale. The target for these updates is derived from the global loss, but the input consists of the locally cached extractions.

By using forward passes to share context, the architecture aims to bypass the vanishing gradient problem entirely. The complementary extraction effectively communicates the "context" needed for an update without the numerical instability of deep differentiation.

Theoretical Foundations

While empirical results are currently conjectured, the authors provide mathematical proofs to support the framework's validity. The most significant claim is Vertex Optimality: if every small trainer at every node converges to its local optimum, they will all eventually agree on the same global prediction.

Furthermore, the authors demonstrate Consistency, showing that in the limit ($t \to \infty$), the local prediction at any internal vertex becomes identical to the prediction at the root. This suggests that information learned in one part of the exnet is successfully propagated throughout the system.

Discussion and Limitations

Xprop offers a modular and flexible alternative to the "Standard Model" of AI. Exnets can be designed for specific tasks, such as overlapping regions for images or attention-based structures for sequences. However, several challenges remain:

  • Empirical Validation: The lack of real-world benchmarks on datasets like ImageNet or LLM tasks is the primary limitation.
  • Memory Overhead: Caching extractions for the update phase increases space complexity.
  • Implementation Complexity: Coordinating thousands of small networks is an engineering hurdle compared to standard matrix multiplications.

The next phase of this research involves a practical implementation in frameworks like PyTorch or JAX to determine if this theoretical elegance translates into competitive performance.

Summary updated

Abstract

Running backpropagation end to end on large neural networks is fraught with difficulties like vanishing gradients and degradation. In this paper we present an alternative architecture composed of many small neural networks that interact with one another. Instead of propagating gradients back through the architecture we propagate vector-valued messages computed via forward passes, which are then used to update the parameters. Currently the performance is conjectured as we are yet to implement the architecture. However, we do back it up with some theory. A previous version of this paper was entitled "Fusion encoder networks" and detailed a slightly different architecture.
BibTeX
@misc{pasteris2024extraction,
  author = {Stephen Pasteris and Chris Hicks and Vasilios Mavroudis},
  title = {{Extraction Propagation}},
  year = {2024},
  eprint = {2402.15883},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.15883},
}
Figure