# Leaf-Relocation Tree Router

- ID: 2653
- Canonical URL: https://synthcore.org/idea/2653/leaf-relocation-tree-router
- API JSON: https://synthcore.org/api/idea/2653.json
- API Markdown: https://synthcore.org/api/idea/2653.md
- Verification status: unverified
- Source: [arXiv:2608.21248](https://arxiv.org/abs/2608.21248)
- Category: architecture
- Solves: scalability, sample-efficiency, accuracy
- ML areas: moe-routing, retrieval, embedding, graph-nn
- Math tags: combinatorics, graph-theory, metric-geometry, optimization
- Ratings: usefulness 6/10; difficulty 6/10; novelty 7/10

## Idea description

Learn a branching hierarchy for tokens, examples, or experts by greedily relocating leaves to reduce T-Robinson violations. The resulting tree supplies hierarchical candidate sets for retrieval or MoE routing, allowing the model to search a small subtree instead of all items while adapting the hierarchy to learned representations.

## Mathematical statement

The paper defines a compatible tree T for a dissimilarity D by requiring every path-induced ordering to satisfy D(x,z)>=max{D(x,y),D(y,z)} for x<y<z. It defines a leaf relocation operation: if v is a leaf adjacent to u, delete vu and insert vw for w not in {v,u}; this preserves that the graph is a spanning tree. We turn this into a discrete objective R_D(T), the sum of sampled pathwise violations. Here P_T is a set of ordered triples lying on common tree paths, D_ij is the embedding dissimilarity, and beta controls a depth penalty. The paper's 2-ball B_xy={z:max(D_xz,D_yz)<=D_xy} motivates grouping items that are simultaneously close to both endpoints into connected routing subtrees.

## Key formulas

- $$B_{xy}=\{z\in X:\max\{D(x,z),D(y,z)\}\leq D(x,y)\}.$$
- $$R_D(T)=\sum_{(x,y,z)\in\mathcal{P}_T}\left[\max\{D_{xy},D_{yz}\}-D_{xz}\right]_+.$$
- $$T'=T-\{vu\}+\{vw\},\qquad v\in L(T),\quad w\in X\setminus\{v,u\}.$$
- $$T\leftarrow T'\quad\text{iff}\quad R_D(T')+\beta\,\mathrm{depth}(T')<R_D(T)+\beta\,\mathrm{depth}(T).$$

## Implementation notes

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.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.