Research map / Learning theory and algorithms / Combinatorial and search optimization
DNCs Require More Planning Steps
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that the number of planning steps a Differentiable Neural Computer is allowed (an adaptive planning budget p(n)) strongly affects its learned time complexity and generalization on graph and algorithmic tasks, and proposes memory temperature recalibration and stochastic planning budgets.
Problem
DNCs trained with the standard constant planning budget (p=10) generalize poorly to larger inputs, and the planning budget's role in learned time complexity, training cost, and stability is unexplored.
Approach
Treats the DNC planning phase as an input-size-dependent budget p(n) grounded in complexity theory; adds a temperature recalibration of the content-based strength beta for memory extension at inference, an input-dependent adaptive memory, and a stochastic planning budget during fine-tuning to induce steady-state behavior.
Key results
- Constant planning budget p=10 generalizes poorly on Shortest Path, while the adaptive budget p(n)=n outperforms it and is nearly matched only by the largest constant budget.
- On Shortest Path the adaptive budget costs about the same training time as the baseline while outperforming all constant budgets; the highest constant budget needs about 4x training time.
- Temperature recalibration (tau=0.85 for 2x memory, tau=0.65 for 5x memory) significantly mitigates the accuracy drop when extending DNC memory at inference.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase the planning budget from p=10 to p(n)=n | DNC · Shortest Path, larger inputs | accuracy | Helped |
| use adaptive p(n)=n instead of a constant budget | DNC · Shortest Path, larger inputs | training time | Helped |
| increase constant planning budget | DNC · Shortest Path, larger inputs | accuracy | Helped |
| increase planning budget beyond the baseline | DNC · Associative Recall, larger inputs | accuracy | No clear effect |
| use an extremely long planning budget | DNC · Associative Recall, larger inputs | accuracy | Hurt |
| use an adaptive planning budget rather than p=10 | DNC · Convex Hull, larger inputs | accuracy | Helped |
| use adaptive planning budget rather than baseline | DNC · MinCut, larger inputs | accuracy | Mixed |
| use p(n)=|V||E| | DNC · MinCut | training stability | Hurt |
| use quadratic planning budget p(n)=n^2 instead of smaller budgets | DNC · Graph Shortest Path, larger inputs | accuracy | Helped |
| add stochastic additional planning steps during fine-tuning (ablation) | DNC with adaptive p(n)=n · Associative Recall, larger inputs | accuracy | Helped |
| add deterministic additional planning steps during fine-tuning instead of stochastic steps (ablation) | DNC with adaptive p(n)=n · Associative Recall, larger inputs | accuracy | No clear effect |
| add stochastic planning steps during fine-tuning (ablation) | DNC with linear planning budget · Graph Shortest Path, larger inputs | accuracy | Helped |
Surprising findings
- Training with extremely long planning budgets (e.g., p=|V||E| on MinCut or the quadratic budget) was unstable and hard to train, and on MinCut good generalization was not achieved.
- Models trained with a linear budget on Shortest Path sometimes failed across seeds, with only successful seeds showing steady-state behavior.
Limitations
- Training is unstable and sensitive to random seed; some linear-budget models failed to generalize.
- Quadratic budget experiment was cut to 3% of the final-lesson training due to cost, so results are preliminary.
- MinCut generalization was not achieved; Convex Hull models did not reach steady state within training time.
Experimental setup
Datasets: synthetic graph shortest path data synthetic MinCut graphs synthetic associative recall sequences synthetic convex hull point sets
Benchmarks: Graph Shortest Path Convex Hull Graph MinCut Associative Recall
Metrics: accuracy on inputs larger than training accuracy vs planning steps A_n(p) training FLOPs
Baselines: DNC with constant planning budget p=10 constant planning budgets (p=25, 50, 100, 200) DNC with linear planning budget p(n)=n
Builds on: Differentiable Neural Computer Adaptive Computation Time
Closest papers by meaning
- Neuro-algorithmic Policies Enable Fast Combinatorial Generalization (ICML 2021 · similarity 0.86)
- System 1.x: Learning to Balance Fast and Slow Planning with Language Models (ICLR 2025 · similarity 0.85)
- Learning Domain-Independent Heuristics for Grounded and Lifted Planning (AAAI 2024 · similarity 0.84)
- Planning Anything with Rigor: General-Purpose Zero-Shot Planning with LLM-based Formalized Programming (ICLR 2025 · similarity 0.84)
- State Encodings for GNN-Based Lifted Planners (AAAI 2025 · similarity 0.84)
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.