Exponential Speedups by Rerooting Levin Tree Search

ArXiv: 2412.05196

🎯 Pitch

By starting a Levin Tree Search at every visited node and sharing effort via a learned rerooter, √lts can achieve an exponential speedup over standard LTS—reducing time T to roughly q·q√T in the best case. This means a search that would take 2^100 steps under LTS can be solved in just a few thousand, but only if the rerooter can reliably identify clue nodes that decompose the problem into smaller subtasks.

---

1. Executive Summary

This paper introduces √lts (pronounced root-LTS), a new search algorithm for deterministic environments that extends Levin Tree Search by implicitly starting an LTS instance at every visited node, with a rerooter—a user-specified or learned function assigning a rerooting weight to each node upon visitation (for example, assigning high weight to "clue" nodes that signal progress toward a solution)—that governs how search effort is shared proportionally among these instances. The core formal guarantee shows that √lts's number of node visits competes with the best decomposition of the search space into subtasks, incurring only a factor related to the rerooter's uncertainty: in the best case with q rerooting points, √lts achieves O(q · q√T) steps where LTS requires time T, representing an exponential speedup. This improvement materializes only when the rerooter provides informative weight assignments that decompose the problem into meaningful subtasks—establishing that the exponential gains over LTS depend critically on the quality of the side information captured by the rerooting weights, not merely on the presence of extra computation.

2. Context and Motivation

What Specific Problem Does This Paper Address?

The paper addresses a fundamental limitation in deterministic tree search: standard search algorithms are constrained to explore the search tree by starting from the root and expanding outward, visiting a node only if its parent has been visited first. This root-anchored exploration makes it difficult for these algorithms to leverage side information that becomes available only deeper in the tree—what the authors call "clues."

A clue is any signal that a particular node is on a promising path toward a solution. Crucially, a clue can only be recognized when the algorithm visits that node (or sometimes when generating its children). The algorithmic challenge is: how should a search algorithm allocate its exploration effort after discovering clues scattered throughout the tree? The naive approaches—ignoring clues entirely, committing greedily to the first promising clue, or starting completely fresh searches from each clue—are either inefficient or lack formal guarantees, particularly when clues can be misleading.

This is not a problem of merely having a better heuristic function. The paper shows (Appendix A.1) that even algorithms with strong optimality guarantees like A* and Weighted A* fundamentally cannot make efficient use of clues while retaining their bounded-suboptimality guarantees, because admissible heuristics force them to explore paths that might bypass clue nodes entirely. Similarly, Monte Carlo Tree Search variants like AlphaZero can be exponentially misled by a single high-reward clue that does not lead to the solution, taking double-exponential time to recover (Appendix A.3). And the paper's own predecessor, Levin Tree Search (LTS), lacks any mechanism to refocus its search after discovering clues—it explores in order of a fixed cost function determined entirely by the initial policy.

The core gap, then, is an algorithm with formal efficiency guarantees that can dynamically redistribute search effort to subtrees rooted at newly discovered promising nodes, without being misled by the volume of uninformative or deceptive clues.

Why Is This Problem Important?

Theoretical significance. The clue problem exposes a structural weakness in how search algorithms relate side information to exploration. In reinforcement learning, reward shaping (Ng et al., 1999) and landmark heuristics (Hoffmann et al., 2004) provide intermediate signals about progress, but search algorithms lack a principled framework for deciding how much computation to allocate to different regions of the tree when those signals arrive dynamically. The paper formalizes this as a subtask decomposition problem—given that side information partitions the search space into subtasks, can an algorithm achieve provable bounds that depend on the difficulty of individual subtasks rather than the global difficulty? A positive answer (which this paper provides) establishes that exponential speedups are theoretically achievable when informative clues are available.

Practical impact across domains. The authors motivate clues through concrete examples spanning multiple search-intensive fields:

• Classical planning: Landmarks—states that must be traversed on any path to the goal—are a well-established concept (Hoffmann et al., 2004). When a search algorithm reaches a landmark, it has made definitive progress, but standard planners cannot exploit this to focus search beyond the landmark.

• Automated theorem proving: A "clue" might fire when a useful lemma is discovered during the proof search. Without a mechanism to capitalize on that lemma, the prover may waste effort reconstructing similar intermediate results.

• Constraint satisfaction: When a particularly difficult subset of constraints is satisfied, that configuration represents a clue that the current partial assignment is worth exploring deeply.

• General problem-solving: Any domain with scoring functions or progress metrics can provide clue signals when substantial improvements occur—crossing a bottleneck, solving a subtask, or passing a threshold.

More broadly, the paper addresses the exploration-exploitation tension in search with learned guidance. Modern approaches like AlphaZero learn both a policy (which actions to prioritize) and a value function (which states are promising). But these learned components are static during a single search episode. Clues and rerooting weights represent a mechanism for dynamic, test-time adaptation of the search strategy based on information that could not have been encoded in the policy or value function beforehand—for instance, because the specific clue configuration depends on the search path taken. The ability to incorporate such runtime signals with formal guarantees is valuable whenever search problems exhibit identifiable intermediate milestones.

Where Do Prior Approaches Fall Short?

The paper provides a detailed taxonomy of how existing search paradigms fail on the clue problem (Section 1 and Appendix A):

1. Admissible heuristic search (A/WA): Cannot reroot without losing guarantees.** A* and Weighted A* are best-first search algorithms that visit nodes in order of $f(n) = g(n) + h(n)$, where $g(n)$ is the cost-to-come from the root and $h(n)$ is an admissible heuristic estimating cost-to-go. The admissibility requirement—that $h(n)$ never overestimates the true remaining cost—is what prevents these algorithms from exploiting clues.

Theorem 19 (Appendix A.1) formalizes this: for any algorithm that guarantees returning a solution within a factor $1 + \varepsilon$ of optimal cost, there exist environments with $q$ clues where that algorithm must visit $\Omega(2^{qa/(1+\varepsilon)})$ nodes, while √lts (which does not retain depth-optimality guarantees) visits only $O(q 2^a)$ nodes. The essential tension is that bounded-suboptimality forces exploration of paths that bypass clues, because the algorithm cannot rule out the possibility that a non-clue path leads to a sufficiently good solution. In the environments constructed, a second solution node at a shallower depth but not descending from any clue forces WA* to search broadly. An admissible heuristic could "prune" by assigning infinite cost to non-clue nodes at depth 50, but this prunes valid solution paths and thus violates admissibility—the guarantee dissolves.

2. Policy-guided search (LTS): No mechanism to redistribute effort. Levin Tree Search (Orseau et al., 2018) is the paper's direct predecessor. LTS uses a policy $\pi$ provided by the user (or learned from data) that assigns a probability to each action. It conducts a best-first search using the cost function $\frac{d}{\pi}(n) = d(n)/\pi(n)$ (later refined to the slenderness cost function $\frac{\lambda}{\pi}(n)$ in this paper), where $\pi(n)$ is the product of action probabilities from the root to node $n$. The formal guarantee: LTS visits a solution node $n^*$ in at most $1 + d(n^*)/\pi(n^*)$ steps when using the $\frac{d}{\pi}$ cost function.

On the 1000-Clues environment (Example 1), the paper shows (Appendix A.2) that LTS requires at least $2^{99}$ node visits in the worst case—essentially no better than uninformed search—because the cost function $\frac{d}{\pi}(\cdot)$ ranks nodes without regard to clue information. Non-clue nodes at depth 98 that do not descend from the helpful clue have the same cost as clue-descending nodes at depth 98, so LTS visits all of them. The fundamental issue is that LTS's cost function is static with respect to clues: it depends only on the policy's action probabilities and node depths, not on clue membership discovered at runtime.

This paper also improves LTS's cost function by replacing $\frac{d}{\pi}$ (or $1 + \frac{d}{\pi}$) with the slenderness cost function $\frac{\lambda}{\pi}$ (Section 4.1), which tightens the self-counting bound. The slenderness $\lambda(n)$ of a node accumulates shares of ancestors proportionally to the policy probability: each child $n'$ of $n$ inherits a fraction $\lambda(n)\pi(n'|n)$ of the ancestor shares, plus 1 for itself. This avoids double-counting ancestors when computing the total number of nodes in a tree, yielding a bound whose ratio to the true count improves over LTS by a factor of $d(\cdot)$ (the depth).

3. Monte Carlo Tree Search (AlphaZero, UCT): Catastrophic misleading by sparse rewards. Appendix A.3 demonstrates two failure modes:

• D-chain environment (Figure 4, Appendix A.3.1): A binary tree where rewards decrease as the algorithm descends along a chain of right-branching nodes, while the true high-reward solution descends from the leftmost branch. Prior work (Coquelin and Munos, 2007; Orseau and Munos, 2024) showed that UCT and AlphaZero take double-exponential time with the solution depth to recover from the misleading intermediate rewards. These algorithms commit most of their search budget to the subtree of the first high-reward node they encounter, and when that node is a dead end, they must exhaustively explore that massive subtree before reallocating effort elsewhere.

• Single misleading reward (Appendix A.3.2): Even a single reward $\alpha \in (0,1)$ placed at a child of the root misleads AlphaZero-type MCTS algorithms into quadratic slowdown. The analysis shows that to find a solution node $n^*$ with reward 1 descending from a different child of the root, the MCTS algorithm must traverse the solution's ancestor at least $2^{d(n^*) - 1}$ times. The exploration bonus must overcome the misleading reward's average, leading to a total node visit bound of $\Omega((\alpha 2^{d(n^*)})^2)$ compared to breadth-first search's $O(2^{d(n^*)})$. √lts, by contrast, multiplies its bound by only $(1 + \alpha)$—a constant factor slowdown.

The common thread in these MCTS failures is greedy commitment: the algorithms allocate search effort proportionally to observed rewards, which works well when rewards are dense and well-shaped, but catastrophically over-commits to the first promising signal when rewards are sparse and potentially misleading.

4. No existing framework for composing searches with dynamic weights. More abstractly, prior work lacked a formal composition framework for search algorithms. The idea of running multiple search instances with shared computation and non-uniform weights has precedents in algorithm selection and universal search (Levin, 1973; Li and Vitányi, 2019), where multiple programs compete for CPU time. Equation (8) captures this: if program $i$ needs $\tau_i$ steps and receives fraction $w_i$ of total steps $T$, a solution is found when $T \leq \min_i (\tau_i + 1)/w_i$. But translating this program-composition idea into a best-first search over a single tree with node-level weight assignments—where the "programs" are LTS instances rooted at visited nodes, and the weights are determined dynamically as the search progresses—requires new machinery: composing self-counting cost functions (Lemma 8), handling non-monotonicity induced by rerooting (Section 5, via the cost function $c^r$), and coping with off-by-one dependencies where weights for a node's subtree depend on information not yet available when the node is generated (Section 5, "Off-by-one $\frac{\lambda}{\pi}$").

How Does This Paper Position Itself Relative to Existing Work?

The paper constructs its contribution along two axes:

Axis 1: Extending LTS, not replacing it. √lts is explicitly an extension of Levin Tree Search. It preserves LTS as a special case: setting the rerooting weight $w_1 = 1$ for the root and $w_t = 0$ for all other nodes collapses √lts's bound to exactly the LTS bound $\frac{\lambda}{\pi}(n_T)$ (Equation 16 after choosing the trivial subtask decomposition). This means √lts is never worse than LTS by more than a factor related to the cumulative rerooting weights, and the robustness analysis (Section 6, Corollary 17) shows this factor can be kept logarithmic in the worst case through appropriate weight reparameterization. The improvement is therefore optional: a poorly designed rerooter causes at most logarithmic overhead, while a good rerooter yields exponential speedups.

Axis 2: Providing a meta-algorithm, not a domain-specific heuristic. The paper does not prescribe how to design clues or rerooting weights for specific domains. It provides the algorithmic framework and its guarantees, with the rerooter treated as an input to the algorithm (like the policy in LTS). The authors explicitly note: "Like the LTS policy, we expect that the rerooter may be learnt from data or designed by the user, but this is beyond the scope of this paper" (Section 1). This positions √lts as a general-purpose search meta-algorithm that can be instantiated with domain-specific side information, analogous to how LTS can be instantiated with a domain-specific learned policy.

This positioning is important because it separates the mechanism (how to compose subtask searches with formal bounds) from the knowledge source (where clues come from). The paper connects clues to established concepts—shaping rewards in RL, landmarks in planning, lemmas in theorem proving—to suggest natural sources of side information, but the theoretical results hold for any rerooting weight assignment. The guarantee (Theorem 11) bounds node visits in terms of the weights actually assigned and the policy's probabilities, regardless of whether those weights come from clues, learned value functions, or any other source.

Relationship to the lower bound. The paper establishes (Theorem 3, Section 3) that for environments with $q$ clue nodes and the solution at relative depth at most $a$ from its closest clue ancestor, any algorithm (randomized or deterministic, with any heuristic information) must visit at least $(q+1)2^{a-1}$ nodes on average. This lower bound serves two purposes: it demonstrates that √lts's upper bound of $O(q 2^a)$ (Example 13) is tight to within a factor of 4, and it establishes impossibility results that rule out certain hoped-for improvements—for instance, no algorithm can achieve $O(m 2^a)$ when $m = o(q)$ clues lie on the solution path. The lower bound also justifies why the factor $q$ (total clues) rather than $m$ (helpful clues) appears in the bound: the algorithm cannot distinguish helpful from misleading clues without exploring their descendants.

The self-counting cost function machinery. While the primary contribution is √lts itself, the paper develops significant supporting theory around self-counting cost functions (Definition 4): a cost function $c$ is self-counting if the number of nodes with $c(n) \leq \theta$ is at most $\theta$ itself. This property cleanly links the cost of a visited node to the step at which it is visited in best-first search (Lemma 5: if $c$ is monotone and self-counting, then $t \leq c(n_t)$ for all steps $t$). The paper introduces:

• The slenderness cost function $\frac{\lambda}{\pi}$ (Section 4.1), which tightens LTS's bounds by avoiding the double-counting of ancestors inherent in $\frac{d}{\pi}$.
• Lemma 8: a composition theorem showing that the pointwise minimum of weighted self-counting cost functions is itself self-counting, provided the weights sum to at most 1. This is the theoretical engine behind composing multiple LTS instances.
• Lemma 35 and Corollary 37: generalizations handling non-monotone compositions, which are necessary because rooted LTS cost functions $\frac{\lambda}{\pi}(\cdot; n_t)$ are not monotone outside the descendants of $n_t$.

This machinery is reusable beyond √lts: any future algorithm that needs to compose multiple guided searches with formal step-count guarantees can build on these composition theorems.

Where this paper does NOT go. The paper is deliberately scoped to the theory and algorithm design, not to empirical validation or learning. There are no experiments with learned policies or rerooters on benchmark domains (the Sokoban example in Appendix H is a back-of-the-envelope calculation for illustration, not an empirical result). The paper establishes the existence and properties of the algorithm and its bounds, leaving to future work the questions of how to learn rerooters from data, how to instantiate clues in specific applications, and whether the theoretical speedups materialize in practice when both policy and rerooter are learned. This scope is consistent with the paper's theoretical-computer-science framing (the first author's affiliation is Google DeepMind, and the paper appears on arXiv in the cs.AI category), but it means the practical utility of √lts depends on empirical validation that has not yet been performed.

3. Technical Approach

3.1 Reader Orientation

√lts is a best-first search algorithm that—instead of exploring the tree outward from the root alone—implicitly starts a new Levin Tree Search at every node it visits, allocating search effort among these "rerooted" searches according to weights assigned by a user-provided rerooter function. The core problem it solves is how to dynamically redistribute computation to promising subtrees discovered deep in the search (e.g., at "clue" nodes signaling progress) while retaining formal guarantees: the number of node visits to find a solution depends on the quality of the policy and the rerooter, and—crucially—is competitive with the best possible decomposition of the search space into subtasks, rather than scaling with the difficulty of the whole problem.

3.2 Big-Picture Architecture (Diagram in Words)

The system has four interacting components:

1. The Policy $\pi$ — a user-provided probability distribution over actions at each node (inherited from LTS). It defines a "path probability" $\pi(n)$ for every node $n$, which quantifies how promising the policy considers that path. The policy determines the shape of the slenderness cost function $\frac{\lambda}{\pi}$ that underlies all search effort allocation.

2. The Rerooter $w$ — a function that, at each step $t$ when node $n_t$ is visited, outputs a non-negative scalar weight $w_t$. This weight can depend on any information available up to step $t$: whether $n_t$ is a clue node, how many clues have been seen so far, the depth, the policy's probability, etc. The rerooter decides what fraction of total search effort should be devoted to the subtree rooted at $n_t$.

3. The Composed Cost Function $c^r$ — the algorithmic core, which combines the policy and the rerooter into a single scalar cost for every node. For a node $n$, $c^r(n)$ is the minimum over all ancestors $n_t \prec n$ of the weighted rooted LTS cost $\frac{1}{w_t}(\frac{\lambda}{\pi}(n; n_t) - 1)$. This composition (Lemma 8) ensures the combined cost function remains self-counting, meaning bounds on node visits translate directly from costs.

4. Best-First Search Priority Queue — a standard BFS loop (Algorithm 1) that repeatedly extracts the node with minimum $c^r(n)$ from a priority queue, visits it, and pushes its children. The BFS automatically allocates exploration effort among the competing rerooted LTS instances proportionally to their weights, without explicitly instantiating separate search processes.

Information flow at each step: (1) the BFS extracts node $n_t$ from the queue; (2) the rerooter inspects $n_t$ and assigns weight $w_t$; (3) for every descendant $n$ of $n_t$ (pushed into the queue at this or later steps), the rooted LTS cost $\frac{\lambda}{\pi}(n; n_t)$ is computed and combined with $w_t$ into the global cost $c^r(n)$; (4) the BFS continues, with nodes descending from high-weight ancestors receiving lower costs and thus being visited sooner. The result is an implicit time-sharing of the search among all visited nodes as search roots, weighted by their rerooting weights.

3.3 Roadmap for the Deep Dive

• First, the self-counting cost function concept (Definition 4, Lemma 5) and the slenderness cost function $\frac{\lambda}{\pi}$ (Section 4.1, Equation 5), because these are the fundamental currency of all bounds—every cost function in the paper is designed to be self-counting so that cost directly translates to step count.
• Second, Lemma 8 (composition) — how multiple self-counting cost functions are combined into one via a pointwise minimum weighted by the rerooter's weights. This is the mathematical engine that enables one BFS to simulate many LTS instances simultaneously.
• Third, the √lts cost function $c^r$ itself (Equation 13), paying special attention to how it handles non-monotonicity (the rooted costs are infinite above their root) and the off-by-one design choice that decouples a node's weight from its ancestors' weights.
• Fourth, Theorem 11 and Corollary 12 — the main guarantee. We walk through the subtask decomposition concept, how the bound separates into segments weighted by cumulative rerooting weights, and what each term physically represents in the search process.
• Fifth, the robustness reparameterization (Corollary 17) — how input weights $\tilde{w}_t$ are transformed into normalized weights $w_t = \tilde{w}_t / \tilde{w}_{\leq t}$ to prevent the bound from becoming vacuous when there are too many clues, and why a logarithmic factor is unavoidable (Remark 18).

3.4 Detailed, Sentence-Based Technical Breakdown

This is a theoretical algorithm-design paper whose core idea is that composing multiple LTS instances—each rooted at a visited node and weighted by a dynamically assigned rerooting weight—into a single best-first search yields formal guarantees that scale with the best subtask decomposition of the problem rather than the overall difficulty.

---

The Currency of Bounds: Self-Counting Cost Functions

The entire analysis of √lts rests on a single, simple property of cost functions.

Definition 4 (Self-counting cost function). A cost function $c: \mathcal{N} \to \mathbb{R}$ is self-counting if, for every threshold $\theta \geq 0$, the number of nodes whose cost is at most $\theta$ is itself at most $\theta$:

$|\{n \in \mathcal{N} : c(n) \leq \theta\}| \leq \theta.$

Why this property matters. Lemma 5 provides the critical connection to best-first search:

A monotone cost function $c$ is self-counting if and only if $t \leq c(n_t)$ for all $t \in \mathbb{N}_1$, where $n_t$ is the node visited at step $t$ of BFS with cost function $c$.

What this means operationally. If you run a best-first search using a monotone self-counting cost function, then when the BFS visits a node at step $t$, the cost $c(n_t)$ of that node is an upper bound on the step number $t$. This transforms the problem of bounding node visits into the problem of designing a self-counting cost function such that solution nodes have low cost. The cost is the bound.

Proof sketch for intuition. BFS with a monotone cost function enumerates nodes in non-decreasing order of cost. So at step $t$, all nodes visited so far have cost at most $c(n_t)$. Since $c$ is self-counting, the number of such nodes is at most $c(n_t)$. But there are exactly $t$ nodes visited so far (counting $n_t$). Hence $t \leq c(n_t)$.

Why monotonicity matters for this equivalence. A self-counting cost function need not be monotone (Example 30: all nodes at depth 10 of a binary tree cost 1024, all others cost infinity—this is self-counting because exactly 1024 nodes have cost 1024, but it's non-monotone because ancestors cost infinity while descendants cost 1024). Lemma 5 requires monotonicity because BFS with a non-monotone cost function may not visit nodes in cost order; nodes with lower cost may be blocked behind higher-cost ancestors in the queue. The equality $t = |\{n_1, \dots, n_t\}| \leq |\{n : c(n) \leq c(n_t)\}|$ no longer holds because there might be nodes with $c(n) \leq c(n_t)$ that have not yet been visited due to queue ordering effects. The paper's main technical challenge is handling this non-monotonicity when composing rerooted cost functions.

---

The Slenderness Cost Function: A Tighter LTS

Before composing LTS instances, the paper improves the base LTS cost function itself. The original LTS uses $1 + \frac{d}{\pi}(n) = 1 + d(n)/\pi(n)$, which is self-counting (Orseau et al., 2018). But this cost function double-counts the ancestors of nodes when summing across leaves of a subtree.

The double-counting problem (Example 6). Consider a chain of nodes $n_1 \to \dots \to n_a$, each with one child of probability 1, so $1 + \frac{d}{\pi}(n_a) = 1 + d(n_a)$. This counts the $d(n_a) + 1$ nodes correctly. Now suppose $n_a$ has two children $n_b$ and $n_c$, each with probability $1/2$. Then $1 + \frac{d}{\pi}(n_b) = 1 + (d(n_a) + 1)/(1/2) = 2d(n_a) + 3$. But the actual number of nodes with cost at most $1 + \frac{d}{\pi}(n_b)$ is $d(n_a) + 3$ (the chain plus the two children). The factor 2 error arises because the ancestors of $n_a$ are counted separately for each branch rooted at $n_a$'s children—the cost function treats $n_b$'s ancestors and $n_c$'s ancestors as disjoint when they are actually shared.

The slenderness solution. Define $\lambda(n)$, the slenderness of node $n$, recursively (Equation 3):

$\lambda(n_1) = 1, \qquad \forall n' \in \mathcal{C}(n) : \lambda(n') = \lambda(n) \pi(n'|n) + 1.$

Intuitively, $\lambda(n)$ is the number of nodes $n$ is "responsible for" in a weighted accounting. The root is responsible for itself ($\lambda = 1$). Each child $n'$ inherits a fraction $\pi(n'|n)$ of its parent's responsibility, plus 1 for itself. If $\pi$ properly sums to 1 over children, then $\sum_{n' \in \mathcal{C}(n)} (\lambda(n') - 1) = \lambda(n)$, meaning the "responsibility beyond self" is conserved across generations. It follows that $1 \leq \lambda(n) \leq 1 + d(n)$ for all $n$, with equality on the right only for a chain where all probabilities are 1.

The slenderness cost function (Equation 5) is then:

$\frac{\lambda}{\pi}(n) = \frac{\lambda(n)}{\pi(n)} = \sum_{n' \preceq n} \frac{1}{\pi(n')}.$

What this computes. For each ancestor $n'$ of $n$ (including $n$ itself), we add $1/\pi(n')$. Since $\pi(n') \leq 1$, each term is at least 1. If the policy assigns low probability to some step, $1/\pi(n')$ is large, inflating the cost—this is how the policy's disagreement with the path manifests in the cost. The sum form makes explicit that $\frac{\lambda}{\pi}$ is monotone: adding a child increases the sum by a non-negative term.

Why this form is tighter. Lemma 24 proves that for any tree $\mathcal{N}'$ rooted at $n_1$, summing $\frac{\pi'(n)}{\pi(n)}\lambda(n)$ over nodes (where $\pi'$ is a "complementary policy" measuring probability not passed to children in $\mathcal{N}'$) yields exactly $|\mathcal{N}'|$, the number of nodes in the tree. This means $\lambda$ performs a lossless accounting: every unit of "responsibility" eventually corresponds to exactly one node. The self-counting property (Proposition 25) follows directly: for the set $\mathcal{N}_\theta = \{n : \frac{\lambda}{\pi}(n) \leq \theta\}$, we have $|\mathcal{N}_\theta| = \sum_{n \in \mathcal{N}_\theta} \frac{\pi_\theta(n)}{\pi(n)}\lambda(n) = \sum_{n \in \mathcal{N}_\theta} \pi_\theta(n) \frac{\lambda}{\pi}(n) \leq \sum_{n \in \mathcal{N}_\theta} \pi_\theta(n) \theta = \theta$, where the inequality uses $\frac{\lambda}{\pi}(n) \leq \theta$ by definition of $\mathcal{N}_\theta$.

Lower bound (Equation 6): for a proper policy, $|\mathcal{N}_\theta| > (\theta - 1)/B$ where $B$ is the average branching factor of $\mathcal{N}_\theta$. The ratio between upper and lower bounds is roughly $B$, compared to $B \cdot d(\cdot)$ for the $\frac{d}{\pi}$ cost function—the improvement is a factor of the depth, which can be substantial in deep search trees.

The rooted variant (Equation 7). For a subtask starting at node $n_a$, we need the cost of reaching $n$ when $n_a$ is treated as the root:

$\frac{\lambda}{\pi}(n; n_a) = \sum_{n_a \preceq n' \preceq n} \frac{1}{\pi(n'|n_a)}$

where $\pi(n'|n_a) = \pi(n')/\pi(n_a)$ is the conditional path probability. This cost is $\infty$ if $n_a \not\preceq n$ (the node is not in the subtree rooted at $n_a$). While self-counting on $\text{desc}^+(n_a)$, it is not monotone on the full tree: ancestors of $n_a$ have infinite cost, but descendants have finite costs.

Telescoping property (Lemma 28). For $n_a \preceq n_b \preceq n$:

$\frac{\frac{\lambda}{\pi}(n; n_a) - 1}{\pi(n_a)} = \frac{\frac{\lambda}{\pi}(n_b; n_a) - 1}{\pi(n_a)} + \frac{\frac{\lambda}{\pi}(n; n_b) - 1}{\pi(n_b)}.$

This additivity is critical for comparing competing rerooted cost functions (Lemma 41) and enables the incremental cost updates that make √lts efficient to implement.

Why $\frac{\lambda}{\pi} - 1$ appears in √lts. The $-1$ term (Equation 13) ensures that when $n = n_t$ (the root of a subtask), the rooted cost is $\infty$ rather than 1. This means $n_t$ itself does not benefit from its own rerooting weight—only its descendants do. This is the "off-by-one" fix discussed below.

---

Composing Self-Counting Cost Functions: The Engine of Time-Sharing

The central insight that makes √lts possible is that self-counting cost functions can be composed into a single self-counting cost function via a weighted pointwise minimum.

Lemma 8 (Composing SCCFs). Let $\{c_i\}_{i \in [N]}$ be $N$ base self-counting cost functions. For a weighting $w$ with $\sum_{i \in [N]} w_i \leq 1$ and all $w_i \geq 0$, define:

$c(n) = \min_{i \in [N]} \frac{c_i(n)}{w_i}.$

Then $c$ is a self-counting cost function.

What this computes. For a fixed node $n$, we evaluate all $N$ base cost functions at $n$, divide each by its weight $w_i$, and take the minimum. The weight $w_i$ acts as a divider: the smaller $w_i$ is, the larger $\frac{c_i(n)}{w_i}$ becomes, making base cost function $i$ less competitive and thus less influential in determining $c(n)$.

Why the minimum works. The proof uses a union bound: nodes where $c(n) \leq \theta$ are those where at least one $\frac{c_i(n)}{w_i} \leq \theta$, i.e., where $c_i(n) \leq w_i \theta$. The cardinality is at most the sum (over $i$) of nodes where $c_i(n) \leq w_i \theta$, which by self-counting of each $c_i$ is at most $\sum_i w_i \theta \leq \theta$.

Analogy to time-sharing programs. Recall Equation (8): if program $i$ needs $\tau_i$ steps and receives fraction $w_i$ of total $T$ steps, a solution is found when $T \leq \min_i (\tau_i + 1)/w_i$. Lemma 8 translates this program-time-sharing guarantee into a node-visit guarantee for best-first search: if we compose multiple self-counting cost functions with weights $w_i$, and a solution node $n_T$ is visited at step $T$ in the composed BFS, then $T \leq c(n_T) = \min_i \frac{c_i(n_T)}{w_i}$. The step count is as good as the best weighted base cost.

The normalization requirement. The weights must sum to at most 1. In practice (Section 5), √lts drops this normalization by observing that BFS is invariant to scaling the entire cost function by a constant. If we use unnormalized weights $\tilde{w}_i$, the effective normalization factor $\sum_i \tilde{w}_i$ appears as a multiplicative constant in all costs. Since BFS only compares relative costs, this constant does not affect the visitation order. The paper exploits this to work with unnormalized weights, which is mathematically convenient and enables weight schemes that depend on cumulative quantities (Example 15).

---

The √lts Cost Function $c^r$: Building the Algorithm

Now we construct the actual cost function that √lts uses in its BFS.

First attempt: the naive composition $\tilde{c}$. After visiting $t$ nodes $n_1, \dots, n_t$, we want to compose $t$ LTS instances—one rooted at each visited node $n_k$, with weight $w_k$. Each base cost function is $\frac{\lambda}{\pi}(\cdot; n_k)$, the rooted slenderness cost. The composition (Equation 11) would be:

$\tilde{c}(n) = \min_{n_t \preceq n} \frac{1}{w_t} \cdot \frac{\lambda}{\pi}(n; n_t).$

Here, the minimization over $n_t \preceq n$ replaces the full minimization over all $t$ because $\frac{\lambda}{\pi}(n; n_t) = \infty$ for $n_t \not\preceq n$.

Problem 1: Non-monotonicity. The base cost functions $\frac{\lambda}{\pi}(\cdot; n_t)$ are monotone on descendants of $n_t$ but not on the whole tree—ancestors of $n_t$ have infinite cost, while descendants have finite costs. The composition $\tilde{c}$ inherits this non-monotonicity. Lemma 5's equivalence between step count and cost requires monotonicity, so we cannot directly claim $T \leq \tilde{c}(n_T)$ from the self-counting property.

Temporary fix: $c^{\max}$. One can force monotonicity by taking the running maximum along each path: $c^{\max}(n) = \max_{n' \preceq n} \tilde{c}(n')$. This preserves self-counting (raising costs can only reduce the set $\{n : c^{\max}(n) \leq \theta\}$) and yields the bound $T \leq c^{\max}(n_T)$ (Equation 12). The cost $c^{\max}(n_T)$ is the maximum—over ancestors $n$ of $n_T$—of the minimum—over all visited ancestors $n_t$ of $n$—of the weighted rooted LTS cost. In max-min form:

$T \leq c^{\max}(n_T) = \max_{n \preceq n_T} \min_{n_t \preceq n} \frac{1}{w_t} \frac{\lambda}{\pi}(n; n_t).$

This bound is already nontrivial (Example 9 derives $T \leq q(2^{a+1} - 1)$ for the clue environment), but two issues remain: (a) the tie-breaking induced by $c^{\max}$ versus $\tilde{c}$ can be refined, and (b) there is an off-by-one circularity in weight assignment.

Problem 2: Off-by-one circularity. When node $n_t$'s parent is visited at step $k$, the child $n_t$ is generated and pushed into the priority queue with cost $\tilde{c}(n_t)$. But $\tilde{c}(n_t)$ depends on $w_t$ (since $n_t \preceq n$, the term $n_t = n_t$ appears in the minimization with weight $w_t$). The weight $w_t$ is assigned only when $n_t$ itself is visited at step $t$, which occurs after step $k$. At step $k+1$, the value of $w_t$—and potentially even the identity of $t$—is unknown. This creates a circular dependency: to compute $\tilde{c}(n_t)$ and insert it in the queue, we need $w_t$; but $w_t$ may depend on information accumulated between steps $k+1$ and $t$ (e.g., $w_{\leq t}$), which is not yet available.

The fix: $c^r$ (Equation 13). The algorithm separates a node from its own rerooting benefit. Define the base cost function for the instance rooted at $n_t$ to be $\infty$ at $n_t$ itself, and finite only for strict descendants:

$c^r_t(n) = \begin{cases} \frac{\lambda}{\pi}(n; n_t) - 1 & \text{if } n_t \prec n, \\ \infty & \text{otherwise.} \end{cases}$

The composed cost is:

$c^r(n) = \min_{t \in \mathbb{N}_1} \frac{c^r_t(n)}{w_t} = \min_{n_t \prec n} \frac{\frac{\lambda}{\pi}(n; n_t) - 1}{w_t}.$

Additionally, set $c^r(n_1) = 1$ to handle the root.

What changed. The minimization condition changed from $n_t \preceq n$ to $n_t \prec n$ (strict ancestor). A node $n$ does not receive a cost reduction from being its own root. Its weight $w_t$ only affects the costs of its descendants. This means when $n_t$ is generated and pushed into the queue, its cost $c^r(n_t)$ depends only on already-visited ancestors $n_k \prec n_t$ and their known weights $w_k$—the circularity is broken. The weight $w_t$ is computed later, when $n_t$ is visited, and from that point onward influences the costs of descendants generated thereafter.

The $-1$ term. Subtracting 1 from $\frac{\lambda}{\pi}(n; n_t)$ ensures that when $n$ is the immediate child of $n_t$, the rooted cost starts at $1/\pi(n|n_t)$ rather than $1 + 1/\pi(n|n_t)$—the difference is minor for bounding but important for the precise telescoping calculations in Lemma 28 and the off-by-one argument above.

Why $c^r$ is preferred over $c^{\max}$ for the analysis. While $c^r$ is non-monotone (like $\tilde{c}$), the paper develops refined analysis tools (Lemma 33, Lemma 35, Corollary 37) that handle the non-monotonicity directly and yield tighter bounds than $c^{\max}$ would. The intuition (Section 5, "Tie breaking") is that $c^{\max}$ forces many nodes that have different $c^r$ costs to share the same $c^{\max}$ cost, effectively losing information about which rerooted instances they belong to. The non-monotone analysis preserves this granularity, leading to bounds that can decompose by subtask (Theorem 11).

Algorithm 1: The implementation. The √lts algorithm is a straightforward BFS using $c^r$:

1. Initialize priority queue $Q_1 = \{n_1\}$; set $t = 1$.
2. At each step, extract $n_t \in \arg\min_{n \in Q_t} c^r(n)$ from the queue.
3. Visit $n_t$: the rerooter assigns weight $w_t$ based on all information available up to step $t$.
4. Generate children $\mathcal{C}(n_t)$; for each child $n'$, compute $c^r(n') = \min_{n_k \prec n'} \frac{\frac{\lambda}{\pi}(n'; n_k) - 1}{w_k}$ using incremental updates (Appendix G).
5. Push children into $Q_{t+1} = (Q_t \setminus \{n_t\}) \cup \mathcal{C}(n_t)$.
6. Increment $t$ and repeat.

Computational efficiency (Appendix G). The naive cost computation is $O(d(n))$ per generated node (minimizing over all ancestors). Lemma 41 provides a pruning criterion: if two ancestors $n_a$ and $n_b$ satisfy $\frac{c^r_a(n_t)}{w_a} \leq \frac{c^r_b(n_t)}{w_b}$ and $\frac{\pi(n_a)}{w_a} \leq \frac{\pi(n_b)}{w_b}$ at some node $n_t$, then for all descendants $n$ of $n_t$, base cost $b$ is permanently dominated by base cost $a$ and can be discarded from the minimization. This allows maintaining a small active set $\mathcal{A}(n_t)$ of non-dominated ancestors, typically of size $O(1)$ in practice. When weights are binary ($w_t \in \{0,1\}$), only the deepest ancestor with weight 1 is ever needed (Remark 42), reducing cost computation to $O(1)$.

---

The Main Guarantee: Theorem 11 and Its Interpretations

The master theorem bounds the step at which √lts visits a node in terms of any user-chosen decomposition of that node's path into subtasks.

Definition 10 (Subtask decomposition). A set of $m$ nodes $\{n_{T_i}\}_{i \leq m}$, visited at steps $T_1 < T_2 < \dots < T_m = T$, is a subtask decomposition of $n_T$ if they form a chain: $n_1 = n_{T_1} \prec n_{T_2} \prec \dots \prec n_{T_m} = n_T$.

What this represents. The user selects checkpoints along the path to the solution—for instance, clue nodes or other milestones—and the bound splits the total search cost into the costs of reaching each checkpoint from the previous one, weighted by how much of the search budget went into each segment.

Theorem 11 (√lts guarantee). Let $n_T$ be the node visited at step $T$ of BFS with cost function $c^r$. Then, for every subtask decomposition $n_{T_1} \prec n_{T_2} \prec \dots \prec n_{T_m}$ of $n_T$:

$T \leq \sum_{j < m} (w_{< T_{j+1}} - w_{< T_j}) \max_{j \leq i < m} \frac{1}{w_{T_i}} \frac{\lambda}{\pi}(n_{T_{i+1}}; n_{T_i}).$

Defining the symbols.

• $T$ is the step at which $n_T$ is visited.
• $w_{< T_j} = \sum_{k < T_j} w_k$ is the cumulative rerooting weight of all nodes visited before step $T_j$.
• $w_{< T_{j+1}} - w_{< T_j}$ is the total rerooting weight of nodes visited during subtask $j$ (from step $T_j$ to just before $T_{j+1}$).
• $\frac{\lambda}{\pi}(n_{T_{i+1}}; n_{T_i})$ is the rooted slenderness cost of reaching $n_{T_{i+1}}$ from $n_{T_i}$ using LTS.
• $w_{T_i}$ is the rerooting weight assigned to the checkpoint node $n_{T_i}$.
• The maximum runs over subtask indices $i$ from $j$ to $m-1$, meaning subtask $j$'s contribution uses the "hardest" (largest weighted cost) among the remaining subtasks from $j$ onward.

What this computes, operationally. For each subtask $j$ (reaching $n_{T_{j+1}}$ from $n_{T_j}$), we multiply the sum of rerooting weights assigned during that subtask, $(w_{< T_{j+1}} - w_{< T_j})$, by the maximum—over $i \geq j$—of the weighted LTS cost $\frac{1}{w_{T_i}} \frac{\lambda}{\pi}(n_{T_{i+1}}; n_{T_i})$ of reaching the next checkpoint. The interpretation: nodes visited during subtask $j$ are not wasted; their cumulative weight is counted toward the maximum remaining difficulty among all subtasks still to come. Later subtasks that are easier (smaller weighted cost) do not inflate the bound.

Why this form captures rerooting behavior. The key term is $\frac{1}{w_{T_i}} \frac{\lambda}{\pi}(n_{T_{i+1}}; n_{T_i})$. If the rerooting weight $w_{T_i}$ is large (e.g., node $n_{T_i}$ was recognized as an important clue), this term becomes small—the subtask from $n_{T_i}$ to $n_{T_{i+1}}$ appears "cheap" because the rerooter committed a large fraction of search effort to it. Conversely, if $w_{T_i}$ is small, this subtask is expensive. The cumulative weight terms $(w_{< T_{j+1}} - w_{< T_j})$ capture that effort spent during earlier subtasks "pays for" the difficulty of later subtasks—if nodes visited during subtask 1 carry high rerooting weights, they inflate the bound for subtasks 2, 3, etc., proportional to their cumulative weight. This is the price of misleading clues: they consume high weights during early subtasks, which then multiply against the difficulty of later subtasks.

Proof sketch (Appendix D). The proof builds up from Lemma 35 (SCCF composition bound for non-monotone functions), specialized to $c^r$ via Corollary 37 ($T \leq 1 + \sum_{i < T} w_i \max_{i < t \leq T} c^r(n_t)$). It then partitions the sum over $i$ into segments corresponding to the subtask decomposition, applies Lemma 33 (Tree-to-path: the costs of nodes visited between $T_j$ and $T_{j+1}$ are bounded by the maximum cost on the path between $n_{T_j}$ and $n_{T_{j+1}}$), and upper-bounds the path costs by the weighted rooted LTS costs of the relevant subtasks. The telescoping property (Lemma 28) ensures the bounds chain together cleanly.

Corollary 12 (Simplified bound). By relaxing the maximum to run over all subtasks ($\max_{j \leq i < m} \dots \leq \max_{1 \leq i < m} \dots$) and telescoping the sum of weight differences:

$T \leq \left(\max_{1 \leq i < m} \frac{w_{< T}}{w_{T_i}} \frac{\lambda}{\pi}(n_{T_{i+1}}; n_{T_i})\right)$

or equivalently,

$T \leq \max_{1 \leq i < m} \frac{w_{< T}}{w_{T_i}} \frac{\lambda}{\pi}(n_{T_{i+1}}; n_{T_i}).$

What this simplification means. The bound is the maximum—over subtasks $i$—of the LTS cost of subtask $i$, multiplied by the factor $\frac{w_{< T}}{w_{T_i}}$. This factor is the inverse of the normalized weight $w_{T_i} / w_{< T}$: if $n_{T_i}$ received, say, half of all rerooting weight assigned up to step $T$, then $\frac{w_{< T}}{w_{T_i}} = 2$, and the bound for that subtask is twice its LTS cost. If most weight went to other (unhelpful) nodes, this factor is large. The bound is dominated by the subtask where the product of difficulty and weight misallocation is largest.

Special case: single subtask (Equation 16). Choosing the trivial decomposition $n_{T_1} = n_1 \prec n_{T_2} = n_T$ (one subtask from root to solution):

$T \leq \frac{w_{< T}}{w_1} \frac{\lambda}{\pi}(n_T).$

This is exactly the LTS bound $\frac{\lambda}{\pi}(n_T)$ multiplied by the factor $\frac{w_{< T}}{w_1}$. If $w_1 = 1$ and most subsequent weights are 0, $w_{< T} \approx 1$ and the bound nearly matches LTS. If many misleading clues receive large weights, $w_{< T}$ could be large, making the bound weaker than LTS. This captures the risk of an uninformative rerooter.

Why LTS is a special case. Set $w_1 = 1$ and $w_t = 0$ for all $t > 1$. Then $w_{< T} = 1$, $w_{T_1} = 1$, and Corollary 12 gives $T \leq \frac{\lambda}{\pi}(n_T)$—exactly the LTS guarantee.

Comparison with the lower bound (Example 13). For the clue environment of Theorem 3, with uniform policy and weights $w_t = 1$ if $n_t$ is a clue, $w_t = 0$ otherwise, choosing the subtask decomposition on all clue ancestors of $n^*$: $q_T$ clue nodes visited by step $T$, so $w_{< T} = q_T$; each $\frac{\lambda}{\pi}(n_{T_{i+1}}; n_{T_i}) \leq 2^{a+1} - 1$ (the cost of searching a perfect binary tree of depth $a$). Corollary 12 gives $T \leq q_T \cdot (2^{a+1} - 1)$. The average-case lower bound is $(q+1)2^{a-1}$, so √lts is within a factor of 4 of optimal without knowing $q$, $a$, or the clue set in advance.

Example 14: Why the full Theorem 11 is sharper. With 6 clue nodes on the path to $n^*$, if the subtask costs are $A < C < B$ (see Figure 3), Corollary 12 gives $T \leq 6B$, suggesting that up to $B$ descendants of each of the 6 clue nodes are visited. Theorem 11's segmented accounting gives $T \leq 3B + 2C + A$: the bounding is tighter because later segments with lower difficulty do not inflate the contribution of earlier segments where fewer clues had been discovered and the weights were less diluted. The more general bound captures that as more clues accumulate, the search becomes more focused.

---

Robustness to Clue Overload: Weight Reparameterization

The naive weight scheme of Example 13 ($w_t = 1$ for each clue) has a fatal flaw: if the total number of clues $q$ is very large or infinite, $q_T$ could be $\Omega(T)$, making the bound $T \leq q_T 2^{a+1}$ vacuous (it doesn't imply $T$ is finite). The bound becomes a tautology rather than a guarantee.

The source of the problem. Unnormalized weights accumulate without bound. If every visited node is a clue (worst case), $w_{< T} = T$, and the bound reads $T \leq T \cdot (\dots)$, which is always true and provides no information about when the solution must be found.

Solution: self-normalizing weights (Example 15). Instead of $w_t = \mathbb{1}[n_t \in \mathcal{N}_q]$, use:

$w_t = \frac{\mathbb{1}[n_t \in \mathcal{N}_q]}{q_t},$

where $q_t$ is the number of clue nodes visited up to (and including) step $t$. The first clue gets weight $1/1 = 1$, the second gets $1/2$, the third $1/3$, etc.

What this does. Since $\frac{1}{q_t} = \frac{q_t - q_{t-1}}{q_t} = 1 - \frac{q_{t-1}}{q_t} \leq \ln \frac{q_t}{q_{t-1}}$, we have:

$w_{< T} = \sum_{t=1}^T w_t \leq 1 + \sum_{t=2}^T \ln \frac{q_t}{q_{t-1}} = 1 + \ln q_T.$

The cumulative weight grows only logarithmically with the number of clues, not linearly. Plugging into Corollary 12 for the clue environment:

$T \leq (1 + \ln q_T) \cdot q_{T_{m-1}} \cdot 2^{a+1} \leq (1 + \ln T) \cdot q_{T_{m-1}} \cdot 2^{a+1},$

which implies $T = \tilde{O}(q_{T_{m-1}} 2^a)$—a finite bound that does not depend circularly on $T$.

The general formulation (Corollary 17). For arbitrary input rerooting weights $\tilde{w}_t \geq 0$, define the transformed weights:

$w_t = \frac{\tilde{w}_t}{\tilde{w}_{\leq t}}, \qquad \text{so that} \qquad w_1 = 1.$

Then:

$w_{< T} = 1 + \sum_{t=2}^{T-1} \frac{\tilde{w}_t}{\tilde{w}_{\leq t}} \leq 1 + \ln \frac{\tilde{w}_{< T}}{\tilde{w}_1},$

and the bound becomes:

$T \leq \left(1 + \ln \frac{\tilde{w}_{< T}}{\tilde{w}_1}\right) \max_{1 \leq i < m} \frac{\tilde{w}_{\leq T_i}}{\tilde{w}_{T_i}} \frac{\lambda}{\pi}(n_{T_{i+1}}; n_{T_i}).$

Key improvement. The factor depending on $T$ is now only logarithmic ($\ln \frac{\tilde{w}_{< T}}{\tilde{w}_1}$), and the factor multiplying each subtask's LTS cost is $\frac{\tilde{w}_{\leq T_i}}{\tilde{w}_{T_i}}$ rather than $\frac{\tilde{w}_{< T}}{\tilde{w}_{T_i}}$. The $\leq T_i$ term does not grow with $T$—it's fixed when the checkpoint $n_{T_i}$ is reached. This means the bound genuinely separates into subtask-local difficulties.

The log factor is tight (Remark 18). Using weights $\tilde{w}_t = \mathbb{1}[n_t \in \mathcal{N}_q] \cdot 2^{q_t}$ in the clue environment gives $\frac{\tilde{w}_{\leq t}}{\tilde{w}_t} = \frac{2^{q_t + 1} - 1}{2^{q_t}} \leq 2$ and $\ln \frac{\tilde{w}_{< T}}{\tilde{w}_1} \leq q_T \ln 2$. The bound becomes $T = O(q_T 2^a) = O(q 2^a)$, matching the lower bound of Theorem 3. The log factor cannot be eliminated in general because it stems from the uncertainty about which clues are on the solution path—the algorithm must observe $q_T$ clues to discover the $m$ helpful ones.

Why this reparameterization is enabled by the off-by-one design. The weight $w_t = \tilde{w}_t / \tilde{w}_{\leq t}$ depends on $\tilde{w}_{\leq t}$, which is the sum of input weights over all steps up to $t$. This quantity is unknown before step $t$—it depends on how many clues are visited between the node's generation and its own visitation. In the naive composition $\tilde{c}$, this would create a circular dependency. But because $c^r$ excludes $n_t$ from benefiting from $w_t$, the weight $w_t$ is only needed after $n_t$ is visited, when $\tilde{w}_{\leq t}$ is known. The off-by-one design is thus essential for making the robust reparameterization possible.

Additional weight schemes (Appendix F). The paper shows that any differentiable increasing function $f$ can transform cumulative input weights: define $w_t = f(\tilde{w}_{\leq t}) - f(\tilde{w}_{\leq t-1})$. Then $w_{< T} = f(\tilde{w}_{< T}) - f(0)$, and the log factor can be replaced by other guarantees. For instance, $f(x) = -1/\ln(e + x)$ gives $w_{< T} \leq 1$ (bounded independent of $T$), at the cost of a larger constant in the subtask term. This flexibility allows practitioners to tailor the robustness guarantee to their domain's characteristics.

4. Key Insights and Innovations

Innovation 1: Reframing Search as a Composition of Weighted Subprocesses, Not a Single Exploration

The dominant paradigm in informed tree search—across A*, Weighted A*, LTS, and MCTS variants—has been to treat search as a single process exploring outward from the root, guided by static side information (a heuristic, a policy, a value function) computed before or during search but applied uniformly regardless of what is discovered along the way. The key conceptual move in this paper is to reframe tree search as a competition among many search processes rooted at different nodes, time-shared according to dynamic, test-time weight assignments. This is not a new heuristic or a better policy-learning method; it is a different way of organizing computation itself during search.

What the field did before. In LTS (Orseau et al., 2018), the policy $\pi$ determines a single cost function $\frac{d}{\pi}$ (or here, $\frac{\lambda}{\pi}$), and best-first search explores in that fixed order regardless of what nodes are visited. If a promising node is discovered deep in the tree, LTS can only reach its descendants by first visiting all nodes with lower $\frac{\lambda}{\pi}$-cost, including vast numbers of nodes unrelated to that discovery. MCTS variants like AlphaZero do dynamically reallocate effort toward promising subtrees, but through a fundamentally different mechanism—backpropagating rewards and using UCB-style exploration bonuses—which the paper shows can lead to catastrophic over-commitment (Appendix A.3) without formal efficiency guarantees. A* and WA* cannot reallocate at all without sacrificing their admissibility-based optimality guarantees (Theorem 19).

What is distinctive here. The paper shows that by maintaining multiple LTS instances rooted at visited nodes and composing their cost functions via a weighted minimum (Lemma 8), a single best-first search queue can implicitly simulate the time-sharing of computation among these instances, with formal step-count guarantees that hold regardless of when or where weights are assigned. The rerooter is not part of the policy—it is a separate channel for side information that the policy cannot encode (or cannot encode without sacrificing its own guarantees). This separation of concerns—the policy handles local action selection, the rerooter handles global resource allocation—is the architectural insight, not any particular implementation detail.

Why this matters beyond this paper. The composition framework (Lemma 8, Lemma 35) is reusable: any future algorithm that needs to combine multiple guided searches with formal guarantees can use this machinery. The idea that weights can be assigned at visitation time and influence future exploration without creating circular dependencies is a design pattern that could apply to stochastic or adversarial settings with appropriate modifications. The paper essentially provides a template for "meta-search" algorithms—algorithms whose job is to orchestrate other search algorithms—with the key theoretical requirement being that the base algorithms expose self-counting cost functions.

Evidence anchor. The proof that the composed cost function $c^r$ is self-counting (via Lemma 8) and that the step bound decomposes into subtask-weighted terms (Theorem 11) demonstrates that this reframing is not merely conceptual—it produces mathematically tractable guarantees where the previous single-process framing produced bounds (like LTS's $2^{99}$ on Example 1) that are exponentially worse than what rerooting achieves.

---

Innovation 2: The Self-Counting Property as a Universal Currency for Step-Count Guarantees

Prior work on LTS (Orseau et al., 2018; Orseau and Lelis, 2021) used the specific cost function $\frac{d}{\pi}$ and proved its specific self-counting property. The conceptual contribution of this paper is to isolate and formalize the self-counting property as the necessary and sufficient abstraction for translating cost into step-count guarantees in best-first search. This is not just a naming exercise—it transforms what was a one-off proof technique into a composable, general-purpose tool.

What the field did before. The standard approach to analyzing best-first search algorithms is algorithm-specific: A* uses admissibility of the heuristic to bound node expansions; LTS uses the particular structure of $\frac{d}{\pi}$ to bound steps; MCTS uses regret analysis. Each analysis is tailored to the algorithm's specific cost function and side information. There was no recognized abstraction that captures why cost functions like $\frac{d}{\pi}$ yield step bounds, while others do not, and no framework for building new cost functions from old ones while preserving that property.

What is distinctive here. Definition 4 and Lemma 5 together establish that for monotone cost functions, "self-counting" is equivalent to "$c(n_t)$ bounds step $t$" —the property that makes the analysis work. This shifts the design problem from "find a cost function that works for my algorithm" to "find a self-counting cost function that assigns low cost to solution nodes." The composition theorem (Lemma 8) then becomes the engine: you can build complex self-counting cost functions from simple ones, and the step-count guarantee follows automatically. The generalization to non-monotone compositions (Lemma 35) extends this to the more complex case that rerooting requires.

The improvement from $\frac{d}{\pi}$ to $\frac{\lambda}{\pi}$ (Section 4.1) is not merely a tighter bound—it is a diagnostic refinement that reveals why the original bound was loose: it double-counted shared ancestors across sibling branches. The slenderness $\lambda(n)$ provides an accounting identity (Lemma 24: summing complementary-policy-weighted slenderness over a tree exactly recovers the node count) that $\frac{d}{\pi}$ lacks. This turns an empirical looseness into a structural understanding.

Significance for algorithm design. Any future algorithm that wants formal step-count guarantees from best-first search need only demonstrate that its cost function is self-counting. This decouples the mechanism of the guarantee (self-counting + BFS = step bound) from the design of the cost function (which encodes domain knowledge, policies, heuristics, etc.). It provides a clear interface: if you can design a self-counting cost function that assigns low cost to desirable nodes, BFS with that cost function will find those nodes quickly, with a provable bound.

Evidence anchor. The proof of Proposition 25 (self-counting property of $\frac{\lambda}{\pi}$) and Lemma 8 (composition) are the formal pillars. Equation (6) shows that $\frac{\lambda}{\pi}$ tightens the bound's ratio to the true node count by a factor of $d(\cdot)$ compared to $\frac{d}{\pi}$, quantifying the structural improvement. Example 7 concretely demonstrates that $\frac{\lambda}{\pi}$ eliminates the double-counting that $\frac{d}{\pi}$ exhibited.

---

Innovation 3: The Subtask Decomposition Bound as a Formalization of Progress-Dependent Search Difficulty

The paper's main guarantee (Theorem 11) is not merely a performance bound—it is a new kind of search guarantee that decomposes the total search cost into contributions from subtasks, where the cost attributed to each subtask depends on the cumulative rerooting weight accumulated before that subtask was reached. This captures a fundamental interaction between exploration and exploitation that has no analog in prior search algorithms.

What the field did before. Standard search guarantees are monolithic: LTS bounds total steps by $1 + d(n^*)/\pi(n^*)$; A* bounds expansions by the number of nodes with $f(n) \leq f(n^*)$. These bounds treat the solution path as an indivisible unit. Even when the problem has natural intermediate milestones, the bound does not reflect that reaching each milestone might be differently difficult or that effort spent before reaching a milestone should not penalize subsequent search as harshly as effort spent after.

What Theorem 11 captures that static bounds miss. Consider two scenarios with the same total solution difficulty: (A) one very hard subtask followed by many easy ones, vs. (B) many subtasks of equal moderate difficulty. The monolithic LTS bound is the same for both. But in √lts, the bound differs: in scenario A, the hard subtask's cost dominates everything, and the weight accumulated during that hard subtask multiplies the costs of all later (easy) subtasks—but since they are easy, the bound remains manageable. In scenario B, the weight accumulation is more gradual, and no single term dominates. The bound adapts to the distribution of difficulty across subtasks, not just the total.

The diagnostic role of $\max_{j \leq i < m}$. The inner maximum in Theorem 11 means that each weight-segment $(w_{<T_{j+1}} - w_{<T_j})$ is multiplied by the hardest remaining subtask from index $j$ onward. This captures the intuition that once you are past the hardest subtask, earlier weight accumulation stops mattering for what remains. The simplified Corollary 12 loses this nuance (it uses $\max_{1 \leq i < m}$ everywhere), which is why Example 14 shows Theorem 11 giving $3B + 2C + A$ while Corollary 12 gives $6B$—a sharper insight into how difficulty concentration shapes the bound.

Why this is conceptually new. This is not just a tighter algebraic manipulation. It formalizes the idea that search difficulty is path-dependent and decomposable, and that an algorithm's guarantee should reflect when along the path the search effort was spent. This connects to ideas from hierarchical planning (where subtasks are solved in sequence) and curriculum learning (where easier subtasks should be mastered first), but translates them into a formal bound on node visits. It suggests that the right way to think about search with side information is not "how hard is the problem?" but "how hard is each subtask, and how much effort was wasted on misleading clues before reaching each one?"

Evidence anchor. Example 14 and Figure 3 concretely illustrate the difference between the sharp (Theorem 11) and simplified (Corollary 12) bounds. The fact that the Sokoban analysis (Appendix H) yields a bound (3,011) within a factor of 2 of the actual node visits (1,853) demonstrates that the subtask decomposition is not just a theoretical artifact—it can produce meaningful, tight estimates when informed by domain-specific clues.

---

Innovation 4: Logarithmic Robustness to Misleading Side Information as a First-Class Design Constraint

The paper identifies and addresses a problem that, to my knowledge, has not been formalized in the search literature: how to design an algorithm whose guarantees degrade gracefully (logarithmically, not linearly) with the volume of uninformative or misleading side information. This is distinct from robustness to noise in heuristics (where A* with inflated heuristics has known guarantees) or robustness to model error (where MCTS with function approximation error has known regret bounds). The issue is specific to dynamic, test-time side information where the algorithm cannot know in advance which signals are helpful.

The problem in concrete terms. In the 1000-Clues environment (Example 1), 999 clues are misleading. If the algorithm allocates equal weight to every clue, it wastes 99.9% of its "attention budget" on dead ends. The lower bound (Theorem 3) says any algorithm must visit $\Omega(q 2^a)$ nodes—the factor $q$ (total clues) cannot be eliminated because the algorithm must explore enough to determine which clues are on the solution path. But can the factor be controlled so the bound doesn't become vacuous when $q$ is large or unknown?

The weight normalization solution (Section 6, Corollary 17). The paper shows that by using self-normalizing weights $w_t = \tilde{w}_t / \tilde{w}_{\leq t}$, the cumulative weight $w_{<T}$ grows only logarithmically with the total input weight, transforming what would be a multiplicative factor of $q$ into an additive log factor. This is not just an algebraic trick—it embodies a principle: each new clue should receive a diminishing share of the remaining attention budget, because earlier clues (even if misleading) already consumed their share. The first clue gets weight proportional to $1/1 = 1$, the tenth clue gets $1/10$, the thousandth gets $1/1000$. The total attention allocated to clues grows as $\ln q$, not $q$.

Why "logarithmic overhead" is the right design target. Remark 18 proves that the log factor is unavoidable in general: by choosing exponentially growing input weights, one can construct environments where the log factor equals $\Theta(q)$, matching the lower bound. This means the self-normalizing scheme is asymptotically optimal in its dependence on $q$—no reweighting can do better without additional assumptions about clue structure. The insight is that the log factor is the price of not knowing which clues are helpful, and this paper's scheme pays exactly that price, no more.

Significance for practical rerooter design. This result provides a safe default for practitioners: even if you do not know how many clues your domain will produce, or how misleading they might be, applying the transformation $w_t = \tilde{w}_t / \tilde{w}_{\leq t}$ ensures that √lts's bound is never worse than a logarithmic factor times the LTS bound. You can be aggressive in assigning high weights to promising nodes without fear of catastrophic breakdown; the normalization caps the damage. This is a robustness guarantee that none of the compared algorithms (A*, LTS, MCTS) provide in the presence of dynamic side information.

Evidence anchor. Example 15 shows the self-normalizing weights transforming the vacuous bound $T \leq q_T 2^{a+1}$ into $T = \tilde{O}(q_{T_{m-1}} 2^a)$, a finite quantity. Corollary 17 generalizes this to arbitrary input weights. Remark 18's construction with $\tilde{w}_t = \mathbb{1}[n_t \in \mathcal{N}_q] \cdot 2^{q_t}$ demonstrates both that the log factor can be reduced to linear in helpful-clue-count with exponentially growing input weights, and that the lower bound of Theorem 3 prevents eliminating it entirely.

5. Experimental Analysis

Evaluation Methodology

Dataset. This paper does not include empirical experiments on benchmark datasets. It is a purely theoretical paper that develops an algorithm (√lts) and proves formal guarantees about its node-visit complexity. The paper provides no experimental results with learned policies or rerooters on any domain.

Base model(s). No machine learning models are trained or evaluated. The "policy" $\pi$ and "rerooter" $w$ are treated as user-provided inputs to the algorithm, not as learned components. The theoretical analysis holds for any policy and any rerooting weight assignment satisfying the stated conditions.

Metrics. The sole metric is number of node visits (steps of best-first search) required to reach a solution node. This is analyzed through formal upper bounds (Theorems 11, Corollary 12, Corollary 17) and compared against a formal lower bound (Theorem 3). There is no runtime measurement, no accuracy metric, and no empirical validation.

Baselines. The paper provides theoretical comparisons against:

• Levin Tree Search (LTS) (Orseau et al., 2018): compared via the bound $T \leq \frac{\lambda}{\pi}(n_T)$ (LTS) vs. $T \leq \frac{w_{<T}}{w_1} \frac{\lambda}{\pi}(n_T)$ (√lts, Equation 16), and more generally via the subtask decomposition comparing product-of-costs (LTS) against max-of-costs (√lts) as shown in Appendix E.
• A and Weighted A** (Hart et al., 1968; Pohl, 1970): analyzed in Appendix A.1, Theorem 19, showing these algorithms require $\Omega(2^{qa/(1+\varepsilon)})$ node visits in constructed environments where √lts requires $O(q 2^a)$.
• Monte Carlo Tree Search variants (UCT, AlphaZero) (Kocsis and Szepesvári, 2006; Silver et al., 2016, 2017b,a): analyzed in Appendix A.3, showing double-exponential or quadratic slowdown relative to breadth-first search in the D-chain and single-misleading-reward environments.
• Breadth-first search: used as an implicit reference point for uninformed search complexity (e.g., $2^{d(n^*)+1}$ nodes for a binary tree of depth $d(n^*)$).

No empirical head-to-head comparisons on shared benchmarks are performed.

Generation budget / compute accounting. The unit of computation is a single node visit (one iteration of the BFS loop: extract minimum-cost node from priority queue, generate children, push into queue). There is no separate accounting for policy evaluation, rerooter evaluation, or cost-function computation; the analysis assumes these are dominated by node generation and tree traversal. The bound relates total node visits $T$ directly to the cost $c^r(n_T)$ of the visited solution node.

Cross-validation / statistical protocol. Not applicable. The guarantees are worst-case or average-case mathematical bounds, not empirical estimates. The lower bound (Theorem 3) uses a randomization argument over the placement of the solution node to establish that any algorithm must visit $\Omega((q+1)2^{a-1})$ nodes on average, and thus also in the worst case.

---

Main Quantitative Results

Since this is a theoretical paper, the "results" are theorems and their instantiations on constructed environments, not empirical measurements. I organize them by the type of guarantee and the environment they analyze.

Theoretical Bounds on Constructed Clue Environments

Headline result: √lts achieves exponential speedup over LTS on problems with informative clue structure.

1000-Clues environment (Example 1, analyzed in Appendix A.2 vs. Example 9). The search space is a perfect binary tree of depth 100, with a single solution node at depth 100 descending from one of 1000 uniformly random clue nodes at depth 50.

• LTS bound (using $\frac{d}{\pi}$): Requires at least $2^{99}$ node visits in the worst case. The analysis (Appendix A.2) shows that all $2^{98+1} - 1$ nodes at depth 98 must be visited before the solution, because non-clue nodes at depth 98 have the same $\frac{d}{\pi}$ cost as clue-descending nodes, and the min-max optimal policy assigns probability 1 only to the single correct branch, yielding $\pi(n^*) = 2^{-98}$.

• √lts bound (Example 9, with uniform weights $w_t = 1$ for clues): $T \leq q_T 2^{a+1}$ where $q_T \leq 1000$ is the number of clues visited, $a = 50$ is the relative depth from clue to solution. This gives $T \leq 1000 \times 2^{51} \approx 2.25 \times 10^{18}$ — still large, but exponentially smaller than $2^{99} \approx 6.3 \times 10^{29}$. The speedup is roughly a factor of $2^{48}$ in the exponent, representing a square-root reduction in the depth exponent (from $2^{100}$ to roughly $q \cdot 2^{50}$).

Lower bound environment (Theorem 3, Section 3). A perfect binary tree where $q$ clue nodes are placed with each clue at depth at most $a$ relative to its closest clue ancestor, and the solution node $n^*$ is chosen uniformly at random among all nodes at depth at most $a$ from any clue. Any search algorithm must visit at least $(q+1)2^{a-1}$ nodes on average.

• √lts upper bound (Example 13): Using unnormalized weights $w_t = \mathbb{1}[n_t \in \mathcal{N}_q]$ and the subtask decomposition on all clue ancestors of $n^*$, Corollary 12 gives $T \leq q_T 2^{a+1}$. Since $q_T \leq q$ (total clues in the tree), this bound is $T \leq q 2^{a+1}$, which matches the lower bound of $(q+1)2^{a-1}$ to within a factor of 4. This establishes that √lts is asymptotically optimal on this class of environments — no algorithm can beat the lower bound, and √lts's upper bound is within a constant factor of it.

What makes this comparison meaningful. The lower bound (Theorem 3) allows the algorithm to know $a$, $q$, and the complete set of clue nodes $\mathcal{N}_q$ in advance. Despite this informational advantage over √lts (which discovers clues only upon visitation), no algorithm can beat $(q+1)2^{a-1}$ on average. √lts achieves $q 2^{a+1}$ without knowing $a$, $q$, or $\mathcal{N}_q$ — it only needs clue membership queries $n \mapsto \mathbb{1}[n \in \mathcal{N}_q]$ at visited nodes. The factor of 4 gap is the price of not knowing the clue set in advance.

Robustness to Clue Overload: Logarithmic vs. Linear Scaling

Headline result: Weight normalization prevents the bound from degrading linearly with the number of misleading clues, replacing a factor of $q$ with $\ln q$.

Infinite-clues environment (Example 15). The same tree structure as Theorem 3, but now the total number of clues $q$ may be very large or infinite. Naive uniform weights $w_t = \mathbb{1}[n_t \in \mathcal{N}_q]$ yield $w_{<T} = q_T$, which could be $\Omega(T)$, making the bound $T \leq q_T 2^{a+1}$ vacuous (it does not imply $T$ is finite, since $q_T \leq T$).

• Self-normalizing weights: Define $w_t = \mathbb{1}[n_t \in \mathcal{N}_q] / q_t$, where $q_t$ is the number of clues visited up to step $t$. Then $w_{<T} \leq 1 + \ln q_T$ (since each term $1/q_t = 1 - q_{t-1}/q_t \leq \ln(q_t/q_{t-1})$, and the sum telescopes).

• √lts bound with self-normalized weights (Example 15): $T \leq (1 + \ln q_T) q_{T_{m-1}} 2^{a+1}$. Since $q_T \leq T$, this implies $T \leq A \ln T$ with $A = q_{T_{m-1}} 2^{a+1}$, which solves to $T \leq 2A \ln A$ (for $A > 0$). The factor multiplying the subtask cost $q_{T_{m-1}} 2^{a+1}$ is now logarithmic in $T$, not linear.

• Why this matters: $q_{T_{m-1}}$ is the number of clues seen before the last helpful clue on the path to $n^*$. This is at most $q$ but does not grow with $T$ once $n_{T_{m-1}}$ is reached. So the bound is genuinely $O(q 2^a \ln(q 2^a))$ — finite and independent of further search. The log factor is the unavoidable price of not knowing which clues are helpful (Remark 18).

Tightness of the log factor (Remark 18). By setting $\tilde{w}_t = \mathbb{1}[n_t \in \mathcal{N}_q] \cdot 2^{q_t}$ and using the transformation $w_t = \tilde{w}_t / \tilde{w}_{\leq t}$, one obtains $\frac{\tilde{w}_{\leq t}}{\tilde{w}_t} \leq 2$ and $\ln(\tilde{w}_{<T}/\tilde{w}_1) \leq q_T \ln 2$. Then Corollary 17 yields $T = O(q_T 2^a) = O(q 2^a)$, matching the lower bound of Theorem 3 exactly (no constant factor gap). This demonstrates that the log factor can be reduced to a constant with exponential input weights, but exponential weights are domain-specific and require knowing the clue structure. In general, the log factor is the cost of not having that knowledge.

Comparison to LTS via the Subtask Decomposition

Headline result: √lts replaces the product of subtask costs in LTS with a maximum, at the price of a weight-ratio factor that is O(1) when the rerooter is informative.

Qualitative comparison (Appendix E). For a subtask decomposition $\{n_{T_i}\}_{i<m}$ of the solution node $n_T$, and omitting the relatively small $\lambda(\cdot)$ terms:

$\text{LTS: } T \leq \prod_{i<m} \frac{1}{\pi(n_{T_{i+1}} \mid n_{T_i})}, \qquad \text{√lts (Corollary 12): } T \leq \max_{1 \leq i < m} \frac{w_{<T}}{w_{T_i}} \frac{1}{\pi(n_{T_{i+1}} \mid n_{T_i})}.$

LTS multiplies the inverse probabilities of each subtask — if there are $m-1$ subtasks each of difficulty $1/\pi \approx 2^a$, the bound is $2^{a(m-1)}$, exponential in the number of subtasks. √lts takes the maximum over subtasks of the weighted inverse probability — the bound is roughly $(\text{weight factor}) \times 2^a$, independent of $m$. When $m$ is large, this is an exponential improvement in $m$.

When does the weight factor degrade? The factor $\frac{w_{<T}}{w_{T_i}}$ is the inverse of the normalized weight $w_{T_i} / w_{<T}$. If the informative checkpoint $n_{T_i}$ received a large fraction of the total weight assigned by step $T$, this factor is small. If most weight went to misleading clues, $\frac{w_{<T}}{w_{T_i}}$ could be large. The robustness analysis (Corollary 17) shows this factor can be bounded by $(1 + \ln(\tilde{w}_{<T} / \tilde{w}_1)) \cdot (\tilde{w}_{\leq T_i} / \tilde{w}_{T_i})$, where the second term does not depend on $T$. So for any fixed $T_i$, the weight penalty is bounded.

Concrete numbers from the Sokoban analysis (Appendix H). While not an empirical experiment, the worked example provides illustrative quantitative comparisons:

• LTS bound: $\frac{\lambda}{\pi}(n^*) = 195{,}879{,}469$ node visits (with a uniform policy on a specific Sokoban level with 4 boxes, solution depth 25).
• √lts with 3 clue types (boxes on goal spots), using the 3-clue subtask decomposition: $T \leq 4 \times \max\{733, 1{,}143{,}408 \times 31, 125{,}496 \times 229, 3{,}024 \times 393\} \leq 141{,}782{,}592$. This is only marginally better than LTS because the M1 and M2 clues are too numerous (the weight normalization $w_t = 1/M_z$ gives too much total weight to misleading clues of type 1 and 2).
• √lts skipping the type-1 clue (subtask decomposition $\{n_1, n_{t_2}, n_{t_3}, n^*\}$): $T \leq 4 \times \max\{7{,}213, 125{,}496 \times 229, 3{,}024 \times 393\} = 114{,}954{,}336$. Still limited by the number of type-2 clues.
• √lts using only the type-3 clue (subtask decomposition $\{n_1, n_{t_3}, n^*\}$): $T \leq 4 \times \max\{795{,}181, 3{,}024 \times 393\} = 4{,}753{,}728$. This is a factor of 40 improvement over LTS ($195.9$ million vs. $4.75$ million).
• With self-normalizing weights $w_t = 1/(1 + q_{k,t})$ (where $q_{k,t}$ counts clues of type $k$ seen up to step $t$): The paper reports that a numerical simulation actually solved the level at $T = 1{,}853$ steps, with $w_{<T} < 3.83$, giving a bound of $T \leq 3.83 \times \max\{733, 9 \times 31, 2 \times 229, 2 \times 393\} \leq 3{,}011$. This predicted bound is within a factor of 2 of the actual step count, and is within a factor of 6 of the cube root of the LTS bound $\frac{\lambda}{\pi}(n^*)$ — representing an exponential-to-polynomial speedup transformation.

---

Comparison to A* and Weighted A* on Clue Environments

Theorem 19 (Appendix A.1). There exist environments with $q$ clue nodes where any algorithm that guarantees returning a solution within a factor $1 + \varepsilon$ of optimal cost must visit $\Omega(2^{qa/(1+\varepsilon)})$ nodes, while √lts (with no depth-optimality guarantee) visits $O(q 2^a)$ nodes.

The constructed environment. All clues descend from one another at relative depth $a$. The first solution node $n^*_1$ descends from the $q$-th clue at depth $qa$. A second solution node $n^*_2$ is placed at depth $\lceil qa/(1+\varepsilon) \rceil - 1$ under the root, not descending from any clue. Since $d(n^*_1) > (1+\varepsilon)d(n^*_2)$, any algorithm with $1+\varepsilon$ bounded-suboptimality guarantee must return $n^*_2$, which requires visiting $\Omega(2^{\lceil qa/(1+\varepsilon) \rceil})$ nodes. √lts, not constrained by depth-optimality, can find $n^*_1$ in $O(q 2^a)$.

What this means quantitatively. If $q = 100$, $a = 10$, and $\varepsilon = 0$ (optimal A*), then WA* requires $\Omega(2^{1000})$ nodes to guarantee optimality, while √lts requires $O(100 \times 2^{10}) = O(10^5)$ nodes. The gap is astronomical. For Weighted A* with $\varepsilon = 1$ (2-approximation), the WA* bound is $\Omega(2^{500})$, still double-exponential in $q$; √lts is unaffected. The essential tradeoff is that bounded suboptimality is incompatible with efficient clue usage; √lts accepts that its solution may be non-depth-optimal to achieve exponential speedups.

---

Comparison to MCTS on the D-Chain and Single-Misleading-Reward Environments

D-chain environment (Appendix A.3.1, Figure 4). A perfect binary tree where intermediate rewards of $(D-1)/D, (D-2)/D, \dots, 1/D$ are placed along a right-branching chain, while the true reward of 1 is at depth $D$ descending from the leftmost branch. All rewards are misleading.

• MCTS (UCT/AlphaZero): Prior work (Coquelin and Munos, 2007; Orseau and Munos, 2024) shows these algorithms take double-exponential time with $D$ to find the solution, because they over-commit to the high-reward (but misleading) subtree.

• √lts (uniform policy, $w_t =$ reward, self-normalized): The paper analyzes that $w_{<T} \leq (D+1)/2$ (since $w_1 = 1$ and subsequent rewards sum to $(D-1)/2$). With $n^*$ at depth $D$, $\frac{\lambda}{\pi}(n^*; n_1) = 2^{D+1} - 1$. From Equation 16: $T \leq (D+1)2^D$, which is only a logarithmic factor worse than breadth-first search's $2^{D+1}$.

• If $n^*$ descends from the first reward node at depth 2: √lts's bound becomes $T \leq 2(D+1)2^{D/2}$ using the subtask decomposition — the square root of breadth-first search's cost, because the rerooter correctly identifies the helpful clue.

Single misleading reward (Appendix A.3.2). One child of the root has reward $\alpha \in (0,1)$ (misleading), the solution $n^*$ with reward 1 descends from the other child, which has no reward.

• AlphaZero: The analysis shows that $T = \Omega((\alpha 2^{d(n^*)-1})^2)$ — quadratic in the breadth-first search cost.
• √lts: $T \leq (1 + \alpha) 2^{d(n^*)+1}$ — only a factor $(1 + \alpha)$ worse than BFS. For $\alpha = 0.5$, AlphaZero takes $\Omega(2^{2d(n^*)-2})$ while √lts takes $O(1.5 \times 2^{d(n^*)+1})$; the difference is exponential in $d(n^*)$.

---

Ablation Studies and Robustness Checks

The paper does not have traditional experimental ablations, but it does explore how different weighting schemes and design choices affect the theoretical bounds. These serve a similar function to ablations in an empirical paper.

Naive uniform weights ($w_t = 1$ for clues) vs. self-normalizing weights ($w_t = 1/q_t$): Example 9 vs. Example 15. The naive scheme gives $T \leq q_T 2^{a+1}$, which becomes vacuous when $q_T = \Omega(T)$. The self-normalizing scheme adds only a logarithmic factor $\ln T$ (or $\ln q_T$). The paper demonstrates this analytically — the bound's dependence on $T$ shifts from potentially linear to logarithmic. The cost is that earlier clues get higher weight than later ones (first clue gets weight 1, tenth gets 1/10), which may slow convergence if the first clues are misleading. But the bound remains finite regardless.

Corollary 12 (simplified) vs. Theorem 11 (sharp) bound (Example 14, Figure 3): The simplified bound gives $T \leq 6B$, while Theorem 11 gives $T \leq 3B + 2C + A$ for a path with costs $A < C < B$. The sharp bound captures that weight spent before reaching tougher subtasks should not be multiplied by the difficulty of those tougher subtasks beyond what is strictly necessary. This matters when the hardest subtask is early in the decomposition (in which case Corollary 12 is nearly tight) versus late (in which case Theorem 11 is significantly tighter). No empirical measurement of this gap is provided; it is an analytic comparison.

Rooted LTS cost $\frac{\lambda}{\pi}$ vs. original LTS cost $\frac{d}{\pi}$ (Section 4.1, Appendix B): The slenderness cost function tightens the self-counting bound by a factor of $d(\cdot)$ (the depth). Example 6 and 7 (Figure 2) illustrate: for a chain that branches into two children, $\frac{d}{\pi}$ overcounts by a factor of roughly 2 because it double-counts shared ancestors; $\frac{\lambda}{\pi}$ exactly recovers the correct node count. The lower bound (Equation 6) shows $|\mathcal{N}_\theta| > (\theta - 1)/B$, so the gap between upper and lower bounds is $O(B)$ for $\frac{\lambda}{\pi}$ vs. $O(B d(\cdot))$ for $\frac{d}{\pi}$. This is a direct improvement to the base cost function that √lts inherits from LTS.

Complementary policy definition and Lemma 24 (self-counting proof technique): This is not an ablation per se, but the paper's choice to prove self-counting via the complementary policy $\pi'$ (Definition 22) — rather than via direct counting as in Orseau et al. (2018) — is what enables the exact accounting identity $|\mathcal{N}'| = \sum_{n \in \mathcal{N}'} \frac{\pi'(n)}{\pi(n)} \lambda(n)$. This technique reveals why $\frac{\lambda}{\pi}$ is tight (every unit of "responsibility" corresponds to exactly one node) and generalizes the proof structure that Lemma 35 later uses for composed cost functions.

Weight transformation functions (Appendix F, Example 40): Different choices of the transformation $f$ in $w_t = f(\tilde{w}_{\leq t}) - f(\tilde{w}_{\leq t-1})$ produce different robustness profiles. $f(x) = x$ yields the naive scheme (no normalization). $f(x) = \ln(1+x)$ yields $w_{<T} \leq \ln(1 + \tilde{w}_{<T})$ — logarithmic growth, as in Corollary 17. $f(x) = -1/\ln(e + x)$ yields $w_{<T} \leq 1$ (bounded independent of $T$), but at the cost of larger constant factors in the subtask term ($(e + \tilde{w}_{\leq T_i}) \ln^2(e + \tilde{w}_{\leq T_i})$). This is analogous to an algorithmic hyperparameter: how aggressively to suppress the weight of later clues. The paper does not provide empirical guidance on choosing $f$; it only characterizes the theoretical tradeoff.

Tie-breaking between $c^r$ and $c^{\max}$ (Section 5): The paper's decision to analyze $c^r$ (non-monotone) rather than $c^{\max}$ (monotone) is justified analytically: $c^{\max}$ forces many nodes with distinct $c^r$ costs to share the same cost, losing information about which rerooted instance they belong to. The tighter bound of Theorem 11 relies on Lemma 35 (which handles non-monotone SCCF compositions) and would be looser if derived from $c^{\max}$. There is no experimental comparison of the two cost functions' practical performance; the argument is purely theoretical.

Root-only LTS ($w_1 = 1$, $w_t = 0$ for $t > 1$) as a special case: Setting $w_1 = 1$ and all other weights to 0 collapses √lts to exactly LTS, with the bound $T \leq \frac{\lambda}{\pi}(n_T)$ from Equation 16. This is both a sanity check (√lts strictly generalizes LTS) and a demonstration that the rerooter can always be "turned off" if it provides no useful information, with no penalty. The robustness guarantee of Corollary 17 means that even with an arbitrary rerooter, the bound degrades by at most a $\ln(\tilde{w}_{<T} / \tilde{w}_1)$ factor.

---

Critical Assessment

This paper's central claims are theoretical existence proofs, not empirical demonstrations. The appropriate critical assessment is therefore: do the theorems prove what they claim to prove, and do the constructed environments fairly represent the conditions under which the claims are meaningful?

Claim: "√lts achieves exponential speedup over LTS in the best case with $q$ rerooting points, taking $O(q \sqrt[q]{T})$ steps where LTS takes $T$."

This claim is theoretically supported by the comparison in Appendix E and the specific environments analyzed. On the 1000-Clues environment, LTS requires $\Omega(2^{99})$ nodes while √lts requires $O(1000 \times 2^{50})$ — the speedup is from an exponent of 99 to an exponent of roughly 50, which is exponential in the depth. On the D-chain, √lts achieves $O((D+1)2^D)$ vs. MCTS's double-exponential, which relative to the uninformed baseline is a poly-to-exponential improvement.

However, the claim depends critically on the phrase "in the best case." The "best case" requires:

1. The rerooter assigns high weight to nodes on the solution path and low (or zero) weight to all other nodes. In Example 9, this is achieved by $w_t = 1$ for clues on the path and $w_t = 0$ everywhere else. If the rerooter assigns weight indiscriminately to every node, $w_{<T} = T$ and the bound collapses to the LTS bound (or worse). The speedup is not automatic — it requires an informative rerooter.

2. The total number of clues $q$ is not too large relative to the number of helpful clues $m$. If $q = \Omega(2^{am})$ — that is, clues are so numerous that the tree is saturated with them — the factor $q$ in the bound overwhelms any advantage from subtask decomposition (Example 9's worst case). The lower bound (Theorem 3) proves this is unavoidable: when clues are numerous and uniformly distributed, the distinction between helpful and misleading clues is information-theoretically expensive to resolve.

3. The policy $\pi$ itself must be competent enough that subtask costs $\frac{\lambda}{\pi}(n_{T_{i+1}}; n_{T_i})$ are manageable. If the policy assigns exponentially small probability to the path between checkpoints, the LTS cost within each subtask is exponentially large, and no amount of rerooting can compensate. Rerooting redistributes effort among subtasks; it does not reduce the intrinsic difficulty of any single subtask.

These conditions are not hidden — the paper states them explicitly through the form of the bounds — but they mean that the practical value of √lts hinges on the ability to learn or design good rerooters, a problem the paper explicitly leaves to future work. The theoretical result shows what is possible; it does not demonstrate what is achievable with current learning methods.

Claim: "The number of node visits is competitive with the best decomposition into subtasks, at the price of a factor that relates to the uncertainty of the rerooter."

The factor is quantified as $\frac{w_{<T}}{w_{T_i}}$ in Corollary 12, or $\frac{\tilde{w}_{\leq T_i}}{\tilde{w}_{T_i}} \times (1 + \ln \frac{\tilde{w}_{<T}}{\tilde{w}_1})$ in Corollary 17. The "uncertainty" interpretation is accurate: if the rerooter is perfectly confident and assigns all weight to the solution-path checkpoints, $w_{<T} / w_{T_i} = m-1$ (the number of checkpoints, a small constant). If the rerooter is maximally uncertain and assigns equal weight to every clue, the factor becomes $q$ (linear in total clues) under naive weighting, or $\ln q$ under self-normalized weighting.

Genuine weakness: The metric of "competitiveness" is qualitative, not quantitative. The paper compares √lts's bound to an idealized decomposition where each subtask's cost is exactly $\frac{\lambda}{\pi}(n_{T_{i+1}}; n_{T_i})$ without cross-subtask interference. This idealized baseline is not itself a real algorithm — it assumes one could magically start an independent LTS from each checkpoint without paying the search cost to reach that checkpoint in the first place. √lts pays exactly that cost through the cumulative weight terms. So √lts is "competitive" in the sense that its bound differs from the idealized bound by the weight-ratio factor, but this is a bound-to-bound comparison, not a comparison against a competing real algorithm with different guarantees.

What would strengthen this claim: A direct comparison against the optimal oracle strategy — an algorithm that knows the clue set $\mathcal{N}_q$ and the depth $a$ in advance — showing that √lts's worst-case overhead over that oracle is at most logarithmic. This is partially addressed by Remark 18 and the lower bound of Theorem 3: the oracle lower bound is $(q+1)2^{a-1}$, and √lts's upper bound is $q 2^{a+1}$ (without normalization) or $O(q 2^a \ln q)$ (with self-normalization), both within constant/log factors of the lower bound. But this oracle knows $q$ and $a$; a stronger oracle might also know which clues are on the solution path (the $m$ helpful ones among the $q$ total). The lower bound in Theorem 3 does not distinguish between algorithms that know $m$ and those that do not, because it randomizes the solution location uniformly over all clue-relative positions. A finer-grained lower bound distinguishing $m$ from $q$ would clarify whether √lts's factor of $q$ (or $\ln q$) is truly optimal.

Claim: "Like LTS, the policy and rerooter can be learnt from data."

This claim is not supported by any experiments or theoretical analysis in the paper. It is stated as motivation and expectation (Section 1: "we expect that the rerooter may be learnt from data or designed by the user, but this is beyond the scope of this paper"). The paper does not:

• Propose a learning objective for the rerooter.
• Analyze the sample complexity of learning a rerooter from data.
• Show that a learned rerooter preserves the theoretical guarantees (the guarantees assume the rerooter is an exogenous input, not itself learned).
• Compare learned-rerooter √lts against learned-policy LTS on any domain.

This is the most significant gap between the paper's theoretical contribution and its practical aspirations. The theorems hold for any rerooter, but whether a rerooter that is good enough to realize exponential speedups can be learned efficiently is entirely open. The Sokoban example (Appendix H) uses a hand-designed rerooter based on domain knowledge (counting boxes on goal spots), and even then, the bound improves over LTS only when the less informative clue types (1 and 2 boxes) are ignored. Designing or learning a rerooter that automatically downweights uninformative clues is non-trivial.

Missing empirical validation. The paper provides no experiments whatsoever on benchmark search problems. There is no comparison of √lts against LTS, A*, or MCTS on standard planning domains, puzzle benchmarks, or theorem-proving tasks. The Sokoban analysis is a back-of-the-envelope calculation, not a controlled experiment. The paper's positioning as a theoretical contribution is clear, but the absence of even a single empirical demonstration — even on a toy domain — makes it difficult to assess whether the constants hidden in the asymptotic bounds are favorable, whether the cost-function computation overhead (Appendix G) is negligible or dominant in practice, and whether the non-monotonic cost function causes pathological queue-ordering behavior that degrades performance relative to the bound.

Missing ablations that would strengthen the theory. Several theoretical "ablations" could clarify the contribution:

• What if we used $\frac{d}{\pi}$ (original LTS) instead of $\frac{\lambda}{\pi}$ for the base cost functions? The paper claims $\frac{\lambda}{\pi}$ is tighter, but does not analyze how much of the exponential speedup is due to the tighter base cost vs. the rerooting mechanism. If the speedup is primarily from $\frac{\lambda}{\pi}$, then the rerooting contribution is overstated.

• What if we composed LTS instances using the harmonic mean instead of the minimum (Remark 32)? The paper notes that the harmonic mean fails to preserve self-counting in general, but does not explore whether it works in restricted settings or provides empirical advantages.

• What is the actual runtime overhead of the $O(|A(n_k)|)$ cost computation (Appendix G)? The optimization requires maintaining an active set of non-dominated ancestors, and Lemma 41 provides a pruning condition. But the size of this active set in the worst case (with complex weight patterns) is not analyzed, nor is the amortized cost of the pruning step.

Conditional nature of the claims. The paper's results hold under specific, clearly stated conditions:

• The domain must be deterministic with a tree-structured state space. Transpositions (multiple paths to the same state) are not handled, and the bounds would not directly apply to DAG search.
• The policy $\pi$ must be proper (probabilities sum to at most 1 at each node) for the self-counting property to hold. This is standard for LTS but limits the class of policies.
• The rerooting weights must be non-negative and assigned at node visitation time. They can depend on arbitrary observable information but cannot be revised retroactively.
• The solution must be unique or first-found: the bounds hold for the first solution node visited, not for returning an optimal or best solution among many.
• The guarantees are on node visits, not wall-clock time. The priority queue operations, cost-function updates, and rerooter evaluations are assumed to be $O(1)$ or otherwise negligible.

Bottom line. The theorems prove — convincingly and rigorously — that there exists an algorithm with formal guarantees that decomposes search effort across subtasks in proportion to dynamic weight assignments. The exponential-speedup claim holds when the rerooter provides high-weight signals at helpful checkpoints and low-weight signals elsewhere. The robustness claim (logarithmic degradation) holds under the self-normalizing weight transformation. What remains unproven is whether such rerooters can be obtained for real problems without hand-engineering, and whether the theoretical constants translate to practical speedups. These are empirical questions that the paper explicitly defers.

6. Limitations and Trade-offs

The Rerooter Must Be Hand-Designed or Learned — Neither Is Demonstrated

The assumption or constraint. √lts treats the rerooter $w$ as an exogenous input, like the policy $\pi$, but unlike the policy — for which LTS provides a learning objective (Orseau and Lelis, 2021; Orseau et al., 2023) — the paper provides no method, objective, or theory for learning a rerooter from data. The authors acknowledge this explicitly:

"Like the LTS policy, we expect that the rerooter may be learnt from data or designed by the user, but this is beyond the scope of this paper" (Section 1).

The paper's only concrete instantiation is the hand-designed Sokoban rerooter in Appendix H, which uses domain-specific knowledge (counting boxes on goal spots, computing the combinatorial number of states with $z$ boxes on goals) that is problem-specific and manually engineered.

The consequence. The exponential speedups the paper proves are conditional on having an informative rerooter. The gap between "proves what is possible with a good rerooter" and "provides a method to obtain a good rerooter" is the central practical obstacle to deploying √lts. Without a learning procedure, a practitioner faces two unappealing options: (a) hand-design rerooters per domain, which requires deep domain knowledge and may not scale to complex problems where informative clues are hard to identify a priori; or (b) guess at rerooting weights, which the robustness analysis (Section 6) shows degrades the bound gracefully (logarithmically), but only in the worst-case sense — a random rerooter provides no speedup.

More subtly, even if a learning procedure existed, the paper offers no analysis of generalization: the guarantees hold for whatever weights the rerooter actually assigns at test time, but if the rerooter is learned on training problems and applied to novel test problems, its weight assignments may be miscalibrated. There is no theory linking training-distribution rerooter quality to test-distribution guarantees.

What evidence exists in the paper. The Sokoban example (Appendix H) is the only illustration of a concrete rerooter. It shows that even with careful hand-design, the rerooter's quality matters enormously:

• Using all three clue types (1, 2, 3 boxes on goals): bound improves only marginally over LTS ($141.8$ million vs. $195.9$ million, a ~28% reduction).
• Skipping the less informative type-1 clue: bound decreases to $115.0$ million (~41% reduction).
• Using only the most informative type-3 clue: bound drops to $4.75$ million (factor of ~40 improvement over LTS).
• Self-normalizing weights with per-clue-type tracking: actual solve at $1{,}853$ steps, bound of $3{,}011$ (factor of ~$65{,}000$ improvement over LTS).

This progression demonstrates that rerooter design is nontrivial — the best result required ignoring the majority of available clues (types 1 and 2) and using a carefully tuned weight normalization scheme. There is no automatic method for making these choices.

Mitigation status. Not addressed. The paper suggests learning as future work, but provides no algorithmic scaffold for doing so (e.g., a loss function, a training procedure, or an analysis of what properties a learned rerooter must satisfy to preserve the theoretical guarantees). The robustness reparameterization (Corollary 17) ensures that a poorly designed rerooter does not cause catastrophic failure, but it does not make a weak rerooter strong.

---

The Difficulty Estimation (Clue Discovery) Overhead Is Not Accounted For

The assumption or constraint. The rerooting weights $w_t$ are assigned at node visitation time and can depend on any information available up to step $t$, including "features of the current and previously-visited nodes" (Section 2). However, the paper's analysis treats the weight assignment as instantaneous and costless — the bound counts only node visits (BFS iterations), not the computational cost of evaluating the rerooter. For many natural rerooters — particularly those that inspect the current state for clue membership — this evaluation may involve non-trivial computation (e.g., checking whether a partially completed proof contains a useful lemma, or whether a Sokoban state has $z$ boxes on goals).

The consequence. If the rerooter evaluation is expensive (e.g., requiring a neural network forward pass, or a combinatorial check), the wall-clock time per node visit increases, and the relationship between node-visit bounds and actual runtime weakens. This is not a flaw in the theoretical bound — node visits are the natural unit for tree search analysis — but it means the exponential speedup in node visits may not translate 1:1 to exponential speedup in wall-clock time if the rerooter is expensive and is called at every visited node.

A deeper issue: the paper's motivating examples (1000-Clues, D-chain, Sokoban) involve clue checks that are computationally trivial (testing membership in a known set of nodes, observing a reward value, counting boxes on goals). But for the motivating real-world applications (automated theorem proving, where a clue fires when a "hopefully-helpful lemma is found"; constraint satisfaction, where a clue fires "when some difficult constraints are satisfied"), evaluating clue membership may itself be a hard subproblem. In the limit, if recognizing a clue is as hard as recognizing a solution, the rerooter provides no computational advantage — it merely shifts the difficulty from search to evaluation.

What evidence exists in the paper. None. The paper provides no analysis of rerooter computational cost, no discussion of how clue-checking complexity scales with problem size, and no comparison of node-visit speedups vs. wall-clock speedups. The cost-function optimization in Appendix G addresses only the overhead of computing $c^r(n)$ from known weights, not the overhead of computing the weights themselves. The paper acknowledges a related but distinct cost issue — the difficulty estimation cost in another context — only in passing, noting that the off-by-one design ensures the weight $w_t$ need not be known when $n_t$ is generated, but saying nothing about the cost of computing $w_t$ when $n_t$ is visited.

Mitigation status. Not addressed. A practitioner would need to assess whether the per-node rerooter cost is amortized by the reduced node count. For domains where clues are cheap to evaluate (e.g., checking whether a board state satisfies a simple predicate), this overhead is negligible. For domains where clue evaluation requires substantial computation, the tradeoff may be unfavorable. The paper provides no framework for analyzing this tradeoff.

---

Deterministic Tree Assumption Excludes DAGs, Transpositions, and Stochastic Environments

The assumption or constraint. The entire analysis assumes a deterministic tree-structured search space where each node has a unique parent and there are no transpositions (multiple paths to the same state). The formalism defines $\text{par}(n)$ as the single parent of $n$ and builds all guarantees on the tree structure: $\text{anc}(n)$, $\text{desc}(n)$, and the policy as a distribution over children at each parent. The paper states this scope explicitly:

"We are interested in tree search algorithms for deterministic domains" (Section 1).

And in the conclusion:

"While many search domains are deterministic in nature (e.g., theorem proving, many games, program synthesis, etc.), it could be valuable to extend √lts to tackle stochastic domains" (Section 7).

The consequence. Many practical search problems involve transpositions (directed acyclic graphs, DAGs). In Sokoban, the same board state can be reached through different action sequences. In theorem proving, the same intermediate lemma can be derived in multiple ways. In classical planning, different action orderings can produce identical states. When transpositions exist, the tree assumption overcounts nodes — the same state appears as multiple distinct nodes in the tree. The self-counting property (Definition 4) counts tree nodes, not distinct states, so the $\frac{\lambda}{\pi}$ bound — and all √lts bounds derived from it — can be loose by a factor equal to the average number of distinct paths to each state. This is not a failure of the bound (the algorithm still visits at most the bounded number of tree nodes), but it means the bound's relationship to problem difficulty weakens: a problem with many transpositions may have a large tree-node count but a small state-space size, and the bound will be pessimistic.

For stochastic environments, the entire framework breaks down because the policy $\pi$ is no longer solely under the algorithm's control — the environment may transition to states the policy assigned low probability. The self-counting cost function $\frac{\lambda}{\pi}$ relies on the policy probabilities being normative (determining where search effort goes), not descriptive (predicting environment dynamics). Extending to stochastic domains would require a fundamentally different cost structure.

What evidence exists in the paper. The Sokoban analysis (Appendix H) explicitly acknowledges this issue:

"Multiple nodes in the search tree may correspond to the same states... Full transposition tables — to ensure visiting each state only once — likely takes about half this number of node visits on average."

The analysis then uses a policy that avoids undoing the previous action "unless a box has been pushed," which is a weak form of transposition avoidance but does not prevent revisiting states through longer cycles. The bounds are computed on tree nodes, not distinct states, so the $T \leq 3{,}011$ bound and the $T = 1{,}853$ actual solve count refer to tree-node visits, not distinct-state visits. With full transposition detection, the actual number of state visits would be lower, potentially by a significant factor.

Mitigation status. Not addressed for the core theory. The paper suggests extending to stochastic domains as future work (Section 7) but does not discuss DAGs or transpositions. A practitioner implementing √lts on a domain with transpositions could add a transposition table to prune duplicate states, but (a) the theoretical bounds would no longer directly apply (they would overcount), and (b) the rerooting mechanism interacts nontrivially with transpositions — if the same state is reached through two different paths with different weights, which rerooting instance "owns" the state? The paper provides no guidance.

---

No Depth- or Cost-Optimality Guarantees — Only "Find Some Solution"

The assumption or constraint. √lts inherits from LTS the guarantee of finding a solution node, with no claim about the quality (depth, cost, optimality) of that solution. The paper's statement of the guarantee is:

"Our upper bounds hold for every node visited before the algorithm stops, irrespective of the stopping criterion used" (Remark 2).

This means the bound $T \leq \dots$ applies to the $T$-th visited node $n_T$, but $n_T$ could be an arbitrarily deep or costly solution. √lts does not preferentially search for shallower solutions; it searches according to the cost function $c^r$, which balances policy guidance and rerooting weights but has no built-in preference for solution quality.

The consequence. Theorem 19 (Appendix A.1) formalizes the tradeoff: bounded suboptimality is incompatible with efficient clue usage. Weighted A* can guarantee a solution within factor $1+\varepsilon$ of optimal cost but requires $\Omega(2^{qa/(1+\varepsilon)})$ node visits in clue environments. √lts requires only $O(q 2^a)$ node visits but may return a solution that is depth-optimal or may return one that is $qa/(1+\varepsilon)$ times deeper than the shallowest solution — the gap can be arbitrarily large depending on clue placement.

This is a fundamental tradeoff, not an oversight. But it means √lts cannot be used when solution quality matters — e.g., in cost-minimizing planning, shortest-path problems, or anytime settings where the first solution's quality bounds subsequent search. The algorithm might find a solution at depth $qa$ while a depth-optimal solution at depth $qa/(1+\varepsilon)$ exists but is never visited because it does not descend from any clue node. The paper constructs exactly such environments (Theorem 19 proof) to demonstrate that any algorithm retaining bounded-suboptimality must be exponentially slower.

For domains where the only objective is finding any solution (e.g., proving a theorem, finding any satisfying assignment, solving a puzzle), this tradeoff is acceptable. For domains where solution cost matters (e.g., robot motion planning, resource-constrained scheduling), it is disqualifying without modification.

What evidence exists in the paper. Theorem 19 and its proof (Appendix A.1) provide a formal separation: for any $\varepsilon \geq 0$, there exist environments where bounded-suboptimal algorithms require double-exponential time while √lts requires only single-exponential time, because √lts accepts potentially unbounded suboptimality. The environments are constructed adversarially — a shallow solution is placed off the clue path — but they illustrate the structural impossibility of achieving both guarantees simultaneously.

Mitigation status. Not mitigated. The paper positions this as a feature (efficiency at the cost of optimality), not a bug, and the lower bound (Theorem 3) shows it is information-theoretically necessary. A practitioner who needs bounded suboptimality has no recourse within the √lts framework — they must use Weighted A* and accept potentially exponential slowdown, or use a hybrid approach (e.g., run √lts to find a solution quickly, then use its depth as a bound for A*). The paper mentions no such hybridization.

---

The Slenderness Cost Function Improvement Is Significant but Domain-Dependent

The assumption or constraint. The paper replaces LTS's $\frac{d}{\pi}$ cost function with the tighter $\frac{\lambda}{\pi}$ (Section 4.1), proving that the ratio between upper and lower bounds improves by a factor of $d(\cdot)$ (the depth). However, the actual magnitude of this improvement depends on the structure of the policy and the tree, and the paper does not characterize the conditions under which the improvement is large versus negligible.

The consequence. The slenderness improvement is most significant when the policy assigns highly non-uniform probabilities across children at nodes with many children. In Example 20 (Appendix B.1), if the policy assigns probabilities $p$ and $1-p$ to left and right children, $\frac{\lambda}{\pi}(n) \leq \max\{1/p, 1/(1-p)\} / \pi(n)$ compared to $\frac{d}{\pi}(n) = (\ell+r)/\pi(n)$. The slenderness bound replaces the depth factor $(\ell+r)$ with $\max\{1/p, 1/(1-p)\}$ — which is a constant (independent of depth) if $p$ is bounded away from 0 and 1. But if the policy is nearly uniform ($p \approx 1/2$ in a binary tree), the slenderness improvement is only a factor of 2, and if the tree has low branching factor, the depth factor $d(n)$ is not large to begin with.

For the Sokoban example (Appendix H), the slenderness improvement is modest because the policy is approximately uniform among valid moves (3–4 choices per node), so $\frac{\lambda}{\pi}$ and $\frac{d}{\pi}$ differ by roughly a factor equal to the number of children per node, not the full depth. The bulk of the speedup (factor of ~40 to ~65,000) comes from rerooting, not from the tighter base cost function.

More subtly, the choice of cost function interacts with the rerooting mechanism: because $\frac{\lambda}{\pi}$ telescopes cleanly (Lemma 28) while $\frac{d}{\pi}$ does not (Appendix B.3, the offending term in red), the slenderness cost function is structurally necessary for the efficient incremental cost updates in Appendix G and for Lemma 41's ancestor-pruning condition. Without $\frac{\lambda}{\pi}$, the rerooting composition would be computationally more expensive to evaluate per node. So the choice is not merely a tighter bound; it enables the algorithm to operate efficiently.

What evidence exists in the paper. Example 6–7 (Figure 2) illustrate the double-counting problem and its fix on a minimal example (chain branching to two children). Example 20 provides the bound for non-uniform left/right policies. Example 21 shows that for uniform policies on depth-dependent branching trees, $\frac{\lambda}{\pi}(n)$ exactly equals the number of nodes of depth at most $d(n)$ — a perfect accounting where the self-counting bound is tight. But no general characterization is given for when $\frac{\lambda}{\pi}$ is near-tight versus loose. The lower bound (Equation 6) shows the gap is $O(B)$ where $B$ is the average branching factor, but $B$ is a property of the explored subtree, not known a priori.

Mitigation status. Partially addressed by Appendix B.1, which provides the bound refinement for binary asymmetric policies (Example 20) and for depth-dependent branching with uniform policies (Example 21). But the analysis is per-structure, not a general theorem. A practitioner choosing between implementing $\frac{d}{\pi}$ (simpler) and $\frac{\lambda}{\pi}$ (tighter but requires maintaining $\lambda$ values) has no easy test for whether the complexity is warranted. The paper implicitly argues for $\frac{\lambda}{\pi}$ by showing it is never worse and sometimes much better, but the implementation cost is not discussed.

---

The Log-Factor Robustness Guarantee Applies Only to Cumulative Weight, Not Subtask Costs

The assumption or constraint. The robustness analysis (Section 6, Corollary 17) shows that the factor $w_{<T}$ in the simplified bound can be controlled to grow only logarithmically with the total input weight $\tilde{w}_{<T}$ through the reparameterization $w_t = \tilde{w}_t / \tilde{w}_{\leq t}$. This prevents the bound from becoming vacuous when many clues are present.

The consequence. However, the logarithmic control applies only to the cumulative-weight factor, not to the subtask cost terms $\frac{\tilde{w}_{\leq T_i}}{\tilde{w}_{T_i}} \frac{\lambda}{\pi}(n_{T_{i+1}}; n_{T_i})$. The factor $\frac{\tilde{w}_{\leq T_i}}{\tilde{w}_{T_i}}$ depends on how much weight was assigned to other nodes before reaching the checkpoint $n_{T_i}$, not merely on the weight of $n_{T_i}$ itself. If a misleading clue receives a weight comparable to or larger than the helpful checkpoint's weight, this factor inflates the subtask cost.

Concretely, if the first visited clue is misleading and receives weight $\tilde{w} = 1000$ (because it looks promising), while the second visited clue (on the solution path) receives weight $\tilde{w} = 1$ (because it is less distinctive), then $\frac{\tilde{w}_{\leq T_2}}{\tilde{w}_{T_2}} \approx 1001$, multiplying that subtask's LTS cost by three orders of magnitude. The self-normalization $w_t = \tilde{w}_t / \tilde{w}_{\leq t}$ controls the total weight accumulation (the outer log factor), but does not prevent a poorly calibrated rerooter from assigning wildly disproportionate weights that inflate individual subtask terms.

This is particularly relevant if the rerooter is learned: a learned rerooter may confidently assign high weight to patterns that correlate with solution paths in training but are misleading in a particular test instance. The robustness guarantee ensures the bound does not become infinite, but the constant factor could be large enough to erase any practical speedup.

What evidence exists in the paper. Example 15 and the Sokoban analysis implicitly rely on the rerooter assigning higher weight to more informative clues and lower weight to less informative ones. In the Sokoban case, this was achieved by setting $w_t = 1/M_z$ where $M_z$ (the estimated number of clues of type $z$) decreases sharply with $z$ ($M_1 = 1{,}143{,}408$, $M_2 = 125{,}496$, $M_3 = 3{,}024$). This naturally gives higher weight to rarer, more informative clues. But a rerooter that assigns high weight to any clue — without estimating its frequency — would produce large $\frac{\tilde{w}_{\leq T_i}}{\tilde{w}_{T_i}}$ factors. The paper does not analyze sensitivity to miscalibrated weight magnitudes.

Mitigation status. Not addressed. The robustness analysis controls only the outer logarithmic factor from weight accumulation; the subtask-specific weight ratios $\frac{\tilde{w}_{\leq T_i}}{\tilde{w}_{T_i}}$ remain sensitive to the relative magnitudes of $\tilde{w}$ values. A practitioner designing a learned rerooter would need to ensure not just that helpful nodes get positive weight, but that their weight is large relative to the cumulative weight of previously visited nodes — a stronger condition that the paper does not formalize or provide learning guidance for.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper introduces a new category of search algorithm guarantee: bounds that decompose a solution path into subtasks and scale with the maximum weighted difficulty of any subtask, rather than the product of all subtask difficulties or the total problem difficulty. This is not an incremental improvement to an existing bound — it is a different shape of guarantee, one that reflects the insight that search effort should not be penalized multiplicatively for having passed through intermediate milestones. The conceptual shift is from thinking of search as a single monolithic process to thinking of it as a time-shared composition of subprocesses, where the allocation of computation among subprocesses is itself part of the algorithm's design and analysis.

What makes this more than a new algorithm. The self-counting cost function framework (Definition 4, Lemma 5, Lemma 8) provides a reusable abstraction layer for designing and analyzing search algorithms with formal step-count guarantees. Prior to this work, the connection between cost functions and step bounds was algorithm-specific: LTS proved its particular $\frac{d}{\pi}$ cost was self-counting, but the concept of self-counting as the necessary and sufficient property for translating cost to step count was not isolated. By formalizing this abstraction, the paper makes it possible to design new search algorithms by composing self-counting cost functions — a form of algorithmic algebra — and immediately obtain step-count guarantees from the composition theorem (Lemma 8) without re-proving the bound from scratch. This lowers the barrier to entry for designing provably efficient search algorithms: one need only demonstrate that the base cost functions are self-counting, and the framework handles the composition.

Reconciling contradictory prior intuitions about side information. The paper provides a unifying explanation for a tension that has existed in the search literature: why do some algorithms benefit from intermediate progress signals (reward shaping in RL, landmarks in planning) while other algorithms — particularly those with formal optimality guarantees — seem unable to use them without losing those guarantees? Theorem 19 gives a precise, formal answer: bounded suboptimality is fundamentally incompatible with efficient clue usage. Any algorithm that guarantees a solution within factor $1+\varepsilon$ of optimal cost must, in some environments, explore exponentially many nodes that bypass clues entirely, because it cannot rule out the possibility that a non-clue path leads to a sufficiently good solution. This is not a flaw in A* or WA* — it is an information-theoretic consequence of the guarantee they provide. By contrast, √lts accepts unbounded suboptimality (it finds some solution, not necessarily a good one) and extracts exponential speedups from clues in exchange. This tradeoff was latent in the literature — A* provides optimality but cannot use clues; MCTS uses rewards but can be exponentially misled — but the paper makes it explicit and quantifiable.

The resolution matters practically: it means that when solution quality matters, clues cannot help (in the worst case, with formal guarantees). When solution quality does not matter — when finding any solution is sufficient — clues can provide exponential speedups with the right algorithmic infrastructure. Researchers no longer need to wonder whether their domain's intermediate signals could be exploited with formal efficiency guarantees; they now know the conditions under which the answer is yes (abandon depth-optimality) or no (retain bounded suboptimality).

Which directions become more attractive. The paper makes three research directions substantially more attractive than before.

First, learned rerooters become a well-posed problem: the paper shows that if you can assign high weight to nodes on the solution path and low weight elsewhere, you get exponential speedups. This is a clean supervised or reinforcement learning objective — predict which visited nodes are on a solution path, or predict the subtask difficulty from the current node, or estimate the probability that the current node shares a solution-path ancestor with an already-visited high-weight node. Before this paper, the concept of "learning to allocate search effort among subtrees" lacked both an algorithmic mechanism and a formal guarantee to optimize for. Now both exist.

Second, self-counting cost function design becomes a recognized subfield. The paper demonstrates that the self-counting property composes under weighted minimums, but it does not exhaust the space of possible compositions or base functions. Are there self-counting cost functions that incorporate heuristic information (as A* does with $f = g + h$) while remaining self-counting? Can value-function-based costs be made self-counting? The abstraction invites exploration beyond LTS-like policy-based costs.

Third, search with transpositions under rerooting. The paper explicitly works with trees, not DAGs, and the bounds count tree nodes, not distinct states. Extending the self-counting and composition framework to graphs where multiple paths reach the same state — ideally preserving the subtask-decomposition guarantee while avoiding double-counting — would make √lts applicable to essentially all practical search domains (planning, theorem proving, puzzle solving).

Which directions become less attractive. The lower bound (Theorem 3) and the separation from bounded-suboptimal search (Theorem 19) collectively establish that no algorithm can simultaneously exploit clues and retain bounded suboptimality. This makes research programs that attempt to design "clue-aware A*" or "landmark-guided WA* with optimality guarantees" provably futile in the worst case — such algorithms either sacrifice the guarantee (at which point they are just heuristic variants without formal properties) or suffer exponential slowdown relative to √lts. The paper does not say these algorithms are useless in practice (average-case behavior may be better), but it does say that formal worst-case guarantees are impossible, which should shift research attention toward average-case empirical evaluation for such hybrids rather than theorem-proving.

The paper also casts doubt on the wisdom of using MCTS/AlphaZero-style algorithms in domains with sparse, potentially misleading intermediate rewards — at least without explicit mechanisms to prevent the greedy over-commitment that the D-chain analysis (Appendix A.3) exposes. The double-exponential and quadratic failure modes are not artifacts of particular hyperparameter settings; they stem from the UCB formula's fundamental structure, which allocates effort proportionally to observed reward. The paper does not claim MCTS is "bad" — it has been transformative in games with dense, well-shaped rewards — but it does suggest that for domains where intermediate signals are sparse and potentially deceptive, rerooting-based allocation is structurally more robust.

---

Follow-Up Research This Work Enables

Learning rerooters from solution trajectories using the subtask decomposition as a loss function. The paper provides a bound (Theorem 11, Corollary 12) that depends on the rerooter's weight assignments at checkpoints along the solution path. This bound can be interpreted as a loss: given a set of training problems with known solution paths and a policy $\pi$, the quantity $\max_{i < m} \frac{w_{< T}}{w_{T_i}} \frac{\lambda}{\pi}(n_{T_{i+1}}; n_{T_i})$ is what a good rerooter should minimize. A concrete follow-up would train a neural rerooter — mapping a node's features (state, depth, policy probability, features of the path so far) to a scalar weight $\tilde{w}$ — by minimizing this bound on training problems, using the self-normalizing transformation $w_t = \tilde{w}_t / \tilde{w}_{\leq t}$ to ensure robustness. The experiment would compare the learned rerooter's √lts performance against LTS and against a hand-designed rerooter on a benchmark like Sokoban puzzle sets or International Planning Competition domains. A strong result would show that the learned rerooter recovers at least 50% of the theoretical speedup (the gap between LTS's product-of-costs bound and √lts's max-of-costs bound) on held-out problems, demonstrating that the bound is not just a theoretical artifact but a viable training signal.

Characterizing the empirical gap between $\frac{\lambda}{\pi}$ and $\frac{d}{\pi}$ across policy structures. The paper proves that $\frac{\lambda}{\pi}$ tightens the self-counting bound by a factor of $d(\cdot)$ in the worst case, but the actual improvement depends on the policy's entropy and the tree structure (Example 20 shows a factor from $d(n)$ down to $\max\{1/p, 1/(1-p)\}$ for binary asymmetric policies). A systematic empirical study would measure the actual node-visit counts of BFS with $\frac{\lambda}{\pi}$ vs. $\frac{d}{\pi}$ on a range of policies — from near-uniform to highly peaked — and tree structures (chains, balanced trees, irregular branching) to determine when the slenderness improvement is practically meaningful (factor >2) versus negligible. This would provide guidance on whether implementing $\frac{\lambda}{\pi}$ (which requires maintaining $\lambda$ values and the active-ancestor set of Appendix G) is worth the implementation complexity, or whether the simpler $\frac{d}{\pi}$ suffices for most practical policies. The experiment would also reveal whether the self-counting tightness (the ratio of the bound to the true node count, bounded by $B$ for $\frac{\lambda}{\pi}$ vs. $B \cdot d(\cdot)$ for $\frac{d}{\pi}$) correlates with actual BFS step counts — the bound is an upper bound, and a loose bound does not necessarily mean loose actual performance.

Extending √lts to graph search with transposition detection. This is the most practically important theoretical extension. The paper's tree assumption means every distinct path to the same state counts as a separate node, inflating both the actual node visits and the bounds. A follow-up would reformulate the self-counting property and the composition theorem for DAGs with transpositions, where the "cost" of a state should reflect the minimum over all paths, and the "count" of states with cost $\leq \theta$ should count each state once. The key challenge is that $\frac{\lambda}{\pi}$ counts tree nodes via the telescoping sum (Equation 5), and this identity breaks when multiple paths merge — a state's $\lambda$ value becomes ill-defined because it has multiple sets of ancestors. A successful extension would define a graph-aware slenderness (perhaps based on the policy's probability of reaching a state via any path, not a specific path), prove a graph-self-counting property with a bound involving the number of distinct states rather than tree nodes, and extend the composition theorem to graph-structured base cost functions. The baseline comparison would be LTS with a transposition table vs. √lts with a transposition table on standard planning benchmarks (Sokoban, sliding puzzles, grid navigation), measuring both node visits and distinct-state visits. A negative result — showing that transpositions fundamentally break the subtask decomposition guarantee — would be equally valuable, as it would delineate the boundary of the theory's applicability.

Empirical comparison of √lts against modern MCTS variants on sparse-reward domains. The paper provides theoretical worst-case analyses showing MCTS can take double-exponential or quadratic time on constructed environments (D-chain, single misleading reward), while √lts requires only linear or linearithmic time. But these are adversarial constructions, not representative benchmarks. A fair empirical comparison would implement both √lts (with a learned or hand-designed rerooter) and a modern MCTS variant (e.g., AlphaZero-style with policy and value networks) on a suite of sparse-reward puzzle domains: Sokoban, the 15-puzzle, Rubik's Cube, and grid-based pathfinding with misleading dead-end rewards. Both algorithms would use the same policy network (trained via imitation learning on optimal trajectories) and the same compute budget (wall-clock time or total node visits). The hypothesis from the paper's analysis is that √lts should dominate on problems with sparse, potentially deceptive intermediate rewards, while MCTS might retain an advantage on problems with dense, well-shaped rewards where its backpropagation and UCB exploration are well-suited. A finding that √lts matches or exceeds MCTS on even a few sparse-reward benchmarks would be practically significant; a finding that MCTS outperforms √lts across the board (despite the theoretical worst-case results) would suggest that the adversarial constructions are too pessimistic and that MCTS's average-case behavior is robust enough for practice.

Designing and testing alternative weight transformation functions for specific domain characteristics. Corollary 17 uses the self-normalizing transformation $w_t = \tilde{w}_t / \tilde{w}_{\leq t}$, and Appendix F sketches a family of transformations $w_t = f(\tilde{w}_{\leq t}) - f(\tilde{w}_{\leq t-1})$ with different robustness profiles (bounded cumulative weight, logarithmic growth, etc.). A systematic study would characterize this design space empirically: for different "clue density" regimes (how many clues per solution-path node) and "clue informativeness" regimes (what fraction of clues are on the solution path), which transformation $f$ minimizes actual node visits? The experiment would sweep over $f(x) = x$ (naive), $f(x) = \ln(1+x)$ (logarithmic), $f(x) = \sqrt{x}$ (sublinear), $f(x) = -1/\ln(e+x)$ (bounded), and a few others, on synthetic clue environments (controlling $q$, $m$, $a$ independently) and one real domain (Sokoban with automatically generated clues). The practical deliverable would be a decision tree for practitioners: if clues are dense and mostly misleading, use logarithmic; if clues are sparse and mostly helpful, use square-root; if the total number of clues is unknown, use bounded. The paper's theory says all these transformations preserve the asymptotic bound (up to constants), but the constants matter for practical performance, and this experiment would measure them.

Stress-testing the rerooting mechanism: what happens when the rerooter is adversarially misleading? The paper's robustness analysis (Section 6) assumes the rerooter may be uninformative (assigning weight indiscriminately) but not actively malicious. What if an adversary controls the rerooting weights — for instance, in a security context where an attacker can craft clue-like patterns that trigger high weights on dead-end subtrees? The paper's self-normalizing scheme ensures the bound degrades at most logarithmically, but the actual node-visit count could still be inflated by a constant factor. A concrete study would design adversarial rerooting-weight sequences on the clue environments of Theorem 3 and measure the actual slowdown relative to the LTS baseline. This would reveal whether the logarithmic bound is tight in adversarial settings or whether the algorithm has hidden vulnerabilities (e.g., the priority queue ordering could cause starved subtrees to be explored exponentially late despite low weight). A finding of robustness would strengthen the practical case for √lts in untrusted environments; a finding of vulnerability would motivate research into adversarially robust rerooting-weight schemes.

---

Practical Applications and Downstream Use Cases

Automated theorem proving with lemma discovery. In theorem proving, a proof search may generate millions of intermediate clauses, most of which are dead ends. Occasionally, the prover discovers a lemma — a useful intermediate result that substantially reduces the remaining proof length. A lemma is a natural "clue": the node where the lemma is proved should receive high rerooting weight, focusing subsequent search on consequences of that lemma rather than continuing to explore the original search space. The paper's framework provides a mechanism for this: when a lemma is proved (detected by a heuristic or a learned lemma-recognizer), the rerooter assigns a high weight to that node, and √lts automatically allocates more search effort to descendants of that lemma. The guarantee (Theorem 11) means that if the lemma genuinely simplifies the remaining proof (the subtask cost $\frac{\lambda}{\pi}$ from lemma to QED is small), the bound reflects this — the total search cost is dominated by the hardest subtask, not the product of all subtask difficulties. The self-normalizing weights (Corollary 17) prevent the prover from being overwhelmed if many "lemmas" turn out to be unhelpful: the log factor ensures that trying many dead-end lemmas does not cause catastrophic slowdown. The practical benefit is a theorem prover that can dynamically refocus its search when useful intermediate results are discovered, without the implementer needing to hard-code a specific lemma-usage strategy.

Constraint satisfaction with bottleneck detection. In constraint satisfaction problems (CSPs), certain subsets of constraints are "bottlenecks" — if they can be satisfied simultaneously, the remaining problem is much easier. A CSP solver using √lts could recognize when a bottleneck has been passed (e.g., when all constraints of a particularly difficult type are simultaneously satisfied for the first time in a partial assignment) and assign high rerooting weight to that partial assignment. The subsequent search would be concentrated on completions of that promising partial assignment, while still maintaining exploration of alternatives (through the weights of other nodes in the priority queue). The exponential speedup demonstrated on the clue environments (Section 3) translates directly: if there are $q$ partial assignments that satisfy the bottleneck constraints, only one of which can be completed to a full solution, √lts finds the solution in $O(q \cdot 2^a)$ steps where $a$ is the depth from bottleneck to solution, compared to $2^{q \cdot a}$ for uninformed search. The Sokoban analysis (Appendix H) provides a concrete template: box-on-goal counts serve as bottleneck indicators (a partial state with more boxes on goals is a tighter bottleneck), and the rerooting weights can be scaled inversely with the estimated number of such states ($M_z$ in Appendix H) to prioritize the rarest, most informative bottlenecks.

Puzzle and game solving with hierarchical decomposition. Many puzzles (Sokoban, sliding puzzles, Rubik's Cube variants) have natural hierarchical structure: solving the puzzle involves achieving a sequence of recognizable subgoals (e.g., in a Rubik's Cube, solving one face, then the middle layer, then the last layer). These subgoals are clues. A puzzle-solving system using √lts would run a single best-first search from the initial state, with a rerooter that recognizes subgoal achievement and assigns rerooting weights. When the first subgoal is achieved, the search automatically shifts focus to paths that build on that subgoal, while retaining the ability to backtrack if the subgoal turns out to be on a non-optimal path (by weighting alternative branches proportionally). The theoretical speedup — from the product of subgoal difficulties (LTS) to the maximum (√lts) — means that the system's performance scales with the hardest subgoal, not the number of subgoals. For puzzles with many intermediate milestones, this is the difference between exponential and linear scaling in the number of milestones. The paper's robustness guarantee ensures that if the subgoal recognizer occasionally fires on false positives (states that look like subgoals but are not on the solution path), the performance penalty is logarithmic in the number of false alarms, not linear — the system is forgiving of imperfect clue detectors.

Learned search policy deployment with dynamic test-time adaptation. Modern search systems increasingly use learned policies (e.g., AlphaZero's policy network, learned heuristics for A*) that are static during a single search episode. But test-time conditions may differ from training in ways that a static policy cannot anticipate — for example, a specific problem instance may have an unusual structure that the policy handles poorly, but a runtime signal (rapid improvement in a scoring function, reaching a rare state) indicates that the search is on a promising path. √lts provides a mechanism for injecting test-time adaptation into policy-guided search without retraining the policy: the rerooter can incorporate any information available at test time (including information not present in the training distribution) and dynamically reallocate search effort. This is particularly valuable in domains where the policy is trained on a broad distribution but deployed on specific instances with identifiable structure — for example, a code-generation policy trained on general programming tasks, deployed to solve a specific algorithmic problem where passing certain test cases or achieving a particular intermediate program state serves as a clue that the current partial program is on the right track. The separation of concerns — the policy handles local action selection, the rerooter handles global search-budget allocation — means the rerooter can be updated or specialized per deployment context without retraining the policy.

---

When to Prefer This Method

The paper explicitly articulates a tradeoff between √lts and bounded-suboptimal algorithms (A*, WA*) through Theorem 19 and constructs a separation between √lts and MCTS through the analyses in Appendix A.3. The decision criteria are:

• Prefer √lts over A/WA when** solution quality (depth-optimality or bounded suboptimality) is not required, AND the domain provides identifiable intermediate progress signals (clues) that a rerooter can exploit. Theorem 19 proves that bounded-suboptimal algorithms require $\Omega(2^{qa/(1+\varepsilon)})$ node visits in environments where √lts visits $O(q 2^a)$ — the gap is exponential in the number of clues when clues are numerous. However, if a depth-optimal or bounded-suboptimal solution is mandatory, √lts provides no quality guarantee and should not be used.

• Prefer √lts over MCTS (AlphaZero, UCT) when rewards or intermediate signals are sparse and potentially misleading. The D-chain analysis (Appendix A.3.1) shows MCTS taking double-exponential time in solution depth on such domains, while √lts takes $O((D+1)2^D)$ — linearithmic in the uninformed search cost. The single-misleading-reward analysis (Appendix A.3.2) shows MCTS taking $\Omega((\alpha BFS)^2)$ while √lts takes $O((1+\alpha)BFS)$. However, MCTS may outperform √lts on domains with dense, well-shaped rewards (e.g., board games where every move provides incremental positional evaluation) because MCTS's averaging and UCB exploration are well-suited to that regime; the paper does not analyze this case.

• Prefer LTS over √lts when no informative rerooter is available. Setting $w_1 = 1$ and $w_t = 0$ for all $t > 1$ collapses √lts to exactly LTS (Equation 16), so √lts is never worse than LTS by more than the logarithmic robustness factor (Corollary 17). But if the rerooter is uninformative (assigns similar weight to all nodes), √lts provides no speedup over LTS and introduces implementation complexity (the $c^r$ cost function, the active-ancestor maintenance of Appendix G). In such cases, using plain LTS with the improved $\frac{\lambda}{\pi}$ cost function is simpler and equally effective.