{"id":"b0198d22-5f2f-4dca-a9b8-01ad636340cc","arxiv_id":"2412.05196","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"A rerooting variant of Levin Tree Search matches the best subtask decomposition and visits at most O(q times the q-th root of T) nodes when plain LTS needs T.","lead":"Rerooting Levin Tree Search starts a search from every visited node and shares effort between those searches using a rerooter. The paper proves this can find solutions exponentially faster than ordinary Levin Tree Search when the rerooter points at useful subtasks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: Theorem 11 and Corollary 12 appear internally sound, and the exponential speedup is explicitly conditional on a good rerooter, which the paper states as a limitation rather than concealing.","rationale":"The reader's verdict is ACCEPT with high confidence, and I find no load-bearing objection to the formal result. The proof of Theorem 11 and its simplification in Corollary 12 are internally consistent: the composition bound of Lemma 35 applies to non-monotone self-counting costs, and Corollary 37 plus Lemma 33 connects path costs to the number of visited nodes without requiring monotonicity of c^r. The robustness discussion in Section 6 addresses the main failure mode of vacuous bounds when the number of clues is large. The reader's weakest assumption is the conditional nature of the speedup on a good rerooter; this is a genuine practical limitation and an open problem, but the paper is transparent about it and does not claim a learning procedure. Thus the correct verdict is unchanged: accept the theoretical contribution while keeping the caveat about rerooter availability visible.","tokens_in":28696,"tokens_out":28845,"duration_ms":322546,"concrete_test":"Independently re-derive Eq. (14) from Lemma 35, paying particular attention to the case where misleading positive-weight clues lie outside the chosen subtask path; then run a small brute-force simulation of BFS with c^r on a binary tree with one helpful and one misleading clue under a uniform policy, comparing actual node-visit counts to the Corollary 12 bound under several tie-breaking rules. If any simulation exceeds the bound, the theorem has a tie-breaking loophole; otherwise the proof is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I checked the argument that supports the central claim. Theorem 11 (Eq. 14) is derived from Lemma 35 and Lemma 33; the decisive steps are the segment partition (Eq. 22), the tree-to-path bound on each segment, and the extraction of the '-1' term in Eq. (22f). The extraction is justified because the final segment contributes at least one unit via (w_{<T_m} - w_{<T_{m-1}})/w_{T_{m-1}} >= 1, even if earlier segments require dropping their '-1' terms. Corollary 12 follows by telescoping the sum. The robustness reparameterization in Section 6 (Corollary 17) converts arbitrary input weights into w_t = \\tilde w_t / \\tilde w_{\\le t}, replacing a potentially linear w_{<T} factor by a logarithmic one; the proof's self-reference to 'Corollary 17' is a typo for 'Corollary 12', not a substantive gap. The only real caveat is the one the reader identifies: the advertised O(q * q-th root of T) speedup presupposes a rerooter that assigns positive weight to an ancestor chain ending at the solution, and no learning procedure for such a rerooter is given. This is, however, explicitly stated as beyond the scope of the paper ('we expect that the rerooter can be learnt from data'), and the formal claims are conditional bounds that hold for every input rerooter. I therefore do not regard this as a correctness flaw in the central theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces √LTS (root-LTS), a best-first tree-search algorithm that composes Levin Tree Search instances implicitly rooted at every visited node, with the effort shared according to a user-supplied rerooting weight w_t assigned to each visited node. The central theoretical claim is Theorem 11 and Corollary 12: for every subtask decomposition n_{T_1} ≺ ... ≺ n_{T_m} = n_T of the visited node n_T, the visit count satisfies T ≤ Σ_{j<m} (w_{<T_{j+1}} − w_{<T_j}) max_{j≤i<m} (1/w_{T_i}) λ_π(n_{T_{i+1}}; n_{T_i}) and, in simplified form, T ≤ max_{i<m} (w_{<T}/w_{T_i}) λ_π(n_{T_{i+1}}; n_{T_i}), where λ_π is a new self-counting cost function that tightens the previous LTS bound of 1 + d/π. In clue environments, when the rerooter assigns positive weight to q clue nodes on the solution path, this yields an O(q 2^a) visit bound against an LTS baseline of Ω(2^{m(a−1)}), an exponential speedup that matches a new lower bound (Theorem 3) within a constant factor. A weight reparameterization (Corollary 17) replaces a potentially linear factor w_{<T} by a logarithmic factor, giving robustness to an overload of misleading clues. The paper also argues (Appendix A) that A*, weighted A*, and MCTS-style algorithms cannot exploit such clues while retaining their usual guarantees.","tokens_in":29039,"tokens_out":57197,"duration_ms":472063,"significance":"If the results hold, this is a substantial contribution to the theory of guided tree search: it is the first to convert LTS's multiplicative-in-subtasks guarantee into a max/sum form at the price of a rerooting-weight factor, and it provides a matching lower bound for clue environments. The central proof in Appendix D is careful and, to the best of my check, correct: Lemma 33 and Lemma 35 genuinely handle the non-monotone cost, Lemma 36 supplies the self-counting base functions, and the segment partition in Eqs. (22a)–(22f) is sound, including the extraction of the −1 term. The slenderness cost function λ_π is a real (if modest) improvement over 1 + d/π, and Corollary 17's reparameterization is an elegant device. The paper ships no code or machine-checked proofs, but the derivations are detailed enough to be verified by hand, which I did for the key steps. I also judge that the main caveat flagged by a critical reader — that the advertised exponential speedup presupposes a good rerooter and no learning procedure is provided — is honestly disclosed in Sections 1 and 7 ('we expect that the rerooter may be learnt from data...","major_comments":[{"comment":"The displayed derivation T ≤ w_{<T} max_{i<m} q_{T_i} λ_π(n_{T_{i+1}}; n_{T_i}) ≤ (1 + ln q_T) q_{T_m}^{m−1} 2^{a+1} is true but too loose to support the conclusion drawn from it. Since a subtask decomposition must satisfy n_{T_m} = n_T (Definition 10) and the example sets n_T = n*, one has T_m = T, hence q_{T_m} = q_T ≤ T; substituting back gives the circular inequality T ≤ (1 + ln T) T^{m−1} 2^{a+1}, which is vacuous for m ≥ 2. The subsequent sentence 'Since q_{T_m}^{m−1} does not depend on T' is therefore false as written, and the claimed implication T = Õ(q_{T_m}^{m−1} 2^a) with a T-independent right-hand side, as well as the conclusion that n* is necessarily eventually visited, does not follow from this argument. The example already contains a sound route to the main robustness conclusion via Eq. (16): T ≤ w_{<T} λ_π(n*) ≤ (1 + ln q_T) λ_π(n*) ≤ (1 + ln T) λ_π(n*), which with the footnote's self-bounding trick gives T = O(λ_π(n*) ln λ_π(n*)), i.e., within a log factor of LTS. I recommend restructuring Example 15 around that argument and correcting or dropping the q_{T_m}^{m−1} bound.","section":"Section 6, Example 15"},{"comment":"The main theorem is stated for 'every subtask decomposition', but Definition 10 permits the degenerate case m = 1 when n_T = n_1 (i.e., T = 1). For m = 1 the sum in Eq. (14) is empty, so the theorem would assert T ≤ 0, which is false for T = 1. The proof's extraction of the −1 term in Eq. (22f) requires the last segment j = m−1 to exist, i.e., m ≥ 2, and also requires w_{T_{m−1}} > 0 for the ratio (w_{<T_m} − w_{<T_{m−1}})/w_{T_{m−1}} to be well-defined and ≥ 1. This is a degenerate edge case that does not affect any application in the paper (all uses have m ≥ 2), but the statement should be corrected, e.g., by requiring m ≥ 2 in Theorem 11 and Definition 10 and by noting that the bound is infinite unless w_{T_i} > 0 for the chosen decomposition.","section":"Theorem 11 and Definition 10"}],"minor_comments":[{"comment":"The proof begins 'The result follows from Corollary 17', which is a self-reference; it should read 'from Corollary 12'. In the same proof, the index range of the telescoping sum should be t = 2, ..., T−1 rather than t = 2, ..., T (since w_{<T} = w_1 + Σ_{t=2}^{T−1} w_t).","section":"Section 6, proof of Corollary 17"},{"comment":"The claim that the rooted cost λ_π(·; n_a) is self-counting is essential for Lemma 36, which is used in the proof of Theorem 11, but it is only asserted in a footnote ('All the proofs can be readily adapted at the expense of heavier notation'). Please include the short argument (applying the complementary-policy proof of Proposition 25 within the subtree rooted at n_a with the conditional policy).","section":"Section 4.1 and Lemma 36"},{"comment":"The ancestor relation is introduced with both nodes printed as 'n' ('we write n ≺ n for n ∈ anc(n)'), which is unreadable; use distinct symbols (e.g., n ≺ n′) as in the table of notation in Appendix I.","section":"Section 2"},{"comment":"The paper should state explicitly the standing assumptions that rerooting weights are nonnegative, that w_1 > 0 for non-vacuous bounds, and that the bound of Corollary 12 (and Eq. (16)) is infinite unless w_{T_i} > 0 for the subtask nodes used. Currently these positivity conditions are implicit.","section":"Section 5 and Corollary 12"},{"comment":"The pseudocode computes min_{n_k ≺ n} (1/w_k)(λ_π(n; n_k) − 1) without guarding against w_k = 0; the surrounding text handles zero weights via infinite cost, but the pseudocode should exclude ancestors with zero weight.","section":"Algorithm 1"},{"comment":"The phrase 'any state no state is visited twice' is garbled and should be reworded. Also, the final numerical bound reads T ≤ 3.83 max{733, 9 × 31, 2 × 229, 2 × 393} ≤ 3 011; the maximum is 786 and 3.83 × 786 ≈ 3 010, so the displayed value is consistent, but a quick check of the arithmetic would be good.","section":"Appendix H"}],"recommendation":"minor_revision","confidential_remarks":"The central claim of the paper is sound: I checked the proof of Theorem 11 in Appendix D step by step, including Lemmas 33, 35, and 36 and the segment partition, and found no error for m ≥ 2. The lower bound (Theorem 3) and Corollary 17 are also correct modulo the typo noted. The issues I raise are local but real: Example 15 in Section 6 contains an unsupported inference that should be rewritten, and Theorem 11 needs a non-degeneracy condition (m ≥ 2). Both are easily fixed without changing the paper's conclusions. The paper is well within the scope of the journal, the citation practice to prior LTS work is appropriate, and I have no novelty concerns. I recommend minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a genuine extension of LTS, not a repackaging. The new cost function λπ is tighter than d/π, and the composition argument (Lemma 8, Theorem 11, Corollary 12) replaces the product over subtasks by a max. I checked the appendix proof of Theorem 11 carefully. The segment partition and the tree-to-path bound (Lemma 33) do the work; the extraction of the '-1' term is justified because the final segment contributes at least one. The proof is sound as far as I can see. The lower bound in Theorem 3 is a useful independent check.\n\nWhat is genuinely new: √LTS runs an implicit LTS from every visited node with weights supplied by a rerooter, and the guarantee is competitive with the best subtask decomposition. The slenderness cost function is a nice contribution on its own, with a tighter self-counting bound. I believe the paper is honest about scope: the exponential speedup is conditional on a rerooter that assigns positive weight to an ancestor chain of useful nodes. The paper says learning the rerooter is future work, and Section 6 shows what can go wrong with too many misleading clues. The robust reparameterization in Corollary 17 is a reasonable fix, though the proof contains a self-reference typo ('Corollary 17' should be 'Corollary 12') that should be corrected.\n\nSoft spots, in proportion. There is no implementation and no benchmark. The Sokoban appendix is illustrative, not empirical. The central theorem is conditional on a good rerooter, and no procedure for constructing one is given. That is a limitation the authors state clearly, so it is not a hidden flaw. The paper cites its own prior work for LTS; that is appropriate since it builds directly on it. The references to A*, MCTS etc. are adequate for context. I did not find a circularity problem: the theorem is a conditional guarantee, not fitted to data.\n\nWho is this for? Someone working on policy-guided search or formal guarantees for planning could use Theorem 11 and the λπ cost function. If you are looking for an empirical paper about learning rerooters, this is not it. As a theory paper, it is careful and the main result checks out. The paper deserves a serious referee; it might need some revision on the presentation of the robustness result and the typo, but the core contribution is solid.","headline":"Solid extension of Levin Tree Search with a correct composition theorem; the practical speedup is conditional on a rerooter nobody yet knows how to learn, but the formal contribution stands.","tokens_in":29555,"tokens_out":1592,"would_cite":true,"duration_ms":15528,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T20","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Rerooting a Levin tree search at every visited node can cut T visits to about q times the qth root of T, and a lower bound proves this rate is near-optimal.","keywords":["Levin tree search","rerooting","best-first search","self-counting cost functions","slenderness","efficiency guarantees","policy-guided search","Sokoban"],"falsifier":"On a perfect binary tree of depth $D$ (say $D=20$) with $q=8$ clue nodes whose closest clue ancestor is at relative depth $a=5$, and one solution below one of the clues, run $\\sqrt{\\text{LTS}}$ with a uniform policy and rerooting weight 1 at each clue node. Corollary 12 predicts the solution is visited at step $T<q\\,2^{a+1}=512$; a run exceeding that on a fixed tie-breaking rule would refute the main bound. In the randomized version of the same environment, the lower-bound theorem says every algorithm must average at least $(q+1)2^{a-1}=144$ visits, so an algorithm averaging less would refute that bound.","tokens_in":28531,"feed_emoji":"🔍","tokens_out":17563,"duration_ms":164648,"temperature":0.7,"pith_summary":"Levin Tree Search (LTS) is a best-first search for deterministic environments that is guided by a policy and comes with a guarantee on the number of node visits before it finds a solution. This paper introduces $\\sqrt{\\text{LTS}}$, a rerooting variant that implicitly starts an LTS search at every visited node and divides search effort among those roots according to weights supplied by a 'rerooter'. The central result is that if plain LTS needs $T$ visits and the rerooter identifies $q$ useful rerooting points, $\\sqrt{\\text{LTS}}$ can get by with $O(q\\sqrt[q]{T})$ visits in the best case, and the paper proves a lower bound showing no algorithm can do asymptotically better in the relevant clue environments. The reason the bound matters is that LTS's guarantee multiplies the costs of successive subtasks, while $\\sqrt{\\text{LTS}}$ replaces that product by a maximum, so the gain is exponential in the number of useful subtasks.","feed_headline":"Rerooting turns Levin search's T steps into q-th-root time","feed_subtitle":"With q useful rerooting points, visits drop to about q times the qth root of T, a rate no algorithm can beat in general.","key_machinery":"The load-bearing mechanism is the composition of self-counting cost functions. A cost function $c$ is self-counting when $|\\{n:c(n)\\le\\theta\\}|\\le\\theta$ for every $\\theta\\ge0$; for a monotone self-counting cost, best-first search reaches any node $n_t$ with $t\\le c(n_t)$. The paper's slenderness cost $\\lambda_\\pi$ is self-counting and tightens LTS's old cost by removing a $d(n)$ factor. $\\sqrt{\\text{LTS}}$ composes one rooted slenderness cost $\\lambda_\\pi(\\cdot;n_t)$ for every visited node $n_t$, weighted by the rerooter weight $w_t$, into the single cost $c^r$ of Eq. (13), and a telescoping identity for $\\lambda_\\pi$ lets different roots be compared along one path. The subtask decomposition of Definition 10 is the analytical lens: it chooses any monotone chain of high-weight nodes ending at the solution, and the theorem reads the total visit count off the hardest weighted link in that chain.","core_discovery":"The paper's central discovery is that rerooting turns the multiplicative structure of LTS's guarantee into an additive one. In place of the cost $d(n)/\\pi(n)$, it uses a slenderness cost $\\lambda_\\pi(n)=\\sum_{n_1\\preceq u\\preceq n}1/\\pi(u)$, which avoids double-counting shared ancestors, and then composes one rooted slenderness cost per visited node into a single search cost $c^r(n)=\\min_{n_t\\prec n}(\\lambda_\\pi(n;n_t)-1)/w_t$. The main guarantee, Theorem 11 with the simplified Corollary 12, states that for every subtask decomposition $n_{T_1}\\prec\\cdots\\prec n_{T_m}=n_T$ of the solution node, the visit count satisfies $T\\le \\max_{i<m}(w_{<T}/w_{T_i})\\,\\lambda_\\pi(n_{T_{i+1}};n_{T_i})$, where $w_{<T}$ is the cumulative rerooting weight. Because LTS multiplies the same subtask costs while $\\sqrt{\\text{LTS}}$ takes their maximum, the new bound can be exponentially smaller in the number of subtasks. In the paper's clue environments, putting rerooting weight 1 on each clue node matches the lower bound $(q+1)2^{a-1}$ within a factor of 4.","pith_inferences":["A testable extension the paper leaves implicit is to train the rerooter on solved instances by rewarding weight on nodes that belong to a good subtask decomposition; the bound then predicts that the speedup transfers to structurally similar instances.","The composition lemma is independent of the slenderness cost, so the same rerooting technique could combine other self-counting signals, for example one derived from an admissible heuristic, without multiplying their guarantees.","Mapping clues to concrete progress signals such as landmarks, shaping rewards, lemmas, or satisfied constraints, and measuring how $w_{<T}$ grows, gives a practical way to choose rerooting weights that the paper motivates but does not develop."],"forward_implications":["If the rerooter sets positive weight on a chain of $q$ useful rerooting points in the clue environments, $\\sqrt{\\text{LTS}}$ visits $O(q\\,2^a)$ nodes while LTS needs $\\Omega(2^{m(a-1)})$; the gap grows exponentially with the number $m$ of useful clues.","The main bound holds for every visited node and for any stopping criterion, so anytime use of $\\sqrt{\\text{LTS}}$ inherits the same guarantee without modification.","With the reweighting of Corollary 17, $\\sqrt{\\text{LTS}}$ is never worse than a logarithmic factor of the LTS bound even when the number of clues is large or unbounded.","In the D-chain environment, $\\sqrt{\\text{LTS}}$ with reward-based rerooting weights stays within a log factor of breadth-first search where UCT-style algorithms can take double-exponential time, and with one aligned reward it achieves about the square root of breadth-first time.","The best-case rate $O(q\\sqrt[q]{T})$ matches the paper's lower bound up to a constant factor, so no algorithm can asymptotically improve on it in general in these environments."],"supporting_citations":[{"why":"It defines the original Levin Tree Search with the depth-over-policy-probability cost function that the new algorithm reroots.","marker":"[Orseau et al., 2018]"},{"why":"It supplies the tighter LTS bound and the policy-learning setup from which the slenderness cost function is derived.","marker":"[Orseau et al., 2023]"},{"why":"It shows how to learn the policy that LTS and root-LTS take as input.","marker":"[Orseau and Lelis, 2021]"},{"why":"It originates the weighted-sharing-of-computation idea that Lemma 8 adapts to compose self-counting cost functions.","marker":"[Levin, 1973]"},{"why":"It provides the best-first-search formalization with priority queues that the entire analysis uses.","marker":"[Pearl, 1984]"},{"why":"It motivates the use of unnormalized weights, which lets the bounds depend on cumulative rerooting weight.","marker":"[Mourtada and Maillard, 2017]"}],"fun_headline_variants":["Rerooting Levin search yields exponential speedup","Levin search rerooted: visits drop to q-th root of T","Exponential speedup from rerooting Levin tree search","Rerooting turns Levin's T steps into q-th root time","From T to q-th root of T: rerooting Levin search"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The exponential speedup presupposes a rerooter that assigns positive weight to a chain of useful nodes leading to the solution with bounded gaps between consecutive useful nodes; the paper does not provide a procedure that produces such a rerooter for a concrete domain.","fun_headline_variants_meta":{"raw":{"variants":["Rerooting Levin search yields exponential speedup","Levin search rerooted: visits drop to q-th root of T","Exponential speedup from rerooting Levin tree search","Rerooting turns Levin's T steps into q-th root time","From T to q-th root of T: rerooting Levin search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001004,"raw_usage":{"total_tokens":4328,"prompt_tokens":1105,"completion_tokens":3223,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":721,"completion_tokens_details":{"reasoning_tokens":3137}},"tokens_in":721,"tokens_out":3223,"duration_ms":22783,"temperature":1.0,"reasoning_tokens":3137,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T20:50:43.724488+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a perfect binary tree of depth $D$ (say $D=20$) with $q=8$ clue nodes whose closest clue ancestor is at relative depth $a=5$, and one solution below one of the clues, run $\\sqrt{\\text{LTS}}$ with a uniform policy and rerooting weight 1 at each clue node. Corollary 12 predicts the solution is visited at step $T<q\\,2^{a+1}=512$; a run exceeding that on a fixed tie-breaking rule would refute the main bound. In the randomized version of the same environment, the lower-bound theorem says every algorithm must average at least $(q+1)2^{a-1}=144$ visits, so an algorithm averaging less would refute that bound.","supporting_citations":[{"cited_title":"Single-agent policy tree search with guarantees","cited_arxiv_id":null,"evidence_quote":"It defines the original Levin Tree Search with the depth-over-policy-probability cost function that the new algorithm reroots."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the tighter LTS bound and the policy-learning setup from which the slenderness cost function is derived."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It shows how to learn the policy that LTS and root-LTS take as input."},{"cited_title":"Heuristics: Intelligent Search Strategies for Computer Problem Solving","cited_arxiv_id":null,"evidence_quote":"It provides the best-first-search formalization with priority queues that the entire analysis uses."},{"cited_title":"Efficient tracking of a growing number of experts","cited_arxiv_id":null,"evidence_quote":"It motivates the use of unnormalized weights, which lets the bounds depend on cumulative rerooting weight."}],"review_version":1}