% Cref{thm:indep} -> Theorem 3 % thm:main_with_prompts -> Theorem 2 % thm:agnostic -> Theorem 4 % lem:trigram -> Corollary 1 \documentclass[11pt]{article} \usepackage{longtable} \usepackage{threeparttable} \usepackage[numbers,super,sort&compress]{natbib} \usepackage{setspace} % natsub \usepackage{lineno} % natsub \usepackage{url} \providecommand{\urlprefix}{URL } \providecommand{\bibinfo}[2]{#2} \providecommand{\eprint}[2][]{\url{#2}} %taken from macros.tex: \usepackage{fullpage} % small margins \usepackage{microtype} \usepackage{graphicx} \usepackage{subfigure} \usepackage{booktabs} \usepackage{color} \usepackage{lmodern} \usepackage{bbm} % for indicator function % \usepackage[most]{tcolorbox} \usepackage{listings} \lstdefinestyle{prompt}{ basicstyle=\ttfamily\small, columns=fullflexible, keepspaces=true, showstringspaces=false, breaklines=true, breakatwhitespace=true, } \newtcblisting{promptbox}[1][]{% listing only, listing options={style=prompt}, colback=gray!5, colframe=black!40, boxrule=0.6pt, arc=2pt, left=6pt,right=6pt,top=6pt,bottom=6pt, #1 } % \usepackage{amsmath} \usepackage{amssymb} \usepackage{mathtools} \usepackage{amsthm} \usepackage{hyperref} \usepackage[capitalize]{cleveref} \usepackage{bm} \usepackage{listings} \newtheorem{assumption}{Assumption} \newtheorem{definition}{Definition} \newtheorem{theorem}{Theorem} \newtheorem{corollary}{Corollary} \newtheorem{lemma}{Lemma} \newtheorem{observation}{Observation} \crefname{observation}{Observation}{Observations} \Crefname{equation}{Eq.}{Eqs.} \Crefname{figure}{Fig.}{Figs.} \Crefname{table}{Table}{Tables} \def\calA{{\mathcal{A}}} \def\calB{{\mathcal{B}}} \def\calC{{\mathcal{C}}} \def\calE{{\mathcal{E}}} \def\calF{{\mathcal{F}}} \def\calG{{\mathcal{G}}} \def\calH{{\mathcal{H}}} \def\calL{{\mathcal{L}}} \def\calM{{\mathcal{M}}} \def\calN{{\mathcal{N}}} \def\calR{{\mathcal{R}}} \def\calS{{\mathcal{S}}} \def\calU{{\mathcal{U}}} \def\calV{{\mathcal{V}}} \def\calW{{\mathcal{W}}} \def\calX{{\mathcal{X}}} \def\GT{{\mathrm{GT}}} \def\rub{{\mathrm{rub}}} \DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\E}{\mathbb{E}} \def\dichotomous{{binary}} \def\Dichotomous{{Binary}} \def\midd{\middle\|} \newcommand{\set}[2]{\left\{#1\;\middle|\;#2\right\}} % ---- longest brace in the current line (edit once per display) ---- \newcommand*\UBmax{\beta_0+\beta_1 t+\gamma_1\cos(2\pi t/365)+\delta_1d_t} % ---- aligned‑underbrace macro ------------------------------------- \newcommand*\UB[2]{% \underbrace{% #1% the visible material \mathclap{\phantom{\UBmax}}% zero‑width ghost to give equal depth }_{\displaystyle #2}% } \newcommand{\shortdash}{\scalebox{1.0}[1]{-}} \def\sing{\operatorname{sr}} % _\mathrm{tr}} % \def\gerr{\mathrm{err}} % \def\cerr{\mathrm{mis}} % \newcommand{\gerr}{\operatorname{err}_{\mathrm{hal}}} \newcommand{\gerr}{\operatorname{err}} \newcommand{\cerr}{\operatorname{err}_{\mathrm{iiv}}} \def\cerrt{\cerr} \def\hatft{\hat{f}} \def\hatf{\hat{f}} % \def\cerrt{\cerr} \def\MM{\mathrm{MM}} \def\I{{\mathbbm{1}}} \def\IDK{{\mathrm{IDK}}} \newcommand{\KL}[2]{\mathrm{KL}\left(#1\;\midd\;#2\right)} \newcommand{\TV}[2]{\left\|#1-#2\right\|_{\mathrm{TV}}} \newcommand{\mis}[3]{\mathrm{GCE}_{#1}(#3,#2)} \newcommand{\mc}[3]{\mathrm{Mis}_{#1}(#3,#2)} \newcommand{\coarsen}[2]{#1^{#2}} \newcommand{\sparsity}{s} % \newcommand{\cmis}[3]{\mathrm{CCE}_{#1}(#2,#3)} \newcommand{\strings}{X} \def\train{x_\mathrm{train}} \def\trainvec{{\bf x}_{\mathrm{train}}} \def\ytrain{y_\mathrm{train}} \def\ytrainvec{{\bf y}_{\mathrm{train}}} \def\bal{\beta} \def\1{\mathbf{1}} \def\supp{\mathrm{supp}} \def\eps{\varepsilon} \def\opt{\mathrm{opt}} \def\A{{\mathcal{A}}} \def\B{{\mathcal{B}}} \def\C{{\mathcal{C}}} \def\D{{\mathcal{D}}} \def\F{{\mathcal{F}}} \def\G{{\mathcal{G}}} \def\H{{\mathcal{H}}} \def\J{{\mathcal{J}}} \def\K{{\mathcal{K}}} \def\L{{\mathcal{L}}} \def\M{{\mathcal{M}}} \def\N{{\mathcal{N}}} \def\O{{\mathcal{O}}} \def\P{{\mathcal{P}}} \def\Q{{\mathcal{Q}}} \def\R{{\mathcal{R}}} \def\S{{\mathcal{S}}} \def\T{{\mathcal{T}}} \def\U{{\mathcal{U}}} \def\V{{\mathcal{V}}} \def\W{{\mathcal{W}}} \def\Y{{\mathcal{Y}}} \def\Z{{\mathcal{Z}}} \def\reals{{\mathbb{R}}} \def\nats{{\mathbb{N}}} \def\ints{{\mathbb{Z}}} \def\c{\mathbf{c}} \def\r{\mathbf{r}} \def\x{\mathbf{x}} \def\endtoken{{\oslash}} \def\BS{\mathrm{BSw}} \def\doc{\text{doc}} \def\emptystring{{\epsilon}} \newcommand{\abstention}[1]{{\color{blue}[\textit{#1}]}} %end macros.tex \usepackage{graphicx} \usepackage[table]{xcolor} \usepackage{hhline} \usepackage{tablefootnote} \usepackage{enumitem} \usepackage[singlelinecheck=false]{caption} % global % \newcommand{\ofir}[1]{\textcolor{red}{[Ofir: #1]}} % \newcommand{\adam}[1]{{\color{blue} [adam: #1]}} % \newcommand{\santi}[1]{{\color{blue} santi: #1}} \setcounter{theorem}{4} \setcounter{corollary}{1} \setcounter{equation}{4} % \setstretch{1.9} % natsub \linenumbers % natsub \title{Supplementary Information: Evaluating large language models for accuracy incentivizes hallucinations} \date{} \begin{document} \maketitle \section*{}\label{Supplementary_Information} \subsection*{Proof of Theorem 3} We begin by reviewing the Good-Turing ($\GT$) estimator of missing mass \citep{good_population_1953} and its guarantees \citep{mcallester_concentration_2003}. In that setting, $N$ iid samples $s\sim \nu^N$ are drawn from distribution $\nu$ over set $\calS$---abstentions are not a consideration. The missing mass is the probability that a new example drawn from $\nu$ would not be in the training sample $s$, and the estimate $\GT$ is the fraction of training samples that occur exactly once. We first state the prior guarantees and then adapt them to our setting with abstentions. A guarantee of McAllester and Ortiz \citep{mcallester_concentration_2003} can be stated as: \begin{corollary}\citep{mcallester_concentration_2003}\label{cor:their} Let $s\sim \nu^N$ be $N$ iid samples from distribution $\nu$ over set $\calS$. Let $M:=\Pr_{x \sim \nu}[x \notin s]$ and $\GT$ be the fraction of samples that occur exactly once. For any $\gamma \in (0,1]$: $$ \Pr_{s \sim \nu^N}\left[~\left|M-\GT\right| \le \frac{1}{N} + 2.42\sqrt{\frac{\ln(4/\gamma)}{N}}~\right] \ge 1-\gamma. $$ \end{corollary} \begin{proof} Let $\overline\GT:=\E[\GT]$ and $\overline{M}:=\E[M]$. The corollary follows by combining concentration bounds on $M$ and $\GT$. First Theorem 1 of prior work \citep{ms00} shows: $$ \overline\GT -\overline{M} \in [0, 1/N] $$ Then, Theorems 10 and 16 \citep{mcallester_concentration_2003} imply that with probability $\le \exp(-N\eps^2)$, $M$ will deviate from $\overline{M}$ by more than $\eps$ in either direction, together, by the union bound giving for $\eps:=\sqrt{\frac{\ln(4/\gamma)}{N}}$, $$ \Pr_{s \sim \nu^N}\left[~|M-\overline{M}|\ge \sqrt{\frac{\ln(4/\gamma)}{N}}\right] \le \frac{\gamma}{4} + \frac{\gamma}{4} = \frac{\gamma}{2}. $$ Following prior work \citep[Lemma 13]{ms00}, McDiarmid's inequality \citep{McDiarmid1989} directly implies the convergence of $\GT$, since changing any one example can change $\GT$ by at most $2/N$. Hence, $$ \Pr_{s \sim \nu^N}\left[~|\GT-\overline{\GT}|\ge \sqrt{\frac{2\ln(4/\gamma)}{N}}\right] \le 2 \exp\left(-\frac{2\cdot \frac{2\ln(4/\gamma)}{N}}{4/N}\right) = \frac{\gamma}{2}. $$ Combining these three displayed equations, gives, by the union bound, $$ \Pr_{s \sim \nu^N}\left[~|\GT-M|\ge \frac{1}{N} + (1+ \sqrt{2})\sqrt{\frac{\ln(4/\gamma)}{N}}\right] \le \frac{\gamma}{2} +\frac{\gamma}{2} = \gamma. $$ Finally, the corollary follows from $1+ \sqrt{2} \le 2.42$. \end{proof} We now extend this to the case of an abstention response $\bot$ which is not counted in $\sing$. Specifically, we say a query $c$ is \textit{answered} in the training data if there is a training example $(c^{(i)},r^{(i)})$ with $c^{(i)}=c$ and $r^{(i)} \ne \bot$, and \textit{unanswered} otherwise. Let $$\calU:=\calC \setminus \{c^{(i)} \mid i\le N, r^{(i)} \ne \bot\}$$ denote the set of unanswered queries. Of course, by memorizing $a_c$ for answered queries, one can achieve perfect accuracy classifying the answered queries. We extend Turing's Missing Mass (MM) estimate to abstentions as follows: $$\MM := \Pr_{(c,r) \sim p}[c \in \calU \wedge r \ne \bot].$$ We similarly use \Cref{cor:their} to show that $\sing$ is a good estimator of $\MM$: \begin{lemma}\label{lem:gt} For all $N$, $\gamma \in (0,1]$: $$ \Pr\left[~\left|\MM-\sing\right| \le 4.42\sqrt{\frac{\ln(5/\gamma)}{N}}~\right] \ge 1-\gamma. $$ \end{lemma} \begin{proof} The only difference between our $\MM$-$\sing$ and the standard $M$-$\GT$ is that we ignore abstentions. To adapt the previous bounds, consider the sample $s$ which is derived by replacing all $x=(c,\bot)$ with simply $x=\bot$ for any $c$, but otherwise leaving $x$ unchanged. This collapses all IDK responses into identical examples. Thus $\GT$ may count at most one extra singleton compared to $\sing$, $$\GT - \sing \in \left\{0,\frac{1}{N}\right\}.$$ The above substitution induces a distribution $\phi$ where $\phi(\bot)=\sum_c \mu(c)p(\bot \mid c)$ is the probability of abstaining. Similarly, we have $M - \MM \in \{0,\phi(\bot)\}$ with $M - \MM = \phi(\bot)$ if $\bot \notin s$, which happens with probability $(1-\phi(\bot))^N$. But we also have $(1-\phi(\bot))^N \le \gamma/5$ if $\phi(\bot) \ge \frac{1}{N}\ln \frac{5}{\gamma}$. Hence, regardless of the value of $\phi(\bot)$, $$\Pr\left[M - \MM \in \left[0,\frac{1}{N}\ln \frac{5}{\gamma}\right]~ \right] \ge 1-\frac{\gamma}{5}.$$ Combining the above two displayed equations gives,\footnote{This follows from the fact that both \(A:=M-\MM\) and \(B:=\GT-\sing\) are non-negative. If \(0\le A\le \tfrac1N\ln\!\frac{5}{\gamma}\) and \(0\le B\le \tfrac1N\), because \(\tfrac1N\le \tfrac1N\ln\!\frac{5}{\gamma}\), the larger of the two upper bounds is \(\tfrac1N\ln\!\frac{5}{\gamma}\), so \(\lvert A-B\rvert\le \tfrac1N\ln\!\frac{5}{\gamma}\). } \begin{equation}\label{eq:w3} \Pr\left[ \bigl|(M - \GT) - (\MM - \sing)\bigr| \le \frac{1}{N}\ln \frac{5}{\gamma} \right] \ge 1-\frac{\gamma}{5}. \end{equation} \Cref{cor:their} at $\frac{4}{5}\gamma$ gives, $$ \Pr\left[~\left|M-\GT\right| \le \frac{1}{N} + 2.42\sqrt{\frac{\ln(5/\gamma)}{N}}~\right] \ge 1-\frac{4}{5}\gamma. $$ Combining with \Cref{eq:w3} gives, by the union bound and triangle inequality, $$ \Pr\left[~\left|\MM-\sing\right| \le \frac{1}{N}\ln \frac{5}{\gamma} + \frac{1}{N} + 2.42\sqrt{\frac{\ln(5/\gamma)}{N}}~\right] \ge 1-\gamma. $$ Finally, the lemma follows from the fact that for $z:=\frac{2}{N}\ln \frac{5}{\gamma} \ge \frac{1}{N}\ln \frac{5}{\gamma} + \frac{1}{N}$, we have $z \le \sqrt{z}$ as long as $z \le 1$ (otherwise the Lemma holds trivially because the bound is $>2$). \end{proof} % Define the \textit{interim error} $\gamma$ of the classifier to be its expected error given the training data: % $$ % \gamma :=\E[\cerr \mid \mathrm{training\ data}]. % $$ % Of course, the interim error $\gamma \ge \mu$ is at least its expected error on only unanswered queries: % $$ % \mu := \sum_{c \in \calU} \frac{1}{2} \mathrm{1}_{\hat{f}(c} % $$ % %by memorizing $a_c$ for answered queries, one can achieve 0 error on answered queries. \begin{lemma}\label{lem:hp} For any $N \ge 1$, $\gamma \in (0,1]$, and any algorithm outputting $\hat{p}$, $$\Pr\left[2\,\cerr \ge \sing-\frac{6\ln(3N/\gamma)}{\sqrt{N}}\right] \ge 1-\gamma.$$ \end{lemma} \begin{proof} By \Cref{lem:gt}, $$ \Pr\left[~\left|\MM-\sing\right| \le 4.42\sqrt{\frac{\ln(10/\gamma)}{N}}~\right] \ge 1-\frac{\gamma}{2}. $$ Note that $\sqrt{\ln(10/\gamma)} \le \ln(3N/\gamma)$ for $N \ge 2$ (and the lemma holds trivially for $N=1$). Also, $\sqrt{2} + 4.42 \le 6$. Hence, it suffices to show that, $$\Pr\left[2 \,\cerr \ge \MM - \sqrt{\frac{2}{N}}\ln\frac{3N}{\gamma}\right] \ge 1-\frac{\gamma}{2}.$$ Let $\zeta := \ln(3N/\gamma)/N$ and the probability of each query appearing with an answer (not $\bot$) according to $p$ to be: $$\mu'(c):=\mu(c)\alpha_c,$$ so $\mu'(c)=p(c, a_c)$ once $a_c$ is selected. Also note that $\MM=\sum_{c \in \calU}\mu'(c)$. The lemma will thus follow from the following two inequalities: \begin{align} \Pr\left[\forall c \in \calU~\mu'(c) \le \zeta\right] &\ge 1- \frac{\gamma}{3}\label{eq:unseen}\\ \Pr\left[2 \cerr \ge \MM-\sqrt{\frac{2}{N}}\ln\frac{3N}{\gamma}~\middle|~ \forall c \in \calU~\mu'(c) \le \zeta\right] & \ge 1-\frac{\gamma}{6}.\label{eq:last} \end{align} The $\mu'(c)\le \zeta$ condition will enable us to use Hoeffding bounds. For \Cref{eq:unseen}, note that there are $\le 1/\zeta$ queries $c$ with $\mu'(c) \ge \zeta$. For each of these queries, the probability $c \in \calU$ is at most $(1-\zeta)^N$. Hence, by the union bound, $$ \Pr\left[\exists c \in \calU:~\mu'(c) > \zeta\right] \le \frac{1}{\zeta} (1-\zeta)^N \le \frac{1}{\zeta} e^{-\zeta N} = \frac{N}{\ln(3N/\gamma)} \frac\gamma{3N} \le \frac{\gamma}{3},$$ % \begin{align*} % \Pr\left[\exists c \in \calU~\mu(c, a_c) > \zeta\right] &\le \frac{1}{\zeta} (1-\zeta)^N \\ % &\le \frac{1}{\zeta} e^{-\zeta N}\\ % &= \frac{N}{\ln(3N/\gamma)} \frac\gamma{3N}\\ % &\le \frac{\gamma}{3}, % \end{align*} which is equivalent to \Cref{eq:unseen}. We now move on to establish \Cref{eq:last}. Let the indicator $\I[\phi]$ to denote 1 if predicate $\phi$ holds and 0 otherwise. The error $\cerr$ is at least its error summed over $c \in \calU , r \in \calR_c$, of course, which by definition of $D$ is, \begin{align*} \cerr&\ge \frac{1}{2}\sum_{c\in \calU} \mu(c)\alpha_c\I[\hatft(c,a_c)=-] + \frac{1}{2}\sum_{c\in \calU}\mu(c)\sum_{r \in \calR_c \setminus \{a_c\}} \frac{\I[\hatft(c,r)=+]}{|\calR_c|-1} \\ &\ge \frac{1}{2}\sum_{c\in \calU} \mu'(c)\I[\hatft(c,a_c)=-] + \frac{1}{2}\sum_{c\in \calU}\mu'(c)\sum_{r \in \calR_c \setminus \{a_c\}} \frac{\I[\hatft(c,r)=+]}{|\calR_c|-1} \\ &= \sum_{c \in \calU}\mu'(c) \gamma_c \text{ for }\gamma_c := \frac{1}{2} \left( \I[\hatft(c,a_c)=-] + \sum_{r \in \calR_c \setminus \{a_c\}} \frac{\I[\hatft(c,r)=+]}{|\calR_c|-1}\right) \end{align*} Thus $\cerr \ge \sum_{c \in \calU} \mu'(c) \gamma_c$ with $\gamma_c$ define above, and it is not difficult to see that $\gamma_c \in [0,1]$. (The $\mu'(c) \le \zeta$ condition will enable us to apply Hoeffding bounds to $\sum \mu'(c)\gamma_c$.) Thus instead of \Cref{eq:last} it suffices to show, \begin{equation}\label{eq:toshow17} \Pr\left[2\sum_{c \in \calU} \mu'(c) \gamma_c \ge \MM-\sqrt{\frac{2}{N}}\ln\frac{3N}{\gamma}~\middle|~ \forall c \in \calU~\mu'(c) \le \zeta\right] \ge 1-\frac{\gamma}{6}. \end{equation} Now for the key trick: because the algorithm's output is independent of $a_c$ for unseen $c \in \calU$, one can equivalently imagine the $a_c$'s being selected for unseen $c \in \calU$ only \textit{after} running the algorithm on the training data to select $\hat{p}$ which determines $\hat{f}$. Thus, let us suppose that $a_c$ will later be chosen for $c \in \calU$ but that the training data and thus $\hatft$ are \textit{already fixed}. Then, we observe that $\E[\gamma_c] = 1/2$ because each $r\in \calR_c$ contributes $1/2|\calR_c|$ to this expectation regardless of whether it is $\hatft(c,r)=\pm$. This gives $\E[\sum_c \mu'(c)\gamma_c] = \MM/2$ since $\MM=\sum_c \mu'(c)$. Finally, we can apply the Hoeffding bound to $\sum_c \mu'(c) \gamma_c$ since $\mu'(c)\gamma_c$ are independent random variables each in $[0,\mu'(c)]$. The bound depend on, $$\sum_{c\in \calU} (\mu'(c))^2 \le \max_{c \in \calU} \mu'(c) \sum_{c\in \calU} \mu'(c) \le \max_{c \in \calU} \mu'(c) \le \zeta \text{ if } \forall c \in \calU ~ \mu'(c) \le \zeta.$$ The Hoeffding bound thus gives, $$\Pr\left[\sum \mu'(c)\gamma_c \le \frac{\MM}{2} -\sqrt{\frac{\zeta \ln(6/\gamma)}{2}} ~\middle|~ \forall c \in \calU ~ \mu'(c) \le \zeta\right] \le \frac{\gamma}{6},$$ which implies \Cref{eq:toshow17} since $\sqrt{2\zeta \ln(6/\gamma)} = \sqrt{2\ln(3N/\gamma)\ln(6/\gamma)/N}\le \ln(3N/\gamma)\sqrt{2/N}$ (using $\ln (6/\gamma) \le \ln(3N/\gamma)$ for $N\ge 2$ and again the lemma holds trivially for $N=1$). \end{proof} We now prove Theorem 3. \begin{proof}[Proof of Theorem 3] The following more general lower bound, for any $\gamma \in (0,1]$, follows directly from Theorem 2, with $\max_c |\calV_c|=2$, and \Cref{lem:hp}. Specifically, with probability $\ge 1-\gamma$: $$\gerr \ge \sing - \frac{2}{\min_c |\calE_c|}- \frac{6\ln(3N/\gamma)}{\sqrt{N}}- \delta.$$ For $\ge 99\%$ probability at $\gamma=0.01$, we use the simplification that $6 \ln(3N/\gamma) \le 35 + 6 \ln N$. Now let $L:=\max_c |\calE_c|.$ For the upper bound, we now show that there is an efficient algorithm outputting calibrated $\hat{p}$ (so $\delta=0$), and with probability $\ge 1-\gamma$, $$\gerr \le\sing - \frac{\sing}{L +1} + 5\sqrt{\frac{\ln(5/\gamma)}{N}}.$$ The 99\% probability bound in the theorem follows from $5\sqrt{\ln(500)} \le 13$. The calibrated language model learning algorithm memorizes $a_c$ for $(c,a_c)$ seen in the training data and agrees perfectly with $p$ on those $c \notin \calU$ seen in the training data. For the unseen $c \in \calU$, it abstains with the correct probability $1-\alpha_c$ but otherwise is uniformly random over $\calR_c$: $$\hat{p}(r \mid c) := \begin{cases} 1-\alpha_c & \text{ if }r=\bot\\ \alpha_c & \text{ if }c \notin \calU, r=a_c\\ \alpha_c/|\calR_c| & \text{ if }c \in \calU, r\in \calR_c\\ 0 & \text{ otherwise.} \end{cases}.$$ It is easy to see that, for this $\hat{p}$, $$\gerr=\sum_{c \in \calU}\mu(c)\frac{\alpha_c}{|\calR_c|}(|\calR_c|-1) \le\sum_{c \in \calU}\mu(c)\alpha_c\frac{L}{L+1}=\MM\frac{L}{L+1}.$$ Finally, by \Cref{lem:gt} $$\Pr\left[~|\MM-\sing| \le 5\sqrt{\frac{\ln(5/\gamma)}{N}}\right] \ge 1-\gamma.$$ These imply, $$\Pr\left[~\gerr \le\frac{L}{L+1} \sing + 5\sqrt{\frac{\ln(5/\gamma)}{N}}\right] \ge 1-\gamma,$$ as needed. It only remains to show that $\delta_z=0$ for all $z \in [0,1]$. By definition of $\delta_z$, \begin{align*} \delta_z &= \left|\Pr_{(c,r) \sim \hat{p}}\left[\hat{p}(r \mid c)>z\right] - \Pr_{(c,r) \sim p}\left[\hat{p}(r \mid c)>z\right]\right|\\ &=\left|\sum_c \mu(c)\sum_{r:\hat{p}(r \mid c) > z}\bigl(\hat{p}(r \mid c)-p(r \mid c)\bigr)\right| \end{align*} By definition $\hat{p}(r\mid c)=p(r\mid c)$ everywhere except for $c \in \calU, r\in \calR_c$. But for each $c \in \calU$, $\hat{p}(c, r)$ is constant over $r \in \calR_c$, so $\hat{p}(c, r)>z$ for either all $r \in \calR_c$ or none of them. Hence the inner sum above is 0 in any case because $\sum_{r \in \calR_c} \hat{p}(r \mid c) - p(r \mid c)=0$ and $\hat{p}(\bot \mid c)=p(\bot \mid c)$. \end{proof} \subsection*{Proofs of Corollary 1 and Theorem 4} With just one correct answer per prompt, like a multiple-choice exam, it is intuitive that one must generate errors if the only valid response is the unique correct answer and one cannot reliably distinguish correct answers from others. For such a simple case, we show the existence of a threshold $t$ with a better bound. In particular, let $$ \cerr(\hat{f}_t) := \Pr_{x \sim D}\left[\hat{f}_t(x) \ne f(x)\right], \text{ where } \hat{f}_t(c,r) :=\begin{cases} + & \text{ if } \hat{p}(r \mid c) > t,\\ - & \text{ if } \hat{p}(r \mid c) \le t. \end{cases} $$ Hence $\hat{f}=\hat{f}_t$ for $t=1/\min |\calE_c|$ and $\hat{f}$ defined in the paper body. We now state and prove a stronger theorem than Theorem 4. Theorem 4 follows immediately from the definition of $\mathrm{opt}(\mathcal{G})$ and the following theorem. \begin{theorem}\label{thm:mc} Suppose $|\calV_c|=1$ for all $c \in \calC$ and let $C=\min_c |\calE_c|+1$ be the number of choices. Then, for all $p, \hat{p}$, there is some threshold $t \in [0,1]$ such that: $$\gerr \ge 2\left(1-\frac{1}{C}\right)\cerr(\hat{f}_t).$$ \end{theorem} Note that the proof of Corollary 1 follows immediately from \Cref{thm:mc} \begin{proof}[Proof of Corollary 1] The proof follows immediately from \Cref{thm:mc} and the fact that $\cerr(\hat{f}_t)=1/2$ because a classifier $\hat{f}_t$ based on a trigram model cannot distinguish between $c_1,c_2$. \end{proof} We now prove \Cref{thm:mc}. \begin{proof}[Proof of \Cref{thm:mc}] Consider picking a uniformly random $t \in [0,1]$. We show that: \begin{equation}\label{eq:prob} \gerr \ge 2\left(1-\frac{1}{C}\right)\E_{t\in [0,1]}[\cerr(\hat{f}_t)], \end{equation} This implies that there must exist some threshold $t \in [0,1]$ for which it holds. Note that for uniformly random $t \in [0,1]$, $$\Pr_{t \in [0,1]} \left[\hat{f}_t(c,r)=+\right] = \hat{p}(r \mid c).$$ First, the expected false positive rate (misclassifications where $\hat{p}(r \mid c) > t$) is: \begin{align*} \Pr_{t \in [0,1], x \sim D}\left[\hat{f}_t(x) = +, f(x)=-\right] &= \frac{1}{2}\sum_c \mu(c) \sum_{r \in \calE_c} \frac{1}{|\calE_c|} \Pr_t \left[\hat{f}_t(c,r)=+\right]\\ &\le \frac{1}{2}\sum_c \mu(c) \sum_{r \in \calE_c} \frac{1}{C-1} \hat{p}(r \mid c)\\ &= \frac{1}{2(C-1)} \gerr. \end{align*} Let $a_c$ denote the unique element of $\calV_c$. Then the expected false negative rate is, \begin{align*} \Pr_{t \in [0,1], x \sim D}\left[\hat{f}_t(x) = -, f(x)=+\right] &= \frac{1}{2}\sum_c \mu(c) \Pr_t\left[\hat{f}_t(c, a_c)=-\right] \\ &= \frac{1}{2}\sum_c \mu(c) \left(1-\hat{p}(a_c \mid c)\right) \\ &= \frac{1}{2}\gerr. \end{align*} Hence the expected misclassification rate, the sum of the expected false positive and negative rates, satisfies: $$\E_t[\cerr(\hat{f}_t)] \le \frac{1}{2}\left(\frac{1}{C-1}+1\right)\gerr,$$ which is equivalent to \Cref{eq:prob} after rearranging terms. \end{proof} % \bibliographystyle{naturemag} % \bibliography{REFS_FINAL} \begingroup \renewcommand{\refname}{Supplementary Information References} \begin{thebibliography}{99} \expandafter\ifx\csname url\endcsname\relax \def\url#1{\texttt{#1}}\fi \expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi \providecommand{\bibinfo}[2]{#2} \providecommand{\eprint}[2][]{\url{#2}} \bibitem{good_population_1953} \bibinfo{author}{Good, I.~J.} \newblock \bibinfo{title}{The population frequencies of species and the estimation of population parameters}. \newblock \emph{\bibinfo{journal}{Biometrika}} \textbf{\bibinfo{volume}{40}}, \bibinfo{pages}{237--264} (\bibinfo{year}{1953}). \newblock \urlprefix\url{https://doi.org/10.1093/biomet/40.3-4.237}. \bibitem{mcallester_concentration_2003} \bibinfo{author}{McAllester, D.} \& \bibinfo{author}{Ortiz, L.} \newblock \bibinfo{title}{Concentration inequalities for the missing mass and for histogram rule error}. \newblock \emph{\bibinfo{journal}{Journal of Machine Learning Research}} \textbf{\bibinfo{volume}{4}}, \bibinfo{pages}{895--911} (\bibinfo{year}{2003}). \bibitem{ms00} \bibinfo{author}{McAllester, D.~A.} \& \bibinfo{author}{Schapire, R.~E.} \newblock \bibinfo{title}{On the convergence rate of {Good--Turing} estimators}. \newblock In \emph{\bibinfo{booktitle}{Proceedings of the Thirteenth Annual Conference on Computational Learning Theory (COLT~2000)}}, \bibinfo{pages}{1--6} (\bibinfo{publisher}{Morgan Kaufmann}, \bibinfo{address}{Palo Alto, California, USA}, \bibinfo{year}{2000}). \newblock \urlprefix\url{https://www.learningtheory.org/colt2000/papers/McAllesterSchapire.pdf}. \bibitem{McDiarmid1989} \bibinfo{author}{McDiarmid, C.} \newblock \bibinfo{title}{On the method of bounded differences}. \newblock In \bibinfo{editor}{Siemons, J.} (ed.) \emph{\bibinfo{booktitle}{Surveys in Combinatorics, 1989: Invited Papers at the Twelfth British Combinatorial Conference}}, vol. \bibinfo{volume}{141} of \emph{\bibinfo{series}{London Mathematical Society Lecture Note Series}}, \bibinfo{pages}{148--188} (\bibinfo{publisher}{Cambridge University Press}, \bibinfo{address}{Cambridge, UK}, \bibinfo{year}{1989}). \end{thebibliography} \endgroup \end{document}