acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Multi-agent LLMs, Generalizable LLM Routing, Heterogeneous agents

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_FhhaOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes GREAT, a framework for generalizing LLM routing to unseen models and candidate sets. The method combines a dynamic case-based memory of past routing decisions and a strategy for constructing diverse candidate sets during training. Experiments across routing backbones and benchmarks report improvements in accuracy and execution cost, including settings with unseen LLMs and held-out datasets.

Critical strengths

Generalization to unseen LLMs and changing candidate pools is a practically important challenge for LLM routing. The method is evaluated across five routing backbones and multiple benchmarks, and the paper reported improvements in both accuracy and execution cost.

Critical weaknesses

Theorem 2 establishes submodularity over collections of candidate LLM sets, whereas Algorithm 1 greedily adds individual LLMs to construct a single candidate set. Submodularity in the former does not imply submodularity in the latter. Thus, the claimed approximation guarantee does not appear to apply to the actual algorithm, undermining a central theoretical contribution. GraphPlanner+GREAT achieves 85.8% accuracy and 64.4 cost in Table 1, compared with 87.0% and 59.4 in Table 2, and 83.2% and 91.5 in Table 4. The paper does not clearly explain the differences in experimental settings underlying these results, making the reported improvements difficult to assess reliably.

Questions for authors

How does Theorem 2 justify Algorithm 1, given that the theorem concerns selecting sets from a collection, while the algorithm selects individual LLMs within a set? Why do the GraphPlanner+GREAT results differ across Tables 1, 2, and 4?

Reviewer_ZvP2OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the generalization of Large Language Model (LLM) routing when the set of candidate models changes—specifically when encountering LLMs that were not seen during the training phase. The authors propose the GREAT framework, which consists of two primary components:

  1. Dynamic Case-Based Memory: This component records the execution states, selected LLMs, and associated execution costs from past routing decisions. It employs both local and global memory mechanisms to retrieve relevant historical cases, thereby informing current routing decisions. The global memory is continuously updated during training and frozen during inference, while the local memory is accumulated dynamically as individual tasks are executed.
  2. Diverse Candidate Set Construction: Through a bilevel optimization framework, the selection of a candidate set is framed as an alignment problem between training gradients and validation gradients. The authors introduce a "gradient-alignment-based coverage objective"—which they prove to be submodular—and utilize a greedy strategy to select the training candidate set, enhancing the model's ability to generalize to previously unseen combinations of LLMs.

The experiments span five task categories and 11 benchmarks, with the GREAT framework integrated into five distinct types of routers. In scenarios where the sets of LLMs used for training and testing are disjoint, the authors report an improvement in average accuracy of 1.6–7.1 percentage points, alongside an 8.8%–36.5% reduction in execution costs. When tested on combinations of previously unseen datasets and LLMs, accuracy improved by 3.3–5.2 percentage points, while costs decreased by 8.2%–57.6%. The paper also provides a comparison of candidate set selection strategies, an ablation study of the memory mechanism, and an analysis of training efficiency.

Critical strengths

1. The research addresses a highly practical problem, and the proposed method offers strong generalizability.

As new Large Language Models (LLMs) continue to emerge, routing mechanisms must adapt to models—and combinations thereof—that were not encountered during the training phase. This paper tackles this practical challenge by introducing improvements in two key areas: the utilization of historical routing information and the construction of candidate sets for training. GREAT can be integrated into various existing routing architectures without requiring a complete replacement of the original training objectives, which underscores its practical utility and potential for scalability.

2. The experimental evaluation is comprehensive and demonstrates consistent performance gains.

The authors evaluated five different routing models across five task categories and 11 benchmarks, specifically examining scenarios involving unseen LLMs, unseen datasets, and varying candidate sets. The experimental results indicate that GREAT can simultaneously enhance task performance and reduce execution costs across multiple settings. Furthermore, the authors compared six different candidate set selection strategies and conducted ablation studies to analyze the impact of local memory, global memory, and the size of the candidate set, providing robust empirical evidence for the effectiveness of the proposed method.

Critical weaknesses

1. There is a discrepancy between the theoretical guarantees and the algorithm used to construct the candidate set.

Theorem 2 in the paper proves that when selecting a set of training subsets from a library of candidate sets, the coverage function exhibits submodularity, allowing for an approximation guarantee via a greedy algorithm. However, Algorithm 1 constructs a single candidate set by adding LLMs one by one. These two processes correspond to different optimization problems: the former involves selecting candidate sets from a library, while the latter involves selecting individual models from a model pool.

Consequently, the current theoretical results do not appear to directly support the greedy construction method used in Algorithm 1 or its near-optimality. In particular, the paper fails to sufficiently demonstrate that the objective function retains the required submodularity property when models are added to an individual candidate set. This undermines the alignment between the paper’s theoretical contributions and its practical algorithm.

2. There is a lack of sufficient explanation regarding the generalization mechanism for unseen LLMs and the associated deployment costs.

Appendix A of the paper suggests that when an unseen set of candidate models is encountered during testing, the corresponding training gradients must be computed, and the most similar historical candidate set must be retrieved based on gradient similarity. However, for a truly unseen LLM, calculating such gradients would likely require executing the model, collecting feedback, and performing additional gradient estimation.

This raises a critical question: can this method perform zero-shot routing for entirely new LLMs, or does it require the collection of execution data for these new models first? If additional model invocations are necessary, the associated costs and latency could negate the overall cost advantages claimed in the paper. Furthermore, the "memory" in the proposed approach primarily records execution states, selected models, and costs—without explicitly storing information regarding response quality or task success. As a result, there is no direct evidence to show how this dynamic memory can reliably correct erroneous routing decisions made in the past.

These issues complicate the assessment of the method’s actual generalization capability and its value for practical deployment.

Questions for authors

Please see above.

Reviewer_7d3AOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper propose GREAT, a framework for generalizing LLM routing to unseen candidate models. It combines a dynamic case-based memory with a gradient-alignment-based procedure for selecting diverse training candidate sets. Experiments across five routing backbones report consistant improvements in accuracy and execution cost on unseen LLMs and held-out datasets.

Critical strengths
  • The considered problem is an important one. Relevant to ICLR conference's main topic.
  • The experimental setup looks complete.
Critical weaknesses
  1. The reported "better" results is not convincing from statistical point of view. Most benchmarks contain only 50 test questions (30 for AIME), and the paper does not report variance across training seeds or confidence intervals. Several accuracy improvements are small relative to the evaluation granularity, making their significance difficult to assess.
  2. There seems some gap between theory and algorithm. Theorem 2 establishes submodularity over collections of candidate sets, whereas Algorithm 1 greedily adds individual models to construct a single set. It is unclear whether the theoretical approximation guarantee applies to the implemented algorithm. The distinction between weak and exact submodularity also needs clarification.
  3. It is not clear to me how to apply this method in runtime (or test-time). Appendix A requires computing a training gradient for an unseen candidate set to retrieve its corresponding memory. How this gradient is obtained without additional task supervision or potentially expensive model executions is not explained. The resulting inference overhead is also unclear.
Questions for authors
  1. Can the authors clarify how Algorithm 1 is theoretically justified by Theorem 2? Does the proposed guarantee hold for greedy model-level selection?
  2. How to apply the algorithm at runtime? How is the gradient for an unseen candidate set computed at inference time? Does it require additional executor calls, and is this overhead included in the reported costs?
  3. Can the authors provide multi-seed evaluations with confidence intervals, clarify the differences between the reported experimental results?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.