Horizon-Tuned Prototype Router
Implementation & benchmark of arXiv:2608.25298 — Sequential Euclidean tree construction with exponential memory: distributional performance and worst-case guarantees
Source paper: Sequential Euclidean tree construction with exponential memory: distributional performance and worst-case guarantees arXiv:2608.25298 ⓘ · analyzed Aug 29, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Use exponentially weighted states as slowly moving prototypes for online mixture-of-experts routing or continual learning. Route each embedding by its distance to the current prototype, then update only the selected prototype; the memory parameter controls the tradeoff between rapid adaptation and resistance to routing noise.
Formulas
Mathematical statement
Let p_i be normalized embeddings in B_2^d(1), and let x_{i-1} be a prototype before observing p_i. The paper's attachment penalty is l_i=||p_i-x_{i-1}||^alpha, where alpha>0, and the prototype update is x_i=gamma x_{i-1}+(1-gamma)p_i. Because this is a convex combination, x_i remains in the unit ball whenever p_i does. The endpoint gamma=0 follows the current sequence locally, while gamma=1 freezes the initial anchor. For d>=2, the distributionally optimal fixed parameter for N observations has 1-gamma_N^*=Theta(N^{-1/2}); for alpha=2, the stated expansion is gamma_N^*=1-N^{-1/2}+1/(2N)+O(N^{-3/2}). For arbitrary sequences and 0<alpha<=3, the asymptotic worst-case mean attachment cost is (2/(1+gamma))^alpha. The neural adaptation uses squared distances, alpha=2, as routing scores and uses the horizon estimate N_e for each expert to select gamma.
Implementation notes
Add one prototype state x_e per expert e in a small MoE layer or per class in a continual-learning classifier. At step t, compute a normalized embedding p_t=normalize(W_p h_t). For each expert, compute the score s_{t,e}=-||p_t-x_{e}||_2^2/tau, where tau is a learned or fixed routing temperature, and select the top one or top two experts. After the selected expert processes the example, update only its state using x_e=gamma_e x_e+(1-gamma_e)p_t; leave unselected states unchanged. Track an exponentially averaged assignment count m_e and set an estimated horizon N_e=max(1,total_steps/(m_e+epsilon)); initialize gamma_e=1-1/sqrt(N_e)+0.5/N_e, clipping gamma_e to [0,0.9999]. Normalize or clip embeddings before routing because the paper's guarantees assume bounded points. Compute the theoretical robustness proxy B_e=(2/(1+gamma_e))^2, while estimating the actual mean attachment loss from minibatches. The first cheap experiment should use a 4- or 8-expert Transformer on CIFAR-100 or a streaming language-model benchmark. Compare learned router logits, random routing, fixed EMA prototypes, and the horizon-tuned prototypes. Track validation accuracy or perplexity, expert-load imbalance, routing-switch frequency, average and worst-decile attachment loss, and performance after adversarially ordering classes or topics. The hypothesis is fewer unstable routing switches and better recovery under distribution shifts at comparable FLOPs.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.