Leaf-Relocation Tree Router

Use this as a periodically refreshed hierarchy for an MoE router or approximate-nearest-neighbor retrieval module. Maintain a tree over M expert prototypes e_j or over a memory bank of item embeddings. Set D_ij=1-cos(e_i,e_j), using L2-normalized prototypes. Initialize T with an approximate minimum-spanning tree over a k-nearest-neighbor graph, then perform S local-search rounds. In each round, sample leaves v, identify the current parent u, and propose several destination vertices w. Form T'=T-{(v,u)}+{(v,w)} and estimate R_D(T') on sampled triples: choose random endpoint pairs, recover their tree path, sample an interior vertex y, and evaluate [max(D_xy,D_yz)-D_xz]_+. Accept the relocation only when the explicit objective including beta times tree depth decreases. For routing, descend from the root using query-to-child-centroid distances, then score only experts in the selected leaf subtree plus a small number of sibling subtrees; apply top-k gating within that candidate set. For retrieval, scan only the selected subtree and optionally its 2-ball-like neighboring branches. R_D and the relocation rule come from the paper; kNN initialization, sampling, beta, and branch width are empirical choices. First benchmark on a 100k-item sentence-embedding retrieval task and a 64-expert Switch-style language model. Compare flat retrieval or dense routing at equal recall or perplexity. Success is 2-4x fewer distance or routing evaluations at no more than 1% quality loss, with lower R_D and stable expert utilization.