Summary
A number of recent works in language generation can be framed as proposing two step methods, with a method to generate proposal strings, and another to rank these strings before choosing the best one to be output (this includes, e.g., MBR decoding).
This paper analyses this practice with a communication-theoretic approach.
They first assume that, given a query $q$, the goal of decoding is to generate a string $y$ in a set $\mathcal{X}(q)$.
They then assume the generator’s output $p(y_{1:N} \mid q)$ can be decomposed as $p(x_{1:N} \mid q)p(y_{1:N} \mid x_{1:N})$, with $x_n \in\mathcal{X}(q)$ and $p(y_{1:N} \mid x_{1:N})$ representing some kind of noise perturbation.
They then analyse the probability $p(rank(y_{1:N}) \notin\mathcal{X}(q) \mid q)$ under different assumptions, showing that for many this value goes to zero as $N$ goes to infinity.
Finally, they run two experiments showing their theoretically derived predictions $p(rank(y_{1:N}) \notin\mathcal{X}(q) \mid q)$ seem to correlate with the empirical probability of decoding errors.
Strengths
The paper is well written and in general easy to follow (although I think section 4 could use a bit more hand-holding).
The paper provides an interesting theoretical analysis to a widely popular text generation framework.
The 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:
* limited empirical evaluation, with only two tasks, one generator model, and two reranking methods (besides an oracle ranker).
* the evaluation also makes some (in my opinion) debatable claims. E.g., in line 236 the authors state “[...] the imperfect reranker with majority voting, which fits the data well, as shown by the red curve.”. However, analysing Fig 4 (top), I would argue that the solid lines do not capture the data behaviour that well. In fact, the model’s performance seems to be empirically close to convergence with N, but the solid lines go monotonically down. Maybe running this analysis for larger values of $N$ would show whether the data indeed fits the predictions (specially if the predicted power law would generalise to larger values of $N$ as fit in the current data, and without fitting it on the new results).
Questions
In the code generation experiments, the paper says “we use only one test case for each problem (Shi et al., 2022), and select one candidate by taking a majority vote over the execution results, dismissing hypotheses that fail to execute on the test case.” If a single test case is used, how is majority voting performed exactly? More details here could be helpful.
As a minor suggestion: I found the use of a “communication theoretical” framing here a bit distracting, and it seems to me it could be discarded with no significant change to the paper’s contributions. The authors, for instance, discuss error correcting codes early in the paper, but then they (admittedly) do not require generated strings to be error-corrected. (The selected string simply needs to be in an acceptable set $rank(y_{1:N}) \notin\mathcal{X}(q) $.) Besides, the generator and ranker are framed as a sender and a receiver—with a noisy channel in between them—but no message is actually decoded by the receiving ranker. Alternatively, highlighting the role that a communication-theoretical framing has in the paper (and why it is needed) could be useful.
Limitations
The authors properly discuss their analysis limitations in the paper.