Reranking Laws for Language Generation: A Communication-Theoretic Perspective

Thank you for your review and suggestions. We are happy that you found our paper well written and the motivation and theoretical analysis interesting. We understand that your main concerns about our paper are related to our empirical validation—we address them below. We hope that this clarifies and alleviates your concerns.

“The related work analysis is not comprehensive. There are several ranking and reranking works in recommended systems, and none of them is mentioned or compared in this paper.”

We welcome any suggestions you may have about related literature in reranking on recommender systems. Note, however, that the focus of our paper is very different: we are primarily concerned with reranking outputs of LLM generators and we study how the quality of the combined system is affected by the number of generated hypotheses and what their asymptotic properties are. Most of the works we are familiar with in the context of recommender systems study the different problem of, given a list of $N$ recommendations, reduce its size to $K<N$ elements through reranking.

“The experiments are not convincing enough. This paper only conducts two downstream experiments, i.e., Code generation and Machine translation. The results should be evaluated through more common and popular downstream tasks, such as QA (question choice) scenarios.”

Thank you for the suggestion. We have run additional experiments on mathematical and commonsense reasoning benchmarks, and we observed that the same trends hold also for these two tasks, validating our method on other domains. We hope that this alleviates your concerns regarding the experimental part of our paper. Please see the general response for more details.

“There is only 1 baseline for the text-to-code generation task and 2 baselines for the machine translation task. In particular, the one baseline for the text-to-code generation task is majority voting, which is not representative enough.”

Could you please clarify what you mean by “baseline”? Please note that our main goal is not to compare any method to a specific baseline but rather to validate our theoretical analysis using perfect and imperfect rerankers. Besides, we want to highlight that majority voting can be seen as a particular case of MBR decoding (Bertsch et al., 2023). In our experiments on text-to-code generation, we use MBR-exec (Shi et al., 2022), which is based on execution match. We would like to note that reranking methods relying on execution-based metrics are widely used in code generation (see, e.g., Chen et al., 2023; To et al., 2024). To clarify, as explained to Reviewer aDZG, MBR-exec consists of (1) sampling programs from an LLM, (2) executing each program on one test case, and (3) selecting the example with the minimal execution result-based Bayes risk. We use a 0/1 matching loss between execution results and the Bayes risk of a program is defined by the sum of the loss between itself and the other sampled programs. Since we are comparing the execution result of different programs, the Bayes risk will be minimal for the programs whose execution result is more frequent, hence the term “majority voting”. However, we understand that this term may be a bit misleading in this context and will update the paper accordingly. We will also use the additional page to include information on how MBR decoding works, instead of simply pointing to the papers.

References:

Chen et al., 2023. CodeT: Code Generation with Generated Tests.

To et al., 2024. Functional Overlap Reranking for Neural Code Generation.

Thank you for your positive review and suggestions. We are glad that you found our paper well written and easy to follow, and the theoretical analysis interesting. We address below your main concerns.

“limited empirical evaluation, with only two tasks, one generator model, and two reranking methods (besides an oracle ranker).”

Thanks for pointing this out. While our focus was on machine translation and text-to-code generation, we have run additional experiments on mathematical and commonsense reasoning benchmarks and observed that the same trends hold also for these two tasks, validating our method on other domains. We hope that this alleviates your concerns regarding the limited empirical evaluation of our method. Please see the general response for more details.

“the evaluation also makes some (in my opinion) debatable claims (...) the authors state “[...] the imperfect reranker with majority voting, which fits the data well (...) analysing Fig 4 (top), I would argue that the solid lines do not capture the data behaviour that well (...) Maybe running this analysis for larger values of N would show whether the data indeed fits the predictions (...).”

As discussed in the limitations section, while the experiments suggest a reasonable fit, you are right that the fit is not perfect and we will adjust the text accordingly. In fact, for large $N$, errors are rare events, and therefore prone to statistical inaccuracies (this is visible in the “steps” observed in the code generation plots). For text-to-code generation, in practice, most work does not use more than 200 samples due to the increased cost. For LLM-based machine translation, the work of Farinhas et al. (2023), which we use in our experiments in Section 5.2, suggests that using a smaller $N$ is enough. Even though this is not discussed in the paper, the cost of MBR decoding grows quadratically with the number of hypotheses $N$, making it impractical to try values higher than these ones. In any case, both results appear to be consistent with the new tasks we experimented on (as mentioned in the previous point).

“In the code generation experiments, the paper says “we use only one test case for each problem (Shi et al., 2022), and select one candidate by taking a majority vote over the execution results, dismissing hypotheses that fail to execute on the test case.” If a single test case is used, how is majority voting performed exactly? More details here could be helpful.”

We agree more details will be helpful – due to space constraints we ended up trimming some details about specific reranking techniques such as MBR decoding or reranking based on quality estimation. In this particular experiment, we follow MBR-exec, an approach proposed by Shi et al. (2022) that consists of (1) sampling programs from an LLM, (2) executing each program on one test case, and (3) selecting the example with the minimal execution result-based Bayes risk. We use a 0/1 matching loss between execution results and the Bayes risk of a program is defined by the sum of the loss between itself and the other sampled programs (of course, the ground-truth program output is not used). This is described in detail in the original paper (see., e.g., their Section 3). We break ties by selecting the program with the smallest sampling index, corresponding to a random selection. For completeness, for machine translation we followed the exact same procedure as described in Farinhas et al. (2023). In this case, as described in L243-246, MBR decoding does not use “execution results” but is rather based on a utility function based on a reference-based metric (in our case, Comet-22). We agree that this information should be described in more detail, and we will add descriptions of all the methods that we used for text-to-code generation and machine translation in a dedicated section.

Thank you for the suggestions!

I thank the authors for their response. I still think that running this analysis for larger values of $N$ would be good (or improving how the paper assesses that the data fits its predictions), but I have increased my scores due to the extra experiments added. I think this is an interesting paper that should be accepted.

Thank you for your positive review and suggestions. We are glad that you found our paper to be very well written, the math to be clear and sound, and our method to have practical use. We address below your concerns about our paper.

“there is not the same binary notion of acceptable/unacceptable (...) I would like to see an additional discussion (...) for continuous evaluation metrics”

This is a very good suggestion. Our framework can indeed be extended to continuous evaluation metrics, although some concepts (e.g. the notion of “asymptotically error-free”) would need to be modified accordingly. We sketch below some ways in which this extension could be made:

• We would need to posit a probability density for the continuous evaluation metric (instead of a Bernoulli error probability) for each hypothesis coming from the generator. In the simplest case, this could be a Gaussian distribution with some input-dependent mean and variance. For bounded evaluation metrics (e.g. between 0 and 1) other families would be more suitable (e.g. uniform or Beta distributions).
• For a perfect reranker and independent hypotheses, the resulting output after reranking would be distributed according to the corresponding extreme value distribution (this models the distribution of the highest quality score among the $N$ hypotheses). Extreme value distributions are an important subject of study in order statistics. For example, for the Gaussian case above, we would obtain a Gumbel distribution, for uniform we obtain Beta, etc. The asymptotic case ($N \rightarrow \infty$) corresponds to one of Gumbel, Fréchet or Weibull families (this is a consequence of the Fisher–Tippett–Gnedenko theorem [1]). From the extreme value distribution, we can obtain the expected quality score or the probability of a quality score being below a threshold.
• Unfortunately, the generalization to imperfect rerankers (e.g. Mallows or Zipf-Mandelbrot rerankers) seems much harder than in the binary case.

In the paper, we opted for focusing on the binary acceptable/unacceptable case for three main reasons: (1) This case is simpler to analyze and to understand (particularly when rerankers are imperfect). (2) It is still highly relevant in practice – e.g., in code generation, as well as other tasks, the code either executes and gives the correct answer, or it doesn’t (regardless of its quality). (3) It would be very hard to cover both the binary and continuous cases in the right level of detail in a single 9-page paper, hence we decided to go deeper on the former and leave the latter for future work.

Yet, we will use the additional page to add this discussion, as suggested.

[1] David, Herbert A.; Nagaraja, Haikady N. (2004). Order statistics. John Wiley & Sons. p. 299.

“Some aspects of the abstract/intro are confusing because terms have not been defined and their equivalences in an LLM generator-reranker system have not yet been specified.”

Thank you for pointing this out. The paragraph in L41-47 and Figure 1 provide a brief explanation of how an LLM generator-reranker system can be seen as a communication system, but we agree that the wording might not be easily understood for a first-time reader. We will improve the text and update the caption of Figure 1 to include more information, hopefully making it more clear.

“There isn’t much intuition about what the R.V. X corresponds to in the generator-reranker system”.

In our setup, we assume that a sender transmits $N$ message descriptions in parallel through noisy channels, resulting in the generation of $N$ potentially corrupted hypotheses $y_i, i\in\{1,...,N\}$. The LLM generator consists of both the sender and the noisy channels, where the $y_i, i\in\{1,...,N\}$ are the $N$ hypotheses sampled from the model. For example, in a machine translation scenario, these $y_i$ correspond to $N$ alternative translations, each potentially containing errors. The message descriptions $x_1, ..., x_N \in \mathcal{X}(q)^N$ correspond to acceptable answers within the equivalence class $\mathcal{X}(q)$ (as explained in footnote 1), before being corrupted by the noisy channel. This will be clarified in the final version.

“Some more intuition behind the scale parameter (...) would be helpful”

We agree that this can be further clarified in the paper. We mentioned the cases of a random reranker ($e^{-\lambda}=1$) and a perfect reranker ($e^{-\lambda}=0$). For a Mallows model, $e^{-\lambda}$ strictly between 0 and 1 correspond to imperfect rerankers that are better than random. The lower this value, the higher the quality of the reranker. Thus, $e^{-\lambda}$ works as an inverse measure of reranker quality. We will clarify.

“The computational experiments are not very comprehensive (...).”

We agree that the paper becomes stronger if we report experiments in more tasks beyond machine translation and text-to-code generation. We have run additional experiments on mathematical and commonsense reasoning benchmarks, validating our method on other domains. Similar trends hold for the new experiments, which confirms the general applicability of our approach. We hope that this alleviates your concerns. Please see the general response and attached figure for details.

(continues in a follow-up comment)

“I didn't understand (...) lines 148-9 (...) the quality of the reranker depends on the quality of the generator.”

Thank you for letting us know that you found this part unclear. We want to clarify that the quality of the reranker itself is independent of the quality of the generator. While both perfect and Mallows rerankers achieve exponentially decreasing error probabilities as the number of hypotheses $N$ increases, the exact rate of convergence is different. For the Mallows reranker, the rate of convergence also depends on the parameters of the Mallows model ($\lambda$). As shown by Eq. (2), $P_\mathrm{err}(N; q)$ decays exponentially as $\epsilon^N$, where $\epsilon$ is the probability of generating an unacceptable hypothesis. For a Mallows model, Proposition 1 shows that the error probability also decays exponentially, with $P_\mathrm{err}(N; q) = \mathcal{O}((e^{-\lambda}(1-\epsilon) + \epsilon)^N)$. While the convergence rate $e^{-\lambda}(1-\epsilon) + \epsilon$ is generally greater than $\epsilon$, it still ensures an exponentially decreasing error probability as $N$ increases. Thus, what we meant with the bolded comment in lines 148-9 is that Mallows rerankers behave asymptotically like perfect rerankers but with a higher effective error probability, due to the additional factor depending on $e^{-\lambda}$. That is, asymptotically, a bad (Mallows) reranker is equivalent to a perfect reranker with a worse generator. We will clarify this in the final version.

“move the first sentence of 3.3 to right after providing the expression for the partition function.”

Even though this result is not used in the previous section, we agree with the recommendation. We will update the paper accordingly, keeping a reminder in Section 3.3.

“In footnote 1: equivalent class -> equivalence class.”

Thanks for pointing this out, we will fix the typo.

Thank you for your positive review and suggestions. We are happy that you found our approach to be well formalized and flexible, the parallel with communication theory useful, and the experiments relevant.

We agree that the paper would benefit from more discussion about how our results can be useful in practice. Sections 6 and 8 already provide some information about this (e.g., the reranking laws allow us to predict how many hypotheses are necessary to achieve a desired error probability), but we will update the manuscript with a more specific analysis in Section 5. Additionally, we have run additional experiments on mathematical and commonsense reasoning benchmarks. Similar trends hold for the new experiments, which confirms the general applicability of our approach and further validates our theoretical model. Please see the general response for more details.