Research map / Large language models / Reasoning and chain of thought

MESS+: Dynamically Learned Inference-Time LLM Routing in Model Zoos with Service Level Guarantees

NeurIPS 2025 · Large language models › Reasoning and chain of thought · approach: Routing, pruning and distillation for reasoning · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes MESS+, an online Lyapunov virtual-queue routing algorithm that learns per-model request satisfaction probabilities with a lightweight ModernBERT predictor to minimize LLM inference energy while meeting an SLA satisfaction rate.

Problem

Routing requests across an LLM model zoo to minimize operating cost while guaranteeing a minimum long-run request satisfaction rate (SLA), without prior knowledge of which model satisfies each request.

Approach

Combines a Lyapunov drift-plus-penalty virtual queue tracking SLA undershoot with an online-trained satisfaction predictor; per-request routing solves a small optimization over predicted satisfaction and energy cost, with epsilon-style exploration (probability c/t^{1/4}) that queries all models to label satisfaction.

Key results

• Averaged across 8 benchmarks, MESS+ achieves 1.08 MJ cost at 68.44% satisfaction (alpha 66%), versus 2.11 MJ for RouterDC and 2.04 MJ for RouteLLM, roughly 2x cheaper while satisfying SLA.
• On ARC Challenge (alpha 50%), MESS+ costs 0.83 MJ vs 2.09 MJ for RouterDC with 53.64% satisfaction.
• With a larger Qwen zoo (32B/7B/1.5B/0.5B), MESS+ costs 0.84 MJ vs 1.13 MJ for RouterDC at 67.55% satisfaction (alpha 67%), up to 1.6x cheaper than baselines.

Measured effects reported in the paper

Surprising findings

• Educated guessing with prior knowledge still undershoots the SLA on some benchmarks (e.g., ARC Easy 74.00% vs alpha 75%), showing that fixed random routing is not reliably SLA-compliant.
• Routing overhead of the predictor is small (4.65% of average LLM call cost), but RouteLLM overshoots alpha by routing most requests to the 70B model, raising cost.

Limitations

• Requires user satisfaction feedback for every request and exploration that queries all models, which may be impractical.
• Assumes i.i.d. requests and cost for the theory; experiments show empirical but not proven robustness to non-i.i.d. settings.
• Evaluated only on multiple-choice benchmarks with binary correctness labels and small zoos (3 or 4 models).

Experimental setup

Datasets: ARC Challenge ARC Easy BoolQ LogiQA PiQA SciQ SocialIQA Winogrande

Benchmarks: ARC Challenge ARC Easy Winogrande BoolQ LogiQA PiQA SciQ SocialIQA

Metrics: operating cost (MJ energy per request) request satisfaction rate (%) model call ratio

Baselines: Llama 3.2 1B only Llama 3.1 8B only Llama 3.3 70B only Educated Guessing RouteLLM RouterDC

Builds on: RouteLLM RouterDC Lyapunov drift-plus-penalty

Closest papers by meaning

• BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute (ICML 2025 · similarity 0.89)
• TokenRouter: Efficient Serving System for Token-Level LLM Routing (NeurIPS 2026 · similarity 0.89)
• Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing (ICLR 2024 · similarity 0.89)
• Dr.LLM: Dynamic Layer Routing in LLMs (ICLR 2026 · similarity 0.89)
• Efficient LLM Scheduling by Learning to Rank (NeurIPS 2024 · similarity 0.89)
• RACER: Risk-Aware Calibrated Efficient Routing for Large Language Models (ICML 2026 · similarity 0.88)