DNCs Require More Planning Steps
This addresses a problem for researchers and practitioners using neural networks for algorithmic reasoning, highlighting a key constraint that impacts model performance, though it is incremental in focusing on a specific aspect of existing DNC methods.
The paper investigates how the planning budget (number of steps allowed) affects the generalization of Differentiable Neural Computers (DNCs) in solving algorithmic problems, showing that insufficient planning steps can lead to poor generalization and memory utilization across tasks like Graph Shortest Path and Associative Recall.
Many recent works use machine learning models to solve various complex algorithmic problems. However, these models attempt to reach a solution without considering the problem's required computational complexity, which can be detrimental to their ability to solve it correctly. In this work we investigate the effect of computational time and memory on generalization of implicit algorithmic solvers. To do so, we focus on the Differentiable Neural Computer (DNC), a general problem solver that also lets us reason directly about its usage of time and memory. In this work, we argue that the number of planning steps the model is allowed to take, which we call "planning budget", is a constraint that can cause the model to generalize poorly and hurt its ability to fully utilize its external memory. We evaluate our method on Graph Shortest Path, Convex Hull, Graph MinCut and Associative Recall, and show how the planning budget can drastically change the behavior of the learned algorithm, in terms of learned time complexity, training time, stability and generalization to inputs larger than those seen during training.