# Smoothed Analysis of Inconsistent A*

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

## Key facts

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

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

- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search](https://mlsanity.com/paper/2205.09963/) (2022)
- [Embeddings and labeling schemes for A*](https://mlsanity.com/paper/2111.10041/) (2021)
- [Smoothed complexity of local Max-Cut and binary Max-CSP](https://mlsanity.com/paper/1911.10381/) (2019)
- [Smoothed Analysis of Online Metric Problems](https://mlsanity.com/paper/2507.17834/) (2025)

## Abstract (arXiv)

The A* search is a fundamental path-finding algorithm in artificial intelligence. While admissible and consistent heuristics guarantee efficient performance by expanding each state at most once, modern search applications frequently employ powerful but inconsistent heuristics derived from machine learning, randomized evaluations, etc. A long-standing theoretical barrier to using these inconsistent heuristics is the risk of catastrophic node re-expansion, which yields a worst-case exponential time complexity of Omega(2n). However, empirical observations contradict this pessimistic bound, demonstrating that inconsistent A* operates highly efficiently in practice. To bridge this significant gap between theory and practice, this paper presents the first smoothed analysis of the A* algorithm using inconsistent heuristics. We model typical real-world noise by applying slight random perturbations to the edge weights of worst-case search graphs. Our main result proves that the expected smoothed time complexity of inconsistent A* is bounded by a polynomial, specifically a total iteration number of O(n2 m kappa), where n is the number of nodes, m is the number of edges, and kappa controls the scale of random perturbations. Furthermore, we also show that this result naturally extends to the functionally equivalent problem of Dijkstra's algorithm on negative-weight graphs.