- 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 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 . The set is generated in a hypergeometric fashion, and therefore it is not necessarily a set of I.I.D samples.
2 comments
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.
Dear reviewer, thank you for the careful reading and thoughtful comments. Here we respond to the questions you raised.
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.
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.
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.
Thank you, you are correct and we will fix this.
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/K chance of being selected roughly aggregately. More formally, if the it were chosen uniformly randomly from [K] each round, then the distribution conditioned on choosing it is the same as the general distribution because the it’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!