acceptodds
Under review as a conference paper at ICLR 2027

Principled Top- Selection for Language Models with Hybrid Gradients

Abstract

Selecting the best items out of candidates is a critical component of modern large language model systems, such as document selection in Retrieval-Augmented Generation (RAG) and expert routing in Mixture-of-Experts (MoEs). However, training these selection modules remains challenging due to weak gradient signals and suboptimal exploration-exploitation tradeoffs. Furthermore, prior works often rely on heuristics, lacking principled objectives and approaches that explicitly model and solve the top- selection problem. In this work, we propose a principled objective for training selection modules, whose gradient naturally provides richer training signals in a hybrid form—containing both a supervised component and policy gradients. We show that the selection problem becomes harder as increases, and our algorithm converges at rate , with the optimal upper bound achieved by balancing between bias and variance. Practically, we apply our method to a set of tasks involving top- selection, including synthetic regression problems, RAG, and MoE systems, showing that our method outperforms the baselines in next-token prediction perplexity and QA task accuracies.

Primary area:
optimization
Keywords:
Top-k selection, Optimization, Language models

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_WpQxOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to train top-k selection modules in language model systems, including document rerankers in RAG and expert routers in MoE. It argues that ordinary backpropagation mainly adjusts how selected items are combined, while providing limited direct feedback on the selection decision itself. The authors formulate training as minimizing expected task loss over subsets sampled without replacement. The resulting gradient combines a policy gradient term that updates selection probabilities with a supervised term that improves predictions using the selected items. A tunable coefficient on the policy gradient controls the bias–variance tradeoff.

The paper analyzes the relationship to an all-candidate reference objective and derives convergence bounds under stated assumptions. Experiments cover synthetic regression, RAG reranker training with frozen language models, and small MoE models trained from scratch on Wikitext-103. All experiments select three items while varying the candidate pool size. The reported results improve selection accuracy, QA exact match, and language modeling perplexity over the evaluated baselines, including a supervised-only variant, with a small nonzero policy-gradient weight generally performing best.

Critical strengths
  1. The distinction between learning which items to select and how to combine them is useful. It identifies a limitation of training through the selected outputs alone and motivates giving the selector direct feedback on its decisions through the final task loss.
  2. The explicit treatment of the bias–variance tradeoff is practically well motivated. It recognizes that an unbiased gradient can be difficult to use when its variance is high, and provides a simple way to balance noisy selection feedback with the supervised training signal.
  3. The evaluation examines both selection quality and prediction performance. Synthetic regression allows direct evaluation against known selection targets, while RAG and MoE test the approach with frozen and jointly trained predictors, respectively. These complementary settings strengthen the empirical case for the method.
Critical weaknesses
  1. The benefit of computing probabilities for unordered sets is not yet clear. A simpler hybrid estimator can use the probability of the actual sampling order while retaining the same sampling procedure, prediction loss, and supervised gradient. The current supervised-only comparison supports adding policy feedback, but does not establish how much additional benefit comes from accounting for all possible sampling orders.
  2. Practical scalability beyond k=3 is not sufficiently demonstrated. All experiments vary the candidate pool size while fixing the number of selected items at three. The paper does not report the cost of computing and differentiating the set probabilities in Eq. 8, or the resulting training overhead. Results at larger k, together with runtime measurements, would help establish whether the method remains practical as the selection budget grows.
  3. The preference for a very small λ\lambda may depend on the loss baseline. The method uses the average loss of other examples as a reference for the current selection. Since examples differ in difficulty, the policy feedback may contain noise unrelated to selection quality. It remains unclear how much the benefit of shrinking the policy term comes from compensating for this noise.
  4. The incremental benefit of policy feedback beyond exploration control remains unclear. The supervised-only baseline already includes stochastic selection and tuned sampling temperatures, and some additional gains on real tasks are modest. Although the improvements are consistent, the current evidence leaves open whether similar gains could be achieved through simpler adjustments to exploration. This makes the practical value of the additional policy-gradient term harder to assess.
Questions for authors
  1. Does summing over all sampling orders improve the results? In one regression or MoE experiment, could you compare the proposed method with a version that uses only the probability of the actual sampled order for the policy gradient? Keep the other settings the same. This would show how much the extra step of combining all possible orders adds to the final performance.

  2. How much extra computation does the method require? For example, a set of eight items has 8! = 40320 possible sampling orders, so explicitly summing over them could be expensive. Could you clarify how set probabilities are computed in practice and compare per-step training time with supervised-only training at k=3,4,8, including the time spent on set probabilities? Reporting task performance at one larger k would also help show whether the gains justify the extra cost.

  3. Would a different loss baseline change which λ\lambda works best? The current baseline uses losses from other examples, which may differ in difficulty. In one regression experiment, could you instead use each example’s own past losses as its baseline? Comparing the two choices would help show whether a very small λ\lambda still works best when the baseline better reflects the current example’s difficulty.

  4. Could you provide stronger evidence for the gains over supervised-only training? Some improvements are modest, particularly in the RAG language-modeling experiments. Could you compare the hybrid and supervised-only methods on one additional benchmark? Alternatively, you could repeat one representative experiment and report the average performance and variation across runs. These results would help establish whether adding the policy-gradient term provides a consistent benefit.

4 comments
AuthorsOpenReview ↗

Rebuttal by Authors

We appreciate the reviewer for the comments, and we address the concerns and clarification questions as follows.

[Probability of the actual sampling order] We thank the reviewer for this insightful question. Following the reviewer’s suggestion, denoting the sampled ordered sequence as SS, we use the probability of SS as πθ(I)\pi_{\theta}(I) in policy gradient computation, and the rest stays the same. We compare this 'Sequence probability' variant with our proposed method on the regression task.

MSE loss ($\times$1e-3, ↓\downarrow) on the regression task.

m=128m=512
Sequence probability1.37 (.01)3.25 (.03)
Set probability (ours)1.16 (.01)2.85 (.02)

The results show that computing the exact policy gradient (i.e., calculating the set probability rather than the sequence probability) is important. Theoretically, the update of the ‘Sequence probability’ baseline may not correspond to an objective function, and this would yield a biased gradient for the surrogate objective. We have also added the results to Table 4 in the revised paper.

[Memory and time] We thank the reviewer for mentioning this. We would like to clarify that computing π(I)\pi(I) does not require enumerating the k⋅k!k \cdot k! orderings: the denominator of each ordering depends only on which experts were drawn before, so the sum factorizes over subsets and can be computed by dynamic programming in O(k⋅2k)O(k\cdot 2^k) per token per selection module. This yields 2,048 rather than 322,560 terms at k=8k=8.

These costs of computing are negligible compared with the dominating costs of running forward and backward passes to optimize the model. Furthermore, the cost is independent of the candidate pool size and model width, so the costs become even more negligible as the model size scales up, a scenario where mm-choose-kk problems become exponentially more difficult, and our method has more advantage.

To further demonstrate scalability, we report the extra time and peak GPU memory needed for set probability compared to using the O(k)O(k) ordered sequence probability. The results are averaged across 20 steps. We use A100 GPU, m=64m=64, batch size = 128, one MoE layer. We observe that in each training step, our method adds 3.2 ms at k=3k=3 and 9.8 ms at k=8k=8, with at most 0.23 GB of additional peak memory. We have added these discussions to Appendix C of the revision.

k=3k=6k=7k=8
Memory+0.0 GB+0.05 GB+0.11 GB+0.23 GB
Time+3.2 ms+7.2 ms+7.7 ms+9.8 ms

[Leave-one-out baseline] We thank the reviewer for this suggestion. We would like to highlight that our method is general, and we can use any baseline for the gradient estimation. The leave-one-out baseline is a common and classical baseline for policy gradient. Following the reviewer’s suggestion, we run the suggested experiment on the regression task, replacing the leave-one-out baseline with an exponential moving average of each example’s own past losses.

MSE loss ($\times$1e-3, ↓\downarrow) for two baselines at m∈{128,512}m\in\{128, 512\}.

m=128m=512
Past loss1.28 (.02)3.12 (.04)
Leave-one-out1.16 (.01)2.85 (.02)

We observe that the optimal λ=0.05\lambda=0.05, so the variance of the policy term is dominated by subset sampling rather than example difficulty. Therefore, the preference for small λ\lambda is not an artifact of the baseline. We have also added this table to Table 3 of the revision.

[Benefit of policy gradient] We thank the reviewer for this question. First, we’d like to clarify that policy gradient provides signals on which subsets should be selected, whereas the supervised-only baseline only differentiates through the aggregation of already selected items, thus only providing signals on how to aggregate the selected items. Second, the supervised-only baseline already incorporates simple adjustments to facilitate exploration, including adding random noise to the item scores and tuning the sampling temperatures from a grid. Another baseline adds Gaussian noise with learned standard deviations [1] for exploration. Therefore, our improvements are relative to advanced baselines that already incorporate exploration. Empirically, we show that the policy term helps improve performance consistently over all the datasets.

[1] Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer. ICLR 2017.

AuthorsOpenReview ↗

Rebuttal by Authors (cont.)

[3-seed results and scaled-up MoE] In our original submission, we fixed the random seed to 0 for all methods, so the models are trained from the same initialization. To further demonstrate the statistical significance of the results, we run additional experiments with three random seeds and report the average and standard deviation of the metrics. We also add experiments for m=128m=128 for the multi-layer MoE setting, so we now have 10 MoE architectures. The results are shown in the tables below and updated in our revision, where we observe consistent improvements in our method.

MSE loss ($\times$1e-3) on the regression task.

m=64m=128m=256m=512
Deterministic1.02 (.01)2.02 (.01)5.71 (.02)5.97 (.02)
Gaussian1.38 (.02)2.16 (.02)5.13 (.03)6.18 (.04)
DefaultMoE1.19 (.01)1.43 (.01)1.87 (.02)3.30 (.03)
SparseMixer1.40 (.01)1.92 (.02)3.12 (.03)4.32 (.04)
Supervised-only0.99 (.01)1.42 (.01)1.92 (.02)4.68 (.03)
Ours0.95 (.02)1.16 (.01)1.49 (.03)2.85 (.02)

Top-1 selection accuracy on the regression task.

m=64m=128m=256m=512
Deterministic89.0 (.1)66.9 (.3)4.3 (.5)0.7 (.3)
Gaussian80.9 (.3)64.1 (.7)15.1 (1.6)2.2 (1.4)
DefaultMoE80.5 (.2)68.7 (.3)53.4 (.8)41.2 (1.5)
SparseMixer86.3 (.4)74.3 (.5)46.2 (.9)26.8 (1.1)
Supervised-only89.8 (.2)80.2 (.6)60.4 (1.3)11.9 (1.6)
Ours91.1 (.3)84.7 (.6)67.0 (1.1)47.8 (1.3)

Perplexity on Wikitext-103 by MoE (one layer).

m=8m=16m=32m=64m=128
Deterministic86.30 (.21)84.58 (.19)86.36 (.41)86.01 (.17)85.77 (.23)
Gaussian85.45 (.43)82.72 (.68)82.56 (.47)82.05 (.16)83.43 (.38)
DefaultMoE87.21 (.54)89.61 (.28)87.45 (.49)87.05 (.29)84.56 (.47)
SparseMixer87.92 (.67)86.23 (.52)86.31 (.61)86.21 (.23)86.23 (.33)
Supervised-only84.76 (.43)80.87 (.32)77.86 (.22)74.67 (.45)74.04 (.39)
Ours84.09 (.59)79.98 (.41)76.63 (.39)73.01 (.56)71.64 (.52)

Perplexity on Wikitext-103 by MoE (two layers).

m=8m=16m=32m=64m=128
Deterministic71.04 (.09)69.38 (.10)68.42 (.25)69.09 (.43)61.88 (.14)
Gaussian69.54 (.26)67.21 (.12)67.93 (.24)66.36 (.39)59.07 (.28)
DefaultMoE70.68 (.24)70.56 (.18)69.26 (.51)67.43 (.34)63.11 (.57)
SparseMixer71.22 (.39)68.34 (.51)68.66 (.30)69.67 (.37)63.42 (.33)
Supervised-only69.07 (.42)64.97 (.73)62.87 (.69)59.69 (.26)53.64 (.36)
Ours68.49 (.41)64.15 (.68)61.56 (.52)58.12 (.55)51.01 (.32)

Perplexity on wikitext-103 by RAG (Qwen-2.5-1.5B and Llama-3.2-3B).

QwenLlama
m=8m=16m=32m=8m=16m=32
Policy-only7.51 (.07)7.58 (.07)7.88 (.08)6.70 (.06)7.10 (.05)7.49 (.05)
ICRALM6.64 (.05)7.02 (.07)7.67 (.07)5.38 (.05)5.57 (.02)6.08 (.03)
REPLUG6.59 (.06)6.88 (.05)7.62 (.06)5.37 (.04)5.58 (.02)5.96 (.04)
Supervised-only6.51 (.05)6.78 (.06)7.26 (.07)5.32 (.04)5.55 (.03)5.88 (.03)
Ours6.38 (.02)6.65 (.05)7.15 (.03)5.26 (.05)5.43 (.04)5.76 (.02)

EM accuracy on NQ.

QwenLlama
m=8m=16m=32m=8m=16m=32
Policy-only25.1 (.6)29.5 (.4)30.5 (.4)29.9 (.3)31.7 (.5)33.3 (.4)
ICRALM27.4 (.3)29.7 (.3)30.5 (.5)30.6 (.3)34.2 (.4)35.1 (.2)
REPLUG27.2 (.3)29.9 (.3)31.4 (.5)31.1 (.2)32.9 (.6)34.7 (.3)
Supervised-only27.6 (.4)31.2 (.5)32.5 (.3)31.5 (.3)34.3 (.3)35.4 (.4)
Ours28.7 (.4)32.1 (.3)33.5 (.4)32.4 (.3)35.2 (.3)36.7 (.2)

Answer doc recall on NQ.

QwenLlama
m=8m=16m=32m=8m=16m=32
Policy-only55.9 (.5)62.5 (.6)67.4 (.6)55.4 (.5)63.0 (.4)67.4 (.3)
ICRALM65.3 (.3)74.2 (.5)81.3 (.2)65.1 (.4)73.4 (.1)79.2 (.2)
REPLUG64.9 (.3)73.4 (.4)79.4 (.3)64.8 (.2)73.1 (.2)78.3 (.3)
Supervised-only65.7 (.5)75.3 (.3)82.9 (.3)65.6 (.3)74.1 (.2)81.8 (.3)
Ours67.0 (.4)75.9 (.7)84.0 (.9)66.8 (.3)75.2 (.3)82.8 (.4)

EM accuracy on TriviaQ.

QwenLlama
m=8m=16m=32m=8m=16m=32
Policy-only56.4 (.6)58.1 (.5)61.1 (.5)70.7 (.4)71.1 (.4)72.9 (.5)
ICRALM60.2 (.3)61.3 (.3)62.1 (.2)72.2 (.2)74.4 (.2)74.3 (.4)
REPLUG60.5 (.4)61.7 (.3)63.3 (.4)72.8 (.2)74.7 (.3)75.3 (.3)
Supervised-only61.4 (.2)62.7 (.3)65.1 (.3)73.4 (.5)75.2 (.4)75.7 (.3)
Ours62.3 (.3)63.9 (.3)66.3 (.4)74.0 (.3)75.9 (.3)76.9 (.4)

Answer doc recall on TriviaQ.

QwenLlama
m=8m=16m=32m=8m=16m=32
Policy-only80.3 (.4)83.7 (.5)86.8 (.4)80.3 (.5)83.8 (.3)86.1 (.3)
ICRALM86.2 (.3)89.1 (.2)90.8 (.3)86.8 (.2)90.0 (.2)91.2 (.3)
REPLUG86.6 (.3)89.7 (.2)91.0 (.3)86.5 (.3)90.2 (.4)91.6 (.4)
Supervised-only86.9 (.2)90.4 (.3)92.4 (.3)86.9 (.3)91.1 (.5)92.2 (.4)
Ours87.5 (.4)91.6 (.4)94.1 (.2)88.0 (.4)91.9 (.3)93.4 (.3)

Thank you for the detailed response and substantial additional experiments. The new results have largely addressed my concerns and strengthened the empirical evidence side. I encourage the authors to incorporate these results and clarifications into the revised manuscript. I am happy to raise my score.

AuthorsOpenReview ↗

Reply to Reviewer Response

Thank you again for your valuable time and review! We are glad to know that the concerns have been addressed. Your insights strengthen this paper, and we will keep the new results and clarifications in our next version.

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

This paper discusses the learning model with a k-component selection procedure. For the general Top-k selection, it lacks sufficient evidence to select the global optimal modules or components in the practical training. To overcome this issue, it proposes the joint optimization of the selection and downstream task via hybrid gradients, a policy learner and a weight learner. Both theoretical analysis and empirical studies are conducted on the proposed method, and the performance is improved on several practical scenarios.

Critical strengths
  1. Selection like submodular optimization is a good perspective to understand the MoE problem. This also provides an insight in several practical cases in the training.

  2. The modeling is clear and easy to understand. I believe this is a clever way to model and solve the problem.

Critical weaknesses
  1. The convergence rate could be further refined since the unexpected constant bound, which can not be directly stated as a general optimization rate in the paper.

  2. Some key lemmas or formulas have certain issues and require further discussion and verification.

  3. The scale of the experiments is too small; current testing is limited to simple RAG tasks and extremely small-scale MoE tasks, and has not been conducted on actual, real-world network architectures.

  4. This modeling may have some issues when adopting in the MoE architecture. Specifically, top-k experts are a group of feature-preferred projection learners. If we adopt the sampling, the experts may be receive a lot of tokens whose embedding projection are totally different. This is an unexpected case in MoE architectures. Overall, the practical application of the proposed method is yet required more discussions.

  5. As the general experience, the sampling process costs a lot of time in the training. This modeling may introduce a large burden on the time and training efficiency. The authors do not report the training profiles.

Questions for authors
  1. Lemma B.6 and B.7 lack the temperature term τ\tau in the final bound. Authors should revise them in the proofs. There exist constructible counterexamples to the current conclusion that cause it to violate the upper bound.

  2. The gap r_\min is not a general constant. Lemma B.6 requires it at least satisfies r_\min\geq \log(2(m-k)). It must be discussed in details to claim the potential impacts on the theoretical analysis. The current conclusion is not strictly valid.

  3. The convergence rate include ϵ\epsilon and r_\max terms. Even for the λ=1\lambda=1, the gradient norm is still a constant upper bound. This only proves a possible neighborhood of the optimum is achievable instead of the valid convergence.

  4. Only the performance are reported. Does the selection module truly convergent in the training? Can author provide the learned distribution trends or other useful validation to show the selection policy is exactly optimized?

  5. What is the profile in the training in both memory and time efficiency?

4 comments
AuthorsOpenReview ↗

Rebuttal by Authors

We are grateful for the reviewer's detailed feedback. We present our responses and address the concerns as follows.

[Memory and time] We thank the reviewer for this question. We would like to clarify that the only overhead in our algorithm is to compute the set probabilities P(S)P(S) (Eq. (8)) and sample from them using the existing Python library (Lemma 3.1). Computing P(S)P(S) does not require enumerating the k⋅k!k \cdot k! orderings: the denominator of each ordering depends only on which experts were drawn before, so the sum factorizes over subsets of SS and can be computed by dynamic programming in O(k⋅2k)O(k\cdot 2^k) per token per selection module. This yields 2,048 probabilities at k=8k=8, and extra memory is rather small.

These costs are negligible compared with the dominating costs of running forward and backward passes to optimize the model. Furthermore, the cost is independent of the candidate pool size and model width, so the costs become even more negligible as the model size scales up, a scenario where mm-choose-kk problems become more difficult, and our method has more advantage.

To further demonstrate scalability, we report the extra time and peak GPU memory needed for set probability compared to using the O(k)O(k) ordered sequence probability. The results are averaged across 20 steps. We use an A100 GPU, m=64m=64, batch size = 128, one MoE layer. We observe that in each training step, our method adds 3.2 ms at k=3k=3 and 9.8 ms at k=8k=8, with at most 0.23 GB of additional peak memory. We have added these discussions to Appendix C of the revision.

k=3k=6k=7k=8
Memory+0.0 GB+0.05 GB+0.11 GB+0.23 GB
Time+3.2 ms+7.2 ms+7.7 ms+9.8 ms

[Application to MoE] Our sampling ensures that experts with higher router scores are more likely to be selected, and the sampling temperature controls the degree of exploration. In addition, we use policy gradients to learn the distribution over selected sets of experts, discouraging unfavorable expert assignments with large losses. We also empirically demonstrate that our method outperforms common baselines. We acknowledge that the exploration/exploitation tradeoff is a fundamental problem for MoE in general, which is why prior MoE papers use noisy top-kk sampling via adding Gaussian or Gumbel noise [1,2]. We have added more discussion to the paper.

[Experiment scale] We thank the reviewer for this question. We would like to first note that the RAG experiment finetunes Qwen-2.5-1.5B and Llama-3.2-3B, showing that large language models, despite being heavily trained, can still obtain additional performance gains from our selection module tuning. Our regression and MoE experiments are not on large models, but our selection problem is large-scale in the sense of being sparse (mm=128 or 512). We observe that 512-choose-3 or 128-choose-3 (denoted as 3/128) is already a sparse activation rate compared to many popular MoEs: Mixtral [3] uses 2/8, Grok-1 [4] uses 2/8, Phi-3.5-MoE [5] uses 2/16, OLMoE [6] uses 8/64, Qwen2-MoE [7] uses 4/60, and Qwen3 [8] uses 8/128. The toy problem on regression helps to precisely understand the top-k selection procedure as we can control the data generation process and labels.

We further addressed the reviewer’s concern by additionally running the m=128m=128 experiment in a larger-scale multi-layer MoE setting, and our improvement is consistent across all ten MoE architectures (Table 10 in revision). In Figure 6, we can observe that our method has better scaling in mm. Due to resource constraints, we do not perform pretraining on even larger model architectures. Our goal is to provide insights and analyses that we believe would generalize to larger scales, given the trends across mm’s in our results and our principled formulation.

[τ\tau in Lemmas B.6 and B.7] We thank the reviewer for catching this. Lemma B.6 was stated with p=softmax(z/τ)p=\text{softmax}(z/\tau), but the proof used the temperature-free softmax Jacobian. In our setup, τ\tau enters only the sampling distribution πθ\pi_{\theta}, and the aggregation weights are temperature-free (Appendix B.1). We have updated the lemma to p=softmax(z)p=\text{softmax}(z), under which CB=12CrChC_B = 12 C_r C_h is valid. In Lemma B.7, τ\tau was hidden inside CθC_{\theta} through Cθ=mk2Cr/τC_{\theta}=m k^2 C_r/\tau. We now state it explicitly in Lemma B.6 and B.7.

[1] Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer. ICLR 2017.
[2] MoEs Are Stronger than You Think: Hyper-Parallel Inference Scaling with RoE. arXiv 2025.
[3] Mixtral of Experts. Arxiv 2024.
[4] GitHub: xai-org/grok-1.
[5] Phi-3 Technical Report: A Highly Capable Language Model Locally on Your Phone. Arxiv 2024.
[6] OLMoE: Open Mixture-of-Experts Language Models. Arxiv 2024.
[7] Qwen2 Technical Report. Arxiv 2024.
[8] Qwen3 Technical Report. Arxiv 2025.

AuthorsOpenReview ↗

Rebuttal by Authors (cont.)

[Condition on γmin⁡\gamma_{\min}] The reviewer is correct that our proof implicitly requires γmin⁡≥log⁡(2(m−k))\gamma_{\min} \geq \log(2(m−k)). It was used because Lemma B.6 was stated only for subsets with ρI≤1/2\rho_I\leq 1/2, and the proof of Lemma B.7 needed this assumption to apply Lemma B.6. We have extended Lemma B.6 to all subsets, so the proof of Lemma B.7 no longer needs this requirement. The bound on ϵ\epsilon therefore holds for any γmin⁡>0\gamma_{\min}>0. A larger γmin⁡\gamma_{\min} only makes ϵ\epsilon smaller, and we have made changes in our revision.

[Convergence vs. neighborhood] We thank the reviewer for this question. In the paper, we establish convergence to both neighborhoods and stationary points for different objectives. To avoid confusion, we have made the wording more precise in Section 4. There are two statements: (1) For our surrogate objective JJ, the constant term in Eq. (9) vanishes and the algorithm converges to stationary points of JJ at rate O(1/T)O(1/\sqrt{T}). JJ is the objective that matches the practical deployment, where only kk items are used, and it upper-bounds FF for the NLL loss. (2) For the dense objective FF, Eq. (10) gives convergence to a neighborhood of radius governed by ϵ\epsilon, the truncation bias from evaluating k<mk<m items. The bias exists because one cannot optimize the dense selection objective (Eq. (1) in the paper) due to efficiency constraints. We are not aware of any previous work that studies convergence of practical top-kk selection algorithms to the true objective.

[Convergence of selection module] We thank the reviewer for this question. We would like to refer to Figure 8 in the original submission, where we visualize the evolution of selection decisions during optimization. The line chart represents the loss decrease, and each background color represents one selection decision on test samples. The figures show that the change in selection decisions slows down as optimization continues, so the selection policy converges. In addition, in our regression problem, we report the Top-1 selection accuracy of the selection module (Table 1 in our original submission). The selection accuracy is significantly higher than the random selection at initialization, and our method consistently outperforms the baselines.

Reviewer_xF4kOpenReview ↗

Thanks for the rebuttal

Thank authors for the rebuttal. The global optimal exists but the current continuous modeling may not accurately search for. I am not sure whether it would be an NP hard problem. And I believe the Eq (9) and (10) requires a remark to demonstrate how the constant bound affect the convergence in the main context. Other concerns have been successfully addressed and I will maintain the recommendation of acceptance at the current stage.

AuthorsOpenReview ↗

Reply to Reviewer Response

We thank the reviewer for replying and for maintaining the recommendation. We present our response as follows:

[Global optimum] We agree with the reviewer. Theorem 4.1 guarantees convergence to first-order stationary points, not to the globally optimal subset, which is the standard guarantee for non-convex stochastic optimization. The underlying discrete problem is closely related to best-subset selection, which is NP-hard in general [1,2]. Besides these, we would like to make three comments: (1) Our theoretical analyses focus on the discrete selection problem in language model architectures, where the selection and prediction modules are jointly optimized as in practical MoE deployment. The classical subset selection methods typically do not apply to MoE applications due to sparsity constraints. (2) The stochastic formulation does not exclude the optimum, since the expected loss over subsets is minimized by a distribution concentrated on the best subset. The difficulty lies more in the search than in the modeling. (3) The policy-gradient term is intended to help this search by providing signals on which subsets to select, and empirically it improves ground-truth selection accuracy (Table 2).

[Remark on the constants in Eq. (9-10)] We thank the reviewer for this suggestion, and we have added a remark after Theorem 4.1 in the revision. In summary, we remark that in Eq. (9), our algorithm reaches a neighborhood of a stationary point of JJ whose size shrinks as λ→1\lambda\to 1. At λ=1\lambda = 1, this term is zero. For the dense objective FF, Eq. (10) retains the bias from using k<mk < m items, which does not shrink with λ\lambda or TT.

[1] Sparse Approximate Solutions to Linear Systems. SIAM 1995.
[2] Best Subset Selection via a Modern Optimization Lens. Annals of Statistics 2016.

Reviewer_LWK2OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This work studies how to train top-K selection modules. It minimizes expected loss over k item subsets sampled without replacement from a softmax policy. Under certain conditions, this upper-bounds the dense objective. The gradient combines a REINFORCE term with a leave-one-out batch baseline and a pathwise term through the aggregation weights. This work's experiments cover synthetic regression, reranker training and small MoE models.

Critical strengths
  1. One extra loss term and one sampled subset per selection decision are enough to train both a RAG reranker and the router in every MoE layer. The sampled items are also distinct, as in deployment. The simplicity and breadth are valuable.
Critical weaknesses
  1. [1] already trains RAG end to end on an expected utility over k documents sampled without replacement. That is a closely related stochastic-selection formulation, yet it is not compared. The paper itself calls the score-function plus pathwise split standard for stochastic computation graphs and takes the subset distribution from prior work. The main algorithmic addition is thus the λ\lambda-scaled score-function term with a batch baseline. The contribution rests on showing that this term help.

  2. The bias term of Theorem 4.1 is the smallest at λ=1\lambda = 1 and barely changes for small λ\lambda. In both RAG and MoE, λ\lambda actually used is 1e-3 or 1e-4, where this bias term barely moves. The analysis does not quantitatively connect this tradeoff to observed gains over supervised-only. That margin is small, about one EM point on NQ and TriviaQA. The paper does not report variation across seeds, and the paper shows test performance across λ\lambda values without clearly stating whether λ\lambda was selected on a separate validation split.

[1] Zamani, Hamed, and Michael Bendersky. "Stochastic rag: End-to-end retrieval-augmented generation through expected utility maximization." Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2024.

Questions for authors

None

5 comments
AuthorsOpenReview ↗

Rebuttal by Authors

We appreciate the reviewer’s time and detailed feedback. We address the concerns and clarification questions as follows.

[Novelty and effect of λ\lambda] We thank the reviewer for pointing us to Stochastic RAG [1], which we have cited and discussed in revision. The reviewer is correct that [1] uses a related sampling model, whereas the difference is the gradient: [1] uses straight-through Gumbel-top-kk, a biased pathwise relaxation with no score-function term. Our estimator combines the exact pathwise gradient (i.e., the supervised gradient) with a score-function term (i.e., the policy gradient). Therefore, we refer the reviewer to the existing comparisons between our method and the 'Supervised-only' baseline, which has the same forward pass as [1] and has the unbiased backward pass, whereas [1] uses an approximate and thus biased backward pass.

We agree that the score-function/pathwise split has existed in stochastic computation graph literature, as stated in our submission. Beyond the λ\lambda-scaled term, our contributions are: (1) a set-level objective that approximates and sometimes upper bounds the dense objective whose gradients naturally contain rich signals for top-kk selection, while preserving sparsity, (2) convergence analysis to both the surrogate and the true objective, and (3) applying the objective to a range of top-kk selection problems with comprehensive experiments and comparisons.

We agree that it is a central question whether the policy gradient term helps. In prior literature, this term has typically been dropped or approximated in MoE training because of its variance. In our work, we show that the downweighted policy gradient is beneficial. We provide both theoretical and empirical evidence. Theoretically, Theorem 4.1 characterizes the bias/variance tradeoff: the convergence bound has a variance term growing with λ\lambda and a bias floor shrinking with it, giving an optimal λ⋆∈(0,1)\lambda^{\star}\in(0,1). Empirically, sweeps of λ∈[0,1]\lambda\in[0,1] show that the best-performing λ\lambda is in the interior, outperforming λ=0\lambda=0 in every setting. We now report mean and std over 3 seeds in the following tables and Table 2-10 in our revision.

[Theoretical gains] We would like to clarify that our theoretical analysis has quantitatively connected the bias/variance tradeoff to observed gains over supervised-only. As shown in Theorem 4.1, the hybrid gradient provides a smooth bias-variance tradeoff controlled by λ\lambda: Increasing \lambda reduces the bias and therefore lowers the asymptotic bias floor in the stationarity bound. On the other hand, increasing \lambda increases the variance of the policy gradient. Therefore, the optimal λ⋆∈(0,1)\lambda^{\star}\in (0,1), which is smaller when the policy gradient variance bound σP2\sigma_P^2 is large.

[Empirical gains] We thank the reviewer for noting that the gap over Supervised-only is about 1 EM on QA, whereas we note four things. (1) Our supervised-only (λ=0\lambda=0) is a slightly different method from stochastic RAG (see discussions in the first paragraph in our response), hence the comparisons with Supervised-only are an ablation of the policy gradient, not our margin over prior work. Over ICRALM/REPLUG, the gap is 2-3 EM on NQ at m=32m=32. (2) Our improvement is consistent, outperforming Supervised-only in all 36 RAG settings and all 10 MoE architectures, including the m=128m=128 multi-layer MoE setting we additionally run in this rebuttal. (3) The MoE experiments use ~230 tokens per active parameter, roughly 10$\times$ the Chinchilla-optimal ratio, so every method is at its loss plateau; a 2.6-PPL (3.4% relative) gap that survives saturation is algorithmic. (4) For comparison, REPLUG [2, Fig. 5] reports around 1-2 perplexity improvements in a comparable setting.

We thank the reviewer for mentioning this, and we clarify that hyperparameters, including λ\lambda, were selected on a separate validation set.

[1] Stochastic RAG: End-to-end Retrieval-Augmented Generation through Expected Utility Maximization. SIGIR 2024.
[2] REPLUG: Retrieval-Augmented Black-Box Language Models. ACL 2024.

AuthorsOpenReview ↗

Rebuttal by Authors (cont.)

[3-seed results] In our original submission, we fixed the random seed to 0 for all methods, so the models are trained from the same initialization. To further demonstrate the statistical significance of the results, we run additional experiments with three random seeds and report the average and standard deviation of the metrics. We also add experiments for m=128m=128 for the multi-layer MoE setting, so we now have 10 MoE architectures. The results are in the tables below and updated in our revision, where we observe consistent improvements of our method.

MSE loss ($\times$1e-3) on the regression task.

m=64m=128m=256m=512
Deterministic1.02 (.01)2.02 (.01)5.71 (.02)5.97 (.02)
Gaussian1.38 (.02)2.16 (.02)5.13 (.03)6.18 (.04)
DefaultMoE1.19 (.01)1.43 (.01)1.87 (.02)3.30 (.03)
SparseMixer1.40 (.01)1.92 (.02)3.12 (.03)4.32 (.04)
Supervised-only0.99 (.01)1.42 (.01)1.92 (.02)4.68 (.03)
Ours0.95 (.02)1.16 (.01)1.49 (.03)2.85 (.02)

Top-1 selection accuracy on the regression task.

m=64m=128m=256m=512
Deterministic89.0 (.1)66.9 (.3)4.3 (.5)0.7 (.3)
Gaussian80.9 (.3)64.1 (.7)15.1 (1.6)2.2 (1.4)
DefaultMoE80.5 (.2)68.7 (.3)53.4 (.8)41.2 (1.5)
SparseMixer86.3 (.4)74.3 (.5)46.2 (.9)26.8 (1.1)
Supervised-only89.8 (.2)80.2 (.6)60.4 (1.3)11.9 (1.6)
Ours91.1 (.3)84.7 (.6)67.0 (1.1)47.8 (1.3)

Perplexity on Wikitext-103 by MoE (one layer).

m=8m=16m=32m=64m=128
Deterministic86.30 (.21)84.58 (.19)86.36 (.41)86.01 (.17)85.77 (.23)
Gaussian85.45 (.43)82.72 (.68)82.56 (.47)82.05 (.16)83.43 (.38)
DefaultMoE87.21 (.54)89.61 (.28)87.45 (.49)87.05 (.29)84.56 (.47)
SparseMixer87.92 (.67)86.23 (.52)86.31 (.61)86.21 (.23)86.23 (.33)
Supervised-only84.76 (.43)80.87 (.32)77.86 (.22)74.67 (.45)74.04 (.39)
Ours84.09 (.59)79.98 (.41)76.63 (.39)73.01 (.56)71.64 (.52)

Perplexity on Wikitext-103 by MoE (two layers).

m=8m=16m=32m=64m=128
Deterministic71.04 (.09)69.38 (.10)68.42 (.25)69.09 (.43)61.88 (.14)
Gaussian69.54 (.26)67.21 (.12)67.93 (.24)66.36 (.39)59.07 (.28)
DefaultMoE70.68 (.24)70.56 (.18)69.26 (.51)67.43 (.34)63.11 (.57)
SparseMixer71.22 (.39)68.34 (.51)68.66 (.30)69.67 (.37)63.42 (.33)
Supervised-only69.07 (.42)64.97 (.73)62.87 (.69)59.69 (.26)53.64 (.36)
Ours68.49 (.41)64.15 (.68)61.56 (.52)58.12 (.55)51.01 (.32)

Perplexity on wikitext-103 by RAG (Qwen-2.5-1.5B and Llama-3.2-3B).

QwenLlama
m=8m=16m=32m=8m=16m=32
Policy-only7.51 (.07)7.58 (.07)7.88 (.08)6.70 (.06)7.10 (.05)7.49 (.05)
ICRALM6.64 (.05)7.02 (.07)7.67 (.07)5.38 (.05)5.57 (.02)6.08 (.03)
REPLUG6.59 (.06)6.88 (.05)7.62 (.06)5.37 (.04)5.58 (.02)5.96 (.04)
Supervised-only6.51 (.05)6.78 (.06)7.26 (.07)5.32 (.04)5.55 (.03)5.88 (.03)
Ours6.38 (.02)6.65 (.05)7.15 (.03)5.26 (.05)5.43 (.04)5.76 (.02)

EM accuracy on NQ.

QwenLlama
m=8m=16m=32m=8m=16m=32
Policy-only25.1 (.6)29.5 (.4)30.5 (.4)29.9 (.3)31.7 (.5)33.3 (.4)
ICRALM27.4 (.3)29.7 (.3)30.5 (.5)30.6 (.3)34.2 (.4)35.1 (.2)
REPLUG27.2 (.3)29.9 (.3)31.4 (.5)31.1 (.2)32.9 (.6)34.7 (.3)
Supervised-only27.6 (.4)31.2 (.5)32.5 (.3)31.5 (.3)34.3 (.3)35.4 (.4)
Ours28.7 (.4)32.1 (.3)33.5 (.4)32.4 (.3)35.2 (.3)36.7 (.2)

Answer doc recall on NQ.

QwenLlama
m=8m=16m=32m=8m=16m=32
Policy-only55.9 (.5)62.5 (.6)67.4 (.6)55.4 (.5)63.0 (.4)67.4 (.3)
ICRALM65.3 (.3)74.2 (.5)81.3 (.2)65.1 (.4)73.4 (.1)79.2 (.2)
REPLUG64.9 (.3)73.4 (.4)79.4 (.3)64.8 (.2)73.1 (.2)78.3 (.3)
Supervised-only65.7 (.5)75.3 (.3)82.9 (.3)65.6 (.3)74.1 (.2)81.8 (.3)
Ours67.0 (.4)75.9 (.7)84.0 (.9)66.8 (.3)75.2 (.3)82.8 (.4)

EM accuracy on TriviaQ.

QwenLlama
m=8m=16m=32m=8m=16m=32
Policy-only56.4 (.6)58.1 (.5)61.1 (.5)70.7 (.4)71.1 (.4)72.9 (.5)
ICRALM60.2 (.3)61.3 (.3)62.1 (.2)72.2 (.2)74.4 (.2)74.3 (.4)
REPLUG60.5 (.4)61.7 (.3)63.3 (.4)72.8 (.2)74.7 (.3)75.3 (.3)
Supervised-only61.4 (.2)62.7 (.3)65.1 (.3)73.4 (.5)75.2 (.4)75.7 (.3)
Ours62.3 (.3)63.9 (.3)66.3 (.4)74.0 (.3)75.9 (.3)76.9 (.4)

Answer doc recall on TriviaQ.

QwenLlama
m=8m=16m=32m=8m=16m=32
Policy-only80.3 (.4)83.7 (.5)86.8 (.4)80.3 (.5)83.8 (.3)86.1 (.3)
ICRALM86.2 (.3)89.1 (.2)90.8 (.3)86.8 (.2)90.0 (.2)91.2 (.3)
REPLUG86.6 (.3)89.7 (.2)91.0 (.3)86.5 (.3)90.2 (.4)91.6 (.4)
Supervised-only86.9 (.2)90.4 (.3)92.4 (.3)86.9 (.3)91.1 (.5)92.2 (.4)
Ours87.5 (.4)91.6 (.4)94.1 (.2)88.0 (.4)91.9 (.3)93.4 (.3)
AuthorsOpenReview ↗

Follow-up by Authors

Dear Reviewer,

Thank you again for your valuable time and detailed feedback! As the author-reviewer discussion phase is approaching its end, we would really appreciate it if you could let us know whether our rebuttal has sufficiently addressed your concerns. If you have any remaining questions or comments, we would be happy to respond before the discussion period ends.

Best regards,
Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.