# The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems

arXiv: https://arxiv.org/abs/2209.03393 · HTML: https://mlsanity.com/paper/2209.03393/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 43 references that are in the map.
- First posted on arXiv 7 Sep 2022.

## Builds on (most cited first, 10 of 10)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Universal Approximation with Deep Narrow Networks](https://mlsanity.com/paper/1905.08539/) (2019)
- [ResNet with one-neuron hidden layers is a Universal Approximator](https://mlsanity.com/paper/1806.10909/) (2018)
- [Neural Network with Unbounded Activation Functions is Universal Approximator](https://mlsanity.com/paper/1505.03654/) (2015)
- [Single-Agent Policy Tree Search With Guarantees](https://mlsanity.com/paper/1811.10928/) (2018)
- [Policy-Guided Heuristic Search with Guarantees](https://mlsanity.com/paper/2103.11505/) (2021)
- [Solving the Rubik's Cube Optimally is NP-complete](https://mlsanity.com/paper/1706.06708/) (2017)
- [Learning to Sparsify Travelling Salesman Problem Instances](https://mlsanity.com/paper/2104.09345/) (2021)

## Abstract (arXiv)

The A* algorithm is commonly used to solve NP-hard combinatorial optimization problems. When provided with a completely informed heuristic function, A* solves many NP-hard minimum-cost path problems in time polynomial in the branching factor and the number of edges in a minimum-cost path. Thus, approximating their completely informed heuristic functions with high precision is NP-hard. We therefore examine recent publications that propose the use of neural networks for this purpose. We support our claim that these approaches do not scale to large instance sizes both theoretically and experimentally. Our first experimental results for three representative NP-hard minimum-cost path problems suggest that using neural networks to approximate completely informed heuristic functions with high precision might result in network sizes that scale exponentially in the instance sizes. The research community might thus benefit from investigating other ways of integrating heuristic search with machine learning.