acceptodds
Under review as a conference paper at ICLR 2027

A Theoretical Study of Model Routing with Distributional Losses

Abstract

Generative AI systems increasingly rely on routing user prompts among multiple generative models with different capabilities, costs, and output qualities. This is the problem of model routing, where a decision-maker selects among different generative models in an online fashion to optimize the quality and minimize the cost of the generated corpus. Currently, the majority of model routing algorithms use hard-coded routing choices or assume that the generated output can be evaluated in a per-prompt manner. However, a per-prompt loss alone cannot capture the efficacy of a generative model; instead, one needs to evaluate the generated output at a *distributional* level. For example, the Fréchet Inception Distance (FID) depends on the distribution of generated images. Motivated by this example, we introduce a formulation of the online model routing problem where the loss can depend on both per-round and distributional-level quantities. We show that one can extend classical decision-making algorithms such as Upper Confidence Bound (UCB) and Explore-Then-Commit to handle such losses when the loss is convex and satisfies a tail-bound assumption. These conditions are satisfied by canonical examples used widely in practice such as FID and Frontier Integral (FI). Overall, our work develops a principled formulation of model routing with novel distributional losses and shows that principled decision making is possible in these challenging settings.

Primary area:
learning theory
Keywords:
model routing, bandits, generative AI

Reviews

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

This paper presents a theoretical study of the model routing problem. Main contributions include the theoretical foundations for the Upper Confidence Bound (UCB) for regret loss and an Explore-Then-Exploit algorithm (and its variants) to find the optimal routing function. While the paper seems very interesting in the beginning, the later parts of the paper, especially the experiments section, seem way too thin and do not have many sufficient results. In addition, I found some issues with the proofs in the appendix.

Critical strengths

The theoretical analysis is in-depth and rigorous, though there are some errors.

Critical weaknesses

There are not enough results in the experiments section to support the presented theories.

Questions for authors

Where does the greedy algorithm (Algorithm 2) in Figure 1 come from? The names Algorithm 1 and Algorithm 2 also seem a bit confusing there.

Could you elaborate more on what the experiments are (e.g., prompts used, task details, model configurations)? Do you have empirical results to support Theorems 1-3 and Algorithms 1-3 from the main text?

How scalable is your algorithm for finding the best routing function?

In lines 850- 851 (proof of Thm 1), you lost a factor of K in the first term and hence a missing factor of K1/pK^{1/p} in line 862, which affects your claim of Theorem 1.

In line 900, I do not think the samples are I.I.D. If you look at lines 9-11 in Algorithm 2, you are picking samples conditioned on f(pt)=itf(p_t)=i_t. The set SfS_f is generated in a hypergeometric fashion, and therefore it is not necessarily a set of ∣Sf∣|S_f| I.I.D samples.

2 comments

Dear reviewer, thank you for the careful reading and thoughtful comments. Here we respond to the questions you raised.

  1. The algorithms in figure 1 are detailed in Section 5, with more discussion on the setup in Section D. The greedy algorithm is a variant of Algorithm 3 that does not do more exploration steps, as mentioned in Section 5, and it is detailed further in Section E (particularly Lines 1670-1671), and we believe it is a natural candidate to compare against.

  2. We do not detail experiments for Algorithms 1-3 as we believe it is most clear to empirically show our contribution for the “topics” setting. Our experiments are on synthetic data; details are described in Section E.

  3. The algorithm has asymptotically optimal regret, and we expect it to scale well. The constants in our proofs are not tight, but this is due to technical convenience.

  4. Thank you, you are correct and we will fix this.

  5. The samples are IID due to the way in which the model is selected. Specifically, the selection does not use any information about the prompt so each routing function has a 1/K1/K chance of being selected roughly aggregately. More formally, if the iti_t were chosen uniformly randomly from [K][K] each round, then the distribution conditioned on choosing iti_t is the same as the general distribution because the iti_t’s come in independently, and the same applies in aggregate for our bracketed case because the functions do not change.

Thank you again for the time and feedback!

Dear authors,

Thank you for the follow-up response. However, I am still unconvinced about the contribution of your theorems and algorithms, since they are not tangible in the sense that any real data or experiments can corroborate them. Regarding point 5, I still think that the sample is hypergeometric, especially due to line 10 of your Algorithm 2. Nevertheless, this is a minor technical concern; I maintain my original score due to insufficient backing of your main theorems and algorithms, which are the backbone of the paper.

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

This work theoretically studies model routing, which decides which model to use to answer a given prompt, depending on the expertise and cost of the available models. This work focuses on distributional losses, which accounts for the whole distribution of outputs over prompts, reflecting better diversity importance. The authors provide an upper bound on the regret of the Upper Confidence Bound algorithm in Theorem 1 and of a variant of the Explore-then-Exploit algorithm in Theorem 2. Finally, they illustrate their theoretical results experimentally, showing vanishing FID loss for their algorithm against a non-vanishing loss for the greedy algorithm.

Critical strengths

The main strength of that work is to tackle an important problem (model routing) through a principled and theoretical lens which is important to drive further progress and intuition in that area. The focus on distributional losses is interesting and seems novel. Additionally, all theoretical results are clearly stated. The assumptions are precise and well explained (Assumptions 1, 2, 3, 4), and the theorems are self-contained.

Critical weaknesses

The main weakness of this work is clarity. The paper is hard to read linearly and especially to understand the contribution section, which involves Assumptions 1, 2, 3, and 4, which appear only later in the paper. Additionally, the paper lacks precision in defining objects and too often refers the reader to the literature, such as in Example 2 ("similar to the MAUVE loss", "Theorem 1 of Liu et al..."), or in Remark 1 ("the loss from the bandit literature", "all lower bounds from the bandit literature"). While informal, such statements make it very hard to read for a reader not familiar with these works.

Another crucial weakness involves the experiment section, which provides very little context for the experiments, referring the reader to the appendix, which makes this section very hard to understand by itself. For example, Figure 1 compares some Algorithm 6, which has not been defined yet. Additionally, Figure 1 shows the same picture with a zoom on the last fraction of training, which doesn't seem necessary as it is already readable from the left figure. Finally, the absence of confidence intervals or standard deviations makes it hard to judge the robustness of the results.

Questions for authors
  1. In Theorem 33, the size of the function class F\mathcal{F} seem to have an important role in the bound. Could the author clarify whether, in practice, this function class is expected to be finite or even infinite, and what the consequences of an infinite class would be on the regret bound?

  2. I had a hard time understanding whether mim_i is a function from P:rightarrowΔ(X)P :rightarrow \Delta(X) or from P→XP \rightarrow X? Line 64 suggests the former, while equations 1 and 3 suggest the latter.

  3. Is Assumption 4 needed, or can it be derived from Assumption 3 (convexity) and the fact that LtotalL_{total} is defined on the set of probability distributions?

  4. Can the authors explain the equation at line 184? It involves many quantities which I believe were not defined and make this formula hard to understand. In particular what are σg,Σg,r,Ig\sigma_g, \Sigma_g, r, I_g?

  5. What values of pp (from Assumption 2) are expected in practice, and in particular in the context of the experiment from Section 5?

2 comments

Dear reviewer, thank you for the careful reading and thoughtful comments. On clarity, we will revise the exposition to make the paper more self-contained. For the experiment, confidence intervals and standard deviations were not added due to being less interpretable when considering a full training run, but the experiment was run more than once with qualitatively similar results.

Regarding the questions:

  1. F\mathcal{F} is a class of routing functions from prompts to models and for our setting, it should be thought of as finite.

  2. It is P→XP \rightarrow X, thank you for pointing this out

  3. Assumption 4 is not strictly needed and was imposed for technical convenience.

  4. These quantities are specific notation in the earlier work we cited there. The relevant feature is the functional form of O(1/T+1)=O(T−1/4)O(\sqrt{\sqrt{1/T} + 1})=O(T^{-1/4}) in their regret bound (which we improve). We will further revise this for clarity.

  5. p=2p = 2 in Assumption 2 is expected in most cases (sub-Gaussian concentration) and this holds for FID loss as per Example 1.

Thank you again for the time and feedback!

I thank the authors for their answers to my question and especially the notation concerns.

I remain unconvinced on why Assumption 4 was used if "not strictly needed" as acknowledged by the reviewers.

I will maintain my score. My main concerns regarding clarity have not been fully resolved. However, I reiterate that I have broad familiarity with this field but little or no direct research experience on this topic.

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

This paper provides a number of theoretical results regarding model routing, the practice of dynamically selecting the ideal model depending on the input prompt. The authors provide results across formulations where just one model will be chosen for all prompts as well as a version where a prompt-dependent routing function must be chosen among a number of predetermined functions. The authors merge well-known results from multi-arm bandit theory with online model routing to prove mathematical guarantees for the accuracy of routing mechanisms in the limit.

Critical strengths

The paper is extremely well-written and easy to understand. Algorithms, equations, and theorems are explained clearly, and assumptions are justified well. The theoretical findings are both useful and novel to the field of online model routing, providing strong corpus-level guarantees against baseline model choices.

Critical weaknesses

While the theoretical results are promising, the emprical validation is limited. The authors apply their methods only to small synthetic tasks and not to real pretrained generative models, and do not compare against any alternative online model routing methods. It thus remains unclear the extent to which these theoretical results are useful for real-world situations. In addition, exactly which contributions are unique to this paper and which are derived from previous papers is not clear.

Questions for authors
  • On lines 240-243, you note that boundedness of lroundl_{\text{round}} immediately implies assumptions 2 through 4. I do not see this, at least with the notation given. Assumption 3 is a function of probability distributions, not prompt/output pairs, and thus has no meaning with regards to convexity. If the intended meaning was to say that LtotalL_{\text{total}} fulfills all of the assumptions under per-round boundedness and Lglobal=0L_{\text{global}} = 0, that would follow, but the latter assumption is not given.

  • The definition of an oracle ERM is a bit confusing as currently written. Given that iti_t is directly mentioned, I recommend changing xtx_t with mit(pt)m_{i_t}(p_t), just so readers do not need to look back up to confirm definitions. This is a very minor note.

  • Given that the same model is not always the best for all tasks, the proofs in section 4 are especially important. Your current formulation relies on the existence of a predetermined set of routing functions, but this is often just the first (weak) step in what later becomes a more general function parameterized by a set of weights and learned via a policy gradient. Have you considered this next step in your work, or are there fundamental blockers to this path? If this work has been done by others, are there theoretical guarantees that could be applied to that regime? Even a small note in the paper discussing this fact would be very useful for future work.

  • While the related work section provides useful comparisons, it adds confusion regarding exactly what your contribution is relative to recent work in this field. Is it primarily the formal proving of algorithmic results, or is it instead the expansion of previous results to work on a global scale that cannot be calculated until all prompts are done?

1 comment

Dear reviewer, thank you for the careful reading and thoughtful comments. Here we respond to the questions you raised.

  1. We apologize for the confusion; the second interpretation you gave is the intended one. We will clarify this statement in a revision of the manuscript.

  2. Thank you, we will change the notation in a revision of the manuscript.

  3. Thank you for the suggestion, we agree that the setting of a general routing function parametrized by weights and then learned is a very interesting direction. We will add a discussion on this next step in our paper. To the best of our knowledge, no theoretical work has been done on this. We have not yet extended our work to this setting as the theoretical work on model routing is in its infancy, but we are not aware of any blockers either.

  4. We view our main contribution as the formalization of the model routing problem with global losses -- which we believe is a better abstraction of practical settings where the corpus of generated outputs must be evaluated -- and the proof of our algorithmic results. Most of the work on model routing has been in the per-round setting rather than the global setting, while the global setting is a more accurate abstraction where existing bandit results do not apply. A few prior works Hu et al. (2024; 2025a;b); Rezaei et al. (2024) mentioned in our manuscript consider global losses for the case of FID loss, but in our work we prove a tighter concentration for FID and obtain a corresponding improved regret bound to (nearly) optimal O~(T−1/2)\tilde{O}(T^{-1/2}) regret.

Thank you again for the time and feedback!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.