Reranking Laws for Language Generation: A Communication-Theoretic Perspective

Authors: antónio  farinhas
haau-sing  li
andré f t martins
t u darmstadt
ellis  unit lisbon
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 12:41:29

Abstract: To ensure large language models (LLMs) are used safely, one must reduce their propensity to hallucinate or to generate unacceptable answers. A simple and often used strategy is to first let the LLM generate multiple hypotheses and then employ a reranker to choose the best one. In this paper, we draw a parallel between this strategy and the use of redundancy to decrease the error rate in noisy communication channels. We conceptualize the generator as a sender transmitting multiple descriptions of a message through parallel noisy channels. The receiver decodes the message by ranking the (potentially corrupted) descriptions and selecting the one found to be most reliable. We provide conditions under which this protocol is asymptotically error-free (i.e., yields an acceptable answer almost surely) even in scenarios where the reranker is imperfect (governed by Mallows or Zipf-Mandelbrot models) and the channel distributions are statistically dependent. We use our framework to obtain reranking laws which we validate empirically on two real-world tasks using LLMs: text-to-code generation with DeepSeek-Coder 7B and machine translation of medical data with TowerInstruct 13B.

Main paper: 
 introduction: 
 Large language models (LLMs) have shown remarkable performance across many tasks in natural language processing, computer vision, and speech recognition. Despite their capabilities, instances of hallucinations and other critical errors occasionally arise, casting doubt on the reliability of their predictions, without clear indication of when and how badly they might fail (Ji et al., 2023; Guerreiro et al., 2023) . This is particularly concerning as these models are increasingly used in high-stakes applications such as those within the medical or legal domains (Hung et al., 2023) or as agents that can perform multiple tasks, including generating and executing code (Wang et al., 2024) .The most common mitigation strategy is to "steer" the LLM with the aid of a reward model or directly from human preferences, either at training time (Stiennon et al., 2020; Yuan et al., 2024; Rafailov et al., 2024) or during decoding (Liu et al., 2024; Huang et al., 2024) . A simple and effective decoding-time strategy is first to generate multiple hypotheses and then use a reranker to select the most appropriate one. Several generation techniques used with modern LLMs, including voting procedures (Borgeaud and Emerson, 2020; Wang et al., 2023; Liévin et al., 2024; Shi et al., 2022) , minimum Bayes risk decoders (Eikema and Aziz, 2020; Freitag et al., 2022) , quality-aware decoders (Fernandes et al., 2022) , or other types of hypothesis ensembling/reranking techniques (Farinhas et al., 2023; Ni et al., 2023; Bertsch et al., 2023; Li et al., 2024) , embody this idea. An essential aspect of these procedures is that they all add redundancy as an intermediate step (by generating multiple hypotheses) to increase the chances of returning an acceptable answer as the final output.The idea of adding redundancy to decrease the error rate in noisy channels is a cornerstone of communication theory, more specifically in forward error correction methods. In its simplestFigure 1 : Left: A generator-reranker system (G, R) depicted as a communication system ( §2). Given a query q with acceptance set X (q), the sender sends N descriptions through noisy channels. The receiver's goal is to decode an acceptable answer through reranking. Right: Graphical model of the generator G. We consider two different models: a simplified version with N independent hypotheses, represented in black ( §3), and a scenario with exchangeable hypotheses, represented in red ( §4).form-repetition codes-a message block is sent multiple times, and the decoder uses some form of majority voting to recover the original message with high probability (MacKay, 2002; Cover and Thomas, 2006) . The same idea underlies more sophisticated error-correcting codes (Hamming, 1950; Reed and Solomon, 1960; Gallager, 1962; Berrou et al., 1993) .In this paper, we draw a parallel between these two worlds by regarding generator-reranker LLMs as communication systems ( §2 and Fig. 1, left) . We conceptualize the LLM generator G as a sender transmitting N message descriptions in parallel through noisy channels, leading to N potentially corrupted hypotheses. Then, the receiver, which corresponds to the reranker R, decodes the message by ranking the potentially corrupted descriptions and selecting the one found to be most reliable. The goal is for the combined (G, R) system to have lower error rate than G alone, and for the error rate to decay quickly with N . Our main contributions are as follows:• We show that when the channel distributions are independent, this simple protocol is asymptotically error-free (i.e., it generates an acceptable answer almost surely when N → ∞), even in scenarios where the reranker is imperfect, e.g., governed by a Mallows or a Zipf-Mandelbrot model. In the former case, the error probability decays exponentially fast ( §3). • We show that the protocol is still asymptotically error-free if we assume that the channel distributions are statistically dependent. When they are coupled by a Beta prior, we show that the error probability decays as a power law when the reranker is perfect ( §4). • We use our framework to obtain "reranking laws", which we validate empirically on text-to-code generation with DeepSeek-Coder 7B ( §5.1), on machine translation of medical data with TowerInstruct 13B ( §5.2), and on mathematical and commonsense reasoning benchmarks (App. B.3).Notation. We denote [N ] := {1, ..., N } and we use the shorthand notation X 1:N := (X 1 , ..., X N ).We use capital letters (X, Y, ...) for random variables and represent probability distributions by P(X), P(Y ), etc. We denote expectations of functions f under P(X) by E X [f (X)]. 
a communication-theoretic perspective of generator-reranker systems: 
 The focus of our paper is on generator-reranker systems: a generator G (such as an LLM) is prompted with a query q (e.g., a question to be answered, a source text to be translated, or a textual prompt for code). As a response to this query, G generates N candidate answers y 1 , ..., y N (called hypotheses). We are agnostic about the internals of G and the way the hypotheses are generated: they could come from the same system through sampling or beam search, or they could come from an ensemble of different systems. These hypotheses are then processed by a reranker R, which ranks them and returns as the final output the one which is found to be the best answer. We are also agnostic about how R is built-it could be an external system or it could be part of (or share parameters with) the generator. Commonly used rerankers are quality estimators (Fernandes et al., 2022) , energy-based models (Bhattacharyya et al., 2021) , reward models (Li et al., 2022) , and minimum Bayes risk decoders (Kumar and Byrne, 2002; Eikema and Aziz, 2020; Freitag et al., 2022; Shi et al., 2022) .Regardless of specific design decisions, the goal of the generator-reranking system (G, R) is to leverage the reranker R to produce better answers (according to some quality metric) than the ones which would be obtained through G alone (e.g., a single sample). In this paper, we show that the propensity for this combined system to generate unacceptable outputs, such as those containing critical errors or hallucinations, decays quickly enough with N under mild assumptions on G and R.We draw an analogy with communication theory as follows. Let Σ be an underlying alphabet and Σ * := ∞ i=0 Σ i its Kleene closure, i.e., the set of strings from Σ. Given the query q, we denote by X (q) ⊆ Σ * the set of acceptable answers. 1 We assume the communication system depicted in Fig. 1 (left), a form of multiple description source coding (Ozarow, 1980; Gamal and Cover, 1982; Laneman et al., 2005) . In this framework, the sender transmits N acceptable answers (called descriptions) x 1 , ..., x N ∈ X (q) N in parallel through noisy channels. These descriptions are corrupted according to a distribution P(y 1 , ..., y N |x 1 , ..., x N ), so that some hypotheses y i may become unacceptable (y i ∈ Σ * \ X (q)). This "channel noise" is a way to conceptualize the imperfections of the generator G. On the receiver side, a decoder processes the (potentially) corrupted descriptions and estimates x = g(y 1 , ..., y N ) using some decoding function g. The overarching goal is to achieve a low error probability P err (N ; q) := P( X / ∈ X (q) | q) for any query q. By bounding the maximal probability of error (over all queries), the average error probability is automatically bounded (Cover and Thomas, 2006, §8) . In this paper, we focus on rerankers as the decoding functions, where g(y 1 , ..., y N ) returns the top ranked answer, i.e., g(y 1 , ..., y N ) = y i for some i ∈ [N ].We formalize this construction by considering different models for G and R in the following sections, studying the conditions under which the resulting protocol is asymptotically error-free: Definition 1. A protocol is asymptotically error-free if, for any query q, the probability of the decoder outputting an unacceptable answer approaches zero as N tends to infinity, i.e., limEQUATIONFor simplicity, we assume that X 1 , ..., X N are conditionally independent given the query q, i.e., that P(x 1 , ..., x N |q) = N i=1 P(x i |q). 2 We also assume that Y 1:N are independent from q given X 1:N such that q → X 1:N → Y 1:N forms a Markov chain. Taken together, these two assumptions mean that P(x 1:N , y 1:N |q) = P(x 1:N |q)P(y 1:N |x 1:N ) = N i=1 P(x i |q) P(y 1:N |x 1:N ). 
generator-reranker systems with independent hypotheses: 
 We first consider the case where the corrupted descriptions Y 1:N are conditionally independent and identically distributed (i.i.d.) given X 1:N and where Y i depends only on X i , that is, P(y 1:N |x 1:N ) = N i=1 P(y i |x i ). Conceptually, this is the scenario where the parallel channels do not interfere, and it corresponds to the graphical model shown in Fig. 1 (right) without the part in red. While this case may not be very realistic in practice-for example, when the hypotheses produced by the generator are all sampled from the same model-it makes the analysis simpler. We will show later in §4 how the analysis can be extended when this assumption does not hold, reusing the results from this section.In the sequel, given a query q, we let ϵ denote the probability of a hypothesis being unacceptable,ϵ := P(Y i / ∈ X (q) | X i = x i , q) = P(Y i / ∈ X (q) | X i = x i ).We start by assuming that R is a perfect reranker, which implies that it produces an acceptable output when presented with a set of N hypotheses if and only if at least one of them is acceptable. In this case, the error probability becomesEQUATIONThus, P err (N ; q) goes to zero exponentially fast with N for any ϵ ∈ [0, 1), indicating that when the hypotheses are independent and the reranker is perfect, the protocol is error-free.On the other end of the spectrum, if the reranker is random-i.e., if it selects one of the N hypotheses uniformly at random, we obtainEQUATIONthat is, we obtain the same error probability as the generator alone, as expected.We consider now more realistic rerankers. A statistical ranking model widely used in machine learning applications is the Mallows model (Klementiev et al., 2008 (Klementiev et al., , 2009;; Chierichetti et al., 2018; Tang, 2019) . Let Π denote the set of permutations over N elements, and let d : Π × Π → R + be a distance function between permutations. In this paper, we use the Kendall-tau distance d(π, π ′ ), which returns the number of adjacent transpositions needed to turn π into π ′ . Given a location parameter π 0 ∈ Π and a scale parameter λ ∈ R + , the probability of a ranking π according to the Mallows model is P(π; π 0 , λ) = exp(-λd(π, π 0 ))/Z(λ), where Z(λ) is the partition function.In our setting, we assume that π 0 is the ground truth (oracle) ranking3 of the hypotheses y 1 , ..., y N and π is the ranking obtained by the reranker model, so that P(π; π 0 , λ) expresses how imperfect the reranker might be. Note that the family of Mallows models include both perfect and random rerankers as limit cases, respectively as λ → +∞ and as λ = 0.4 Let η j denote the marginal probability that the reranker places at the top the j th highest ranked hypothesis according to the oracle, i.e., η j = P(π 0 (π -1 (1)) = j). When K out of the N hypotheses are unacceptable, the reranker will pick an unacceptable hypothesis with probability N j=N -K+1 η j . Combining this with the fact that the probability of G generating K unacceptable hypotheses is a binomial distribution, the error probability becomesP err (N ; q) = P(g(Y 1 , ..., Y N ) / ∈ X (q) | q) = E X 1:N |q P(g(Y 1 , ..., Y N ) / ∈ X (q) | X 1:N , q) = N K=0   N K ϵ K (1 -ϵ) N -K N j=N -K+1 η j   . (4)Note that (4) holds for any reranker with top-1 (marginal) probability mass function η = [η 1 , ..., η N ], not only Mallows models. Naively determining η would require marginalizing P(π; π 0 , λ) by summing over all permutations π satisfying π 0 (π -1 (1)) = j, which is intractable due to the factorial number of terms involved. Fortunately, tractable combinatorial expressions exist for Mallows models (Fligner and Verducci, 1986; Lebanon and Mao, 2008) : the partition function has the compact expression Z(λ) = N j=1 (1 -e -λj )/(1 -e -λ ), and we have (Lebanon and Mao, 2008, Prop. 5) :η j = Z -1 (λ) π:j=π0(π -1 (1))e -λd(π,π0) = e -λ(j-1)N r=1 e -λ(r-1).( Plugging ( 5) into (4), invoking the binomial theorem, and simplifying, we obtainP err (N ; q) = P(g(Y 1 , ..., Y N ) / ∈ X (q) | q) = ϵ if λ = 0 [e -λ (1-ϵ)+ϵ] N -e -λN 1-e -λNotherwise.(6)Notably, when λ → +∞ (perfect reranking), the failure probability becomes ϵ N , as expected (see (2)), demonstrating the model's ability to interpolate between scenarios of random reranking (λ = 0) with a failure probability of ϵ (see (3)), and optimal reranking (λ → +∞) with a failure probability of ϵ N . A plot is shown in Fig. 2 (left), for several values of e -λ ∈ [0, 1].Our next result, proved in App. A.1, shows that, even with an imperfect reranker, an asymptotically error-free protocol is possible: Proposition 1. When R is a Mallows reranker, for any λ > 0, the protocol is asymptotically error-free and the error probability decays exponentially fast, P err (N ; q) = O((e -λ (1 -ϵ) + ϵ) N ).This result shows that P err (N ; q) converges Q-linearly to zero with rate of convergence e -λ (1 -ϵ) + ϵ > ϵ. Therefore, Mallows rerankers behave asymptotically as a perfect reranker but where the generator has an increased error probability.Given this result, one might wonder whether any reranker "slightly better than random" suffices to obtain an asymptotically error-free protocol. This it not the case, as the next counter-example shows.Example 1. Assume a reranker with probability mass function η j ∝ (N -j + 1). The resulting protocol is not asymptotically error-free; we have P err (N ; q) = O(ϵ 2 ). Therefore, the error is reduced from O(ϵ) to O(ϵ 2 ) but it is not eliminated. More generally, if η j ∝ (N -j + 1) r for a fixed positive integer r, we have P err (N ; q) = O(ϵ r+1 ). See App. A.2 for a proof and plots.Next, we present a class of rerankers weaker than Mallows which still lead to error-free protocols.For Mallows models (using the Kendall-tau distance), the marginal probabilities ( 5) can be written as η = softmax(-λz), where z = [0, 1, ..., N -1] ⊤ . We now consider transformations that yield distributions with heavier tails, which we will see later in §5 to be a better empirical fit in several applications. A known extension to softmax is the γ-entmax (Peters et al., 2019) , 5 a family of transformations parametrized by γ ≥ 0,EQUATIONwhich recovers softmax as a limit case when γ → 1. In (7), τ is a constant which ensures that γ-entmax(z) is normalized. When γ > 1, γ-entmax can return sparse distributions (Blondel et al., 2020) . Conversely, when γ < 1, γ-entmax leads to heavy-tailed distributions (see App. A.3).Let us now consider η = γ-entmax(-λz), where z = [0, 1, ..., N -1] ⊤ , instead of (5) . Letting p := 1/(1 -γ), b = λ/p, and a = p+τ λ -1 (where a is seen here as a normalizing constant that replaces τ ), and assuming a > -1 and γ < 1, we can write the γ-entmax model as η j = b -p (a + j) -p . Note that γ < 1 is equivalent to p > 1. This is called a Zipf- Mandelbrot model (Zipf, 1932; Mandelbrot, 1965) . This model generalizes the famous Zipf's law, which applies empirically to many practical contexts, such as the frequency table of words in a corpus of natural language (Powers, 1998) . The constant a is determined to satisfy N j=1 (a + j) -p = b p . When N → ∞, the left hand side becomes the Hurwitz zeta function (Hurwitz, 1882) , which equals the Riemann's zeta when a = 0,EQUATION)The following result, proved in App. A.4, shows that Zipf-Mandelbrot rerankers (which are weaker than Mallows rerankers and become the latter when γ → 1) still ensure error-free protocols. The proof makes use of the integral representation of the Hurwitz zeta function ( 8) and of the dominated convergence theorem, reusing the result for Mallows models in Proposition 1. Proposition 2. When R is a Zipf-Mandelbrot reranker, for any λ > 0 and γ < 1, the protocol is asymptotically error-free. We assume now a more realistic scenario where the independence assumption of §3 might not hold. For example, (X 1 , Y 1 ), ..., (X N , Y N ) might be only exchangeable-this is the case, for example, when the hypotheses are generated from G by sampling from a given model, conditioned on the query. In communication theory parlance, this assumes the presence of channel "interference" that introduces dependencies between the errors at the various channels, although permuting the messages at each channel does not change the joint distribution. By de Finetti's theorem (Diaconis and Freedman, 1980) , exchangeability implies that there is some mixture variable h ∈ H such that P(x 1:N , y 1:N ) =H dP(h) N i=1 P(x i |h)P(y i |x i , h). We assume further that h = (q, τ ) can be decoupled into the query variable q, which conditions x, and a random variable τ , which conditions y, such that P(x i |h) := P(x i |q) and P(y i |x i , h) := P(y i |x i , τ ). This corresponds to the graphical model in Fig. 1 (right), including the part in red. We let τ be a continuous random variable in[0, 1] such that E[τ ] = ϵ = P(Y i ̸ = X (q) | X i ). A convenient choice is a Beta distribution with parameters α and β, p(τ ; α, β) := Γ(α+β) Γ(α)Γ(β) τ α-1 (1 -τ ) β-1 .Perfect reranker and Beta coupling. If R is a perfect reranker, the error probability isEQUATIONWhen τ ∼ Beta(τ ; α, β), the N th -raw moment (9) has a closed form, leading to P err (N ; q) = N i=1α+i-1 α+β+i-1 . The next result, proved in App. A.5 using Gautschi's inequality (Gautschi, 1959 ) and the Stirling's formula, shows that we still obtain an error-free protocol, albeit the error decays slower than in the independent case-no longer exponentially but rather following a power law.Proposition 3. When τ ∼ Beta(τ ; α, β) and with a perfect reranker, the protocol is error-free and the error probability decays as a power law, P err (N ; q) = O(N -β ). Furthermore, for β < 1, wehave P err (N ; q) ∈ Γ(α+β) Γ(α) (α + β + N ) -β , Γ(α+β) Γ(α) (α + β + N -1) -β .Imperfect reranker. When τ ∼ Beta(τ ; α, β), the probability of exactly K out of N messages being corrupted is (due to the conjugacy between the Beta prior and the binomial distribution)N K 1 0 dτ p(τ ; α, β)τ K (1 -τ ) N -K = N K K i=1 (α+i-1) N -K i=1 (β+i-1) N i=1 (α+β+i-1). Therefore, using the reranker marginals η as in (4), we getEQUATIONwhich leads to the plot in Fig. 3 for Mallows and Zipf-Mandelbrot models. 6The next result, proved in App. A.6, shows that the dependencies considered in this subsection do not compromise the error-free protocol when it exists for any density p(τ ) which is finite in (0, 1) (not necessarily a Beta distribution). The proof invokes the dominated convergence theorem to enable commuting the limit with the integral sign.Proposition 4. Let G τ be a generator producing independent hypotheses ( §3) where each hypothesis is acceptable with probability 1 -τ . Let the reranker R be such that (G τ , R) has error probability P indep err (N ; q, τ ) → 0 for every τ ∈ (0, 1) (i.e., it is asymptotically error-free). Assume that the function τ → P indep err (N ; q, τ ) is measurable for every N ∈ N. Then, when R is used with a generator G which produces exchangeable hypotheses with arbitrary distribution p(τ ), finite in (0, 1), the system (G, R) is still asymptotically error-free.This result has important implications: it tells us that, to design error-free protocols, it is sufficient to verify if they are error-free in the simpler case where hypotheses are independent. 
experiments: 
 In this section, we demonstrate the validity of our reranking laws on two different tasks:7 text-to-code generation ( §5.1) and machine translation of medical data ( §5.2). Following existing literature on scaling laws for language modeling, we fit all curves on the development set using least squares (Ghorbani et al., 2022, App. E) and plot them on the unseen test set. 8 In all cases, we consider the generalized model presented in §4 with parameters α, β, and a Zipf-Mandelbrot reranker with parameters γ, and e -λ , which becomes a Mallows reranker when γ → 1. This is done in two steps: first, we fit α and β using the data for the perfect reranker (e -λ = 0). Then, we fit γ and e -λ using the already estimated α and β and the data for the imperfect reranker. Our code is available at https://github.com/deep-spin/reranking-laws.We use a sanitized version of the MBPP dataset (Austin et al., 2021; Liu et al., 2023) , a widely used benchmark for evaluating code LLMs, which includes 400 programming problems in Python. For each problem, the dataset includes ground-truth programs and three test cases with input and ground-truth output. We split the dataset in two equally sized parts to get development and test splits.We generate 200 hypotheses with DeepSeek-Coder 7B (Guo et al., 2024) using a sampling temperature of 1 (see App. B.1 for the prompt template). As in previous work, for simplicity, 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 (Wang et al., 2023) . A hypothesis is considered unacceptable if the result of at least one test case (out of three) is different from the ground truth.Fig. 4 (top) shows the log failure rate on the dev and test sets (left and right, respectively) as a function of N . Even though the oracle fit is not perfect, we get α = .1, β = .309, γ = .001, and e -λ = .003 for the imperfect reranker with majority voting, which fits the data well, as shown by the red curve.We use the TICO-19 dataset (Anastasopoulos et al., 2020) , which includes 3071 English sentences in the medical domain (i.e., COVID-19 related content) translated into 38 languages. We use the official splits, which contain 971 examples for development and 2100 for testing, focusing on translating from English (EN) to Portuguese (PT), Spanish (ES), and Russian (RU).For each source sentence, we sample 50 translation hypotheses with a temperature of 1 from Tow-erInstruct 13B (Alves et al., 2024) using the prompt template in App. B.2.9 Folowing Farinhas et al.(2023), we consider two reranking strategies: selecting the best candidate with MBR decoding using COMET-22 as the utility metric (Eikema and Aziz, 2020; Rei et al., 2022a) and reranking based on quality estimation using the reference-free CometKiwi (Fernandes et al., 2022; Rei et al., 2022b) . Since we cannot afford to collect human evaluation scores for each sampled hypothesis, we consider a translation to have a critical mistake (i.e., to be unacceptable) if its COMET-22 score is below 0.85, and an oracle (perfect) reranker that picks the translation with the highest COMET-22 score.We follow the described procedure using the data from all language pairs together. Fig. 4 (bottom)shows the log failure rate on the dev and test sets as a function of N . We get α = 0.1 and β = 0.46. Additionally, we have γ = 0.182 and e -λ = 0.001 for MBR decoding and γ = 0.001 and e -λ = 0.005 for QE reranking. See App. B.2 for additional plots showing these curves when the data from each language pair is used to fit a separate model. Again, we see a reasonable fit, especially for the imperfect rerankers, with MBR decoding leading to lower failure rates than reranking with QE. 
discussion and related work: 
 We believe the communication-theoretic perspective introduced in this paper might inspire the design of new protocols for increasing the quality and safety of LLMs. The generator-reranker system studied in this paper bears resemblance with repetition codes, a very naive (and inefficient) class of errorcorrecting codes. Can more powerful designs (Hamming, 1950; Reed and Solomon, 1960; Gallager, 1962; Berrou et al., 1993) inspire more efficient protocols? In machine translation, other forms of adding redundancy, such as lattice generation (Singhal et al., 2023) and hypothesis recombination (Vernikos and Popescu-Belis, 2024) , suggest that more efficient designs are indeed possible.Recent work also suggests that LLM-based evaluators could be used as highly effective rerankers in specific tasks (Kim et al., 2024) . While LLMs are not yet ready to fully replace human evaluators across diverse NLP tasks (Bavaresco et al., 2024) , in some cases, they can even provide fine-grained assessments in addition to single scores (Kocmi and Federmann, 2023; Fernandes et al., 2023a) .Another class of communication systems allow for feedback, e.g., in "automatic repeat request" protocols (Lin et al., 1984) , where the receiver has a backchannel to request the sender to retransmit missing bits of information. This framework can be useful to analyze LLM protocols where the generator generates a varying number of hypotheses interactively, relying on feedback from another module, such as a reward model or a confidence estimator, as in Quach et al. (2023) . Communication with feedback was also used recently by Jung et al. (2024) for summarization when the generator error probability ϵ is large-our mild conditions for asymptotically error-free protocols (Propositions 1-4) suggest that "bootstrapping" a correct answer is possible even in scenarios where G is very weak. Additionally, recent work has shown that LLMs may struggle with planning or self-verification, advocating instead for tighter integration between LLMs and external model-based verifiers (Kambhampati et al., 2024) . This supports our view that using external feedback models can improve LLMs by enabling interactive, error-correcting communication.We provide reranking laws, which allow us to predict how many hypotheses are necessary to achieve a desired error probability. This links to a rich body of literature aiming to predict the performance of deep learning models in terms of fundamental parameters, such as the model size or the amount of compute and data used to train them (Hestness et al., 2017 (Hestness et al., , 2019)) . These so called "neural scaling laws" have been studied in the context of language modeling (Kaplan et al., 2020; Hoffmann et al., 2022) and machine translation (Ghorbani et al., 2022; Fernandes et al., 2023b) , where we observe a power-law scaling for the performance as a function of each fundamental parameter. Our paper complements this line of work by considering the decoding dimension for generator-reranker systems.The analysis and theoretical results of this paper focus on binary acceptable/unacceptable decisions; however it is possible to extend our framework to consider also continuous quality metrics (such as COMET scores for translation (Rei et al., 2020) ) by replacing the notion of "asymptotically error-free" protocol (Definition 1) by a more general concept associated to a quality target. A possible path is to posit a probability density for the continuous quality metric (instead of a Bernoulli error probability) for each hypothesis coming from the generator, such as a Gaussian or uniform distribution with some input-dependent parameters. 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 evaluation metric score among the N hypotheses). Extreme value distributions are an important subject of study in order statistics (David and Nagaraja, 2004) and their densities have closed form expressions in some restricted cases: for example, the Gaussian assumption above yields a Gumbel distribution, and a uniform assumption yields a Beta distribution. The asymptotic case (N → ∞) corresponds to one of Gumbel, Fréchet or Weibull families (this is a consequence of the Fisher-Tippett-Gnedenko theorem (David and Nagaraja, 2004) ). From the extreme value distribution, we can obtain the expected evaluation metric score or the probability of a quality score being below an acceptable threshold. However, the generalization to imperfect rerankers (such as the Mallows or Zipf-Mandelbrot rerankers described in §3.2 and 3.3) seems harder than in the binary case and requires further investigation.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: We provide all the details in §5 and App. B.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusions: 
 We presented a communication-theoretic perspective of generator-reranker LLMs, where the generator G is conceptualized as a sender transmitting N descriptions in parallel through noisy channels, and the reranker R decodes the message by selecting the most appropriate description. Under mild conditions, the combined system (G, R) yields an acceptable answer almost surely when N → ∞.Experiments on text-to-code generation and machine translation with LLMs validate our framework.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: While we do not report error bars, for machine translation, we consider multiple language pairs and report individual and combined results (see §5.2 and App. B.2).Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
limitations and broader impacts: 
 We regard our paper as a first step connecting communication theory and LLMs, as discussed in §6. However, it should be noted that our work has several limitations. First, the guarantees of error-free protocol in Propositions 1-4 are only asymptotic, and in certain cases a large N may be necessary to achieve a large enough error decrease. We provide convergence rates only for Mallows rerankers (with independent hypotheses and also in the dependent case, when combined with a Beta prior). Second, there is no simple recipe to determine if the Mallows and Zipf-Mandelbrot reranker models are a good empirical fit to concrete rerankers. The same applies to the prior distribution p(τ ) which makes hypotheses dependent. Third, while our experiments in §5 suggest a reasonable fit in two tasks (code generation and machine translation), the fit is not perfect. A challenge is that, 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). Finally, although our framework focuses on binary acceptable/unacceptable decisions, it can be extended to continuous evaluation metrics, but this would require modifications to some concepts (e.g., the notion of asymptotically error-free protocols). Despite these limitations, the binary case remains highly relevant in practice-for example, in code generation, where the output either executes correctly or it does not. We expect future work to overcome some of these limitations.In considering the broader impact of our work, it is crucial to acknowledge its early stage and predominantly theoretical nature, which lends the discussion a speculative quality. We believe that our research can significantly enhance the reliability of LLMs by facilitating the identification of potential system failures, holding promise in fields such as natural language processing and computer vision, where robustness and error prediction are paramount. While not directly addressing environmental concerns shared across different LLMs (Strubell et al., 2019) , our work could indirectly contribute to energy efficiency efforts by quantifying the efficiency of reranking methods, potentially reducing computational requirements while maintaining requisite quality thresholds during inference. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: We discuss the broader impact of our work in §8.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We are not releasing any data or models.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We cite the creators of the datasets/models used in our paper, including the name of the corresponding licenses in App. B.1 and App. B.2.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: A.1 Proof of Proposition 1Let λ ϵ := -log e -λ (1 -ϵ) + ϵ and define F (N ) = log P err (N ; q) = e -λϵN -e -λN1-e -λN. Observe that 0 < λ ϵ < λ for any λ > 0 and ϵ ∈ (0, 1). We extend the domain of F to the real numbers in [1, +∞). We will prove that F (N ) is decreasing and that lim N →∞ F ′ (N ) = -λ ϵ . This shows that P err (N ; q) → 0 at asymptotic rate e -λϵ . We haveF ′ (N ) = (e -λϵN -e -λN ) ′ e -λϵN -e -λN - (1 -e -λN ) ′ 1 -e -λN =-λ ϵ e -λϵN + λe -λN e -λϵN -e -λN -λe -λN 1 -e -λN ≤ 0, hence F (N ) is decreasing. Since the second term tends to zero, the limit is given by the first term:lim N →∞ F ′ (N ) = lim N →∞ -λ ϵ e -λϵN + λe -λN e -λϵN -e -λN = lim N →∞ -λ ϵ 1 -e (-λ+λϵ)N + λ e (-λϵ+λ)N -1 = -λ ϵ ,where we used the fact that e (-λ+λϵ)N → 0 and e (-λϵ+λ)N → +∞. This proves the desired claim, that is, the error probability decreases exponentially fast with rate e -λϵ . Note that, for a perfect reranker (λ → ∞), we get e -λϵ = ϵ and we recover the rate ϵ N seen in §3.1.We first provide a proof for r = 1. We haveN j=N -K+1 η j = K j=1 η N -K+j = K j=1 j N j=1 j = K(K+1) N (N +1) . Plugging this into Eq. ( 4), we obtainEQUATIONwhere B(N, ϵ) denotes the binomial distribution with parameters N and ϵ and we use the facts thatE K∼B(N,ϵ) [K] = N ϵ and E K∼B(N,ϵ) [K 2 ] = N ϵ(1 -ϵ) + N 2 ϵ 2. Therefore, we obtain lim N →∞ P err (N ; q) = ϵ 2 .We now prove the general case r ≥ 1. From Faulhaber's formula, we haveK j=1 j r = 1 r+1 r j=0 r+1 j B j K r-j+1, where B j = j ℓ=0 1 ℓ+1 ℓ m=0 ℓ m (-1) m (m + 1) j denotes the j th Bernoulli number. Therefore, we getN j=N -K+1 η j = K j=1 η r N -K+j = K j=1 j r N j=1 j r = r j=0 r+1 j B j K r-j+1 r j=0 r+1 j B j N r-j+1 . (12)Plugging this into Eq. ( 4), we obtainEQUATION)We now use the fact that the raw moments of the binomial distribution B(N, ϵ) are given byE K∼B(N,ϵ) [K m ] = m ℓ=0 m ℓ N ℓ ϵ ℓ , where m ℓ := 1 ℓ! ℓ i=0(-1) ℓ-i ℓ i i m are the Stirling numbers of the second kind, and N ℓ := N ! (N -ℓ)! is the ℓ th falling power of N . Therefore, when N → ∞, (13) becomes limEQUATION)The plots in Fig. 5 show examples for several values of r. When γ > 1, γ-entmax can return sparse distributions (Blondel et al., 2020) . This case has been extensively studied as a way to, e.g., filter large output spaces (Correia et al., 2020; Peters and Martins, 2021) or to produce more interpretable predictions (Correia et al., 2019; Martins et al., 2020 Martins et al., , 2021 Martins et al., , 2022)) . Conversely, when γ < 1, γ-entmax leads to distributions with heavier tails, which is the case of our interest, as described in §3.3. See Fig. 6 for an illustration of γ-entmax for different values of γ in the two-dimensional case. For γ > 1, all mappings saturate at z = ±1/γ -1; this does not happen for γ ≤ 1.Note that we can writeEQUATION)The error probability isEQUATION)Since a is the normalizing constant such that1 = ζ(p, a + 1) = 1 b p Γ(p) ∞ 0 dt t p-1e (a+1)t (1-e -t ) (cf. Eq. ( 8)), we can interpret the expression above as the expectation of f N (t) := ((1-ϵ)e -t +ϵ) N -e -tN under the probability distribution on (0, ∞) with density π(t) :=1 b p Γ(p) t p-1 e (a+1)t (1-e -t ) . Since f N (t) → 0 pointwise for t ∈]0, ∞[and it is bounded in that interval, we can invoke the dominated convergence theorem to commute the limit and integral sign. We then have that P err (N ; q) → 0.Let us consider first the case where β = 1. Then,P err (N ; q) = N i=1 α + i -1 α + β + i -1 = α α + 1 α + 1 α + 2 • • • α + N -1 α + N = α α + N → 0.Now consider the case where β > 1. We have for each term in the product that α+i-1 α+β+i-1 < α+i-1 α+i , hence we must have P err (N ; q) < α α+N . Since the sequence is positive (since all terms are positive) and decreasing (since all terms are < 1), we must also have P err (N ; q) → 0 when β > 1.Finally, let us analyze the case where 0 < β < 1. From (9), we haveEQUATIONWe invoke Gautschi's inequality, which states that x 1-s < Γ(x+1) Γ(x+s) < (x + 1) 1-s for any x and s ∈ (0, 1). We set s := 1 -β and x := α + β + N -1, from which we obtain the desired result.To show that the error probability decays as a power law for any β > 0, we use Stirling's formula, which states thatEQUATIONTherefore,EQUATIONA.6 Proof of Proposition 4Let P indep err (N ; q, τ ) denote the error probability of the generator-reranker system when the hypotheses are independent and each hypothesis produced by G has error probability τ . The error probability of the generator-reranker system with exchangeable hypotheses is given byEQUATIONTherefore, lim N →∞ P err (N ; q) = lim N →∞ 1 0 dτ p(τ )P indep err (N ; q, τ ). Since P indep err (N ; q, τ ) ∈ [0, 1] for any N ∈ N and τ ∈ [0, 1], we have that p(τ )P indep err (N ; q, τ ) ∈ [0, p(τ )], and therefore the integrand is bounded by p(τ ), which integrates to 1. Therefore we can invoke the dominated convergence theorem and switch the limit and integral signs. Since by assumption lim N →∞ P indep err (N ; q, τ ) = 0 pointwise for any τ ∈ (0, 1), we obtain lim N →∞ P err (N ; q) = 1 0 dτ p(τ ) lim N →∞ P indep err (N ; q, τ ) = 0.B.1 Text-to-code generation Licenses. We use DeepSeek-Coder 7B (Guo et al., 2024) , which is available under a permissive license that allows for both research and unrestricted commercial use. We report results on the MBPP dataset (Austin et al., 2021; Liu et al., 2023) , released under an Apache license. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.A key difference between our framework and most lossless communication systems is that there is no need to communicate a specific message-any answer in the equivalence class X (q) is acceptable, hence, if the decoder recovers any message in this set, the communication is considered successful. This is a natural conceptualization in problems involving natural language (where a paraphrase of a correct answer is still correct) or code (where multiple programs might lead to the same execution).In fact, all results in this paper still hold if there are dependencies between X1, ..., XN .More specifically, we assume that the hypotheses are ranked according to some quality metric compatible with X (q), that is, unacceptable answers should be ranked after acceptable answers.Notably, e -λ strictly between 0 and 1 correspond to imperfect rerankers that are better than random. Lower values indicate higher-quality rerankers, making e -λ an inverse measure of reranker quality.Peters et al. (2019) call this α-entmax; we use γ instead not to clash the notation to be introduced in §4.Since τ ∼ Beta(τ ; α, β), we have E[τ ] = α/(α + β), which we set to ϵ to match the independent setting from §3, resulting in β = (ϵ -1 -1)α. Hence, α is our only new free parameter. As α → 0 + , the hypotheses become maximally dependent and reranking is hopeless; as α → ∞, the scenario reverts to full independence.App. B.3 contains additional experiments on mathematical and commonsense reasoning benchmarks.We use scipy.optimize.least_squares.This model outperforms all existing open-source alternatives (even of larger scales) for translating content between the supported languages and is also competitive withGPT-4 (OpenAI et al., 2023), especially when combined with MBR decoding (Alves et al., 2024, App. A). 


Decision: This paper presents an understanding of generator-reranker systems from a communication-theoretic perspective.  The paper's main claim is that these systems can be asymptotically error free as more and more samples are drawn, even if the ranker is noisy. This is analyzed both theoretically and empirically in two domains, with additional results included during the rebuttal period.

The reviewers mostly praised the core ideas of this paper, its writing, and its theoretical contribution. EFsu gives some good suggestions for improvement. I agree with Efsu that there is a somewhat major conceptual weakness of the paper in that it treats generation in a binary correct/not correct fashion. However, the authors' rebuttal is quite informative here and will be a good addition to the paper.

Overall, the interestingness of the paper outweighs any concerns about lack of more extensive empirical evaluation or development.

Reviews: review: paper_summary: paper_summary: The paper provides a framework for understanding the theoretical properties of generator-reranker systems for language generation. It relates the reranking process to error correction during the decoding of messages in noisy channels, a concept that has been well-studied in communication theory. Explicitly, the paper conceptualizes an LLM generator as a sender transmitting messages through noisy channels, with the reranker acting as the receiver decoding these messages. This framing explains why 1) things like redundancy in the set of generated strings are helpful in generator-reranker systems, actually increasing the likelihood of an acceptable output and 2) increasing the number of options from the generator in the reranking process generally increases system performance. The paper makes several theoretical contributions, showing that when generator-reranker systems meet certain theoretical requirements, there is a guarantee of “error-free” performance. This property holds even when channel distributions are not independent, i.e., when the same model is used to generate possible solutions to the input. The paper provides some empirical verification of their proposed laws.
strength_weakness: strength_weakness: The applicability of the communication system framework to generator-reranker systems is somewhat questionable given that there is not the same binary notion of acceptable/unacceptable for language generation systems. Rather, we’re dealing with a continuous spectrum of quality and the appeal of the generator-reranker system is its ability to increase quality (perhaps amongst “acceptable” solutions) rather than move from the realm of unacceptable to acceptable answers. The impact of this difference between the theoretical framework and the evaluation of generation systems in practice isn’t really discussed. 
There are a few points that could be addressed to improve readability:
* 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. For example, the reader won’t know what the implications of “channel distributions being statistically dependent” are (mentioned in the abstract) until after they’ve read through much of the paper.
* There isn’t much intuition about what the R.V. X corresponds to in the generator-reranker system 
* Some more intuition behind the scale parameter (other than just the settings that it gives for its extreme values) would be helpful


The computational experiments are not very comprehensive, exploring only two generation tasks (one generator model for each task). It is thus unclear how general their results are.
questions: questions: * I didn't understand the (bolded) comment in lines 148-9. It makes it sound as though the quality of the reranker depends on the quality of the generator. Could this be clarified?
* Minor style recommendation: Perhaps move the first sentence of 3.3 to right after providing the expression for the partition function. That feels like a more natural place to me. In footnote 1: equivalent class -> equivalence class
limitations: limitations: The authors discuss most of the limitations present in their work. I would like to see an additional discussion of the implications of their results for continuous evaluation metrics (rather than binary acceptable/unacceptable)
paper_summary: paper_summary: This paper proposes to regard generator-reranker LLMs, i.e., LLMs generating multiple outputs and then reranking them, as communication systems. The idea is to consider the outputs noisy with the objective for the reranker to find the less noisy one.
strength_weakness: strength_weakness: - Absence of analysis of the experiment results. This is a critical weakness of the paper. The experimental settings are described, and the results are given (plots), but without any comment. For the MT experiments, the authors wrote that they got some scores, and then we have the next section.
questions: questions: Please comment on your results. What do you conclude from them? Why are they insightful (or not insightful)? How can they be used in future work? etc.
The paper is really good but we miss some analysis.
limitations: limitations: Limitations are adequately addressed.
paper_summary: paper_summary: A number of recent works in language generation can be framed as proposing two step methods, with a method to generate proposal strings, and another to rank these strings before choosing the best one to be output (this includes, e.g., MBR decoding).
This paper analyses this practice with a communication-theoretic approach.
They first assume that, given a query $q$, the goal of decoding is to generate a string $y$ in a set $\mathcal{X}(q)$.
They then assume the generator’s output $p(y_{1:N} \mid q)$ can be decomposed as $p(x_{1:N} \mid q)p(y_{1:N} \mid x_{1:N})$, with $x_n \in\mathcal{X}(q)$ and $p(y_{1:N} \mid x_{1:N})$ representing some kind of noise perturbation. 
They then analyse the probability $p(rank(y_{1:N}) \notin\mathcal{X}(q)  \mid q)$ under different assumptions, showing that for many this value goes to zero as $N$ goes to infinity.
Finally, they run two experiments showing their theoretically derived predictions $p(rank(y_{1:N}) \notin\mathcal{X}(q)  \mid q)$ seem to correlate with the empirical probability of decoding errors.
strength_weakness: strength_weakness: In general, I liked this paper. In my opinion however, its main weaknesses are:
* limited empirical evaluation, with only two tasks, one generator model, and two reranking methods (besides an oracle ranker).
* the evaluation also makes some (in my opinion) debatable claims. E.g., in line 236 the authors state “[...] the imperfect reranker with majority voting, which fits the data well, as shown by the red curve.”. However, analysing Fig 4 (top), I would argue that the solid lines do not capture the data behaviour that well. In fact, the model’s performance seems to be empirically close to convergence with N, but the solid lines go monotonically down. Maybe running this analysis for larger values of $N$ would show whether the data indeed fits the predictions (specially if the predicted power law would generalise to larger values of $N$ as fit in the current data, and without fitting it on the new results).
questions: questions: 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.


As a minor suggestion: I found the use of a “communication theoretical” framing here a bit distracting, and it seems to me it could be discarded with no significant change to the paper’s contributions. The authors, for instance, discuss error correcting codes early in the paper, but then they (admittedly) do not require generated strings to be error-corrected. (The selected string simply needs to be in an acceptable set $rank(y_{1:N}) \notin\mathcal{X}(q) $.) Besides, the generator and ranker are framed as a sender and a receiver—with a noisy channel in between them—but no message is actually decoded by the receiving ranker. Alternatively, highlighting the role that a communication-theoretical framing has in the paper (and why it is needed) could be useful.
limitations: limitations: The authors properly discuss their analysis limitations in the paper.
paper_summary: paper_summary: This paper proposes a reranking principle for language generation from a communication-theoretic perspective.  The paper conceptualizes the generator as a sender transmitting multiple descriptions of a message through parallel noisy channels. A receiver is designed to decode the message by ranking the descriptions and selecting the one found to be most reliable. Experiments show the effectiveness of proposed method in text-to-code generation task and machine translation of medical data task.
strength_weakness: strength_weakness: 1 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.

2 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.

3 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.
questions: questions: Please see the weakness.
limitations: limitations: Yes

Comments: title: Response to Authors
comment: 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.
Thanks for your detailed response!

As my concerns are eliminated, I will raise my score.
> “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.