Reranking Laws for Language Generation: A Communication-Theoretic Perspective
Authors: António Farinhas
Haau-Sing Li
Andre Martins
Venue: NeurIPS 2024 spotlight (2024)
Keywords: language generation
reranking
communication theory
reliability
Primary area: natural_language_processing

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.

Reranking Laws for Language Generation: A Communicatinn-Therree Perspective
António Farinhas 1.2
Haau-Sing Li
André T. Martins' 122,45
Instituto Superior Técnico, Universidade de Lisboa
Instituto de Telecomunicações
' UUiqqitoos Knowledge Processing Lab, TU Darmstadt fantonio. farinhas, andre mammmmrrt)ssceecmc uliaboa.pt pt. hli@ukp- tu-darmstadt.de
"ELLIS Unit Lisbon Unbabel
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 of- ten used strategy is to first let the LLM generate multiple hypotheses and then employ a reranker to choose the best one. this paper, we draw parallel be- tween 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 message through parallel noisy channels. The receiver decodes the message by ranking the (potentially corrupted) descriptions and se- lecting the 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 Zipf-Mandelbrot models) and the channel distributions are statistically dependent. We use our framework to obtain reranking laws which validate empirically on two real-world tasks using LLMs: text-to-code generation with DeepSeek- 7B and machine translation of medical data with TowerInstruct 13B.
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 the reliability of their predictions, without clear indication of when and how badly they might fail (Ji et al., 2023; Guerreiro 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 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-tine strategy is first generate multiple hypotheses and then use reranker to select the most appropriate one. Several generation techniques used with modern LLMs, including voting procedures (Borgeaud and Emerson, 2020; Wang al., 2023; Liévin et al., 2024; Shi al., 2022), minimum Bayes risk decoders (Bikema 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 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 cornerstone of communication theory, more specifically in forward error correction methods. In its simplest
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Generator
Reranker
X1
Yi
21 x(4)
91
#t. E X(4)
x2(2)
X
Figure I: Left: A generator-reranker system (G, R) depicted as communication system ($2). Given a query q with acceptance set (q), the sender sends N descriptions through noisy channels. The receiver's 's goal is to decode an acceptable answer through reranking. Right: Graphical model of the generator G. We consider two different models: simplified version with N independent hypotheses, represented in black (S3), and 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 al., 1993).
In this paper, we draw a parallel between these two worlds by regarding generator-rcranke LLMs as communication systems ($2 and Fig. 1, left). We conceptualize the L.MM generator G 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 have lower error rate than G alone, and for the error rate 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 - 00), even in scenarios where the reranker is imperfect, e.g., governed by a Mallows or a Zinf-Mandelhrot model. In the former case, the error probability decays exponentially fast ($3).
We show that the protocol is still asymptotically frrer-free if we assume that the channel distribu- tions are statistically dependent. When they are coupled by a Beta prior, we show that the error probability decays as 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- -oneer 7B ($5.1), 1), on machine translation medical data with TowerIn- struet 13B ($5.2), and on mathematical and commonsense reasoning benchmarks (App. B.3).
Notation. We denote [N] := {1, N} and the shorthand notation X1.N := (X1 XN). We use capital letters (X, ...) for random variables and represent probability distributions by P(Y), etc. We denote expectations of functions f under P(X) by [x))
2 A Communication-Theorede 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.. question to be answered, source text to be translated, or a textual prompt for code). As response to this query, G generates N candidate answers yI...., B/ (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 an external system could 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), I), reward models (L.i al., 2022), and minimum Bayes risk decoders (Kumar and Byrne, 2002; Eikema and Aziz, 2020; Freitag al., 2022; Shi et al., 2022).

---

Regardless of specific design decisions, the goal of the generator rerankinn 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 Σ. = U D its Kleene closure, i.e., the set of strings from Σ. Given the query g. we denote by X (1) S Σx the set of acceptable answers." We assume the communication system depicted in Fig. (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) æ NN X())"" in parallel through noisy channels. These descriptions are corrupted according to distribution P(y1,.... ..... UN |.i,,.., ZNy ), so that some hypotheses yi may become unacceptable (Yi E Σ" A(())). This "channel noise"
way to conceptualize the imperfections of the generator G. On the receiver side, decoder processes the (potentially) corrupted descriptions and estimates & - -(v1,, 3/N) using some decoding function g. The overarching goal is to achieve a low error probability (NV: q) == P(X & (44)) | 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(y1, -..y UN) returns the top ranked answer, i.e., ((V1 ..... UN) yı for some E [N].
We formalize this construction by considering different models for and R in the following sections, studying the conditions under which the resulting protocol is asymptotically error-free:
Definition 1. A protocol is asymptoticallly error-free if. for any query q, the probability of the decoder outputting unaccepiable answer approaches zero as N tends to infinity, i.e.,
lim P(g(Y YN) $ x(9) g) = O. N-00
(1)
Par
For simplicity, we assume that X1, ..., N are conditionally independent given the query q, i.e., that P(#1...., =x\(g) (4) = II P We also assume that Y1.N are independent from given X1.N such that q + X1NN + Y1.N forms a Markov chain. Taken together, these two assumptions mean N' that P( (q) IP(C ()) (II P(ssl))) P(yI:N
3 Generator-Reranker Systems with Independent Hypotheses
We first consider the case where the corrupted descriptions YI. are conditionally independent and identically distributed (i.id.) given X1.v and where Y, depends only on X,, that is, ( [IIN)) = I (P (zz). 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- 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 & (4 X x,, 1) = P.Y, & x()) X, xx.).
3.1 Perfect and random rerankers
We start by assuming that R is perfect reranker, which implics that it produces an acceptable output when presented with a set of N hypotheses if and only at least one of them is acceptable. In
A key difference between our framework and most lossless communication systems is that there is no need to communicate specific message- any answer in the equivalence class (2(2) is acceptable, hence, if the decoder recovers any message in this set, the communication is considered successful. This is natural conceptualization in problems involving natural language (where paraphrase of a correct answer is still correct) or code (where multiple programs might lead to the same exccution).
In fact, all results in this paper still hold if there are dependencies between Ki,..,,N..
3

---

this case, the enror probability becomes
Per = (P ...) $ X()) q) = Ex ((g( YN) $ x(()) |x,,N
ExINY la P(Y & x()), vi E [N] X1:N)]
P(Y $ X(1) xx)) II
=
(2)
Thus, (N;; q) goes to zero exponentially fast with N for any E 00 1), indicating that when the hypotheses are independent and the reranker perfect, the protocol is error-free.
On the other end of the spectrum, if the reranker is random-i.. -.e. if selects one of the N hypotheses uniformly at random, we obtain
Perr (): P(o((,, YN) & x()) q) = Ex P(o(Y Yv) & x()) XI:Ns
= Ex
E. [P(2 x(() XINN =,, (3)
that is, we obtain the same error probability as the generator alone, as expected.
3.2 Imperfect reranker: Mallows model
We consider now more realistic rerankers. A statistical ranking model widely used in machine learning applications is the Mallows model (Klementiev et al., 2008, 2009; Chierichetti et al., 2018; Tang, 2019). Let II denote the set of permutations over N elements, and let d II x II - RR be a distance function between permutations. In this paper, we use the Kendall-tar distance d(x, x²), which returns the number of adjacent transpositions needed to turn into x'. Given a location parameter To E IT and a scale parameter À E R.,, the probability of a ranking т according to the Mallows model is (rr; no; A) = exp(-Ad(x, m (A)). where ((A) is the partition function.
In our setting, we assume that mo is the ground truth (oracle) ranking" the hypotheses yi...., V/N and æ is the ranking obtained by the reranker model, that [T To, A) expresses how imperfect the reranker might be. Note that the family of Mallows models include both perfect and random rerankers limit cases, respectively X + toc and as X 0."
Let 77y denote the marginal probability that the reranker places at the top the jth highest ranked hypothesis according the oracle, i.e., " (= =). When K out of the N hypotheses are unacceptable, the reranker will pick an unacceptable hypothesis with probability Σj=N f/- Combining this with the fact that the probability of G generating K unacceptable hypotheses is a binomial distribution, the error probability becomes
Porr
(N; (er q) PPg(( YN) & X²()) q) = ExIN 14 [P YN) $ x'(x) | o)
=
Σ K=0
(1 - N J=N K+1
TJ
(4)
K
Note that (4) holds for any reranker with top-1 (marginal) probability mass function 17 [17, nv].
not only Mallows models. Naively determining 17 would require marginalizing (PT;; mo. X) by summing over all permutations π satisfying To( (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
e ->>i)// --11)/(11 - e ^^), and we have (Lebanon and Mao, 2008, Prop. 5):
-
= 7 (A)
Σ
e -dd(T,F0)
(5)
EN M(rr11
TIJ=RO (()) (())
MMore specitically, we assume that the hypotheses ranked according some quality metric compatible with (g),, that is, unacceptahle answers should he ranked after acceptahle answers.
"Notably, e strictly between 0 and correspond to imperfect rerankers that are better than random. Lower values indicate higher-quality rerankers, making e an inverse measure of reranker quality.

---

Log failure rate (wrt baseline)
-30
60
-90
-120
100
N
am 1.00
>/ 0.75
0.50
0.25
--1- 0.00
y=10
V=
0.25
Figure 2: Log of the failure rate (difference with respect to the baseline rate log e) function of the number of generated independent hypotheses for several values of e and Mallows model ($3.2). Right: Hipf-Maadellboo model ($3.3).
0.3. Left:
Plugging (5) into (4), invoking the binomial theorem, and simplifying, obtain
if =
Par (N: g) = P(g(",( Yv) & (()) 1
je (1 (1-
(6)
otherwise.
Notably, when À + +oo (perfect reranking). the failure probability becomes eN expected (see (2)), demonstrating the model's ability to interpolate between scenarios of random reranking (A = 0) with failure probability of (see (3)), and optimal reranking (A - +00) with failure probability of e plot shown in Fig. (left), for several values of e E [0, 1].
Our next result, proved in App. A. shows that, even with an imperfect reranker, an asymptotically error- free protocol is possible:
Proposition 1. When R is Mallows reranker, for any X 0, the protocol is asymptotically error-free and the error probability decays exponentially fast, Pere (N; g) (((c~A(1cc)+c))
This result shows that Pere(NV: q) converges Q-linearly to zero with rate of convergence E --(11 > e. Therefore, Mallows rerankers behave asymptotically as 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- counter-example shows.
Example 1. Assume reranker with probability mass function π x (N - +++1), 1). The resulting protocol is not asymptotically error-free;
have g)) O(e)). Therefore, the error is
reduced O(e) to ( but it is not eliminated. More generally, if n2 x (N - 1y for a fixed positive integer r, we have Peer (N: = O(e-1). See App. A.2 for a proof and plots.
Next, we present class of rerankers weaker than Mallows which still lead to error-free protocols.
3.3 Imperfect reranker: Zipf-Mandelbrot model
For Mallows models (using the Kendall-tau distance). the marginal probabilities (5) can be written as 77 = softmax(-Xa) where x = [0, 1,..., .N- - _ We now consider transformations that yield distributions with heavier tails, which will see later in $5 to be a better empirical fit in several applications. A known extension to softmax is the y-entmax (Peters et al., 2019), a family of transformations parametrized by 7 0,
>-entmax(x) = [1 + ( 1)(2 /6-1
(7) In (7), is constant which ensures that
which recovers softmax limit case when ? m-entmax(2) 22 is normalized. When 7 > 1, ?-entmax can return sparse distributions (Blondel et al., 2020). Conversely, when 7 1, 7-entmax leads heavy-tailed distributions (see App. A.3).
Peters al. (2019) call this a-entmax; use instead not clash the notation be introduced in $4.
5

---

Let us now consider (--entmx(-xxx) where = No.1,,..NN11] instead of (5). Letting p := 1/(1 7), b \/p, and = p+r 1 (where a is seen here as a normalizing constant that replaces 7), and assuming > -1 and 7 < 1, we can write the 7-enimax model as 17; = b P(a + j) Note that y < 1 is equivalent to p 1. This called Zipf-Mandelbrot model (Zipf, 1932; Mandelbrot, 1965). This model generalizes the famous Zipf"s 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 is determined to satisfy ΣØ= (a + +) = b² When N + Je, the left hand side becomes the Hurwitz zeta function (Hurwitz, 1882), which equals the Riemann's 's zeta when a = 0.
X
C(p, a + = Σ
00
T(p) J. di --ー elatt)(l---t)
1
1
f=1 (a+j))
The following result, proved in App. A.4, shows that Zipf-MManelbbot 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 a Zipf- Sinf-Mandelbrot reranker, for any X and y < 1, the protocol is asymptotically error-free.
Fig. 2 (right) shows how this model differs from the one presented in $3.2. Since the reranker is weaker, the error curves bend causing the error decrease to be slower, but still convergent to zero.
4 Generator- Systems with Dependent Hypotheses
We assume now more realistic scenario where the independence assumption of $3 might not hold. For example, (X1. Y)), ..., (XN, YN) might be only exchangeable this is the case, for example, when the hypotheses are gener- ated from G by sampling from given model, conditioned on the query. In communica- tion theory parlance, this assumes the pres-
Log failure rate (oot baselne)
-2
ence of channel "interference" that introduces dependencies between the errors at the var-
ious channels, although permuting the mes- sages each channel does not change the joint distribution. By de Finetti's theorem (Diaconis and Freedman, 1980), exchangeabil- ity implies that there is some mixture vari- able h E H. such that P(I V1:N) JN (h) II (P(c,)/)P(() h).
50
100
1.02
Figure 3: Log of the failure rate as a function of the number of generated exchangeable hypotheses N for several values of y, e ~>, and a 0.3.
We assume further that h = (q, 7) can be decoupled into the query variable q, which conditions xr and a random variable T, which conditions y. such that P(z := (P(z; (q) and P(y æ h) := (2 [r,, T). This corresponds to the graphical model in Fig. 1 (right), including the part in red. We let 7 be continuous random variable in [0, 1] such that E[r] = = P(Y: * X((g) X,). A convenient choice is Beta distribution with parameters and B, p(T; a, 8) ((
[(a)(3)) a 11 8-1
Perfect reranker and Beta coupling. Pon (N: q) F(g((Y)...)) YN) $ x((g) q) Ex,wll [PP(g(Y), YN) $ x()) X
If is perfect reranker, the error probability is
= Exx [. d' p(T) II P(Y & x(()) x1, = E.
N
(9)
When T ~ Beta(T; ar ()) the th -raw moment (9) has a closed form, leading to Par (N; q) = a I a+3+i-1- The next result, proved in App. A.5 using Gautschi's 's inequality (Gautschi, 1959) and the Stirling's '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(T; o, 3) and with perfect reranker, the protocol is error-free and the error probability decays as a power law, (N = OONNN- Furthermore, for 3 < 1, we
have (N: g) E ((a+t) (a + 3 + N)- T(
[(a) (a + 3 + N - 1)--
Imperfect reranker. When Beta(T; a, B), the probability of exactly K out of N mes- sages being corrupted is (due to the conjugacy between the Beta prior and the binomial distri- bution) (x) Ju dr p(T; B)r K (1 7)N-K (x) (o-,toi--100 (104:11)1 11: (B-
Therefore, using
(a+00--))
the reranker marginals 17 in (4), we get
N
(a ( II N- 1 (8+i-1)
N
gN)
Σ
Σ
(10)
K
I (a
K=0
j=N-K+1
which leads to the plot in Fig. 3 for Mallows and Zipf-Mandelbrot models. 6
The next result, proved 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(T) which is finite in (0, 1) (not necessarily Beta distribution). The proof invokes the dominated convergence theorem to enable commuting the limit with the integral sign.
Proposition 4. Let G be generator producing independent hypotheses ($3) where each hy- pothesis is acceptable with probability
т. Let the reranker R be such that (G+, R) has error probability Pert (N; q, T) + 0, 0.for every T (0, 1) (i.e., it is asymptotically error-free), Assume that the function T + (N:: 7) measurable for every N E N. Then, when R is used with generator G which produces exchangeable hypotheses with arbitrary distribution p(T). funite in (0, 1), the system (G, R) is still asymptotically error-free.
This result has important implications: it tells that, design error-free protocols, it is sufficient to verify if they are error-free in the simpler case where hypotheses are independent.
5 Experiments
In this section, we demonstrate the validity of our reranking laws on two different tasks:? text-to-code generation ($5.1) and machine translation of medical data ($5.2). Following existing literature scaling laws for language modeling, we fit all curves on the development set using least squares (Ghorbani et al., 2022, App. H) and plot them the waseen test set. 8 In all cases, consider the generalized model presented in $4 with parameters a, B, and a Mand-Mandellbot reranker with parameters 7, and - which becomes a Mallows reranker when 7 - 1. This done in two steps: first, we fit a and 33 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 httpa/////mmpeppp//poeaiiiieegge
laws.
5.1 Code generation
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-trutt truth output. We split the dataset in two equally sized parts to get development and test splits.
We generate 200 hypotheses with DeepSeek-Code Coder 7B (Guo al., 2024) using a sampling temperature of (see App. B.1 for the prompt template). As in previous work, for simplicity, we use only one test case for each problem (Shi al., 2022), and select one candidate by taking majority vote over the
"Since T ~ Beta r: ax, 3). we have [[[]] = a/(a= + 3). which we set to c to match the independent setting from $3, resulting in 3 = (c- 1)a. Hence, is our only new free parameter. As + 0*, the hypotheses become maximally dependent and reranking hopeless; as a - oc. the scenario reverts to full independence. 7 App. B.3 contains additional experiments on mathematical and commonsense reasoning henchmarks.
We use scipy. . optimiiieee imiie..... least paresttssuuess.
7

---

Log fallure rate (wrt baseline)
0.0
majority voting
Log fallure baseline)
0.0
majority voting oracle
oracle
-0.
-0.5
-1.5
100
150
200
Log failure rate (wit baseline)
Log (wrt baseline)
qe
qe
mbr
mbr
-0.5
oracle
oracle
-1.0
20 30
10 N
50
Figure 4: Log of the failure rate as a function of N. The empirical data is represented with dots (lefit: dev, right: test set) and our fitted models with solid and dashed lines (imperfect and perfect reranker, respectively). Top: text-to-code generation ($5.1). Bottom: machine translation ($5.2).
execution results, dismissing hypotheses that fail to execute on the test case (Wang et al., 2023). A hypothesis is considered unacceptable the result least one test case (out of three) different from the ground truth.
Fig. 4 (top) shows the log failure rate on the dev and test sets (left and right, respectively) function of N. Even though the oracle fit is not perfect, we get a = .1, 3 = .309, ,001, and e-> = .003 for the imperfect reranker with majority voting, which fits the data well, shown by the red curve.
5.2 Machine translation
We use the TICO-19 dataset (Anastasopoulas 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) Portuguese (PT), Spanish (ES), and Russian (RU).
For each source sentence, we sample 50 translation hypotheses with a temperature from Tow- erInstruct 13B (Alves et al., 2024) using the prompt template in App. B.2." Folowing Farinhas et al. (2023). we consider two reranking strategies: selecting the best candidate with MBR decoding using COMET-22 the utility metric (Eikema and Aziz, 2020; Rei al., 2022a) and reranking based quality estimation using the reference-free CometKiwi (Fernandes et al., 2022: Rei et al., 2022b). Since cannot afford to collect human evaluation scores for each sampled hypothesis, we consider a translation to have critical mistake (i.e., to unacceptable) if its COMET-22 score is below 0.85, and 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. (bottom) shows the log failure rate on the dev and test sets
function of N. We get 0.1 and
0.46. Additionally, we have 7 = 0.182 and e 0.001 for MBR decoding and = 0.001 and 0.005 for QE reranking. See App. B.2 for additional plots showing these curves when the data
"This model outperforms all existing open source alternatives (even of larger scales) for translating content between the supported languages and is also competitive with GPT-4 (OpenAl et al., 2023), especially when combined with MBR decoding (Alves al., 2024, App. A).

---

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-theoreee 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 error- correcting 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-Bee 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 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 backehannel 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 reward model a confidence estimator, 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 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 (Kamb- hampati al., 2024). This supports our view that using external feedback models can improve LLMs by enabling interactive, crror-correcting communication.
We provide reranking laws, which allow 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, 2019). These so called "neural scaling laws" have been studied in the context of language modeling (Kaplan 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 reerakr systems.
The analysis and theoretical results of this paper focus binary acceptable/umacceptabbe 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 "asymptoticalll 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 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 Gumbel distribution, and a uniform assumption yields Beta distribution. The asymptotic case (N + oo) corresponds to one of Gumbel, Fréchet or Weibull families (this is a consequence of the Fisher-Tippedt Tippett-Gnedenko 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 Tipf-Mandelbror rerankers described in $ $3.2 and 3.3) seems harder than in the binary case and requires further investigation.

---

7 Conclusions
We presented communication-theoree perspective of generator-reranker LLMs, where the generator 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 co. Experiments on text-to-code generation and machine translation with LLMs validate our framework.
Limitations and Broader Impacts
We regard our paper as a first step connecting communication theory and LLMs, as discussed in $6. However, 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 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 good empirical fit to concrete rerankers. The same applies to the prior distribution p(T) which makes hypotheses dependent. Third, while our experiments in $5 suggest a reasonable fit 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 visible in the "steps" observed the code generation plots). Finally, although our framework focuses on binary acceptable/umacceppabbee decisions, 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 practice- for example, code generation, where the output either executes correctly 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 reranking methods, potentially reducing computational requirements while maintaining requisite quality thresholds during inference.
Acknowledgments
We would like to thank Ben Peters, Duarte Alves, Marcos Treviso, Mário Figueiredo, Sweta Agrawal, and the SARDINE lab team for helpful discussions. This work was supported by EU's Horizon Europe Research and Innovation Actions (UTTER, contract 101070631), ) by the project DECOLLAGE (ERC-2022-CoG 101088763), by the Portuguese Recovery and Resilience Plan through project C645008882-0000000 (Center for Responsible AI), and by Fundação para Ciência Tecnologia through contract UIDB/50008/2020.
References
Pranjal Aggarwal, Aman Madaan, Yiming Yang, and Mausam. Let's sample step by step: Adaptive-consistency for efficient reasoning and coding with LLMs. In Houda Bouamor, Juan Pino, and Kalika Bali, editors, Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 12375-12396, Singapore, December 2023. Associa- tion for Computational Linguistics. doi: 10.18653/v1/203 1111665//1//2223mmmm-mmmmm wwm.:mmminlmmn...... //aclanthology org/ 20233.222222 sanlp-main... 761.
URL https:
Duarte M. Alves, José Pombal, Nuno M. Guerreiro, Pedro H. Martins, João Alves, Amin Farajian, Ben Peters, Ricardo Rei, Patrick Fernandes, Sweta Agrawal, Pierre Colombo, José G. C. de Souza, and André F. T. Martins. Tower: open multilingual large language model for translation-related tasks, 2024.
10

---

Antonios Anastasopoulos, Alessandro Cattelan, Zi-Yi Dou, Marcello Federico, Christian Federmann, Dmitriy Genzel, Franscisco Guzmán, Junjie Hu, Macduff Hughes, Philipp Koehn, Rosie Lazar, Will Lewis, Graham Neubig, Mengmeng Niu, Alp Öktem, Eric Paquin, Grace Tang, and Sylwia Tur. TICO-19: the translation initiative for 10. In Karin Verspoor, Kevin Bretonnel Cohen, Michael Conway, Berry de Bruijn, Mark Dredze, Rada Mihalcea, and Byron Wallace, editors, Proceedings of the 1st Workshop on NLP for COVID-I9 (Part 2) at EMNLP 2020, Online, December 2020. Association for Computational Linguisties. doi: 00.1865531122220mmcovvvlll wwg/o020.oo.. httg///0...lccooiiii.... wwpcovidd9-225555
5. URL https: httphhts//acllaatlollloooo
Jacob Austin, Augustus Odena, Maxwell Nye. Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, and Charles Sutton. Program synthesis with large language models, 2021.
Anna Bavaresco, Raffaella Bernardi, Leonardo Bertolazzi, Desmond Elliott, Raquel Fernández, Albert Gatt, Esam Ghaleb, Mario Giulianelli, Michael Hanna, Alexander Koller, André F. T. Martins, Philipp Mondorf, Vera Neplenbrock, Sandro Pezzelle, Barbara Plank, David Schlangen, Alessandro Suglia, Aditya K Surikuchi, Ece Takmaz, and Alberto Testoni. Llms instead of human judges? a large scale empirical study across 20 nlp evaluation tasks, 2024. URL https: //arxiv. org/ abs/ /206/ 18403.
Claude Berrou, Alain Glavieux, and Punya Thitimajshima. Near shannon limit error-correcting coding and decoding: Turbo-codes. 1. In Proceedings of ICC*93-IEEE International Conference on Communications, volume 2, pages 1064-1070. IEEE, 1993.
Amanda Bertsch, Alex Xie, Graham Neubig, and Matthew Gormley. It's MBR all the way down: Modern generation techniques through the lens of minimum Bayes risk. In Yanai Elazar, Allyson Ettinger, Nora Kassner, Sebastian Ruder, and Noah A. Smith, editors, Proceedings of the Big Picture Workshop, pages 102-122, Singapore, December 2023. Association for Computational Linguistics. doi: 10. 10.183631112223.1. http:///////...iiitrttreeeee 1.9. URL https : http///aaaaaaaaaeae/ee//e////a/t org/2023. bigpicture-1.9.
Sumanta Bhattacharyya, Amirmohammad Rooshenas, Subhajit Naskar, Simeng Sun, Mohit lyyer, and Andrew McCallum. Energy-based reranking: Improving neural machine translation using energy-based models. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli, editors, Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 4528-4537, Online, August 2021. Association for Computational Linguistics. doi: URL pettts::/aclanttiee
10.18653/v1/2021. acl- long..n www.o//.looo....oooooo....ooo
org/ acl -ong. 349.
Mathieu Blondel, Andrλo F.T. Martins, and Vlad Niculae Learning with fenchel-young losses. Journal of Machine Learning Research, 21(35):1-69, 2020. URL http::/jmlmz org/papers/
v21/19-021 021 .html.
Sebastian Borgeaud and Guy Emerson. Leveraging sentence similarity in natural language generation: Improving beam search using range voting. In Alexandra Birch, Andrew Finch, Hiroaki Hayashi, Kenneth Heafield, Marcin Junczys-Dowmun Yusuke Oda, editors, Proceedings of the Fourth Workshop on Neural Generation and Translation, pages 97-109, Online, July 2020. Association for Computational Linguistics. doi: 10.18653/v1/ 2020.ngt- 1.11. URL https: / acl aclanthology org 2020 .gt-1. 1.11.
loannis Konstas, Xian Li, Graham Neubig, and
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss. Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Ben- jamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot leamners In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balean, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 1877-1901. Curran Associates, Inc., 2020. URL https: https://proceeddnng neurips. cc/ paper_ http:/ppperrr2////
Paper. pdf..
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri,
11

---

Gretchen Krueger. Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojeiech Zaremba. Evaluating large language models trained on code, 2021.
Flavio Chierichetti, Anirban Dasgupta, Shahrzad Haddadan, Ravi Kumar, and Silvio Lattanzi. Mal- lows models for top-k lists. Advances in Neural Information Processing Systems, 31, 2018.
Gonçalo M. Correia, Vlad Niculae, and André F. T. Martins. Adaptively sparse transformers. In Kentaro Inui, Jing Jiang. Vincent Ng, and Xiaojun Wan, editors, Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 2174-2184, Hong Kong, China, November 2019, Association for Computational Linguistics. doi: 10. 10.18653/11/D19-1223. wwt//o9- 1223.
URL https: https///acaaaathhooooooo
Gonçalo Correia, Vlad Niculae, Wilker Aziz, and André Martins. Efficient marginalization of discrete and structured latent variables via sparsity. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 11789-118000 11802. Curran Associates, Inc., 2020. URL https: https:///po::eeeee http:///ppoceeen....// nwwrii............m cc/ pdf.
paper/2020 fileellllle// 887 www.c362000444466999777777
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommu- nications and Signal Processing). Wiley-Interscience, USA, 2006. ISBN 0471241954.
H.A. David and H.N. Nagaraja. Order Statistics. Wiley Series in Probability and Statistics. Wiley, 2004. ISBN 9780471654018 https: google bt//bokks/dd-bddFXxgkk/e.
Persi Diaconis and David Freedman. Finite exchangeable sequences. The Annals of Probability, pages 745-764, 1980.
Bryan Eikema and Wilker Aziz. Is MAP decoding all you need? the inadequacy of the mode in neural machine translation. In Donia Scott, Nuria Bel, and Chengqing Zong. editors, Proceedings of the 28th International Conference Computational Linguistics, pages 4506-4522 Barcelona, Spain (Online), December 2020. International Committee on Computational Linguistics. doi: 10.18653/ 2020 col coling-maaln 398.
mww.::ooooiin-mii.9999 URL htt.hht::/// http::////caaaaooooaae//
António Farinhas. José de Souza, and Andre Martins. An empirical study of translation hypothesis ensembling with large language models. In Houda Bouamor, Juan Pino, and Kalika Bali, editors, Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 11956- 19970, Singapore, December 2023. Association for Computational Linguistics. doi: 10. 18653/v1/2023.emmb) main.
URL https: / h/tp//aaaaantt/ httpt/ooaaatttoyooooooooooo org/ emnlp-main 733.
Patrick Fernandes, António Farinhas, Ricardo Rei, José G. C. de Souza, Perez Ogayo, Graham Neubig, and Andre Martins. Quality-aware decoding for neural machine translation. In Marine Carpuat,
de Marneffe, and Ivan Vladimir Meza Ruiz, editors, Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1396-1412, Seattle, United States, July 2022. Association for Computational Linguisties. doi: 10.18665/w1/2022.nnmm hwwp://2222..nnannnnmn/a/ maili URL https: l/aclanthology- Drrg/2022 nwa.n-allaaaaa mmaim.aai0....
Patrick Fernandes, Daniel Deutsch, Mara Finkelstein, Parker Riley, André Martins, Graham Neubig, Ankush Garg, Jonathan Clark, Markus Freitag, and Orhan Firat. The devil is in the errors: Leveraging large language models for fine-grained machine translation evalua- tion. Philipp Koehn, Barry Haddow, Tom Koemi, and Christof Monz, editors, Proceedings of the Eighth Conference on Machine Translation, pages 1066-1083, Singapore, December 2023a. Association for Computational Linguistics. doi: 10.18653/v1/22 1/2023. wmt- 1.100. URI. https:/ / aaccanthllogyyy org/2023. wmt 1ont-1..4 100.
12

---

Patrick Fernandes, Behrooz Ghorbani, Xavier Garcia, Markus Freitag, and Orhan Firat. Scaling laws for multilingual neural machine translation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 10053-10071. PMLR, 23-29 Jul 2023b. URL https:/ https://proceedingg mlr. https//222//eennnndeeee htm..
M. A. Fligner and J. S. Verducci. Distance based ranking models. Journal of the Royal Statistical Society. Series B (Methodolozical), 48(3):359 -69, 1986. ISSN 00359246. URL http://wwwt
jstor. aator.org//ee s 23444433.33
Markus Freitag, David Grangier, Qijun Tan, and Bowen Liang. High quality rather than high model probability: Minimum bayes risk decoding with neural metries. Transactions of the Association for Computational Linguistics, 10:81 1-825, 2022.
Robert Gallager. Low-density parity-check codes. IRE Transactions on information theory, 8(1): 21-28, 1962.
A.E. Gamal and T. Cover. Achievable rates for multiple descriptions. IEEE Transactions on Information Theory, 28(6):851-857, 1982. doi: 10.1109/TIT. 1982.1056588.
Walter Gautsehi. Some elementary inequalities relating the gamma and incomplete gamma function.
J. Math. Phys, 38(1):77-8,, 1959.
Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. Did Aristotle
Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategies. Transactions of the Association for Computational Linguistics, 9:346-361, 04 2021. ISSN 2307-387X. doi: 10.1 (0.1162/tacl_ a 00370. URL https: /estps:/doo..oo http://ttooorg.....// http://...111//aaca.eeee 200700
Behrooz Ghorbani, Orhan Firat, Markus Freitag, Ankur Bapna, Maxim Krikun, Xavier Garcia, Ciprian Chelba, and Colin Cherry. Scaling laws for neural machine translation. In International Conference on Learning Representations, 2022. URI https:/ httpttpp:///peeevieeeeeeee net////wweeeeeeeeeeeeeeeeeeeeeee fftm/rrrddmdd hR_ HR__SMuCxCVV.
Nuno M. Guerreiro, Duarte M. Alves, Jonas Waldendorf, Barry Haddow, Alexandra Birch, Pierre Colombo, and André F. T. Martins. Hallucinations in Large Multilingual Translation Models. Transactions of the Association for Computational Linguistics, 11:1500-1517, 12 2023. ISSN 2307-387X. doi: 10. 12.1162/tcc__.. a 00615. URL htRps: //tp::::://...ie org/ wttp.o...../..........o. www.:/accccccccce a_00615.
Daya Guo, Qihao Zhu, Dejian Yang, Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Y. Wu, Y. K. Li. Fuli Luo, Yingfei Xiong, and Wenfeng Liang. Deepseek-coder; When the large language model meets programming the rise of code intelligence, 2024.
Richard W Hamming. Error detecting and error correcting codes. The Bell system technical journal, 29 1950.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md. Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically, 2017.
Joel Hestness, Newsha Ardalani, and Gregory Diamos. Beyond human accuracy: computational challenges in deep learning. In Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming, PPoPP '19, page 1-14, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978 1500662252. doi: 10. 00.1145329938333295711 URL https: //doi. //doi.org/10. 1145/329388 3295710.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Ruther- ford, Diego de las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katherine Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy. Simon Osindero, Karen Simonyan, Erich Elsen, Oriol Vinyals, Jack William Rae, and Laurent Sifre. An empirical analysis of compute-optimal large language model training. In Alice H. Oh, Alekh Agar- wal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https::/t//// h httpp::///ppeeviiiie
13

---

James Y Huang, Sailik Sengupta, Daniele Bonadiman, Yi-an Lai, Arshit Gupta, Nikolaos Pappas. Saab Mansour, Katrin Kirchoff, and Dan Roth. Deal: Decoding- time alignment for large language models. arXiv preprint arXiv:2402.06114, 2024.
Chia-Chien Hung. Wiem Ben Rim, Lindsay Frost, Lars Bruckner, and Carolin Lawrence. Walk- ing tightrope evaluating large language models in high-risk domains. In Dicuwke Hup- kes, Verna Dankers, Khuyagbaatar Batsuren, Koustuy Sinha, Amirhossein Kazemnejad, Chris- tos Christodoulopoulos, Ryan Cotterell, and Elia Bruni, editors, Proceedings of the 1st Gen- Bench Workshop on (Benchmarking) Generalisation in NLP. pages 99-111, Singapore, December 2023. Association for Computational Linguistics. doi: 10. 1006://///2223.eeeeeeeh---l genbench-1.8. URL http///aaaaattooogy.yoooo .rg......o...ooooooo............ 2023. 1..b
Adolf Hurwitz. Einige eigenschaften der Mirichlet'schen funktionen, die bei der bestimmung der klassenanzahlen binärer quadratischer formen auftreten. Zeitschrift fur Mathematik und Physik, 1882.
Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung. Survey of hallucination in natural language generation. ACM Comput. Surv., 55(12), mar 2023. ISSN 0360-0300. doi: 10. 17300 URL https: //doi.org//0/.//////// 1145/357170
Jaehun Jung, Peter West, Liwei Jiang, Faeze Brahman, Ximing Lu, Jillian Fisher, Taylor Sorensen, and Yejin Choi. Impossible distillation: from low-quality model high-quality dataset & model for summarization and paraphrasing. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2024.
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil B Murthy. Position: LLMs can't 't plan, but can help planning in LLM-modulo frameworks. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41 International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 22895-22907. PMLR, 21-27 Jul 2024. URL attpss//proceeteee press/ watpa//v35//eeee /tt///2///aaaam /tt///aaaaaaaaaaaaaaaaa html.
mml.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models, 2020.
Seungone Kim, Jamin Shin, Yejin Cho, Joel Jang, Shayne Longpre, Hwaran Lee, Sangdoo Yun, Seongjin Shin, Sungdong Kim, James Thorne, and Minjoon Seo. Prometheus: Inducing fine- grained evaluation capability in language models. In The Twelfth International Conference on Learning Representations, 2024. URL https: //ppnreviei wtw/teeuumn/eeee Faa.
Alexandre Klementiev, Dan Roth, and Kevin Small. Unsupervised rank aggregation with distance- based models. In Proceedings of the 25th international conference Machine learning, pages 472-479, 2008
Alexandre Klementiev, Dan Roth, Kevin Small, and Ivan Titov. Unsupervised rank aggregation with domain-speciff expertise. In Twenty- First International Joins Conference on Artificial Intelligence, 2009.
Tom Koemi and Christian Federmann. GEMBA-MQM: Detecting translation quality error spans with GPT-4. In Philipp Koehn, Barry Haddow, Tom Kocmi, and Christof Monz, editors, Proceedings of the Eighth Conference on Machine Translation, pages 768- -78-775,00 Singapore. December 2023. Association for Computational Linguistics. doi: 10.18653/v1/2022. wmtt///22222211111.m.. 1.64. URL https: org/2023..o...ooooo. 2023. wnt 1.64.
//aclanthology org/
Shankar Kumar and William Byrne. Minimum Bayes-risk word alignments of bilingual texts. In Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing
(EMNLP 2002), pages 140-147. Association for Computational Linguistics, July 2002. doi: 012115/1118693.00 1189915/1188999111118 URL https:t//// https://aclanthhllgg/
14

---

J.N. Laneman, E. Martinian, G.W. Wornell, and J.G. Apostolopollos. Source-channel diversity for parallel channels. IEEE Transactions on Information Theory, 51(10):3518- -333999, 2005. doi: 10.1 10.1009/TT:2005.8855 855578.
Guy Lebanon and Yi Mao. Non-patn con-parametric modeling of partially ranked data. Journal of Machine Learning Research, 9(79):2401-22 -4299, 2008. URL http: / // //tpr////mmm//////// org wwtpes//9//eeaarrrrpeepppppeeeee html.
Haau-Sing Li, Patrick Fernandes, Iryna Gurevych, and André F. T. Martins. Doce: Finding the sweet spot for execution-based code generation, 2024. URL https://///// http///xxvvvv.///i www.viiiorrgaeooooo org..sgg///........o.ooo........ ht/gg/////400 13745.
Zichao Li, Prakhar Sharma, Xing Han Lu, Jackie Cheung, and Siva Reddy. Using interactive feed- back to improve the accuracy and explainability of question answering systems post-deployment. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio, editors, Findings of the As- sociation for Computational Linguistics: ACL 2022, pages 926-937, Dublin, Ireland, May 2022. Association for Computational Linguisties. doi: 10. 10.18653/v1/2022. htwp://///.0....dnnnnnna.a..../ https: aclanholoog 2rgg2222..22 findings-acl.
findings-acl.755 URL
Valentin Liévin, Christoffer Egeberg Hother, Andreas Geert Motzfeldt, and Ole Winther. Can large
language models reason about medical questions? Patlerns, 503):100443, 2024. ISSN 2666-3899. doi: httpac/e/arrccee//////3333329200
100943. URI. https// /ttptttpp///ww.... http://wwww.ccccncdccccccc sciencedirect. com/
Shu Lin, Daniel J Costello, and Michael J Miller. Automatic-repeattrrqquee errorcconro schemes.
IEFE Communications magazine, 22(12):5-17, 1984.
Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and LINGMING ZHANG. Is your code generated by chatGPT really correct? rigorous evaluation of large language models for code generation. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https:
//opnreviee. htg.eerrree...eeeooruuaaaaaaaaee www.oormmdddddde 1iwpmmiiidiiqii0rr...
Tianlin Liu, Shangmin Guo, Leonardo Bianco, Daniele Calandriello, Quentin Berthet, Felipe Llinares, Jessica Hoffmann, Lucas Dixon, Michal Valko, and Mathieu Blondel. Decoding-time realignment of language models. arXiv preprint arXiv:2402.02992 2024.
David C. MacKay. Information Theory, Inference & Learning Algorithms. Cambridge University Press, USA, 2002. ISBN 0521642981.
Benoît Mandelbrot. Information theory and psycholinguistics. BB Wolman and E, 1965.
André Martins, António Farinhas, Marcos Treviso, Vlad Niculae, Pedro Aguiar, and Mario Figueiredo. Sparse and continuous attention mechanisms. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20989-219000 20009. Curran Associates, Inc., 2020. URL https: http://rrooediig....rrrrrppppppp neurips cc/ paper_ files
Paper. pdf.
André Martins, Marcos Treviso, António Farinhas, Pedro M. Q. Aguiar, Mário A. T. Figueiredo, Mathieu Blondel, and Vlad Niculac. Sparse continuous distributions and fenchel-young losses. Journal of Machine Learning Research, 23(257):1-74, 2022. URL http: //jmrr org/ hatgg/pprs//////// v23/21-0877 html.
Pedro Henrique Martins, Vlad Niculae, Zita Marinho, and André F. T. Martins. Sparse and structured visual attention. In 2021 IEEE International Conference on Image Processing (ICIP), pages 379-383, 2021. doi: 10.1 199//11142998 2001:2992..2119566666
Ansong Ni, Srini Iyer, Dragomir Radev, Veselin Stoyanov, Wen- Tau Yih, Sida Wang, and Xi Victoria Lin. LEVER: Learning to verify language-to-coo generation with execution. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 26106-26128 PMLR, 23-29 Jul 2023. URI. https:/ ptwpp/edeccee...o//oope mlr, wtw...pes///eee. watsss//222/nii2 html.
15

---

OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Iige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Mohammad Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Sermadett-Shairo. Christopher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-Luisa Brakman, Greg Brockman, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, Andrew Cann, Brittany Carey, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang, Fotis Chantzis, Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu. Hyung Won Chung, Dave Cummings, Jeremiah Currier, Yunxing Dai, Cory Decareaux, Thomas Degry, Noah Deutsch, Damien Deville, Arka Dhar, David Dohan, Steve Dowling, Sheila Dunning, Adrien Ecoffet, Atty Eleti, Tyna Eloundou. David Farhi. Liam Fedus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao, Elie Georges, Christian Gibson, Vik Goel, Tarun Gogineni, Gabriel Goh, Rapha Lontijo-Lopes, Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo, Chris Hallacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost Huizinga, Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang, Haozhun Jin, Denny Jin, Shino Jomoto, Billie Jonn, Heewoo Jun, Tomer Kaftan, Lukasz Kaiser, Ali Kamali, Ingmar Kanitscheider, Nitish Shirish Keskar, Tabarak Khan. Logan Kilpatrick, Jong Wook Kim, Christina Kim, Yongjik Kim, Jan Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo, Lukasz Kondraciuk, Andrew Kondrich, Aris Konstantinidis, Kyle Kosic, Gretchen Krueger. Vishal Kuo, Michael Lampe, Ikai Lan. Teddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanie Lin, Mateusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini, Sam Manning, Todor Markov, Yaniv Markovski, Bianca Martin, Katie Mayer, Andrew Mayne, Bob McGrew, Scott Mayer McKinney, Christine McLeavey, Paul McMillan, Jake McNeil, David Medina, Aalok Mehta, Jacob Menick, Luke Metz, Andrey Mishchenko, Pamela Mishkin, Vinnie Monaco, Evan Morikawa, Daniel Mossing, Tong Mu, Mira Murati, Oleg Murk, David Mély, Ashvin Nair, Reiichrr Nakano, Rajeev Nayak, Arvind Neelakantan, Richard Ngo Hyeonwoo Noh, Long Ouyang, Cullen O' Keefe, Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pantuliano, Giambattista Parascandolo, Joel Parish. Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng, Adam Perelman, Filipe de Avila Belbute Peres, Michael Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokorny, Michelle Pokrass, Vitchyr H. Pong, Tolly Powell, Alethea Power, Boris Power, Elizabeth Proehl, Raul Puri, Alec Radford, Jack Rae, Aditya Ramesh, Cameron Raymond, Francis Real, Kendra Rimbach, Carl Ross, Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt, David Schnurr, John Schulman, Daniel Selsam, Kyla Sheppard, Toki Sherbakov, Jessica Shieh, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Katarina Slama, Ian Sohl, Benjamin Sokolowsky, Yang Song. Natalie Staudacher, Felipe Petroski Such, Natalie Summers, Ilya Sutskever, Jie Tang, Nikolas Tezak, Madeleine B. Thompson, Phil Tillet, Amin Tootoonchian, Elizabeth Tseng, Preston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe, Andrea Vallone, Arun Vijayvergiya, Chelsea Voss, Carroll Wainwright, Justin Jay Wang, Alvin Wang, Ben Wang. Jonathan Ward, Jason Wei, CJ Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng, Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong, Lauren Workman, Sherwin Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming Yuan, Wojciech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao, Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph. Gpt-4 technical report, 2023.
L. Ozarow. On a source cource-coding problem with two channels and three receivers. The Bell System Technical Journal,
1980. doi: 10. 153--7305. 1880.4033444.
Arkil Patel, Satwik Bhattamishra, and Navin Goyal. Are NLP models really able to solve sim- ple math word problems? In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tur, Iz Beltagy. Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou, editors, Proceedings of the 2021 Conference of the North American Chapter of the Association for Compulational Linguistics: Human Language Technologies, pages 2080-2094 Online, June 2021, Association for Computational Linguistics. doi: 10. 006653/v1/200 maacl-main. 168. URL. org/ 202g/2211.oog maaacl-main.. 168.
Ben Peters and André F. T. Martins. Smoothing and shrinking the sparse Seq2Seq search space. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoee, Dilck Hakkani- Tur, Iz Beltagy,
16

---

Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou, editors, Proceed- ings of the 2021 Conference of the North American Chapter of the Association for Compu- tational Linguistics: Human Language Technologies, pages 2642-2654, Online, June 2021. Association for Computational Linguistics. doi: 10. 18653//1122221. http://2222.nnlllll111 maacl-main.22 https://aclanthonn
URL
2221 naacl-main 210.
Ben Peters, Vlad Niculae, and André F. T. Martins. Sparse sequence-to-sequenee models. In Anna Korhonen, David Traum, and Lluís Mårquez, editors, Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 1504-1519, Florence, Italy, July 2019, Association for Computational Linguistics. doi: 10. 11.1863//1/P19-1146. URL https: // //aclanthology- org/ 1146.
David MW Powers. Applications and explanations of zipf's law. In New methods in language processing and computational natural language learning, 1998.
Victor Quach, Adam Fisch, Tal Schuster, Adam Yala, Jae Ho Sohn, Tommi S Jaakkola, and Regina Barzilay. Conformal language modeling. In The Twelfth International Conference on Learning Representations, 2023.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36, 2024.
Irving S Reed and Gustave Solomon. Polynomial codes over certain finite fields. Journal of the society for industrial and applied mathematics, 8(2):300-304, 1960.
Ricardo Rei, Craig Stewart, Ana C Farinha, and Alon Lavie. COMET: neural framework for MT evaluation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). pages 2685-2702. Online, November 2020. Association for Computational URL https: htt////aaaaaahhloeooeo org/2020.
Linguistics. doi: 10. emmlp-mmiie 213.
Ricardo Rei, José G. C. de Souza, Duarte Alves, Chrysoula Zerva, Ana C Farinha, Taisiya Glushkova, Alon Lavie, Luisa Coheur, and André F. T. Martins. COMET-22: Unbabel-IST 2022 submission for the metries shared task. In Proceedings of the Seventh Conference on Machine Translation (WMT), pages 578-585, Abu Dhabi, United Arab Emirates (Hybrid), December 2022a. Association for Computational Linguistics. URL https: hat/aacaannhoooooo
org/2022 wnt 1.52.
Ricardo Rei, Marcos Treviso, Nuno M. Guerreiro, Chrysoula Zerva, Ana C Farinha, Christine Maroti, José G. C. de Souza, Taisiya Glushkova, Duarte Alves, Luisa Coheur, Alon Lavie, and André T. Martins. CometKiwi: IST-unbabel 2022 submission for the quality estimation shared task. In Proceedings of the Seventh Conference Machine Translation (WMT), pages 634 645, Abu Dhabi, United Arab Emirates (Hybrid), December 2022b. Association for Computational Linguistics. URL https: / acl /aa/lalaatttt antholoyy org/ 2ogg/0220 2022200222222222 4.6.1.60.
Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zettlemoyer, and Sida I. Wang. Natu- ral language to code translation with execution. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang, editors, Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 3533-3546, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. doi: 10.18653/w1/2022.22 12023..11122...mppmmmi.....22. https://ach http///ccaaatooogyyyyoooo org/ 20222 emnle-main 231.
URL
Prasann Singhal, Jiacheng Xu, Xi Ye, and Greg Durrett. Eel: Efficiently encoding lattices for reranking. Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages
2023.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 00:3008-3021, 2020.
Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and policy considerations for deep learning NIP. In Anna Korhonen, David Traum, and Lluís Mårquez, editors, Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3645-3650,
17

---

Florence, Italy, July 2019. Association for Computational Linguisties. doi: 1...8663/x1//19-1355 URL
wrg/p19 1355.
Wenpin Tang. Mallows ranking models: maximum likelihood estimate and regeneration. In Kamalika
Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference
Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 6125-611 PMLR, 09-15 Jun 2019. URL https: htttpp://procee http://///cceeeee//eeeeeeee/ mlr press/vv1/ taaggaa.nn...// html.
Giorgos Vernikos and Andrei Popescu-Belis Belis. Don't rank, combine! combining machine translation hypotheses using quality estimation. arXiv preprint S.Xiv:2401.066680 2024.
Xingyao Wang, Yangyi Chen, Lifan Yuan, Yizhe Zhang. Yunzhu Li, Hao Peng, and Heng Ji. Executable code actions elicit better LLM agents. In ICLR 2024 Workshop on Large Language Model (LLM) Agents, 2024. https::///oopeeeeeeee
net wett//orumnidd-.oyyiiae.
Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoe Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023. URL
htttp::/openreet wwwpiiewnee/fooouue 1d=11P1NIIMMr...
Hongyi Yuan, Zheng Yuan, Chuanqi Tan, Wei Wang, Songfang Huang, and Fei Huang. Rrhf: Rank responses to align language models with human feedback. Advances in Neural Information Processing Systems, 36, 2024.
George Kingsley Zipf. Selected studies of the principle of relative frequency in language. Harvard university press, 1932.
18

---

A Proofs and Visualizations
A.1 Proof of Proposition 1
Let de = - (1 - c) +0+ +) and define F(N) = log Pe (N: c-AeN-e- 1-e-AN Observe
that 0 < x, < A for any À > and E (0, 1). We extend the domain of to the real numbers in [1, +00). We will prove that F(N) is decreasing and that limN-to F" (N - This shows that (err(N; > 0 at asymptotic rate e e^ We have
('(N)= = (e A - - A e A -
(1-6 1 e
-ree-A - de AN AN e-A.N e
de Ae-AN AN 1 50
hence F(N) is decreasing. Since the second term tends to zero, the limit is given by the first term:
-dce-heN Ae-AN
- -
A
lim (NN lim N-00
N 1 1- c(-c(AAAA)N e(-A+tA) -
lim
N
- AA
where we used the fact that e(-A+d, + 0 and e - +00. This proves the desired claim, that is, the error probability decreases exponentially fast with rate edAc, Note that, for perfect reranker (A + oo), we get e and we recover the rate e seen in $3.1.
A.2 Proof of Example 1
>> - T5 = EE= TN-KK = 21-i7 K(K-1)
We first provide proof for r 1. We have ΣN
N(N+1)
Plugging this into Eq. (4), we obtaín
N
KK (1 (1-c)N K2 KK
EKwB(N.e) K22 + +K
Per (N:q) Σ
K
N2 +
N N +
Nc(1 c) + N2 Nc -01-c) (
(11)
N(N +1)
N+1
where e denotes the binomial distribution with parameters N and and we use the facts that B(. [K] = Ne and EX-B(N)) [K3] Ne(1 - c) + N Therefore, we obtain lim Pem (N: = =
We now prove the general case 2 1. From Faulhaber's 's formula, we have Em= ())) B,K*-++1 where Bj Elzo 8+ E (-1) + 1)3 denotes the 7th Bernoulli number. Therefore, we get
K
5" 5r
E (Tt))B
Σ TJ
T
-N- K-j
Σn Ej (ot B.N
(12)
S=N-K++
1=1
Plugging this into Eq. (4), we obtain
N
K (1 - N) N- Ej= (*+1) ByK
P Pon = Σ
K
E B
K Km0
E
BEER-H(N.))
K--tt!]
(13)
Σj=
B,
We now use the fact that the raw moments of the binomial distribution B(N,e) e) are given by Ex=BBN,,) Ee [m) N where [m]] (110-)) are the Stirling num- bers of the second kind, and N (N- the 4t falling power of N. Therefore, when N - oc. (13) becomes
(1)t) Bo
1r+1e+11
lim (Nr = lim N00
P+1
(14)
N No0
(*+11
BoN++1
The plots in Fig. 5 show examples for several values of r.
19

---

0.8
0.7
0.6
100 200
100 N
200
100 0
200
N
N
Figure 5: Per using rerankers with probability mass function " (N - + 1)" with (1, (from left to right) and = 0.8. The resulting protocol is not asymptotically error-free: the horizontal asymptotes in red correspond to e according to Eq. (14).
A.3 Entmax
When 7 7-entmax tributions (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 produce more inter- pretable predictions (Correia et al., 2019; Mar- tins et al., 2020, 2021, 2022). Conversely, when < 1, 7-entmax leads to distributions with heavier tails, which the case our interest, as described in $3.3. See Fig. 6 for an illustra- tion of y-entmax for different values of ? in the two-dimensional case. For y 1, all mappings saturate at z #1/y - 1; this does not happen for < 1.
sparse dis-
1.0
y=0.25
y-0.5
(softmax)
y=15
y-2.0
0.5
-2
2
Figure 6: Two-dimensional meettma ((
A.4 Proof of Proposition 2
Note that we can write
N
= ((p.a+ c 11)
(a ( j)2
1=1
and
L b P(((p. ((0 -K+1))
K-1
b bb - k1) (
F-1
bT((p) /
clatN+1)1(1 - ---) dt
(15)
20

---

The enror probability is
P Per
Σ K=0
N
(k -) N-
K
K+1
dt
10-1
N
ck (1 - -c)N-K(c -
bpT
ela+N+1)c(1 - r- 6
K
k=0
=(elct1-c)M-1
1P p 1( - -1
(T(p)
1ltttNNepp e-t)
144
(e'e+1-e)- -1 eNN
bPT(p) dp
ell+1)e 6---
dt t
[[(1 - -)e + te) - -
(16)
bPT(p) ela+t)e(1 e)
fx))))00
Since is the normalizing constant such that <(p, 1) (T((p) So dt (1at1-1--- (cf. Eq. (8)), we can interpret the expression above as the expectation of [x(() = ((1-e)e-(+)) _ -IN NNN
pp-
under the probability distribution on (0, 00) with density xtt) == (F(()) elo-Di (t) + 0 pointwise for / Ej0, oof and it is bounded in that interval, we can invoke the dominated
1--1
Since
convergence theorem to commute the limit and integral sign. We then have that P (N:((::) O.
A.5 Proof of Proposition 3
Let us consider first the case where 3 = 1. Then,
a+1 a+N-1 - a ati-1 i=1 a - a+la+2
Pen (N:q)
II
+ 0.
N+N a + N
Now consider the case where 3 > 1. We have for each term in the product that a+9+i-I a+1 hence we must have Pen (N;g) < Since the sequence is positive (since all terms are positive)
o+i-l
< ا+i-l
and decreasing (since all terms are < 1). must also have (N: - 0 when 8 >>> 1.
Finally, let us analyze the case where 0 < 3 < From (9), we have
1 I'aa + B) 7 7a-1(1 -))-7))-17 1 /'' = (N:
Perr Perr(N:
[(a)[(B)
I(a+ T(a+
T(a+ B N) T(a N)T(8)
NN (1-7)881
r(aa T(a B+N)
I(a+ T(a+N) T(a) T(o + 3+NN
(17)
We invoke Gautschi's incquality, which states that 1--s
T( M(++))
< (x + +1)1= for any x and
E (0, 1). We set : 1 and + 8 8+1 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 that
2T
2
( 1
O )))
r($)
(18)
21

---

Therefore,
2x
o+N a+N
T(a + N)
O++NN
lim N0000
lim
P(a + B
N0000
2n
a+8+N
a+b+N
O+
a a+ B N
N
a+N
a+N
(a [ -B
lim N00
a + N
a+
e
-1
lim
(a + ++
(19)
No000
A.6 Proof of Proposition
Let pindep (N; q, T) 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-reranke system with exchangeable hypotheses is given by
Perr (N; 4) = PPo(". YN) & x4) 2) Ex,Nk ((o(. .... YN) & (2) | 9)
= Ex [ dr p(r) P(g(YY,..... YN) X(q) (I,N,T)
= 1.' dr p(T) Exnxle P(o(Y,.... YN) $ x(1) (
(20)
=P
Therefore, 1im Perr (N: q) = lim So dr p(T) ( N,;q;,77 r). Since Pindop q, r) e [0, 1] for any N E N and E [0, 1]. we have that Pindep (N: E (()], and there- fore the integrand bounded by p(T), which integrates dominated convergence theorem and switch the limit and integral signs. Since by assumption lim, pindep (N: 0 pointwise for any T (0, 1), we obtain limy (N)
Therefore we can invoke the
Jo dr limiiimnoo pindep (N:g,7) 0. etr
B Experimental Details
B.1 Text-to-code generation
Licenses. We use CrepSeck-Cooer 7B (Guo al., 2024), which is available under 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.
Prompt template. We generate hypotheses with DeepSeek-Codes 7B (Guo et al., 2024) using the following prompt template:
You are an Al programming assistant, utilizing the DeepSeek Coder model, devel- oped by DeepSeek Company, and you only answer questions related computer science. For politically sensitive questions, security and privacy issues, and other non-computer science questions, you will refuse answer.
### Instruction:
Please complete the following Python function in markdown style code block:
"python
[prompt]]
W
### Response:
"python
22

---

exR- We use 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 program is defined by the sum of the loss between itself and the other sampled programs (the ground-truth program output is not used). We break ties by selecting the program with the smallest sampling index, corresponding to a random selection. See Shi et al. (2022, Section 3) for more details.
B.2 Machine translation
Licenses. We use TowerInstruct 13B (Alves al., 2024), which released under a CC-BY-NC-4.0 license. We report results on the TICO-19 19 dataset (Anastasopoulos et al., 2020), publicly available through a Creative Commons CCO license.
Prompt template. We generate hypotheses with TowerInstruct 13B (Alves et al., 2024) using the following prompt template:
< <mm_startt >user
Translate the following [source language] source text to [target
language]:
[source language]: [source sentence]
[target language]: <lim_end|>
<lim_ siimsstar////sim >assistant
Visualizations. In $5.2 we obtained single reranking law for the all language pairs; we now fit different models for each language pair. Fig. 7 shows the log failure rate the dev and test sets function of N for EN-PT, EN-ES, and EN-RU, While the fits on the dev set are good, there is some degradation on the test set, especially for EN-ES (oracle and MBR decoding), possibly due shift in the distribution of scores/errors. We leave the investigation of more robust techniques and how to adapt these cases for future work.
B.3 Mathematical and commonsense reasoning
Our approach is fully general and can be useful in other domains other than code and language generation. In this subsection, we present additional experiments on mathematical and commonsense reasoning benchmarks. as prior work has shown that generating multiple hypotheses as an intermediate step also advantageous in these scenarios (Wang al., 2023).
We use samples generated by Aggarwal et al. (2023) with code-davinci-O0s. a GPT-3-based model with 175 billion parameters (Brown et al., 2020) which is part of the Codex series (Chen et al., 2021) (please refer to their Section 4 for more details; these samples were made publicly available by the authors at https://github.cm wttpp/u...ooo//aaaaa/aaaaa 1/A /AdaapiivCConiitteeee)) We apply self-consistency over diverse reasoning paths ( (Wang et al., 2023), selecting the most frequent answer in the candidate set, and report results the SVAMP (Patel et al., 2021) and Strategy (Geva al., 2021) datasets. Following 15.1, we split the datasets in two equally sized parts to get development and test splits.
Similarly to Fig. 4, Fig. 8 shows the log failure rate on the dev and test sets (left and right, respectively) as a function of N, confirming that the same trends hold also for these two additional tasks.
B.4 Computing infrastructure
Our insfrastructure consists of 2 machines, each equipped with 8 NVIDIA RTX A6000 GPUs (46GB) and 12 Intel Xeon Gold 6348 CPUs (2.60GHz, 1TB RAM). The machines were used interchangeably. and all experiments were executed on single GPU.
23

---

Log failure rate (wrt baseline)
0.0
failure baseline)
qe
mbr
mbr
-0.5
oracle
-0.5
oracle
-1.0
-1.0
Log failure rate (wit baseline)
0.0
fallure baseline)
0.0
mbr
mbr
-0.5
oracle
-0.5
oracle
1.0
-1.5
-1.5
Log falture rate (wrt (wrt baselinel
0.0
fallure (wit baseline)
0.0
mbr
mbr
-0.
oracle
oracle
-1.0
1.5
Figure 7: Log of the failure as function of N. The empirical data is represented with dots (left: dev, right: test set) and our fitted models with solid and dashed lines (imperfect and reranker, respectively). In this case, we fit separate models for each language pair (from top to bottom: EN-PT, EN-ES, and EN-RU).
perfect
24

---

Log failure rate (wrt baseline)
baseline)
-0.5
0.5
-1.0
1.0
-15
-15
-2.0
self-consistency
self-consistency
oracle
oracle
-2.5
-2.5
20
30
10
30
40
N
Log fallure rate (wit baseline)
0
Log rate (wrt baseline)
-1
-1
-4
-5
self-consistency
-5
self-consistency
oracle
oracle
Mggee
sagrt
16
32
48
64
16
32
48
64
Figure 8: Log of the failure rate function of N. The empirical data is represented with dots (left: dev, right: test set) and our fitted models with solid and dashed lines (imperfect and perfect reranker, respectively). Top: mathematical reasoning on SVAMP. Bottom: commonsense reasoning on StrategyQA.
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and the introduction state our assumptions and contributions. We summarize them in bullet points $1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of work in $8.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
26

---

Justification: We state the full set of assumptions of our theoretical results (Propositions 1-4) and include complete proofs App. A. We provide short proof sketches in the main paper. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide all the information needed to reproduce our results in $5 and App. B. Our code is available at
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
27

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We publicly available data in experiments (although not introducing new datasets). Our code available at https//gthhhhcconddepppppiteaaar laws, with CC-BY 4.0 license.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/nips. wwtpccpppppppppteccceccccc gww.c//gue//////eee Caleee//ooSSSubisSeeeee
seriisssssiiiyyyyoco for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/ettails
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary 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 the core the paper to level 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: While we do not report eтror 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 emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
28

---

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 the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We include the type of computing resources used in our experiments in App. B.4.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https http///eeerppppeee wwtppublic/bhiissattieeiieeieeea
Answer: [Yes]
Justification: Our research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. 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), faimess 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 tied to particular applications, let alone deployments. However, if there is 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 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 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We not releasing any data models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 challenging, and many papers do not require this, but encourage authors to take this into account and make 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 paper, including the name of the corresponding licenses App. B.I and App. B.2.
Guidelines:
The answer NA means that the paper does
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 used and, 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.
30

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Our code is available at https://gttaaaccom//epppppppttee laws, with CC-BY 4.0 license.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
31

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
32


Reviews:
[{"review_id": "gmgbfB3Jut", "reviewer": "Reviewer_EFsu", "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.", "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?\n* 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": "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)", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is very well written. The math is clearly explained and sound; it provides a nice theoretical justification of why generator-reranker systems work well  The topic is also very relevant, since LLM reliability (which is improved by the generator-reranker paradigm) is of utmost concern. The laws proposed in this paper also have practical use: they would allow practitioners to decide the number of strings needed from the generator system to achieve a certain accuracy, without lots of trial and error.", "weaknesses": "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. \nThere are a few points that could be addressed to improve readability:\n* 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.\n* There isn’t much intuition about what the R.V. X corresponds to in the generator-reranker system \n* Some more intuition behind the scale parameter (other than just the settings that it gives for its extreme values) would be helpful\n\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> “there is not the same binary notion of acceptable/unacceptable (...) I would like to see an additional discussion (...) for continuous evaluation metrics” \n\nThis 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:\n- 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). \n- 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. \n- Unfortunately, the generalization to imperfect rerankers (e.g. Mallows or Zipf-Mandelbrot rerankers) seems much harder than in the binary case. \n  \nIn 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. \n\nYet, we will use the additional page to add this discussion, as suggested. \n\n[1] David, Herbert A.; Nagaraja, Haikady N. (2004). Order statistics. John Wiley & Sons. p. 299.\n\n\n> “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.” \n\nThank 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. \n\n> “There isn’t much intuition about what the R.V. X corresponds to in the generator-reranker system”. \n\nIn 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. \n\n> “Some more intuition behind the scale parameter (...) would be helpful” \n\nWe 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. \n\n> “The computational experiments are not very comprehensive (...).” \n\nWe 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. \n\n(_continues in a follow-up comment_)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yBSxB3Ra92", "reviewer": "Reviewer_o8DD", "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.", "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.\nThe paper is really good but we miss some analysis.", "limitations": "Limitations are adequately addressed.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- the approach is very flexible. It doesn’t depend on a particular architecture and the outputs to rerank can be generated by multiple different models.\n- a sound parallel is made with communication theory which helps to understand why this approach works.\n- the approach is well formalized. I couldn’t find any error but be aware that I’m not very familiar with Zipf-Mandelbrot and Mallows model.\n- Two scenarios are taken into account: with and without an independence assumption\n- Experiments with machine translation are very relevant for generator-reranker LLMs", "weaknesses": "- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gyHZeLuWHG", "reviewer": "Reviewer_aDZG", "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).\nThis paper analyses this practice with a communication-theoretic approach.\nThey first assume that, given a query $q$, the goal of decoding is to generate a string $y$ in a set $\\mathcal{X}(q)$.\nThey 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. \nThey 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.\nFinally, 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.", "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.\n\n\nAs 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": "The authors properly discuss their analysis limitations in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and in general easy to follow (although I think section 4 could use a bit more hand-holding).\n\nThe paper provides an interesting theoretical analysis to a widely popular text generation framework.\n\nThe paper then investigates whether these theoretical insights are reflected empirically in real decoding settings.", "weaknesses": "In general, I liked this paper. In my opinion however, its main weaknesses are:\n* limited empirical evaluation, with only two tasks, one generator model, and two reranking methods (besides an oracle ranker).\n* 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> “limited empirical evaluation, with only two tasks, one generator model, and two reranking methods (besides an oracle ranker).” \n\nThanks 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. \n\n> “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 (...).” \n\nAs 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).\n\n> “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.” \n\nWe 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.\n\nThank you for the suggestions!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NrY2gv4fGS", "reviewer": "Reviewer_8my9", "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.", "questions": "Please see the weakness.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1 This paper proposes a reranking principle for language generation from a communication-theoretic perspective. The motivation is interesting and the theoretic analysis seems reasonable.\n\n2 The paper is well-written and easily readable.", "weaknesses": "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.\n\n2 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.\n\n3 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> “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.” \n\nWe 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.\n\n> “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.” \n\nThank 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.\n \n> “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.” \n\nCould 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.\n\nReferences: \n\nChen et al., 2023. CodeT: Code Generation with Generated Tests.\n\nTo et al., 2024. Functional Overlap Reranking for Neural Code Generation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear reviewers, 

We appreciate the time and effort you have taken to review our paper and provide constructive feedback. We are pleased to see that our work has been positively received. 

The main weakness pointed out by the reviewers is that we illustrate our reranking laws on two applications only, code generation and machine translation. We picked these tasks due to their particularly challenging nature and the prevalent use of reranking techniques to improve model performance. However, we believe our approach is fully general and can be useful in other domains as well. Therefore, we followed the reviewers' suggestions and ran additional experiments on mathematical and commonsense reasoning benchmarks, as prior work (Wang et al., 2023) has shown that generating multiple hypotheses as an intermediate step is also advantageous in these scenarios. We used samples generated by Aggarwal et al. (2023) with code-davinci-002, a GPT-3-based model with 175 billion parameters (please refer to their Section 4 for more details; these samples were made publicly available by the authors at https://github.com/Pranjal2041/AdaptiveConsistency). We applied self-consistency over diverse reasoning paths (Wang et al., 2023),  selecting the most frequent answer in the candidate set. We report results on SVAMP (Patel et al., 2021) and StrategyQA (Geva et al., 2021). The attached pdf includes plots similar to Figure 4 in our manuscript, showing the log failure rate as a function of N. We observed that the same trends hold also for these two additional tasks. We hope this alleviates the main concern raised by the reviewers.  

References:

Wang et al., 2023. Self-Consistency Improves Chain of Thought Reasoning in Language Models.

Aggarwal et al., 2023. Let’s Sample Step by Step: Adaptive-Consistency for Efficient Reasoning and Coding with LLMs.

Patel et al., 2021. Are NLP Models really able to Solve Simple Math Word Problems?

Geva et al., 2021. Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategies.

Meta-review: 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.
Decision: Accept (spotlight)