Generalizable Routing to Unseen LLMs via Dynamic Case-Based Memory and Diverse Candidate Sets

Routing among heterogeneous LLMs is essential for reducing the execution cost of agentic systems, where a router must select the most cost-effective model at each round. Generalizing to unseen LLMs remains difficult: state-of-the-art routers depend on representations or memories that are not adapted to the evolving candidate pool, and they are typically trained on a single large pool that limits exposure to diverse LLM combinations. We introduce GREAT, a case-based memory that stores the most recent routing decision for similar inputs and is dynamically updated so that each decision reflects the latest capabilities of the underlying models. We further train routers on a diverse set of candidate sets simultaneously, deriving a candidate-set selection score from the meta-RL formulation, proving its weak submodularity, and using a greedy algorithm with adaptive stopping to construct near-optimal sets. Experiments across diverse benchmarks demonstrate the effectiveness of our approach.