Label Uncertainty in LLM Routing: Effects of Prompt Variation and Decoding Stochasticity

LLM routing systems commonly rely on benchmark-derived labels to decide whether a query should be handled by a smaller model or escalated to a stronger one. However, such labels are often obtained from a single evaluation instance and therefore provide only a sampled observation of model behavior rather than a stable characterization of model capability. This creates uncertainty in routing supervision: a query that appears suitable for a smaller model in one run may become unreliable under a semantically equivalent prompt variation or a different stochastic decoding sample. We study prompt-induced and decoding-induced uncertainty in routing labels and show that both sources can reduce label reliability and propagate to unstable routing decisions. To mitigate this issue, we construct routing labels from repeated evaluations across prompt variants and decoding samples, producing aggregate estimates of model correctness and escalation benefit. Experiments on GPQA with Qwen2.5 models show that these repeated-evaluation-based labels improve cost-adjusted routing utility and reduce regret compared with single-shot correctness labels. Our results suggest that accounting for label uncertainty provides a simple and effective path toward more reliable LLM routing.