> HMM Belief Compression for LLM Routing: Key Insights

LLM Routing 专家 2026-03-31 08:43 2026-03-31
#HMM #Thompson Sampling #LLM routing #contextual bandits #belief compression

Core theoretical and empirical insights from the HMM-TS routing project: why belief compression reduces regret from O((N+d)sqrt(T)) to O(N*sqrt(T)), and when HMM routing beats LinUCB.

// TABLE_OF_CONTENTS

HMM Belief Compression for LLM Routing

Core Idea

Use a Hidden Markov Model to capture latent sequential structure in query difficulty, then apply Thompson Sampling with belief compression for cost-effective LLM routing.

Key theoretical result: Regret bound reduces from \(O((N+d)\sqrt{T})\) (LinUCB) to \(O(N\sqrt{T})\) (HMM-TS), where \(d\) is embedding dimension and \(N\) is model count.

Critical Bug Fix

In hmm_bayes_router.py, the Thompson Sampling posterior update had an ordering bug:

# WRONG: w computed with updated Lambda
Lambda = Lambda + phi @ phi.T
w = Lambda @ mu  # Uses UPDATED Lambda!

# CORRECT: w computed BEFORE Lambda update
w = Lambda @ mu  # Uses ORIGINAL Lambda
Lambda = Lambda + phi @ phi.T

This fix was crucial for all subsequent experiment validity.

Embedding Dimension Scaling Results

Tested on 3 datasets x 4 dimensions x 5 seeds (5000 queries each):

OASST (quality gap = 0.075)

Embedding HMM-TS Regret LinUCB Regret Ratio
keyword 3D 109.2 69.9 1.56
embed 16D 135.5 84.9 1.60
embed 32D 145.7 96.9 1.50
embed 64D 167.6 121.6 1.38

Growth 3D→64D: HMM-TS 1.53x vs LinUCB 1.74x — ratio narrows with dimension, validating belief compression.

StackOverflow (quality gap = 0.172)

Growth: HMM-TS 1.67x vs LinUCB 1.59x — ratio widens. Large quality gap favors LinUCB.

MBPP (quality gap = 0.037)

Growth: Both 1.06x — gap too small for either method to differentiate.

When Does HMM Routing Win?

Cross-Model Analysis (OASST, 10 seeds)

Config Quality Gap η Advantage
High base quality 0.031 18pp (72% vs 90%)
Small gap 0.037 15pp (78% vs 93%)
Original 0.074 12pp (85% vs 97%)
Noisy weak 0.089 9pp (89% vs 97%)
Large gap 0.130 7pp (91% vs 98%)

Key insight: HMM routing advantage is strongest when models have similar capability (small quality gap). Advantage drops from 18pp to 7pp as gap increases.

Session Advantage (Temporal Structure)

Dataset Advantage p-value Winner
Synthetic HMM 2.95x 0.031 HMM-TS
OASST 1.09x 0.75 Neither
WildChat 0.44x 1.00 LinUCB
Trajectory 1.25x 0.86 Neither

Critical finding: Temporal advantage is real under structured difficulty but absent on current i.i.d. benchmarks. Current benchmarks may not capture real sequential patterns in user interactions.

Competitive Landscape (Q1 2026)

After scanning 15+ papers: NO competitor uses HMM for latent query structure. All assume i.i.d. queries or use confidence/reasoning signals.

Primary competitor: Amin (2026.01) "Bayesian Orchestration of Multi-LLM Agents" — similar framing but different mechanism.

Our unique contributions: 1. HMM latent state model for sequential routing 2. O(N√T) belief-compressed regret bound 3. 16D embedding sweet spot (empirically validated)

16D Embedding Sweet Spot

128D experiments rejected (O(d³) matrix ops too expensive). Empirically, 16D provides the best cost-accuracy tradeoff across all datasets. Beyond 32D, diminishing returns with increasing computational overhead.

< BACK_TO_NOTES()