Levin Tree Search (LTS) 알고리즘을 개선한 $\sqrt{\text{LTS}}$ 알고리즘을 제시한다. $\sqrt{\text{LTS}}$는 모든 노드에서 LTS 검색을 시작하며, 사용자 정의 또는 학습된 재루팅(rerooting) 가중치를 통해 검색 노력을 각 LTS 검색에 비례적으로 분배한다. 이러한 재루팅 메커니즘은 탐색 공간을 하위 작업으로 암시적으로 분해하여 속도 향상을 가져온다. $\sqrt{\text{LTS}}$의 노드 방문 횟수는 하위 작업으로의 최적 분해와 경쟁력이 있으며, 재루팅의 불확실성과 관련된 계수만큼의 비용이 발생한다. 최적의 경우 q개의 재루팅 지점이 있다면, LTS가 T의 시간이 걸린다면 $\sqrt{\text{LTS}}$는 O(q√[q]{T})의 시간만 소요된다. 정책과 마찬가지로 재루팅 또한 데이터로부터 학습될 수 있으며, 다양한 분야에 적용될 것으로 기대된다.