Abstract
Divide and Conquer Networks (DiCoNet) introduce a recursive neural architecture designed to solve algorithmic tasks by learning to partition problems into smaller sub-tasks and merging their solutions. By embedding the "divide and conquer" principle as an inductive bias, the model achieves superior generalization to large input sizes and enables optimization for computational efficiency. This approach bridges the gap between traditional algorithmic logic and neural pattern recognition, demonstrating significant performance gains in combinatorial and geometric tasks.
Introduction
Many fundamental algorithmic problems—such as sorting, finding a convex hull, or clustering—exhibit scale invariance. This property implies that the strategy used to solve a small instance of a problem can be applied recursively to solve much larger ones. However, standard neural networks like RNNs or CNNs often treat these tasks as "black-box" regression problems. This leads to two primary failures: a significant generalization gap where models fail on inputs larger than those seen during training, and a complexity mismatch where fixed architectures cannot scale their computation time to the problem's inherent difficulty.
DiCoNet addresses these issues by hard-coding the recursive structure of "divide and conquer" directly into the network's architecture, allowing the model to focus on learning the logic of the algorithm rather than memorizing specific patterns.
Methods: The DiCoNet Architecture
The DiCoNet architecture operates on a dynamic binary tree structure determined by the input itself. It consists of two primary, scale-invariant modules:
- The Split Module ($S_\theta$): This module takes a set of inputs and learns to partition them into two disjoint subsets. Because the splitting decision is discrete, the authors utilize Policy Gradient (REINFORCE) for training. To ensure the model remains permutation-invariant, the module is implemented using architectures like Graph Neural Networks (GNNs).
- The Merge Module ($M_\phi$): Once the base cases (leaves of the tree) are reached, the Merge module combines two partial solutions into a single, larger solution as it traverses back up the tree. This is typically implemented using Pointer Networks or GNNs.
Complexity Regularization
A standout feature of this framework is the use of a regularization term that encourages "balanced" trees. In traditional algorithms, a balanced divide-and-conquer approach leads to $O(n \log n)$ complexity. By maximizing the variance of split probabilities, the network is incentivized to split sets into roughly equal halves, effectively optimizing for computational efficiency during the learning process.
Experimental Evaluation
The authors evaluated DiCoNet on several classic combinatorial and geometric tasks, including Planar Convex Hull, 0-1 Knapsack, and Euclidean TSP.
Key Results
The model demonstrated a remarkable ability to generalize to problem sizes far beyond its training data. In the Convex Hull task, DiCoNet significantly outperformed the standard Pointer Network baseline.
As shown in the results, for $n=100$ points, DiCoNet achieved 80.0% accuracy compared to the baseline's 41.5%. Crucially, while the baseline's performance plummeted to 13.5% for $n=200$, the DiCoNet + Split Reg variant maintained a robust 67.2% accuracy. Similar trends were observed in the Knapsack problem and clustering tasks, where DiCoNet found better local optima than standard iterative algorithms like Lloyd’s for large numbers of clusters.
Conclusion
DiCoNet demonstrates that integrating algorithmic inductive biases into neural architectures is essential for solving scale-invariant problems. By learning to recursively split and merge, the network achieves a level of generalization unattainable by standard black-box models. While challenges remain regarding the stability of discrete optimization via REINFORCE, this work opens new avenues for neural-algorithmic reasoning and meta-learning.
Summary updated