Paper deep dive
Smoothed Analysis of Inconsistent A*
Zhiyang Chen, Hailong Yao
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 9/27/2026, 2:58:45 AM
Summary
This paper presents the first smoothed analysis of the A* search algorithm when using inconsistent heuristics. It addresses the theoretical gap where worst-case complexity is exponential ($\Omega(2^n)$) due to node re-expansion, but practical performance is efficient. By applying random perturbations to edge weights, the authors prove that the expected smoothed time complexity is polynomial, specifically $O(n^2 m \kappa)$, where $n$ is nodes, $m$ is edges, and $\kappa$ is the perturbation scale. The analysis also extends to Dijkstra's algorithm on negative-weight graphs.
Entities (8)
Relation Signals (7)
Smoothed Analysis → appliedto → A* search
confidence 95% · this paper presents the first smoothed analysis of the A* algorithm using inconsistent heuristics.
A* search → hassmoothedcomplexity → O(n^2 m \kappa)
confidence 95% · expected smoothed time complexity of inconsistent A* is bounded by a polynomial, specifically a total iteration number of O(n^2 m \kappa)
A* search → uses → Inconsistent Heuristics
confidence 95% · modern search applications frequently employ powerful but inconsistent heuristics
Inconsistent Heuristics → causes → node re-expansion
confidence 90% · risk of catastrophic node re-expansion, which yields a worst-case exponential time complexity
Martelli → demonstrated → exponential complexity of A*
confidence 90% · Martelli [3] demonstrated that this reopening process can cascade catastrophically, yielding a worst-case time complexity of \Omega(2^n)
Spielman and Teng → introduced → Smoothed Analysis
confidence 90% · smoothed analysis, introduced by Spielman and Teng [4]
A* search → isfunctionallyequivalentto → Dijkstra's algorithm
confidence 90% · functionally equivalent problem of Dijkstra’s algorithm on negative-weight graphs
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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(2^n)$. 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(n^2 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.
Tags
Links
- Source: https://arxiv.org/abs/2609.23680v1
- Canonical: https://arxiv.org/abs/2609.23680v1
Trouble viewing inline? Open PDF directly →
Full Text
45,332 characters extracted from source content.
Expand or collapse full text
Smoothed Analysis of Inconsistent A* Zhiyang Chen Hailong Yao Abstract 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 Ω(2n) (2^n). 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(n2mκ)O(n^2mκ), where n is the number of nodes, m is the number of edges, and κ 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. 1 Introduction The A* search algorithm stands as one of the most fundamental and widely utilized path-finding algorithms in artificial intelligence. Its efficiency is largely driven by its heuristic function, h(⋅)h(·), which estimates the cost from an arbitrary node to the goal node. It is a well-established property that if h(⋅)h(·) is admissible (i.e., it never overestimates the true cost), A* is guaranteed to return an optimal path. Furthermore, if h(⋅)h(·) is consistent, (i.e., the difference between the heuristic values of two adjacent nodes does not exceed the weight of the edge connecting both nodes), A* is guaranteed to expand each state at most once. Thus, using an admissible and consistent heuristic, A* finds the shortest path in at most n−1n-1 iterations for n-node graphs. However, many powerful heuristics derived in practice are inconsistent (sometimes even not admissible). These include heuristics generated by machine learning, randomized evaluations, and compressed pattern databases [1, 2]. The theoretical barrier to deploying inconsistent heuristics lies in the risk of node re-expansion. When a shorter path to a previously expanded node is discovered, A* must reopen that node. In a seminal result, Martelli [3] demonstrated that this reopening process can cascade catastrophically, yielding a worst-case time complexity of Ω(2n) (2^n). Consequently, the prevailing theoretical consensus has historically cautioned against the use of inconsistent heuristics. In contrast, Felner et al. [1] has argued that, in practice, inconsistent A* is generally not as inefficient as the worst-case complexity illustrates. Moreover, inconsistent heuristics are easy to create, adding a diversity of heuristic values, which may lead to a reduction of re-expansions. Felner et al. [1] suggests that “the use of inconsistent heuristics will become an accepted and powerful tool in the development of high-performance search algorithms.” Therefore, a large gap exists between theory and practice. It is natural to ask the following question: Why do A* algorithms with inconsistent heuristics avoid exponential blow-up in practice? Standard algorithmic analysis frameworks struggle to answer this question. Worst-case analysis is overly pessimistic, considering highly artificial graph structures that are fragile and unlikely to occur in real-world domains. Conversely, average-case analysis typically requires rigid, often unrealistic assumptions about the probability distribution of the input graphs and heuristic values, failing to capture the structure of actual problem instances. To bridge this gap, we turn to the framework of smoothed analysis, introduced by Spielman and Teng [4], to explain the practical efficiency of the Simplex algorithm. Smoothed analysis elegantly interpolates between worst-case and average-case analysis. It measures the performance of an algorithm under slight random perturbations of worst-case inputs. If an algorithm exhibits polynomial smoothed complexity, it implies that the pathological instances inducing worst-case exponential behavior are mathematically fragile, which rarely exist due to the random noise in practice. In this paper, we provide the first rigorous smoothed analysis of the A* algorithm using inconsistent heuristics. We assume the edge costs of the search graph are independently perturbed by small random noises. In expectation, the running time of the A* algorithm for smoothed instances will only be a polynomial in the graph size n and the scale of randomness. 1.1 Our contributions Main results. The main contribution of this work is the following theorem. Theorem 1 (Informally, Theorem 2). The smoothed time complexity of inconsistent A* is bounded from above by poly(n,κ)poly(n,κ), where n is the number of nodes in the search graph, and κ is the scale of random perturbations. We also empirically verify the theoretical analysis by numerical experiments. We find that, the worst-case exponential-time instances for A* constructed by Martelli [3] are highly sensitive in practice. The total number of iterations greatly reduces as we increase the perturbation on the instances. Moreover, it is widely known that there is an equivalence between the A* algorithm and the Dijkstra algorithm on graphs with negative weights. Our analysis also works for Dijkstra. We show that, for a shortest path instance with no negative cycles, if the edge weights are randomly perturbed, Dijkstra finds the shortest path in polynomial time. Our techniques. The main difficulty in proving the smoothed complexity is to find enough independent randomness among the intermediate states of inconsistent A*. Previous work on smoothed analysis of heuristic local search algorithms (e.g., Englert et al. [5]) generally uses union bounds over all possible solution improvements to induce a polynomial smoothed complexity bound. However, this does not work for inconsistent A* since there could be an exponential number of path updates. The main proof technique in our analysis is to establish a surprising connection between inconsistent A* and Pareto optimization (a.k.a. multi-objective optimization). Then, we could apply the “winner gap” technique by Beier and Vöcking [6] for the smoothed analysis of Pareto frontiers. We make various modifications to this technique to adapt to our problem. 1.2 Related work Theoretical analysis of A*. Felner et al. [1] has shown that the total number of iterations of inconsistent A* is bounded from above by O(n2W)O(n^2W), where W is the maximum of edge weights. However, their analysis only works for integer weights. Why inconsistent A* with real weights is efficient remains a significant theoretical question. Eden et al. [7] studies the average-case running time of A* with heuristics generated by embedding and labeling schemes. However, their analysis focuses on consistent heuristics. Sakaue and Oki [2] studies the sample complexity of learning an arbitrary heuristic for an A* instance distribution. In their analysis, since the learned heuristic could be inconsistent and inadmissible, they bound the sample complexity by counting all possible paths from the start node to other nodes, which leads to exponential bounds. This indicates that bounding the time complexity of inconsistent A* could be of interest for learning-theoretic problems. Smoothed analysis of algorithms. Originally proposed by Spielman and Teng [4] to study the time complexity of the Simplex method for linear programming, smoothed analysis is widely used to explain the practical efficiencies of a variety of algorithms, including local search [5, 8], algorithm configuration [9, 10], online algorithms [11], and machine learning [12]. We refer readers to Roughgarden [13] for a comprehensive introduction. 2 Preliminaries Problem formulation. We use G=(V,E)G=(V,E) to denote a weighted graph with |V|=n|V|=n nodes and |E|=m|E|=m edges. Each edge (u,v)∈E(u,v)∈ E is associated with a real weight w(u,v)∈[0,1]w_(u,v)∈[0,1]. Without loss of generality, we assume that edge weights are bounded, since we can always normalize the weights by the maximum. In our analysis, we consider a directed graph, but our approach also works for undirected graphs. For simplicity of analysis, we assume the graph is simple, i.e., there is at most one edge from node u to v for any pair (u,v)(u,v), and no self-loops are allowed. Let s∈Vs∈ V denote the start node and t∈Vt∈ V denote the goal node. Moreover, we have a heuristic function h:V→[0,+∞)h:V→[0,+∞) that estimates the shortest path from each node to the goal. The target of the A* algorithm is to find a path s→v1→v2→…→vK→ts→ v_1→ v_2→…→ v_K→ t that minimizes the total weight w(s,v1)+∑i=1K−1w(vi,vi+1)+w(vK,t)w_(s,v_1)+ _i=1^K-1w_(v_i,v_i+1)+w_(v_K,t). Inconsistent A*. The A* algorithm is illustrated in Algorithm 1. In each iteration, the algorithm finds an active node v in OPEN with the minimum f(v)=g(v)+h(v)f(v)=g(v)+h(v), and updates the g value of adjacent nodes if a shorter path is discovered using v. Then we add the updated nodes to OPEN for further updates. Note that since we consider inconsistent heuristics, Algorithm 1 incorporates the reopening process. If the heuristic is not admissible, Algorithm 1 cannot find the shortest path even with reopening. In this case, we could remove lines 4–6 of Algorithm 1, and run the algorithm until convergence. This guarantees optimality, but leads to a longer running time. In fact, our analysis does not rely on the admissibility condition. This means that it also works for this special case, although it is rarely used in practice. Smoothed analysis model. In smoothed analysis, we assume the problem instance is randomly perturbed by a small noise. In our model, the weight of each edge w(u,v)w_(u,v) is not a fixed real value, but a probability distribution supported on [0,1][0,1]. Given a parameter κ, the probability density function of each edge weight w(u,v)w_(u,v) is a bounded function p(u,v):[0,1]→[0,κ]p_(u,v):[0,1]→[0,κ]. The input of the algorithm is obtained by independently sampling each edge weight wew_e based on the density function pep_e. We say that such instances are κ-smoothed. Let T(I)T(I) denote the running time of the algorithm on instance I, let I denote an input, and let I~ I denote a κ-smoothed problem instance. The smoothed time complexity of an algorithm is defined by maxI∼I~I~[T(I)], _ I E_I I[T(I)], where I~ I is taken over all κ-smoothed instances with n nodes. Note that our model only perturbs the edge weights, but the heuristic values could be arbitrary. For example, if κ=1κ=1, each edge weight is a uniform distribution over [0,1][0,1], and our model reduces to average-case analysis. If κ→+∞κ→+∞, our model converges to worst-case analysis. In our model, the heuristic function h:V→[0,+∞)h:V→[0,+∞) is a fixed vector. It may depend on the graph structure and edge weights, but it is independent of the random perturbations. Therefore, given a κ-smoothed instance, we can synthesize the heuristic based on the instance (e.g., the distribution of edge weights), but it should be generated before sampling the weights. On tie-breaking. Note that in the smoothed analysis setting, for any two paths that differ by at least one node, with probability 1, the total lengths (and the f-values as well) of these two paths are different. Thus, in line 3 of Algorithm 1, we break ties arbitrarily without affecting our analysis. Algorithm 1 Inconsistent A* with reopening. 1: A directed weighted graph G=(V,E)G=(V,E) with |V|=n|V|=n nodes and |E|=m|E|=m edges, where each edge e=(u,v)∈Ee=(u,v)∈ E is associated with a real weight we∈[0,1]w_e∈[0,1]; A heuristic function h:V→[0,+∞)h:V→[0,+∞); The start node s∈Vs∈ V and the goal node t∈Vt∈ V. 2: A simple path v1,…,vkv_1,…,v_k where v1=sv_1=s and vk=tv_k=t. 3: Let OPEN=s,CLOSED=∅OPEN=\s\,CLOSED= and g(s)=0g(s)=0; 4: while OPEN≠∅OPEN≠ do 5: Let v←argminv∈OPENg(v)+h(v)v← _v g(v)+h(v); 6: if v=tv=t then 7: return the s-t path by tracing t←p(t)←p(p(t))←…←st← p(t)← p(p(t))←…← s; 8: end if 9: for each node v′v s.t. (v,v′)∈E(v,v )∈ E do 10: Let g′←g(v)+w(v,v′)g ← g(v)+w_(v,v ); 11: if v′∉OPEN∪CLOSEDv then 12: Let g(v′)←g′,p(v′)←vg(v )← g ,p(v )← v, and OPEN←OPEN∪v′OPEN ∪\v \; 13: else if v′∈OPENv and g′<g(v′)g <g(v ) then 14: Let g(v′)←g′,p(v′)←vg(v )← g ,p(v )← v; 15: else if v′∈CLOSEDv and g′<g(v′)g <g(v ) then 16: Let g(v′)←g′,p(v′)←vg(v )← g ,p(v )← v; 17: Move v′v from CLOSED to OPEN; 18: end if 19: end for 20: Move v from OPEN to CLOSED; 21: end while 3 Smoothed Analysis Our main result is the following theorem. Theorem 2. The expected number of iterations of the A* algorithm for a κ-smoothed instance is bounded from above by O(n2mκ)O(n^2mκ). We first introduce some notation for the proof of Theorem 2. Notation. In the A* algorithm, g(u)g(u) is used to denote the path length from the start node to any node u. This depends on the current state of the algorithm. In our analysis, to avoid this dependency, with a little abuse of notation, for any path P, we use g(P)g(P) to denote the length of P. Moreover, all paths in our analysis are simple paths unless otherwise stated. 3.1 Direct and indirect updates Before diving into the proof of Theorem 2, we define direct and indirect updates in Algorithm 1. For each node v∈Vv∈ V, the A* algorithm maintains two state variables: g(v)g(v), the cost of the currently known shortest path from s to v; and p(v)p(v), a parent pointer indicating the immediate ancestor of v in T. By tracing the parent pointers, the A* algorithm implicitly maintains a path tree, denoted by T, that originates at s. The path from s to each node on T represents the current path found by the A* algorithm. We call such paths intermediate paths. In lines 8–16 of Algorithm 1, we select a pair of nodes (v,v′)(v,v ), and update g(v′)←min(g(v′),g(v)+w(v,v′))g(v )← (g(v ),g(v)+w_(v,v )). Depending on whether the topology of the path tree T is altered, we formalize these updates into two distinct categories: Direct and indirect updates. See Figure 1 for an example. Direct updates. A direct update occurs when the algorithm discovers a structurally novel path from s to v that is strictly superior to its previous intermediate path. This kind of update alters the topological structure of the path tree T. Suppose the algorithm is expanding a node v∈Vv∈ V and evaluating its outgoing edge (v,v′)∈E(v,v )∈ E. A direct update is triggered if and only if the path traversing through v offers a lower cost than the currently recorded cost g(v′)g(v ). Therefore, before the update, we have p(v′)≠vp(v )≠ v. After the update, the edge (p(v′),v′)(p(v ),v ) is pruned from T, and the new edge (v,v′)(v,v ) is added into T. Indirect updates. An indirect update occurs when a node v experiences a reduction in its path cost g(v)g(v) strictly as a byproduct of a cost reduction in its current ancestor, without any alteration to the path tree’s topology. Thus, the intermediate path of v remains unchanged. Let v′∈Vv ∈ V be a node that has already been updated, and let v=p(v′)v=p(v ) be its current parent in T. If the path cost g(v)g(v) undergoes an update (i.e., g(v)g(v) is decreased) due to a direct or indirect update upstream, the cost of the path from s to v′v is inherently reduced, despite the local edge (v,v′)(v,v ) in T remaining unchanged. Figure 1: (a) Direct updates; (b) Indirect updates. Blue paths denote original paths, and red paths denote updated paths. Lemma 3. For any A* instance, let U_dir and U_ind denote the number of direct and indirect updates, respectively. We have U≤(n−1)⋅U.U_ind≤(n-1)· U_dir. Proof. We define an update event as the event that the recorded path cost g(v)g(v) of any node v∈Vv∈ V is strictly decreased. The set of all update events ℰE during the entire execution can be partitioned into two disjoint subsets: the set of direct updates ℰdE_d and the set of indirect updates ℰiE_i, such that U=|ℰd|U_dir=|E_d| and U=|ℰi|U_ind=|E_i|. By the definition of an indirect update, an event e∈ℰie _i occurring at a node v strictly preserves its parent pointer p(v)p(v). Therefore, this reduction in g(v)g(v) must be a mathematical consequence of a strictly decreasing update event e′e at its parent node u=p(v)u=p(v). We denote this causal trigger relationship as e′→e → e. Since the search structure T maintained by A* is a directed tree rooted at the start node s (which is never updated), and all update events strictly decrease g-values, any causal chain of updates e←e′←e′←…e← e ← e ←… must be finite and cycle-free. Consequently, tracing any indirect update event e∈ℰie _i backward along this causal chain must ultimately terminate at an update event that is not an indirect update. This terminating root event must be a direct update ed∈ℰde_d _d occurring at some ancestor node r. This establishes a surjective mapping f:ℰi→ℰdf:E_i _d, meaning every indirect update is uniquely rooted in exactly one direct update. To prove the lemma, it suffices to bound the number of indirect updates causally generated by a single direct update. Let ed∈ℰde_d _d be a fixed direct update event occurring at node r. We define its causal progeny S(ed)=e∈ℰi|f(e)=edS(e_d)=\e _i\,|\,f(e)=e_d\. When ede_d occurs, it establishes a newly reduced cost g(r)g(r) and a new parent p(r)p(r). This specific cost reduction propagates downstream along the directed edges of T. Recall that the causal chain is cycle-free. There is no node that will be indirectly updated twice by a fixed direct update. Since the maximum number of nodes in any subtree of T is strictly bounded by n−1n-1, the maximum number of indirect updates causally triggered by ede_d is at most n−1n-1. Thus, we have |S(ed)|≤n−1,∀ed∈ℰd,|S(e_d)|≤ n-1,\,∀\,e_d _d, which proves this lemma. ∎ Therefore, in the following analysis, it suffices to bound U_dir to prove the desired result, since each iteration is triggered by at least one previous update on some node. 3.2 Pareto conditions of node expansion The inconsistent A* algorithm may iterate more than n times, since some nodes may be expanded more than once. The key idea of analyzing the time complexity of inconsistent A* is to characterize the conditions of node re-expansion. Suppose node v′v is re-expanded. Originally, the A* algorithm finds a path from s to v′v . We denote it by PoldP_old. Later, an edge relaxation on some edge (v,v′)∈E(v,v )∈ E finds a new path s→…→v→v′s→…→ v→ v , namely PnewP_new, such that its total weight is smaller than PoldP_old. If the heuristic function h(⋅)h(·) is admissible and consistent, since g(Pold)>g(Pnew)g(P_old)>g(P_new), the A* algorithm will find PnewP_new instead of PoldP_old, so that re-expansion does not happen. However, if h(⋅)h(·) is inconsistent, we can manipulate h(⋅)h(·) so that PnewP_new has not been discovered yet when PoldP_old is found. Concretely, let PnewP_new be a path s→…→u→…→v′→vs→…→ u→…→ v → v, where h(u)h(u) is extremely large such that u is in the OPEN list, waiting to be expanded, while PoldP_old has been discovered. Formally, we define the bottleneck comparison between paths. Definition 4 (Bottleneck comparison). Fix a node v∈Vv∈ V. Let P and P′P be two different paths from s to v, where P=s→u1→…→uk→uk+1→…→uK→vP=s→ u_1→…→ u_k→ u_k+1→…→ u_K→ v, and P′=s→u1→…→uk→uk+1′→…→uK′→vP =s→ u_1→…→ u_k→ u _k+1→…→ u _K → v, with the first k edges being the same (k could be 0), i.e., the longest common prefix of P and P′P . We say P≺P′P P if maxi∈k+1,…,Kg(P(ui))+h(ui)<maxi∈k+1,…,K′g(P′(ui′))+h(ui′), _i∈\k+1,…,K\g(P(u_i))+h(u_i)< _i∈\k+1,…,K \g(P (u _i))+h(u _i), where P(ui)P(u_i) is the prefix of P from s to uiu_i and P′(ui′)P (u _i) is the prefix of P′P from s to ui′u _i. Note that since P differs P′P by at least one edge, in the smoothed analysis setting, with probability 1, maxi∈k+1,…,Kg(P(ui))+h(ui)≠maxi∈k+1,…,K′g(P′(ui′))+h(ui′). _i∈\k+1,…,K\g(P(u_i))+h(u_i)≠ _i∈\k+1,…,K \g(P (u _i))+h(u _i). Therefore, in our definition, we only consider the strict comparison. Moreover, ≺ is a total order. Lemma 5. For any paths P1,P2,P3P_1,P_2,P_3, we have (P1≺P2)∧(P2≺P3)⟹P1≺P3.(P_1 P_2) (P_2 P_3) P_1 P_3. Proof. Let K1,K2,K3K_1,K_2,K_3 denote the number of nodes in P1,P2,P3P_1,P_2,P_3 except the first and the last nodes, respectively. Let k1k_1 denote the length of the longest common prefix (LCP) of P1P_1 and P2P_2, k2k_2 denote the LCP of P2P_2 and P3P_3, and k3k_3 denote the LCP of P1P_1 and P3P_3. For simplicity, we use fj(u)=g(Pj(u))+h(u)f_j(u)=g(P_j(u))+h(u) to denote the f-value on path PjP_j. We use uiu_i to denote the i-th node on the paths P1,P2P_1,P_2 or P3P_3 (we omit the path index for simplicity). Altogether, there are three cases: Case 1: k1<k2k_1<k_2. Since P2P_2 and P3P_3 share more common prefix edges than P1P_1 and P2P_2, it must be k3=k1k_3=k_1. By P1≺P2P_1 P_2, we have maxi∈k1+1,…,K1f1(ui)<maxi∈k1+1,…,K2f2(ui). _i∈\k_1+1,…,K_1\f_1(u_i)< _i∈\k_1+1,…,K_2\f_2(u_i). By P2≺P3P_2 P_3, we have maxi∈k1+1,…,K2f2(ui) _i∈\k_1+1,…,K_2\f_2(u_i) =maxmaxi∈k1+1,…,k2f2(ui),maxi∈k2+1,…,K2f2(ui) = \ _i∈\k_1+1,…,k_2\f_2(u_i), _i∈\k_2+1,…,K_2\f_2(u_i) \ ≤maxmaxi∈k1+1,…,k2f3(ui),maxi∈k2+1,…,K3f3(ui) ≤ \ _i∈\k_1+1,…,k_2\f_3(u_i), _i∈\k_2+1,…,K_3\f_3(u_i) \ =maxi∈k3+1,…,K3f3(ui), = _i∈\k_3+1,…,K_3\f_3(u_i), which implies P1≺P3P_1 P_3. Case 2: k1>k2k_1>k_2. In this case, it must be k3=k2k_3=k_2. Using a similar argument to Case 1, we have P1≺P3P_1 P_3. Case 3: k1=k2k_1=k_2. In this case, P1P_1 and P3P_3 share at least the first k1k_1 edges. We have k3≥k1=k2k_3≥ k_1=k_2. By P1≺P2P_1 P_2 and P2≺P3P_2 P_3, we have maxi∈k1+1,…,K1f1(ui)<maxi∈k1+1,…,K2f2(ui)<maxi∈k1+1,…,K3f3(ui). _i∈\k_1+1,…,K_1\f_1(u_i)< _i∈\k_1+1,…,K_2\f_2(u_i)< _i∈\k_1+1,…,K_3\f_3(u_i). Since the inequality is strict, eliminating the common nodes of P1P_1 and P3P_3 does not affect the inequality, i.e., maxi∈k3+1,…,K1f1(ui)<maxi∈k3+1,…,K3f3(ui), _i∈\k_3+1,…,K_1\f_1(u_i)< _i∈\k_3+1,…,K_3\f_3(u_i), which implies P1≺P3P_1 P_3. ∎ Intuitively, Definition 4 compares two paths using the largest f-value among the path nodes (excluding the common part). These nodes are the bottlenecks of the paths. The A* algorithm finds these paths only if the minimum f-value in the OPEN list exceeds the bottleneck value. Lemma 6. In a smoothed A* instance, suppose P is an intermediate path for some node v. With probability 1, for any other path P′P from s to v, we have g(P)<g(P′)g(P)<g(P ) or P≺P′P P . Proof. Proof by contradiction. Suppose there is a path P′P that satisfies both g(P′)<g(P)g(P )<g(P) and P′≺P P. Following the notation in Definition 4, let l=argmaxi∈k+1,…,Kg(P(ui))+h(ui)l= _i∈\k+1,…,K\g(P(u_i))+h(u_i). Since P′≺P P, for any i∈k+1,…,K′i∈\k+1,…,K \, we have g(P′(ui′))+h(ui′)<g(P(ul))+h(ul)g(P (u_i ))+h(u_i )<g(P(u_l))+h(u_l). Therefore, before ulu_l is expanded, the path P′P will be discovered. Since g(P′)<g(P)g(P )<g(P), P will not become an intermediate path. This leads to a contradiction. ∎ Lemma 6 indicates that there is a Pareto-optimality condition for intermediate paths. For any node v, let P1,P2,…,PNP_1,P_2,…,P_N denote the sequence of intermediate paths of v, where g(P1)>g(P2)>⋯>g(PN)g(P_1)>g(P_2)>…>g(P_N). We have P1≺P2≺⋯≺PNP_1 P_2 … P_N. All paths are Pareto-minimum with respect to g(⋅)g(·) and the bottleneck comparison. See Figure 2 for an illustration. Figure 2: Pareto-optimal conditions for node expansions. 3.3 Smoothed analysis of direct updates The main idea of proving Theorem 2 is to bound the number of intermediate paths for each node. Summing for all nodes yields the upper bound of the total iterations of Algorithm 1. Fix a node v. As previously discussed, we can bound the number of intermediate paths of v by bounding the size of the Pareto set. Let P1,P2,…,PNP_1,P_2,…,P_N denote the sequence of intermediate paths of v, where g(P1)>g(P2)>⋯>g(PN)g(P_1)>g(P_2)>…>g(P_N). Each pair of adjacent paths (Pi,Pi+1)(P_i,P_i+1) denotes an update. If the last edges of PiP_i and Pi+1P_i+1 are identical, this is an indirect update. Otherwise, this is a direct update. Due to Lemma 3, we only consider the number of direct updates. We use the “loser gap” technique to prove a smoothed upper bound, but with a few modifications to adapt our problem. Recall that the edge weights are in [0,1][0,1]. For any path P, we have g(P)∈[0,n]g(P)∈[0,n]. We partition [0,n][0,n] into disjoint intervals [0,ε),[ε,2ε),…,[n−ε,n][0, ),[ ,2 ),…,[n- ,n], each with length ε , where ε>0 >0 is a parameter to be determined later. Consider all simple paths from s to v. Each path P has a total weight g(P)g(P), which lies in some interval kε<g(P)<(k+1)εk <g(P)<(k+1) . (Recall that with probability 1, the total weight of g(P)g(P) will not be in a set of measure zero. Thus, it suffices to consider open intervals.) We will choose ε so small that there is at most one path weight g(P)g(P) that appears in each interval. See Figure 2 for an example. We define a few random variables. • Let Pv,e,kP_v,e,k for node v∈Vv∈ V, edge e=(u,v)∈Ee=(u,v)∈ E and integer k be a simple path from s to v that satisfies the following: (1) Pv,e,kP_v,e,k does not include edge e; (2) The length g(Pv,e,k)<kεg(P_v,e,k)<k ; (3) Among all paths satisfying (1) and (2), Pv,e,kP_v,e,k is the path with the minimum bottleneck. • Let Qv,e,kQ_v,e,k be a path from s to v that satisfies the following: (1) Qv,e,kQ_v,e,k includes edge e; (2) Qv,e,k≺Pv,e,kQ_v,e,k P_v,e,k; (3) Among all paths satisfying (1) and (2), Qv,e,kQ_v,e,k is the path with the minimum length g(⋅)g(·). • Let Gv,e,k=g(Qv,e,k)G_v,e,k=g(Q_v,e,k) be the length of Qv,e,kQ_v,e,k. Lemma 7. For an A* instance, suppose for each node v and each interval Ik=(kε,(k+1)ε)I_k=(k ,(k+1) ), (1) there is at most one path from s to v, such that the path length lies in IkI_k; (2) there is no path length that lies on the terminals of any interval IkI_k. Let U_dir denote the number of direct updates. We have U≤∑v≠s∑k=0⌊n/ε⌋−1∑(u,v)∈E[Gv,e,k∈(kε,(k+1)ε)].U_dir≤ _v≠ s _k=0 n/ -1 _(u,v)∈ EI[G_v,e,k∈(k ,(k+1) )]. Proof. The proof idea is to show that, for each direct update, there exists a unique term Gv,e,kG_v,e,k such that Gv,e,k∈(kε,(k+1)ε)G_v,e,k∈(k ,(k+1) ) holds. Fix a Pareto-optimal intermediate path P from s to v where the last edge is e=(v′→v)e=(v → v). Suppose g(P)∈(kε,(k+1)ε)g(P)∈(k ,(k+1) ). Since there is at most one path in each interval, the length of any path from s to v that is smaller than g(P)g(P) does not exceed kεk . If there is a direct update on P, it must be another Pareto-optimal intermediate path P′P such that (1) P′P does not include edge e; (2) g(P′)<kεg(P )<k ; (3) the bottleneck of P′P is as small as possible. By definition, we find that P′P is exactly Pv,e,kP_v,e,k. Moreover, since P and P′P are two adjacent Pareto-minimum paths, P must satisfies the following: (1) P≺P′P P ; (2) P has the minimum length among all paths that contain edge e and have a smaller bottleneck than P′P . By definition, we find that P is exactly Qv,e,kQ_v,e,k. Thus, we have Gv,e,k∈(kε,(k+1)ε)G_v,e,k∈(k ,(k+1) ). Since each interval contains at most one intermediate path, we charge each Pareto-minimum path to a unique Gv,e,kG_v,e,k, which leads to the desired bound. ∎ Lemma 8. For a κ-smoothed A* instance, for any v,e,kv,e,k, we have ℙ[Gv,e,k∈(kε,(k+1)ε)]≤εκ.P[G_v,e,k∈(k ,(k+1) )]≤ κ. Proof. We use the principle of deferred decisions to prove this lemma. Fix the randomness of all edges except wew_e, the weight of e. Now, since Pv,e,kP_v,e,k does not contain edge e, Pv,e,kP_v,e,k is deterministic. Consider the path length of Qv,e,kQ_v,e,k. Qv,e,kQ_v,e,k satisfies three conditions: (1) Qv,e,kQ_v,e,k contains edge e; (2) Qv,e,k≺Pv,e,kQ_v,e,k P_v,e,k; (3) the path length is minimal. Since the definition of bottleneck comparison does not depend on the last edge of the path, all candidate paths of Qv,e,kQ_v,e,k that satisfy (1) and (2) are deterministic. Moreover, the lengths of all these paths can be represented as the form of a deterministic term+wea deterministic term+w_e. Therefore, the minimum path Qv,e,kQ_v,e,k is also deterministic, independent of the value of wew_e. Therefore, conditioning on all the randomness of wew_e, the probability of Gv,e,k∈(kε,(k+1)ε)G_v,e,k∈(k ,(k+1) ) is equivalent to the probability that wew_e lies in an interval of length ε . Since wew_e is κ-bounded, we have ℙ[Gv,e,k∈(kε,(k+1)ε)]≤εκP[G_v,e,k∈(k ,(k+1) )]≤ κ. ∎ 3.4 Putting things together Now, we are ready to prove Theorem 2. Proof of Theorem 2. Let E denote the event that there is an interval Ik=(kε,(k+1)ε)I_k=(k ,(k+1) ), such that there are two or more paths from s to some node v, where the path lengths both lie in IkI_k. Suppose there are M paths from s to any other node v in total. We have M≤∑i=1n−1(n−1i)i!≤(2n)n+1. M≤ _i=1^n-1 n-1ii!≤(2n)^n+1. By a union bound over all intervals and all pairs of paths, we have ℙ[E]≤(M2)⋅nε⋅(εκ)2=(2n)2n+3εκ2P[E]≤ M2· n ·( κ)^2=(2n)^2n+3 κ^2, since for any two different paths, there is at least one non-common edge, which leads to the fact that both paths lie in an interval of length ε with probability at most (κε)2(κ )^2. Note that ε can be arbitrarily small, the probability of E can be neglected (e.g., by setting ε<1κ2(2n)4n+4 < 1κ^2(2n)^4n+4). Let U_dir and U_ind denote the number of direct and indirect updates, respectively. The total number of iterations of A* is equivalent to the total number of updates. Therefore, the total iteration number U satisfies [U]=[U+U]≤n⋅[U]E[U]=E[U_dir+U_ind]≤ n·E[U_dir] by Lemma 3. Now, we apply the smoothed analysis of the Pareto-minimum paths. If E does not happen, we can simply apply Lemma 7. However, if E happens, the number of updates can be at most M. Concretely, [U] [U] ≤n⋅[U] ≤ n·E[U_dir] ≤n⋅(∑v≠s∑k=0⌊n/ε⌋−1∑(u,v)∈E[Gv,e,k∈(kε,(k+1)ε)]+M⋅ℙ[E]) ≤ n· ( _v≠ s _k=0 n/ -1 _(u,v)∈ EI[G_v,e,k∈(k ,(k+1) )]+M·P[E] ) ≤n⋅(∑v≠s∑k=0⌊n/ε⌋−1∑(u,v)∈Eεκ+M⋅1(2n)2n+1) ≤ n· ( _v≠ s _k=0 n/ -1 _(u,v)∈ E κ+M· 1(2n)^2n+1 ) ≤n⋅(∑v≠s∑(u,v)∈Enκ+o(1/n)) ≤ n· ( _v≠ s _(u,v)∈ Enκ+o(1/n) ) ≤O(n2mκ), ≤ O(n^2mκ), by Lemma 7 and Lemma 8. ∎ 4 Connections to Negative-Weight Dijkstra It is well-known that inconsistent A* is equivalent to the Dijkstra algorithm on negative-weight graphs without negative cycles [3]. Indeed, the original heuristic function h(⋅)h(·) can be seen as a potential function. For each edge (u,v)∈E(u,v)∈ E, we can transform the edge weight into w(u,v)′=w(u,v)+h(v)−h(u)w _(u,v)=w_(u,v)+h(v)-h(u). Recall that the Dijkstra algorithm maintains a path length vector dist:V→ℝdist:V that represents the current path lengths from the start node s to any node. In each iteration, the algorithm finds an active node with the minimal path length, and relaxes adjacent nodes. Due to the existence of negative-weight edges, nodes may be updated for multiple times, which leads to an exponential worst-case complexity. Algorithm 2 Negative-weight Dijkstra’s algorithm with reopening. 1: A directed weighted graph G=(V,E)G=(V,E) with |V|=n|V|=n nodes and |E|=m|E|=m edges, where each edge e=(u,v)∈Ee=(u,v)∈ E is associated with a real weight we∈[−1,1]w_e∈[-1,1]; The start node s∈Vs∈ V. 2: The shortest paths from s to other nodes. 3: Let OPEN=s,CLOSED=∅OPEN=\s\,CLOSED= and dist(s)=0dist(s)=0; 4: while OPEN≠∅OPEN≠ do 5: Let v←argminv∈OPENdist(v)v← _v dist(v); 6: for each node v′v s.t. (v,v′)∈E(v,v )∈ E do 7: Let d′←dist(v)+w(v,v′)d (v)+w_(v,v ); 8: if v′∉OPEN∪CLOSEDv then 9: Let dist(v′)←d′,p(v′)←vdist(v )← d ,p(v )← v, and OPEN←OPEN∪v′OPEN ∪\v \; 10: else if v′∈OPENv and d′<dist(v′)d <dist(v ) then 11: Let dist(v′)←d′,p(v′)←vdist(v )← d ,p(v )← v; 12: else if v′∈CLOSEDv and d′<dist(v′)d <dist(v ) then 13: Let dist(v′)←d′,p(v′)←vdist(v )← d ,p(v )← v; 14: Move v′v from CLOSED to OPEN; 15: end if 16: end for 17: Move v from OPEN to CLOSED; 18: end while 19: return dist; Now, we study the smoothed complexity of negative-weight Dijkstra. Again, given a graph with n nodes and m edges, we assume the weight of each edge e is independently sampled from a distribution with density function pe:[−1,1]→[0,κ]p_e:[-1,1]→[0,κ]. We aim to find the shortest path lengths from a start node s to other nodes. Such instances are called κ-smoothed. Theorem 9. Given a κ-smoothed shortest path instance where the instance has no negative cycle with probability 1, the expected number of iterations of Algorithm 2 is bounded from above by O(n2mκ)O(n^2mκ). The proof of this theorem is essentially identical to Theorem 2. The only difference is in defining a slightly different version of bottleneck comparison. Given two different paths P and P′P from s to some node v, where P=s→u1→…→uk→uk+1→…→uK→vP=s→ u_1→…→ u_k→ u_k+1→…→ u_K→ v, and P′=s→u1→…→uk→uk+1′→…→uK′→vP =s→ u_1→…→ u_k→ u _k+1→…→ u _K → v, with the first k edges being the same (k could be 0), we say P≺P′P P if maxi∈k+1,…,Kw(P(ui))<maxi∈k+1,…,K′w(P′(ui′)), _i∈\k+1,…,K\w(P(u_i))< _i∈\k+1,…,K \w(P (u _i)), where P(ui)P(u_i) is the prefix of P from s to uiu_i, P′(ui′)P (u _i) is the prefix of P′P from s to ui′u _i, and w(⋅)w(·) is the total length of a path. The rest of the proof follows the same argument as Theorem 2. 5 Numerical Experiments We perform numerical experiments on the inconsistent A* instances constructed by Martelli [3] to show that the exponential-time behavior of inconsistent A* is highly sensitive to random perturbations, thus verifying our smoothed analysis result. Figure 3: Martelli’s instance for inconsistent A*. Blue integers are edge weights, and brown integers are heuristic values. Martelli’s instances with exponential worst-case complexities. Martelli’s family of A* instances is based on a construction of negative-weight shortest path instances. Let V=v0,v1,…,vnV=\v_0,v_1,…,v_n\ denote the nodes of a directed graph, where s=vns=v_n is the start node and t=v0t=v_0 is the goal node. For any 1≤i<j≤n1≤ i<j≤ n, there is a directed edge from vjv_j to viv_i. We first define a negative-weight graph, where w2,1′ w _2,1 =−2, =-2, wi+1,1′ w _i+1,1 =wi,1′−(2i−2+1),∀ 2≤i<n, =w _i,1-(2^i-2+1),\,∀\,2≤ i<n, wi,j+1′ w _i,j+1 =wi,j′+1,∀ 1<j+1<i≤n. =w _i,j+1,\,∀\,1<j+1<i≤ n. We also add an extra edge, w′1,0=−∑i=1n−1w′i+1,i.w _1,0=- _i=1^n-1w _i+1,i. Then, we can apply the equivalence between negative-weight Dijkstra and A* to construct an A* instance. The heuristic values of nodes are defined by h(v0) h(v_0) =h(v1)=0, =h(v_1)=0, h(vi) h(v_i) =h(vi−1)+(2i−2+2),∀ 1<i≤n. =h(v_i-1)+(2^i-2+2),\,∀\,1<i≤ n. The weight of each edge (i,j)(i,j) is wi,j=wi,j′+h(vi)−h(vj).w_i,j=w _i,j+h(v_i)-h(v_j). Figure 3 gives the example of Martelli’s construction for n=5n=5. Random perturbations on Martelli’s instances. In Martelli’s instance, the A* algorithm will enumerate every path from s to other nodes, leading to Ω(2n) (2^n) time. We empirically show that with a little random perturbation, the total number of iterations greatly decreases. The result is illustrated in Figure 4. We evaluate the A* algorithm on Martelli’s instance for n=15,20n=15,20 and 2525. (Larger instances are intractable due to the exponential time complexity.) We gradually increase the random perturbation from κ=∞κ=∞ (no perturbation). Each edge is independently perturbed by a uniform random variable supported on [−γ,γ][-γ,γ] for some γ (and thus 1/κ1/κ is γ divided by the maximum weight value). We clip the weights below zero such that all weights are non-negative. For each κ, we repeat the generation of the instances 100 times. Figure 4 gives the average and the standard deviation of the total iteration number. Note that both axes are logarithmic. It is easy to notice that if there is no random perturbation, the iteration number is about 2n2^n. As we slightly increase the perturbation, the iteration number greatly reduces. This verifies our theoretical results and indicates that the exponential behavior of inconsistent A* for worst-case instances is highly fragile. Figure 4: The iteration number of inconsistent A* on Martelli’s instance. 6 Conclusion In this paper, we study the smoothed complexity of the A* algorithm with inconsistent heuristics. We show that the exponential running time behavior of inconsistent A* in the worst case is highly fragile. With a little random perturbation, inconsistent A* finds the shortest path in polynomial time. Our result also works for the Dijkstra algorithm on negative-weight graphs. Numerical experiments verify our theoretical analysis. There are two directions of future research. On the one hand, our bound is still loose compared with practice. Note that if the edge weights are integers in [0,W][0,W], the time complexity of inconsistent A* is only O(n2W)O(n^2W). We conjecture that a corresponding smoothed complexity of O(n2κ)O(n^2κ) is possible. On the other hand, it would be interesting to prove lower bounds for smoothed A* to see what kind of instances are really hard for inconsistent heuristics. References [1] A. Felner, U. Zahavi, R. Holte, J. Schaeffer, N. Sturtevant, and Z. Zhang (2011) Inconsistent heuristics in theory and practice. Artificial Intelligence 175 (9), p. 1570–1603. Cited by: §1.2, §1, §1. [2] S. Sakaue and T. Oki (2022) Sample complexity of learning heuristic functions for greedy-best-first and A* search. In Proceedings of the 36th International Conference on Neural Information Processing Systems, p. 2889–2901. Cited by: §1.2, §1. [3] A. Martelli (1977) On the complexity of admissible search algorithms. Artificial Intelligence 8 (1), p. 1–13. Cited by: §1.1, §1, §4, §5. [4] D. A. Spielman and S. Teng (2004) Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. Journal of the ACM 51 (3), p. 385–463. Cited by: §1.2, §1. [5] M. Englert, H. Röglin, and B. Vöcking (2016) Smoothed analysis of the 2-opt algorithm for the general TSP. ACM Transactions on Algorithms 13 (1). Cited by: §1.1, §1.2. [6] R. Beier and B. Vöcking (2004) Typical properties of winners and losers in discrete optimization. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, p. 343–352. Cited by: §1.1. [7] T. Eden, P. Indyk, and H. Xu (2022) Embeddings and Labeling Schemes for A*. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), Vol. 215, p. 62:1–62:19. Cited by: §1.2. [8] X. Chen, C. Guo, E. V. Vlatakis-Gkaragkounis, M. Yannakakis, and X. Zhang (2020) Smoothed complexity of local max-cut and binary max-CSP. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, p. 1052–1065. Cited by: §1.2. [9] M. Balcan, T. Dick, and E. Vitercik (2018) Dispersion for data-driven algorithm design, online learning, and private optimization. In IEEE 59th Annual Symposium on Foundations of Computer Science, p. 603–614. Cited by: §1.2. [10] Z. Chen, H. Yao, and X. Yin (2025) Learning configurations for data-driven multi-objective optimization. In Proceedings of the 42nd International Conference on Machine Learning, Vol. 267, p. 9642–9663. Cited by: §1.2. [11] C. Coester and J. Umenberger (2025) Smoothed Analysis of Online Metric Problems. In Annual European Symposium on Algorithms (ESA), Vol. 351, p. 115:1–115:14. Cited by: §1.2. [12] D. Arthur, B. Manthey, and H. Röglin (2009) K-means has polynomial smoothed complexity. In Annual IEEE Symposium on Foundations of Computer Science, Vol. , p. 405–414. Cited by: §1.2. [13] T. Roughgarden (2021) Beyond the worst-case analysis of algorithms. Cambridge University Press. Cited by: §1.2.