# Filters and ideal independence

J. Cancino-Manríquez  Institute of Mathematics, Czech Academy of Sciences,
Žitná 25, Praha 1, Praha, Czech Republic<EMAIL_ADDRESS>,  V. Fischer
Institute of Mathematics, Univeristy of Vienna, Kolingasse 14-16, 1090 Vienna,
Austria<EMAIL_ADDRESS>and  C. Bacal Switzer  Institute of
Mathematics, Univeristy of Vienna, Kolingasse 14-16, 1090 Vienna, Austria
<EMAIL_ADDRESS>
###### Abstract.

A family $\mathscr{I}\subseteq[\omega]^{\omega}$ such that for all finite
$\\{X_{i}\\}_{i\in n}\subseteq\mathcal{I}$ and
$A\in\mathscr{I}\setminus\\{X_{i}\\}_{i\in n}$, the set
$A\setminus\bigcup_{i<n}X_{i}$ is infinite, is said to be ideal independent.
An ideal independent family which is maximal under inclusion is said to be a
maximal ideal independent family and the least cardinality of such family is
denoted $\mathfrak{s}_{mm}$.

We show that $\mathfrak{u}\leq\mathfrak{s}_{mm}$, which in particular
establishes the independence of $\mathfrak{s}_{mm}$ and $\mathfrak{i}$. Given
an arbitrary set $C$ of uncountable cardinals, we show how to simultaneously
adjoin via forcing maximal ideal independent families of cardinality $\lambda$
for each $\lambda\in C$, thus establishing the consistency of
$C\subseteq\hbox{spec}(\mathfrak{s}_{mm})$. Assuming $\mathsf{CH}$, we
construct a maximal ideal independent family, which remains maximal after
forcing with any proper, ${}^{\omega}\omega$-bounding, $p$-point preserving
forcing notion and evaluate $\mathfrak{s}_{mm}$ in several well studied
forcing extensions.

###### Key words and phrases:

Ideal independent family, ideal, filter, ultrafilter, cardinal characteristic

###### 2000 Mathematics Subject Classification:

03E35, 03E17

_Acknowledgments._ : The authors would like to thank the Austrian Science Fund
(FWF) for the generous support through START Grant Y1012-N35.

##  1\. Introduction

Given a family $\mathscr{I}\subseteq[\omega]^{\omega}$, the ideal associated
to $\mathscr{I}$ is the collection of all $A\subseteq\omega$ so that
$A\subseteq^{*}\bigcup_{i<n}X_{i}$ for some finite $\\{X_{i}\\}_{i\in
n}\subseteq\mathscr{I}$ where $\subseteq^{*}$ means inclusion mod finite. A
family $\mathscr{I}$ is ideal independent if no $A\in\mathscr{I}$ is in the
ideal generated by $\mathscr{I}\setminus\\{A\\}$. More precisely,
$\mathscr{I}$ is ideal independent, if whenever
$X_{0},...,X_{n-1},A\in\mathscr{I}$ and $A\subseteq^{*}\bigcup_{i<n}X_{i}$
then there is an $i<n$ so that $X_{i}=A$. Almost disjoint families and
independent families are both examples of ideal independent families. An easy
application of Zorn’s lemma shows that there are maximal ideal independent
families, however it is not always the case that a maximal almost disjoint or
a maximal independent family is maximal ideal independent. Thus, the cardinal
characteristic $\mathfrak{s}_{mm}$, defined as the least cardinality of a
maximal ideal independent family, becomes of interest.

An earlier investigation of $\mathfrak{s}_{mm}$ can be found [5], where it is
shown that ${\rm max}\\{\mathfrak{d},\mathfrak{r}\\}\leq\mathfrak{s}_{mm}$ and
that each of the following inequalities $\mathfrak{u}<\mathfrak{s}_{mm}$,
$\mathfrak{s}_{mm}<\mathfrak{i}$, $\mathfrak{s}_{mm}<\mathfrak{c}$ is
consistent. Here $\mathfrak{d}$, $\mathfrak{u}$, $\mathfrak{r}$,
$\mathfrak{i}$ denote the is the dominating number, the ultrafilter number,
the reaping and independence numbers, respectively. We refer the reader to [1]
for definitions and basic properties of the combinatorial cardinal
characteristics, which are not stated here. Strengthening and complimenting
the above results, in Section 2, we establish the following $\mathsf{ZFC}$
inequality, which also answers Question 17 of [5], see Theorem 2.2:

######  Theorem.

$\mathfrak{u}\leq\mathfrak{s}_{mm}$.

As a consequence we obtain the independence of $\mathfrak{s}_{mm}$ and
$\mathfrak{i}$, as the consistency of $\mathfrak{s}_{mm}<\mathfrak{i}$ is
shown in [5, Theorem 16], while the consistency of $\mathfrak{i}<\mathfrak{u}$
is established in Shelah’s [13] and hence by the above theorem,
$\mathfrak{i}<\mathfrak{s}_{mm}$ holds in the latter model.

######  Corollary.

$\mathfrak{s}_{mm}$ and $\mathfrak{i}$ are independent.

A key role in our investigations is taken by specific filters, which are
naturally associated to a given ideal independent family. On one side, these
are filters to which we refer as complemented filters, see Definition 2.1 and
on the other side, filters resembling the notion of a diagonalization filter
for an independent family, see for example [7, Definition 1]. In difference
with earlier instances of diagonalization reals, associated to say almost
disjoint families, towers, or cofinitary groups, the existence of a
diagonalization real for a given ideal independent family, employs a Cohen
real (see Lemma 3.1). Adjoining diagonalization reals for ideal independent
families cofinally along an appropriate finite support iteration, as well as
building on and modifying earlier forcing constructions used to control for
example the spectrum of independence (see in particular [7, 8]) we establish
the following (see Theorem 3.4):

######  Theorem.

(GCH) Let $R$ be a set of regular uncountable cardinals. Then, there is a ccc
generic extension in which for every $\lambda\in R$ there is a maximal ideal
independent family of cardinality $\lambda$.

Moreover, we look at the preservation of small witnesses to
$\mathfrak{s}_{mm}$. The preservation of the maximality of extremal sets of
reals, like mad families, maximal eventually different families of reals, or
maximal independent families, under forcing iterations is usually a non-
trivial task and often involves the construction of a combinatorial object
which is maximal in a strong sense, examples given by tight almost disjoint
and selective independent families. Partially inspired by the notion of an
$\mathcal{U}$-supported maximal independent family in the higher Baire spaces
given in [6], in Definition 4.1 we introduce the notion of an
$\mathcal{U}$-encompassing ideal independent family and establish the
following general preservation result (see Theorems 4.2 and 4.3). We should
point out, that even though, the latter two notions have some superficial
similarities, they do remain significantly different, as they reflect the
structure of rather distinct combinatorial sets of reals.

######  Theorem.

(CH) There is a maximal ideal independent family $\mathscr{I}$ which remains
maximal, and so a witness to $\mathfrak{s}_{mm}=\aleph_{1}$, in any generic
extension obtained by a proper, $\omega^{\omega}$-bounding, $p$-points
preserving forcing notion.

In particular, the above result implies that in many well-studied forcing
extensions, $\mathfrak{s}_{mm}=\max\\{\mathfrak{d},\mathfrak{u}\\}$. We
conclude the paper with a brief discussion of remaining open questions.

###  1.1. Preliminaries

Recall that given $f,g\in\omega$ we write $f\leq^{*}g$ ($f$ is eventually
dominated by $g$), provided there is $n\in\omega$ such that for all $m\geq n$,
$f(m)\leq g(m)$. The cardinal $\mathfrak{b}$, the bounding number is the least
size of a family $A\subseteq\omega^{\omega}$ so that no single
$f\in\omega^{\omega}$ eventually dominates every $g\in A$. Dually, the
dominating number, $\mathfrak{d}$, is the least size of a dominating family,
that is a family $D\subseteq\omega^{\omega}$ so that every
$f\in\omega^{\omega}$ is eventually dominated by some $g\in D$. We denote by
$[\omega]^{\omega}$ the Ramsey space, that is the Polish space of infinite
subsets of $\omega$. Often it is convenient to quotient this space by the
ideal of finite sets. For instance, if $A,B$ in $[\omega]^{\omega}$ then we
write $A\subseteq^{*}B$, read “$A$ is almost contained in $B$” if $A\setminus
B$ is finite. Similarly we say that $A$ and $B$ are almost equal, denoted
$A=^{*}B$, if their symmetric difference is finite, and we say that $A$ and
$B$ are almost disjoint, denoted $A\cap B=^{*}\emptyset$, if their
intersection is finite. Given a family $\mathcal{A}\subseteq[\omega]^{\omega}$
we say that $\mathcal{A}$ has the finite intersection property if any finite
subfamily has infinite intersection. If $\mathcal{A}$ has the finite
intersection property then it may have a pseudo-intersection, i.e. a set
$B\in[\omega]^{\omega}$ so that $B\subseteq^{*}A$ for every $A\in\mathcal{A}$.
The cardinal characteristic $\mathfrak{p}$ is the least size of a family with
the finite intersection property with no pseudo-intersection. An ultrafilter
is is said to be principal if it contains a singleton and non-principal
otherwise. Unless otherwise stated we will assume all ultrafilters are non-
principal. If $\mathscr{U}$ is an ultrafilter then a base for $\mathscr{U}$ is
a subset $\mathcal{B}\subseteq\mathscr{U}$ so that every element
$A\in\mathscr{U}$ almost contains some $B\in\mathcal{B}$. In this case, we say
that $\mathcal{B}$ generates $\mathscr{U}$, sometimes denoted
$\langle\mathcal{B}\rangle$. The cardinal $\mathfrak{u}$, the ultrafilter
number, is the least size of a non-principal ultrafilter base. For an
ultrafilter $\mathscr{U}$ we say that

  1. (1)

$\mathscr{U}$ is a $p$-point if every countable subfamily of $\mathscr{U}$ has
a pseudo-intersection in $\mathscr{U}$;

  2. (2)

$\mathscr{U}$ is a q-point if every partition of $\omega$ into finite sets
$\\{I_{n}\\}_{n<\omega}$ there is a $U\in\mathscr{U}$ so that $|U\cap
I_{n}|=1$ for each $n<\omega$;

  3. (3)

$\mathscr{U}$ is Ramsey, or, selective if it is a $p$-point and a q-point.

  4. (4)

$\mathscr{U}$ is a $p_{\mathfrak{c}}$-point if any
$\mathscr{F}\subseteq\mathscr{U}$, $|\mathscr{F}|<\mathfrak{c}$ has a pseudo-
intersection in $\mathscr{U}$.

Finally, a family $\mathcal{I}\subseteq[\omega]^{\omega}$ is said to be
independent if whenever $\mathcal{A},\mathcal{B}$ are finite, disjoint, non-
empty subfamilies of $\mathcal{I}$, the set $\bigcap
A\setminus\bigcup\mathcal{B}$ is infinite. The least size of a maximal
independent family is denoted $\mathfrak{i}$.

##  2\. Ultrafilters and ideal independence

A central role in our proof of $\mathfrak{u}\leq\mathfrak{s}_{mm}$ is played
by the following filters:

######  Definition 2.1.

Let $\mathscr{I}$ be an ideal independent family. For any $A\in\mathscr{I}$,
let $\mathcal{F}(\mathscr{I},A)$ be the filter on generated by the family
$\\{A\setminus\bigcup F:F\in[\mathscr{I}]^{<\omega}\land A\notin F\\}$. We
refer to the filters of the form $\mathcal{F}(\mathscr{I},A)$ as the
complemented filters of $\mathscr{I}$, while for a fixed $A\in\mathscr{I}$ we
say that $\mathcal{F}(\mathscr{I},A)$ is the complemented filter (of
$\mathscr{I}$) corresponding to $A$.

Note that an ideal independent family $\mathscr{I}$ is maximal if and only if
every $X\in[\omega]^{\omega}$ is either in the ideal generated by
$\mathscr{I}$ or belongs to at least one of the filters
$\mathcal{F}(\mathscr{I},A)$ (these two possibilities are not mutually
exclusive). The name “complemented” comes from this observation: under
maximality every element of the complement of the ideal generated by
$\mathscr{I}$ is in some completemented filter.

######  Theorem 2.2.

$\mathfrak{u}\leq\mathfrak{s}_{mm}$.

###### Proof.

Assume otherwise $\mathfrak{s}_{mm}<\mathfrak{u}$ and let $\mathscr{I}$ be a
maximal ideal independent family of minimal cardinality. Maximality implies
that there is $\\{A_{n}\\}_{n\in\omega}\subseteq\mathscr{I}$ whose union is
almost equal to $\omega$. Define $B_{0}=A_{0}$ and for $n>0$,
$B_{n}=A_{n}\setminus\bigcup_{i<n}A_{n}$. For each $n\in\omega$, let
$\mathcal{F}_{n}$ be the filter $\mathcal{F}(\mathscr{I},A_{n})\upharpoonright
B_{n}$. Since $\mathcal{F}_{n}$ is not an ultrafilter, for any $s\in 2^{n}$
there is $D_{s}\in\mathcal{F}_{n}^{+}\setminus\mathcal{F}_{n}$ such that for
different $s,r\in 2^{n}$, $D_{r}\cap D_{s}=\emptyset$. Now, for each $f\in
2^{\omega}$, define $D^{f}=\bigcup_{n\in\omega}D_{f\upharpoonright n}$. Note
that $D^{f}$ is not almost contained in the union of finitely many elements
from $\mathscr{I}$. Indeed, for any finite $F\subseteq\mathscr{I}$, let
$n\in\omega$ be such that $A_{n}\notin F$. We can assume that
$\\{A_{i}:i<n\\}\subseteq F$. Since $D_{f\upharpoonright n}$ is
$\mathcal{F}_{n}$-positive, it can not be covered by $\bigcup F$. It follows
that $D^{f}$ can not be covered by $\bigcup F$ either. By maximality of
$\mathscr{I}$, for any $f\in 2^{\omega}$, there are $A_{f}\in\mathscr{I}$ and
$F_{f}\in[\mathscr{I}\setminus\\{A_{f}\\}]^{<\omega}$ such that
$A_{f}\setminus\bigcup F_{f}\subseteq^{*}D^{f}$. Note that for no $n\in\omega$
it is the case that $A_{n}=A_{f}$: otherwise, for some $n\in\omega$ we would
have $A_{n}\setminus F_{f}\subseteq^{*}D^{f}$, which implies
$B_{n}\setminus\bigcup F_{f}=A_{n}\setminus\left(\bigcup
F_{f}\cup\bigcup_{i<n}A_{i}\right)\subseteq^{*}D_{f\upharpoonright n}$,
contradicting the choice of the set $D_{f\upharpoonright n}$. Since
$\mathfrak{s}_{mm}<\mathfrak{c}$, there are different $f,g\in 2^{\omega}$ such
that $A_{f}=A_{g}$ and $F_{f}=F_{g}$. By construction, we have that
$A_{f}\setminus F_{f}\subseteq^{*}D^{f}\cap D^{g}\subseteq\bigcup_{i\leq
n_{0}}B_{i}$, where $n_{0}\in\omega$ is the maximal natural number such that
$f\upharpoonright n_{0}=g\upharpoonright n_{0}$. But $\bigcup_{i\leq
n_{0}}B_{i}=\bigcup_{i\leq n_{0}}A_{i}$, which means that
$A_{f}\setminus\bigcup F_{f}\subseteq^{*}\bigcup_{i\leq n_{0}}A_{n_{0}}$, and
so $A_{f}\subseteq^{*}\bigcup F\cup\bigcup_{i\leq n_{0}}A_{i}$, a
contradiction. ∎

The above proof shows that whenever $\mathscr{I}$ is a maximal ideal
independent family such that $|\mathscr{I}|<\mathfrak{c}$, then there are at
most finitely many $A\in\mathscr{I}$ for which the corresponding complemented
filter is not an ultrafilter. Indeed, if there were infinitely many such
$A$’s, one could add them to the family $\\{A_{n}\\}_{n\in\omega}$ in the
above proof and proceed along the same lines to reach a contradiction.
However, this is not necessarily the case for ideal independent families with
cardinality $\mathfrak{c}$, as for example any completely separable maximal
almost disjoint family $\mathcal{A}$ is a maximal ideal independent family
111Recall that a maximal almost disjoint family $\mathcal{A}$ is completely
separable if for any $X\in[\omega]^{\omega}$, there is $B\in\mathcal{A}$ such
that $B\subseteq X$ or $X$ belongs to the ideal generated by $\mathcal{A}$.
and for any $A\in\mathcal{A}$, the corresponding complemented filter
$\mathcal{F}(\mathscr{I},A)$ is the collection of cofinite subsets in $A$. It
remains of interest to characterise those ideal independent families
$\mathscr{I}$ for which there is $A\in\mathscr{I}$ such that
$\mathcal{F}(\mathscr{I},A)$ is an ultrafilter. The following two questions
remain open:

######  Question 2.3.

Is it consistent that there are no maximal ideal independent families
$\mathscr{I}$ with the property that $\mathcal{F}(\mathscr{I},A)$ is an
ultrafilter for some $A\in\mathscr{I}$ ?

As pointed out above, a positive answer to this question implies
$\mathfrak{s}_{mm}=2^{\aleph_{0}}$.

######  Question 2.4.

Is it consistent that for every maximal ideal independent family $\mathscr{I}$
there is an $A\in\mathscr{I}$ so that $\mathcal{F}(\mathscr{I},A)$ is an
ultrafilter?

A positive answer to this question would imply that there are no completely
separable maximal almost disjoint families. It is known that such families
exist under either $\mathfrak{s}\leq\mathfrak{a}$ or
$2^{\aleph_{0}}<\aleph_{\omega}$, see [12] and [10], respectively. In
contrast, we show that at least under certain assumptions there are maximal
ideal independent families $\mathscr{I}$ so that every complemented filter of
$\mathscr{I}$ is an ultrafilter:

######  Proposition 2.5.

If $\mathfrak{p}=\mathfrak{c}$ then there is a maximal ideal independent
family $\mathscr{I}$ with the property that for every $A\in\mathscr{I}$ the
corresponding complemented filter $\mathcal{F}(\mathscr{I},A)$ is a
$p_{\mathfrak{c}}$-point.

###### Proof.

Observe that if $\mathfrak{p}=\mathfrak{c}$,
$\mathcal{Z}\subseteq[\omega]^{\omega}$, $|\mathcal{Z}|<\mathfrak{c}$ and $X$
is not in the ideal generated by $\mathcal{Z}$, then there is a
$Y\in[X]^{\omega}$ which is almost disjoint from every element of
$\mathcal{Z}$. Indeed, consider the forcing notion
$\mathbb{P}_{X,\mathcal{Z}}$ consisting of pairs
$(s,F)\in[X]^{<\omega}\times[\mathcal{Z}]^{<\omega}$, where
$(s_{1},F_{1})\leq(s_{0},F_{0})$ if $s_{1}\supseteq s_{0}$, $F_{1}\supseteq
F_{0}$ and $(s_{1}\setminus s_{0})\cap(\bigcup F_{0})=\emptyset$. It is easy
to see that $\mathbb{P}_{X,\mathcal{Z}}$ is $\sigma$-centered and adds a
subset of $X$ which is almost disjoint from every element of $\mathcal{Z}$.
Since $\hbox{MA}(\sigma\hbox{-centered})$ holds (by
$\mathfrak{p}=\mathfrak{c}$, see [1]), the claim follows.

The family $\mathscr{I}$ is defined recursively. Fix an enumeration of
$[\omega]^{\omega}$ indexed by the even ordinals,
$\\{X_{\alpha}\;|\;\alpha<\mathfrak{c},\;{\rm even}\\}$ so that every element
of $[\omega]^{\omega}$ appears unboundedly often and an enumeration of
$2^{\aleph_{0}}$ indexed by the odd ordinals
$\\{\beta_{\alpha},\;|\;\alpha<\mathfrak{c}\;{\rm odd}\\}$ so that every
ordinal appears unboundedly often, $\beta_{\alpha}\leq\alpha$ for all
$\alpha$, and for every pair
$(X,\gamma)\in[\omega]^{\omega}\times\mathfrak{c}$ there is an $\alpha$ such
that $(X,\gamma)=(X_{\alpha},\beta_{\alpha+1})$. Let
$\mathscr{I}_{\omega}=\\{A_{n}\\}_{n\in\omega}$ be a partition of $\omega$
into infinitely many infinite sets. Suppose
$\mathscr{I}_{\alpha}=\\{A_{\gamma}\\}_{\gamma<\alpha}$ has been defined for
some even $\alpha<\mathfrak{c}$ (limits are even) and $\mathscr{I}_{\alpha}$
is ideal independent. First we define a set $A_{\alpha}$. If $X_{\alpha}$ is
not in the ideal generated by $\mathscr{I}_{\alpha}$ then by the above
observation, there is $A_{\alpha}\subseteq X_{\alpha}$ which is almost
disjoint from every $A_{\gamma}$, for $\gamma<\alpha$. Otherwise take
$A_{\alpha}$ be an arbitrary set such that
$\mathscr{I}_{\alpha}\cup\\{A_{\alpha}\\}$ is ideal independent. Next, take
$\mathscr{I}_{\alpha+1}=\mathscr{I}_{\alpha}\cup\\{A_{\alpha}\\}$ and define
$A_{\alpha+1}$ as follows: Let $\mathcal{F}_{\alpha+1}$ be the filter
$\mathcal{F}(\mathscr{I}_{\alpha+1},A_{\beta_{\alpha+1}})$. At least one of
the sets $X_{\alpha}$, $\omega\setminus X_{\alpha}$ is
$\mathcal{F}_{\alpha+1}$-positive. Let $Y_{\alpha}$ be this one (if they both
are, choose $X_{\alpha}$). Since $\mathfrak{p}=\mathfrak{c}$, there are a
pseudo-intersection $Y^{*}_{\alpha}$ of
$\mathcal{F}_{\alpha+1}\cup\\{Y_{\alpha}\\}$ and a set $Y^{**}_{\alpha}$ which
is almost disjoint from every element of
$\mathscr{I}_{\alpha+1}\cup\\{Y^{*}_{\alpha}\\}$. Finally, take
$A_{\alpha+1}=(A_{\beta_{\alpha+1}}\setminus Y^{*}_{\alpha})\cup
Y^{**}_{\alpha}$ and let
$\mathscr{I}_{\alpha+2}=\mathscr{I}_{\alpha+1}\cup\\{A_{\alpha+1}\\}$. This
completes the construction.

Let $\mathscr{I}=\bigcup_{\alpha<\mathfrak{c}}\mathscr{I}_{\alpha}$. To see
that $\mathscr{I}$ is ideal independent, it suffices to show that
$\mathscr{I}_{\alpha+1}\cup\\{A_{\alpha+1}\\}$ is ideal independent for
$\alpha$ even. To see this, note that $A_{\alpha+1}$ is not in the ideal
generated by $\mathscr{I}_{\alpha+1}$, since it contains a set almost disjoint
from every element of $\mathscr{I}_{\alpha+1}$. Suppose now that there are
finite $F\subseteq\mathscr{I}_{\alpha+1}$ and $A\in\mathscr{I}_{\alpha+1}$
such that $A\setminus\bigcup F\subseteq^{*}A_{\alpha+1}$. Since
$Y^{**}_{\alpha}$ is almost disjoint from every element of the family
$\mathscr{I}_{\alpha+1}$, it follows that $A\setminus\bigcup
F\subseteq^{*}A_{\beta_{\alpha+1}}\setminus
Y^{*}_{\alpha}\subseteq^{*}A_{\beta_{\alpha+1}}$ and thus by ideal
independence of $\mathscr{I}_{\alpha+1}$ we obtain $A=A_{\beta_{\alpha+1}}$.
However, this implies
$Y^{*}_{\alpha}\subseteq^{*}A_{\beta_{\alpha+1}}\setminus\bigcup
F\subseteq^{*}A_{\beta_{\alpha+1}}\setminus Y^{*}_{\alpha}$ which is a
contradiction. To see that $\mathscr{I}$ is maximal, note that if $X$ is not
in the ideal generated by $\mathscr{I}$ then by the even part of the
construction there is $Y\in\mathscr{I}$, such that $Y\subseteq X$ and hence
$\mathscr{I}\cup\\{X\\}$ is not ideal independent.

Finally, we show that $\mathcal{F}(\mathscr{I},A)$ is a
$p_{\mathfrak{c}}$-point. For each odd $\alpha$, say $\alpha=\alpha_{0}+1$,
$A_{\beta_{\alpha}}\setminus
A_{\alpha}=^{*}A_{\beta_{\alpha}}\setminus(A_{\beta_{\alpha}}\setminus
Y^{*}_{\alpha_{0}})=Y^{*}_{\alpha_{0}}$ and so $Y^{*}_{\alpha_{0}}$ is in
$\mathcal{F}(\mathscr{I},A_{\beta_{\alpha}})$. Since every $\beta_{\alpha}$ is
enumerated unboundedly often, pseudo-intersections are added unboundedly often
along the construction and so $\mathcal{F}(\mathscr{I},A_{\beta_{\alpha}})$ is
a $p_{\mathfrak{c}}$-point, provided it is an ultrafilter. It remains to
observe that $Y^{*}_{\alpha_{0}}$ is a pseudo-intersection of either
$X_{\alpha}$ or $\omega\setminus X_{\alpha}$ and so one of those sets is in
the filter. ∎

##  3\. Arbitrarily Large Maximal Ideal Independent Families

In this section we examine the question of how to adjoin via forcing maximal
ideal independent family of arbitrary size and thus begin an investigation of
the spectrum of such families. The spectrum of maximal ideal independent
families, denoted ${\rm spec}(\mathfrak{s}_{mm})$, is defined as the set of
all cardinalities of maximal ideal independent families. Throughout $V$
denotes the ground model and $\mathbb{C}$ denotes the poset for adding a
single Cohen real.

######  Lemma 3.1.

Let $\mathscr{I}$ be an ideal independent family. There is a $ccc$ forcing
$\mathbb{P}(\mathscr{I})$ which adds a set $z$ such that in
$V^{\mathbb{P}(\mathscr{I})}$:

  1. (1)

$\mathscr{I}\cup\\{z\\}$ is an ideal independent family, and

  2. (2)

for each $y\in V\cap([\omega]^{\omega}\backslash\mathscr{I})$ the family
$\mathscr{I}\cup\\{z,y\\}$ is not ideal independent.

###### Proof.

Add a Cohen real to $V$ and consider a filter $\mathcal{F}$ which contains the
Cohen real and is maximal with respect to the following property: for any
$X\in\mathcal{F}$, any $A\in\mathscr{I}$ and finite
$F\subseteq\mathscr{I}\setminus\\{A\\}$, $X\cap(A\setminus\bigcup F)$ is
infinite. Let $\mathbb{M}(\mathcal{F})$ be Mathias forcing relativized to
$\mathcal{F}$, let $x$ be the generic real added by $\mathbb{M}(\mathcal{F})$
over $V^{\mathbb{C}}$, let $\dot{x}$ be $\mathbb{M}(\mathcal{F})$-name for $x$
(in $V^{\mathbb{C}}$) and let
$\mathbb{P}(\mathscr{I})=\mathbb{C}*\mathbb{M}(\dot{\mathcal{F}})$.

######  Claim 3.2.

In $V^{\mathbb{P}(\mathscr{I})}$ the family $\mathscr{I}\cup\\{\omega\setminus
x\\}$ is ideal independent.

###### Proof.

Let $F$ be a finite subset of $\mathscr{I}$. First we prove that $\bigcup F$
does not almost contain $\omega\setminus x$. Let $A\in\mathscr{I}\backslash
F$, $(s,B)\in\mathbb{M}(\mathcal{F})$ and let $n\in\omega$ be arbitrary. Since
the Cohen real belongs to $\mathcal{F}$, we can assume that $B$ is a subset of
it, so $A\setminus(B\cup\bigcup F)$ is infinite. Let $k\in\omega$ be big
enough so $[\max(s),k)\cap(A\setminus(B\cup\bigcup F))$ has more than $n$
elements. Then $(s\cup\\{k\\},B)$ forces that
$(\omega\setminus\dot{x})\setminus\bigcup F$ has more than $n$ elements and
since $n$ was arbitrary, it follows that $(\omega\setminus x)\setminus\bigcup
F$ is infinite. A genericity argument shows that $x\cap(A\setminus\bigcup F)$
is infinite for any $A\in\mathscr{I}$ and
$F\in[\mathscr{I}\setminus\\{A\\}]^{<\omega}$, which implies that
$(A\setminus\bigcup F)\setminus(\omega\setminus x)$ is infinite. ∎

######  Claim 3.3.

Let $A\in([\omega]^{\omega}\cap V)\backslash\mathscr{I}$. Then in
$V^{\mathbb{P}(\mathscr{I})}$, $\mathscr{I}\cup\\{\omega\setminus x,A\\}$ is
not ideal independent.

###### Proof.

Let $A\in[\omega]^{\omega}\cap V$ be an arbitrary set. If there are
$X\in\mathcal{F}$, $B\in\mathscr{I}$ and
$F\in[\mathscr{I}\setminus\\{B\\}]^{<\omega}$ such that
$X\cap(B\setminus\bigcup F)\subseteq^{*}A$, then $x\cap(B\setminus\bigcup
F)\subseteq^{*}A$. But $x\cap(B\setminus\bigcup F)=(B\setminus\bigcup
F)\setminus(\omega\setminus x)$, so $A$ can not be added to
$\mathscr{I}\cup\\{\omega\setminus x\\}$, as witnessed by $B,F$ and
$\omega\setminus x$. On the other hand, if for all $X\in\mathcal{F}$,
$B\in\mathscr{I}$ and $F\in[\mathscr{I}\setminus\\{B\\}]^{<\omega}$ it happens
that $X\cap(B\setminus\bigcup F)\nsubseteq^{*}A$, then $(\omega\setminus
A)\cap X\cap(B\setminus\bigcup F)$ is infinite. Thus, by maximality of
$\mathcal{F}$, $\omega\setminus A\in\mathcal{F}$, which implies that
$x\subseteq^{*}\omega\setminus A$ and so $A\subseteq^{*}\omega\setminus x$. ∎

This completes the proof of the Lemma. ∎

######  Theorem 3.4.

Assume $GCH$. Let $C$ be a set of uncountable cardinals and let $\kappa$ be a
regular uncountable cardinal such that $\sup C\leq\kappa$. Then there is a
$ccc$ generic extension in which

$C\subseteq{\rm spec}(\mathfrak{s}_{mm}).$

###### Proof.

Add $\kappa$ Cohen reals to the ground model $V$ to obtain a model of
$\mathfrak{c}=\kappa$ and for each $\lambda\in C$ let $\mathscr{I}_{\lambda}$
be an ideal independent family of cardinality $\lambda$. Let
$\langle\lambda_{\beta}:\beta<\gamma\rangle$ be an enumeration of $C$. Proceed
with a finite support iteration
$\langle\mathbb{P}_{\alpha},\dot{\mathbb{Q}}_{\alpha}:\alpha<\omega_{1}\rangle$
where each iterand is a finite support iteration of length, the cardinality of
$C$, as follows:

Let $\mathbb{P}_{0}$ be the finite support iteration
$\langle\mathbb{R}_{\beta}^{0},\dot{\mathbb{S}}_{\beta}^{0}:\beta<\gamma\rangle$
defined by $\mathbb{R}_{0}^{0}=\mathbb{P}(\mathscr{I}_{\lambda_{0}})$ and
$\mathbb{R}_{\beta}^{0}\Vdash\dot{\mathbb{S}}_{\beta}^{0}=\mathbb{P}(\mathscr{I}_{\lambda_{\beta}})$.
After forcing with $\mathbb{P}_{0}$, for each $\beta<\gamma$, define
$\mathscr{I}_{\beta}^{0}=\mathscr{I}_{\lambda_{\beta}}\cup\\{x_{\beta}\\}$,
where $x_{\beta}$ is the real from Lemma 3.1 added by the $\beta$-step of the
iteration $\mathbb{P}_{0}$. Now, assume $\mathbb{P}_{\beta}$ and
$\\{\mathscr{I}_{\alpha}^{\beta}:\alpha<\gamma\\}$ are defined. The next step
$\dot{\mathbb{Q}}_{\beta}$ is the finite support iteration
$\langle\mathbb{R}_{\alpha}^{\beta},\dot{\mathbb{S}}_{\alpha}^{\beta}:\alpha<\gamma\rangle$
such that $\mathbb{R}_{0}^{\beta}=\mathbb{P}(\mathscr{I}_{0}^{\beta})$ and
$\mathbb{R}_{\alpha}^{\beta}\Vdash\dot{\mathbb{S}}_{\alpha}^{\beta}=\mathbb{P}(\mathscr{I}_{\alpha}^{\beta})$.
In $V[G_{\beta+1}]$, after forcing with
$\mathbb{P}_{\beta}*\dot{\mathbb{Q}}_{\beta}$, define
$\mathscr{I}_{\alpha}^{\beta+1}=\mathscr{I}_{\alpha}^{\beta}\cup\\{x_{\beta}\\}$,
where $x_{\alpha}$ is the real from Lemma 3.1 added by the $\alpha$-step of
the iteration $\dot{\mathbb{Q}}_{\beta}$. If $\beta$ is a limit ordinal and
$\mathbb{P}_{\alpha}$, $\mathscr{I}_{\eta}^{\alpha}$ are defined for all
$\alpha<\beta$ and $\eta<\gamma$, let $\mathbb{P}_{\beta}$ be the finite
support iteration
$\langle\mathbb{P}_{\alpha},\dot{\mathbb{Q}}_{\alpha}:\alpha<\beta\rangle$ and
for $\eta<\gamma$,
$\mathscr{I}_{\eta}^{\beta}=\bigcup_{\alpha<\beta}\mathscr{I}_{\eta}^{\alpha}$.

Let $\mathbb{P}_{\omega_{1}}$ be the above iteration and for any
$\beta<\gamma$, let
$\mathscr{J}_{\beta}=\bigcup_{\alpha<\omega_{1}}\mathscr{I}_{\beta}^{\alpha}$.
Since any real $y$ in $V[G_{\omega_{1}}]$ is added in some intermediate
extension, we have that $y$ is an element of $\mathscr{J}_{\beta}$ or it can
not be added to $\mathscr{J}_{\beta}$. Then $\mathscr{J}_{\beta}$ is a maximal
ideal independent family, and since $\mathbb{P}_{\omega_{1}}$ preserves all
cardinals and we only added $\omega_{1}$ sets to the family
$\mathscr{I}_{\beta}$ to obtain $\mathscr{J}_{\beta}$, $\mathscr{J}_{\beta}$
has size $\lambda_{\beta}$. ∎

The cardinality of a maximal ideal independent family can have countable
cofinality, while the character of any ultrafilter is uncountable. The first
assertion follows from the previous theorem by taking
$\kappa>\aleph_{\omega}$. The second assertion can be found in [3].

##  4\. Forcing Invariant Maximal Ideal Independent Families

In the following, we construct a maximal ideal independent family with strong
combinatorial properties, which guarantee that its maximality is preserved by
a large number of forcing notions.

######  Definition 4.1.

Let $\mathscr{U}$ be an ultrafilter. A maximal ideal independent family
$\mathscr{I}$ is called $\mathscr{U}\hbox{-\em encompassing}$ if the following
conditions hold:

  1. (1)

$\mathscr{U}\cap\mathscr{I}=\emptyset$, i.e. $\mathscr{I}$ is contained in the
dual ideal of $\mathscr{U}$.

  2. (2)

For every $X\in\mathscr{U}$ the set of $A\in\mathscr{I}$ so that
$X\in\mathcal{F}(\mathscr{I},A)$ is co-countable.

######  Theorem 4.2.

Assume $\mathsf{CH}$. For any $p$-point $\mathscr{U}$ there is a
$\mathscr{U}$-encompassing maximal ideal independent family $\mathscr{I}$ such
that for all $A\in\mathscr{I}$, the corresponding completemented filter
$\mathcal{F}(\mathscr{I},A)$ is a $p$-point.

###### Proof.

Let $\mathscr{U}$ be a $p$-point and $\langle
Y_{\alpha}:\alpha\in\omega_{1}\rangle$ be an $\subseteq^{*}$-decreasing
sequence which generates the $p$-point $\mathscr{U}$. Let $\langle
X_{\alpha}:\alpha\in\omega_{1}\rangle$ be an enumeration of all the infinite
subsets of $\omega$. By recursion we construct a sequence
$\langle\mathscr{I}_{\alpha}:\alpha\in[\omega,\omega_{1})\rangle$ such that:

  1. (1)

For all $\alpha$, $\mathscr{I}_{\alpha}\subseteq\mathscr{U}^{*}$ is a
countable ideal independent family.

  2. (2)

For all $\alpha$, if $X_{\alpha}\notin\mathscr{I}_{\alpha+1}$ then
$\mathscr{I}_{\alpha+1}\cup\\{X_{\alpha}\\}$ is not an ideal independent
family.

  3. (3)

For all $\alpha$, $\mathscr{I}_{\alpha+1}=\mathscr{I}_{\alpha}$ or
$\mathscr{I}_{\alpha+1}=\mathscr{I}_{\alpha}\cup\\{A_{0}^{\alpha},A_{1}^{\alpha}\\}$
for some $A_{0}^{\alpha},A_{1}^{\alpha}\in\mathscr{U}^{*}$ and such that
$A_{0}^{\alpha}\setminus A_{1}^{\alpha},A_{1}^{\alpha}\setminus
A_{0}^{\alpha}\subseteq Y_{\alpha}$.

  4. (4)

If $\alpha$ is a limit ordinal, then
$\mathscr{I}_{\alpha}=\bigcup_{\beta<\alpha}\mathscr{I}_{\beta}$.

  5. (5)

If $A_{i}^{\alpha}\in\mathscr{I}$ is added in step $\alpha$ of the iteration,
$\langle\mathcal{P}^{\alpha,i}_{\beta}:\beta\in[\alpha+1,\omega_{1})\rangle$
is the enumeration of all partitions of $A^{\alpha}_{i}$, for $i\in 2$, and
for all $\alpha$ and $\beta>\alpha$, there are a finite
$F\subseteq[\beta\setminus\\{\alpha\\}]^{<\omega}$ and $k\in\omega$, such that
for any $i,j\in 2$, $A^{\alpha}_{i}\setminus\left(A_{j}^{\beta}\cup\bigcup
F\right)\setminus k$, either, is a partial selector of partition
$\mathcal{P}^{\alpha,i}_{\beta}$, or is contained in one element of the
partition $\mathcal{P}^{\alpha,i}_{\beta}$.

After the recursion we define
$\mathscr{I}=\bigcup_{\alpha<\omega_{1}}\mathscr{I}_{\alpha}$. Condition (1)
makes sure that $\mathscr{I}$ is an ideal independent family and (2) makes
sure that $\mathscr{I}$ is maximal. Condition (3) makes sure that
$\mathscr{I}$ is $\mathscr{U}$-encompassing. Condition (5) makes sure that the
filters $\mathcal{F}(\mathscr{I},A)$ are selective ultrafilters for all
$A\in\mathscr{I}$. We start by setting $\mathscr{I}_{\omega}=\langle
A_{n}:n\in\omega\rangle$ be a partition of $\omega$ into infinitely many
infinite sets, $A_{0}^{n}=A_{1}^{n}=A_{n}$ and
$\langle\mathcal{P}_{\beta}^{n,i}:\beta\in[\omega,\omega_{1})\rangle$ the
enumeration of all partitions of $A_{n}$. Assume $\mathscr{I}_{\alpha}$ has
been constructed. We take care of the set $X_{\alpha}$. If
$X_{\alpha}\in\mathscr{U}$, we just define
$\mathscr{I}_{\alpha+1}=\mathscr{I}_{\alpha}$, and condition (2) from
Definition 4.1 will make sure that $X_{\alpha}$ can not be added to the family
$\mathscr{I}$. If $X_{\alpha}$ is in the ideal generated by the family
$\mathscr{I}_{\alpha}$ we have nothing to do and we can define
$\mathscr{I}_{\alpha+1}=\mathscr{I}_{\alpha}$ again. Otherwise,
$X_{\alpha}\notin\mathscr{U}$ and $X_{\alpha}$ is positive relative to the
ideal generated by $\mathscr{I}_{\alpha}$. Let
$e_{\alpha}:\omega\to\mathscr{I}_{\alpha}$ be an enumeration of the elements
of $\mathscr{I}_{\alpha}$, and define $C_{0}=e_{\alpha}(0)$,
$C_{n+1}=e_{\alpha}(n+1)\setminus\bigcup_{i\leq n}e_{\alpha}(i)$. Now, if
there are $n\in\omega$ and finite
$F\subseteq\mathscr{I}_{\alpha}\setminus\\{e_{\alpha}(0),\ldots,e_{\alpha}(n)\\}$
such that $C_{n}\setminus X_{\alpha}\subseteq^{*}\bigcup F$ and $C_{n}\cap
X_{\alpha}$ is infinite, then we have $C_{n}\setminus\bigcup
F\subseteq^{*}C_{n}\cap X_{\alpha}\subseteq X_{\alpha}$, and we can define
again $\mathscr{I}_{\alpha+1}=\mathscr{I}_{\alpha}$. So let us assume that for
all $n\in\omega$, $C_{n}\setminus X_{\alpha}$ is finite or it is not covered
by any
$F\subseteq\mathscr{I}_{\alpha}\setminus\\{e_{\alpha}(0),\dots,e_{\alpha}(n)\\}$.
Since $e_{\alpha}(n)$ is not almost contained in the union of finitely many
elements from $\mathscr{I}_{\alpha}\setminus\\{e_{\alpha}(n)\\}$, and
$\mathscr{I}_{\alpha}\setminus\\{e_{\alpha}(n)\\}$ is countable, by recursion
we can construct an infinite set $B_{n}\subseteq e_{\alpha}(n)$, such that for
all $Z\in\mathscr{I}_{\alpha}$ different from $e_{\alpha}(n)$, we have $Z\cap
B_{n}=^{*}\emptyset$, and moreover, by going to a subset if necessary, $B_{n}$
is a partial selector of the partition $\mathcal{P}^{\gamma,i}_{\alpha}$ or is
completely contained in one element of the partition
$\mathcal{P}^{\gamma,i}_{\alpha}$, where $\gamma$ and $i$ are such that
$A_{i}^{\gamma}=e_{\alpha}(n)$. Also, since for all $n\in\omega$,
$C_{n}\notin\mathscr{U}$ and $\mathscr{U}$ is a $p$-point, there is
$A\in\mathscr{U}$ such that for all $n\in\omega$, $C_{n}\cap A$ is finite,
$X_{\alpha}\cap A=\emptyset$ and $A\subseteq Y_{\alpha}$. Let $W_{0},W_{1}$ be
infinite disjoint subsets of $A$ which are not in the ultrafilter
$\mathscr{U}$. Define $W$ as,

$W=\left(\bigcup_{n\in\omega}C_{n}\setminus B_{n}\right)\setminus A$

Finally, define $A_{i}^{\alpha}=W\cup W_{i}$, for $i\in 2$, and
$\mathscr{I}_{\alpha+1}=\mathscr{I}_{\alpha}\cup\\{A_{0}^{\alpha},A_{1}^{\alpha}\\}$.
Note that $X_{\alpha}\subseteq A_{i}^{\alpha}$, $A_{i}^{\alpha}\setminus
A_{1-i}^{\alpha}=W_{i}\subseteq Y_{\alpha}$. So we only have to prove that
$\mathscr{I}_{\alpha+1}$ is ideal independent, but this is clear from the
construction of $A_{0}^{\alpha}$ and $A_{1}^{\alpha}$. ∎

######  Theorem 4.3.

Let $\mathscr{U}$ be a $p$-point and let $\mathbb{P}$ be a proper,
$\omega^{\omega}$-bounding forcing notion which preserves $p$-points. Then
$\mathbb{P}$ preserves the maximality of any $\mathscr{U}$-encompassing
maximal ideal independent family $\mathscr{I}$ such that for all
$A\in\mathscr{I}$, the corresponding complemented filter
$\mathcal{F}(\mathscr{I},A)$ is a $p$-point.

Note that this theorem implies that under $\mathsf{CH}$, in the generic
extension by any proper $\omega^{\omega}$-bounding $p$-point preserving
forcing notion $\mathfrak{s}_{mm}$ is $\aleph_{1}$.

###### Proof.

Fix an ultrafilter $\mathscr{U}$, a $\mathscr{U}$-encompassing maximal ideal
independent family $\mathscr{I}$ with the property that all of the
complemented filters of $\mathscr{I}$ are $p$-points, and a proper,
$\omega^{\omega}$-bounding, $p$-point preserving forcing notion $\mathbb{P}$.
Let $p\in\mathbb{P}$ and let $\dot{X}$ be a name so that
$p\Vdash\dot{X}\in[\omega]^{\omega}$. We need to show that some $q\leq p$
forces that $\dot{X}$ cannot be added to $\mathscr{I}$ without destroying
ideal independence. More precisely, this means that we need to either find a
$q\leq p$ so that $q$ forces that $\dot{X}$ is in the ideal generated by
$\mathscr{I}$ or else find $q\leq p$ and an $A\in\mathscr{I}$ so that $q$
forces that $\dot{X}$ is in the complemented filter corresponding to $A$.

Thus suppose towards a contradiction that $p$ forces that $\dot{X}$ is neither
in the ideal generated by $\mathscr{I}$ nor in any filter
$\mathcal{F}(\mathscr{I},A)$ for any $A\in\mathscr{I}$. Note that this implies
in particular that $\dot{X}$ is not in $\mathscr{U}$ since if it were, then in
would be in some filter $\mathcal{F}(\mathscr{I},A)$ (in fact co-countably
many). Since $\mathbb{P}$ preserves $\mathscr{U}$ it follows that $p$ forces
that the complement of $\dot{X}$ is in $\mathscr{U}$ and therefore we can find
a $q\leq p$ and a $Z\in\mathscr{U}$ so that $q\Vdash\dot{X}\cap Z=\emptyset$.
Fix such a $q$ and $Z$. To complete the proof it suffices to therefore show
that some $r\leq q$ forces that $n\in\dot{X}$ for some $n\in Z$.

For any $u\in\mathbb{P}$ let
$X_{u}=\\{n\in\omega\;|\;u\nVdash\check{n}\notin\dot{X}\\}$ be the outer hull
of $\dot{X}$ with respect to $u$, i.e. the collection of $n<\omega$ forced to
be in $\dot{X}$ by some $u^{\prime}\leq u$. Note that
$u\Vdash\dot{X}\subseteq\check{X}_{u}$ for any $u\in\mathbb{P}$. It follows
that for any condition $u$ stronger than $p$, $X_{u}$ is not in the ideal
generated by $\mathscr{I}$. By the maximality of $\mathscr{I}$, moreover we
get that for every $r\leq q$ the set $X_{r}$ is in some complemented filter of
$\mathscr{I}$. Therefore to finish the proof it suffices to show that in fact
any such $X_{r}$ is actually in uncountably many such filters. This suffices
since if this is the case then in particular it applies to $X_{q}$ and, since,
by the definition of $\mathscr{U}$-encompassing, $Z$ is in
$\mathcal{F}(\mathscr{I},A)$ for co-countably many $A\in\mathscr{I}$ there is
some $A\in\mathscr{I}$ so that $Z\cap X_{q}\in\mathcal{F}(\mathscr{I},A)$ and
so $Z\cap X_{q}$ has infinite intersection. Thus, some $r\leq q$ forces that
$n\in\dot{X}$ for some (in fact infinitely many) $n\in Z$. Summing up, it
suffices to show the following claim.

######  Claim 4.4.

For any $u\in\mathbb{P}$ stronger than $p$ the set
$X_{u}\in\mathcal{F}(\mathscr{I},A)$ for uncountably many $A\in\mathscr{I}$.

Fix such a $u\in\mathbb{P}$ and suppose towards a contradiction that there
were only countably many $A\in\mathscr{I}$ with
$X_{u}\in\mathcal{F}(\mathscr{I},A)$. Let $M\prec H_{\theta}$ be a countable
model for $\theta$ sufficiently large with
$\mathbb{P},p,u,\mathscr{I},\mathscr{U}\in M$ containing every $A$ so that
$X_{u}\in\mathcal{F}(\mathscr{I},A)$. Enumerate $\mathscr{I}\cap M$ as
$\\{A_{i}\;|\;i<\omega\\}$. Since $p$, and hence $u$, forces that for each
$n<\omega$ the name $\dot{X}$ is not in $\mathcal{F}(\mathscr{I},A_{n})$, and
each one of such filters is a $p$-point by our assumption and hence an
ultrafilter preserved by $\mathbb{P}$, there is in $M$ a dense set of
conditions below $u$ forcing that $\dot{X}\cap
A_{n}\setminus\bigcup_{i<k_{n},i\neq n}A_{i}$ is finite for some
$k_{n}\in\omega$. Applying $\omega^{\omega}$-boundedness and properness we can
find in the ground model functions $f,g\in\omega^{\omega}$ and a condition
$r\leq u$ which is $(M,\mathbb{P})$-generic so that for each $n<\omega$ we
have

$r\Vdash\dot{X}\cap A_{n}\setminus\bigcup_{i<\check{f}(n),i\neq
n}A_{i}\subseteq\check{g}(n)$

In particular we get that $X_{r}\cap A_{n}\setminus\bigcup_{i<f(n),i\neq
n}A_{i}\subseteq g(n)$ and thus $X_{r}\notin\mathcal{F}(\mathscr{I},A_{n})$
for any $n<\omega$. But then, by applying the same argument to $r$ that we
applied to $u$, we get that $X_{r}$ is in some $\mathcal{F}(\mathscr{I},B)$
for some $B\in\mathscr{I}$ with $B\neq A_{n}$ for any $n<\omega$. This is a
contradiction however since $X_{r}\subseteq X_{u}$ and by definition of the
$A_{n}$’s $X_{u}\notin\mathcal{F}(\mathscr{I},B)$. This contradiction implies
that $X_{q}$ is in uncountably many complemented filters of $\mathscr{I}$ and
hence the proof is complete. ∎

As an straightforward corollary we obtain:

######  Corollary 4.5.

  1. (1)

$\mathfrak{s}_{mm}=\aleph_{1}$ in the Sacks model.

  2. (2)

$\mathfrak{s}_{mm}=\aleph_{1}$ in the Miller partition model and hence
$\mathfrak{s}_{mm}<\mathfrak{a}_{T}$ is consistent.

  3. (3)

$\mathfrak{s}_{mm}=\aleph_{1}$ in the $h$-perfect tree forcing model and hence
$\mathfrak{s}_{mm}<\hbox{non}(\mathcal{N})$ is consistent.

###### Proof.

For (1), it is a standard fact that the iterated Sacks forcing preserves
$p$-points and it is $\omega^{\omega}$-bounding. For (2), in [11], Miller has
constructed a forcing, known as Miller partition forcing, which makes the
cardinal invariant $\mathfrak{a}_{T}$ equal to $\aleph_{2}$, as recently shown
in [4] preserves $p$-points, and as shown in [14]) is
$\omega^{\omega}$-bounding. For (3) recall, that the $h$-perfect tree forcing
is proper, ${}^{\omega}\omega$-bounding, preserves $p$-points and that in the
$h$-perfect tree forcing model $\hbox{non}(\mathcal{N})=\aleph_{2}$, see [9,
Section2]. ∎

An alternation of Miller partition and $h$-perfect tree forcings will lead to
a model of
$\mathfrak{i}=\mathfrak{s}_{mm}<\hbox{non}(\mathcal{N})=\mathfrak{a}_{T}=\aleph_{2}$
(for the effect of the respective posets on $\mathfrak{i}$ see [4] and [15]).

######  Corollary 4.6.

$\mathfrak{s}_{mm}$ is independent of $\mathfrak{a}_{T}$

###### Proof.

In the Miller partition model, $\mathfrak{s}_{mm}<\mathfrak{a}_{T}$. On the
other hand, it is well known that $\mathfrak{a}_{T}<\mathfrak{u}$ holds in the
Random model and hence $\mathfrak{a}_{T}<\mathfrak{s}_{mm}$ holds in that
model as well. ∎

##  5\. Conclusion and Open Questions

The results of the current paper together with those of [5] give either a
$\mathsf{ZFC}$ relation, or establish the independence between
$\mathfrak{s}_{mm}$ and any other well studied cardinal characteristic, with
the exception of the almost disjointness number $\mathfrak{a}$. The following
remains open.

######  Question 5.1.

Is it consistent that $\mathfrak{s}_{mm}<\mathfrak{a}$?

The corresponding question for $\mathfrak{i}$, i.e. the consistency of
$\mathfrak{i}<\mathfrak{a}$ is one of the most interesting open problems in
cardinal characteristics of the continuum and many of the roadblocks towards
solving that problem are the same as trying to answer the question above. See
the appendix of [4] for an interesting discussion on Vaughan’s problem.

As noted in the introduction, Theorem 4.2 implies that $\mathfrak{s}_{mm}={\rm
max}\\{\mathfrak{d},\mathfrak{u}\\}$ in many standard forcing extensions.
However, this is not a $\mathsf{ZFC}$ equality as $\mathfrak{s}_{mm}>{\rm
max}\\{\mathfrak{d},\mathfrak{u}\\}$ holds in the Boolean ultrapower model,
see for example [2]. That model requires a measurable cardinal and increases
both $\mathfrak{u}$ and $\mathfrak{d}$. As a result the following two
questions remain very interesting:

######  Question 5.2.

Is ${\rm max}\\{\mathfrak{d},\mathfrak{u}\\}<\mathfrak{s}_{mm}$ consistent
with $\mathsf{ZFC}$?

######  Question 5.3.

If $\mathfrak{d}=\mathfrak{u}=\aleph_{1}$ does $\mathfrak{s}_{mm}=\aleph_{1}$?

The later question is an ideal independent version of Roitman’s problem.
Theorem 3.4 opens up the possibility of a maximal ideal independent families
of size $\aleph_{\omega}$. We can therefore ask:

######  Question 5.4.

Is it consistent that $\mathfrak{s}_{mm}=\aleph_{\omega}$? More generally can
$\mathfrak{s}_{mm}$ have countable cofinality?

Finally, we ask more generally about the spectrum of maximal ideal independent
families:

######  Question 5.5.

What $\mathsf{ZFC}$ restrictions are there on the set ${\rm
spec}(\mathfrak{s}_{mm})$? Can it be equal to any set of regular cardinals
which includes the continuum?

## References

  * [1] A. Blass, _Combinatorial cardinal characteristics of the continuum_ , in: Foreman M., Kanamori A. (eds) Handbook of Set Theory. Springer, Dordrecht (2010), 24–27.
  * [2] J. Brendle _Mad families and iteration theory_ , Contemp. Math., 302, 1–31, 2002.
  * [3] J. Brendle, S. Shelah _Ultrafilters on $\omega$ \- their ideals and their cardinal characteristic_, Trans. Amer. Math. Soc., 351 (7), 2643-2674, 1999.
  * [4] J. A. Cruz-Chapital, V. Fischer, O. Guzman, J. Supina _Partition forcing and maximal independent families_ , preprint, 2021.
  * [5] J. Cancino, O. Guzman, A. W. Miller _Ideal independent families and the ultrafilter number_ Journal of Symbolic Logic, 86 (1), 128–136, 2021.
  * [6] V. Fischer, D. C. Montoya _Higher independence_ Journal of Symbolic Logic, doi:10.1017/jsl.2022.33, 2022.
  * [7] V. Fischer, S. Shelah _The Spectrum of Independence_ Archive for Mathematical Logic 58 (7-8), 877-884, 2019.
  * [8] V. Fischer, S. Shelah _The Spectrum of Independence II_ , preprint, 2022,
http://www.logic.univie.ac.at/$\sim$vfischer/spectrum04.pdf

  * [9] M. Goldstern, H. Judah, S. Shelah _Strong measure zero sets without Cohen reals_ Journal of Symbolic Logic, 58 (4), 1323–1341, 1993.
  * [10] M. Hrusak _Almost disjoint families in topology_ In recent progress in general topology III, 601–638, 2014.
  * [11] A. Miller, _Covering $2^{\omega}$ with $\omega_{1}$ disjoint closed sets,_ In J. Barwise, H. J. Keisler, K. Kunen, editors, _The Kleene Symposium_ , Volume 101, _Stud. Logic Found. Math._ , 1980, pp. 415–421.
  * [12] H. Mildenberger, D. Raghavan, J. Steprans _Splitting families and complete separability_ Canad. Math. Bull., 57 (1), 119–124, 2014.
  * [13] S. Shelah, _$Con(\mathfrak{u} >\mathfrak{i})$,_ Arch. Math. Logic 31 (6), 1992, pp. 433–443.
  * [14] O. Spinas, _Partition numbers,_ Ann. Pure Appl. Logic 90 (1-3), 1997, pp. 243–262.
  * [15] C. Switzer _Selective independence and $h$-perfect tree forcing notions_ arXiv:2202.12046, 2022.


capbtabboxtable[][]

# Contrastive Decoding Improves Reasoning in Large Language Models

Sean O’Brien1,2∗ Mike Lewis2
1University of California, San Diego 2Meta AI
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We demonstrate that Contrastive Decoding – a simple, computationally light,
and training-free text generation method proposed by Li et al 2022 – achieves
large out-of-the-box improvements over greedy decoding on a variety of
reasoning tasks. Originally shown to improve the perceived quality of long-
form text generation, Contrastive Decoding searches for strings that maximize
a weighted difference in likelihood between strong and weak models. We show
that Contrastive Decoding leads LLaMA-65B to outperform LLaMA 2, GPT-3.5 and
PaLM 2-L on the HellaSwag commonsense reasoning benchmark, and to outperform
LLaMA 2, GPT-3.5 and PaLM-540B on the GSM8K math word reasoning benchmark, in
addition to improvements on a collection of other tasks. Analysis suggests
that Contrastive Decoding improves over existing methods by preventing some
abstract reasoning errors, as well as by avoiding simpler modes such as
copying sections of the input during chain-of-thought. Overall, Contrastive
Decoding outperforms nucleus sampling for long-form generation and greedy
decoding for reasoning tasks, making it a powerful general purpose method for
generating text from language models.

00footnotetext:  Work done as an AI resident at Meta.

Figure 1: Contrastive decoding improves reasoning across model scales and
reasoning tasks.

Figure 2: Contrastive scoring significantly improves performance on HellaSwag,
a standard commonsense reasoning benchmark.

##  1 Introduction

Text is generated from large language models (LLMs) in different ways for
different tasks. For open-ended text generation tasks, truncated sampling is
normally used, as the most likely strings under a model tend to be short and
uninteresting (Holtzman et al., 2020). For reasoning problems, greedy decoding
is normally preferred, to avoid risking sampling errors. This bifurcation is
undesirable; for example it increases the likelihood of reasoning errors
during open-ended generation.

We explore the use of Contrastive Decoding (Li et al., 2022) for solving
reasoning problems with LLMs. Contrastive Decoding (CD) searches for strings
that maximize a weighted difference in likelihood between a stronger _expert_
and a weaker _amateur_ model, and was shown to outperform existing methods for
open-ended text generation. It achieves this by avoiding undesirable modes of
the expert model’s distribution, such as short or generic strings, which tend
to be the most likely under any model, including the amateur.

We show that Contrastive Decoding outperforms greedy decoding on reasoning
problems. On GSM8K, a widely used benchmark consisting of grade-school word
math problems, contrastive decoding improves the performance of various LLaMA
models by up to 8 absolute percentage points. This result outperforms LLaMA 2,
which has 5 billion more parameters and is trained on 40% more data. On
HellaSwag, using the CD objective to rank answers leads LLaMA to outperform
all existing models except GPT-4. We find general improvement on arithmetic
reasoning and multiple-choice ranking tasks, including on models as large as
LLaMA-65B, suggesting that Contrastive Decoding could bring such widespread
improvements to much larger models.

We also analyze the cause of the improvement from Constrastive Decoding.
Empirically, we find that Contrastive Decoding performs less surface-level
copying from the prompt than greedy decoding and misses fewer reasoning steps.
This result suggests that, similarly to findings in Li et al. (2022),
Contrastive Decoding works by reducing repetitive or other undesirable modes
of the model distribution. Our current method yields mixed results for
commonsense reasoning tasks and slightly degrades factual retrieval, both
trends that encourage further refinement of the method.

Overall, we show that Contrastive Decoding not only substantially improves LLM
accuracies on a range of benchmarks, but is also the first generation
algorithm to achieve state-of-the-art results in both reasoning and text
generation problems. These results allow a more unified method for improving
generation from language models across tasks.

Figure 3: CD accentuates what the expert model has learned that the amateur
model has not. Results are taken from greedy decoding with a 65B parameter
expert, using $\alpha=0.1$, $\beta=0.5$ for CD.

##  2 Contrastive Decoding

###  2.1 Simplified Formulation

The original Contrastive Decoding formulation from Li et al. (2022) explicitly
chooses two parameters: $\alpha$ and the intermediate temperature of the
amateur distribution $\tau_{a}$, with the intermediate temperature of the
expert fixed at $\tau_{e}=1$. We slightly refactor the hyperparameter choice
to be more interpretable and simplify the algorithm by working directly in
logit space.

Let $s_{a}^{(i)}$ and $s_{e}^{(i)}$ be the unnormalized scores (logits)
assigned to token $i$ by the amateur and expert models, respectively. $\alpha$
is the same hyperparameter in the original paper: a proportion of the maximum
probability assigned by the expert model, with any tokens assigned a lower
probability masked out. $\beta$ is a hyperparameter corresponding to the
strength of the amateur penalty. We include a leading $(1+\beta)$ coefficient
to the expert logits to decouple the strength of the contrastive penalty from
the expected scale of the output logits, cleanly delineating between the
contrastive tradeoff and the final sampling temperature. This matches the
formulation of DExperts (Liu et al., 2021), with the expert model serving both
as the base prior and steering expert.

1. Determine $\alpha$-mask. $V_{valid}=\\{j\in V,s_{e}^{(j)}\geq\log\alpha+\max_{k\in V}s_{e}^{(k)}\\}$ 2. Subtract amateur logits. $s_{CD}^{(i)}=\begin{cases}(1+\beta)s_{e}^{(i)}-\beta s_{a}^{(i)}&i\in V_{valid}\\\ -\infty&i\not\in V_{valid}\end{cases}$

A PyTorch implementation for this formulation, as well as the original, can be
found in subsection A.1 of the appendix. Our implementation takes three lines
of readable code.

###  2.2 Probabilistic Interpretation

Our implementation of $\alpha$-masking has the same interpretation as in Li et
al. (2022), given that the expert temperature is fixed to $\tau_{e}=1$. We
show the equivalence in Appendix A.2.

Further, we can consider the post-softmax probabilities produced by CD as a
perturbation of the probabilities predicted by the expert model. Not including
$\alpha$-masking, the probability assigned to token $i$ by CD is a normalized
adjustment of the probability assigned by the expert model:

$p_{CD}^{(i)}\propto
p_{e}^{(i)}\left(\frac{p_{e}^{(i)}}{p_{a}^{(i)}}\right)^{\beta}$ (1)

It is therefore clear that as $\beta\to 0$ the contrastive penalty disappears,
and as $\beta\to\infty$ the distribution collapses to the argmax of
$p_{e}^{(i)}/p_{a}^{(i)}$, which is the original formulation from Li et al.
(2022).

##  3 Experiments

###  3.1 Experimental Setup

Models. We use untuned models from the LLaMA 1 family (Touvron et al., 2023)
at all scales. Unless otherwise stated, we use an untuned LLaMA-65B as the
expert and an untuned, LLaMA-architecture model with 1.5B parameters trained
on the same data as the other LLaMA 1 models as an amateur. For one ablation
study, we use models from the FLAN-T5 family (Chung et al., 2022).

Decoding Parameters. We set $\beta=0.5$ and $\alpha=0.1$ for all experiments
unless otherwise stated. We use greedy decoding, except for self-consistency
experiments for which we sample at $\tau=0.7$ following Touvron et al. (2023).

Prompting. For generation tasks, we use 8-shot chain-of-thought prompting, in
line with Touvron et al. (2023). The examples are the same as in LLaMA for
tasks contained in that paper, and taken from Wei et al. (2023) for other
mathematical tasks.

Datasets. Following prior works, we evaluate on a number of datasets. The
following tasks measure performance on algebraic word problems: AQuA (Ling et
al., 2017), ASDiv (Miao et al., 2021), GSM8K (Cobbe et al., 2021), and SVAMP
(Patel et al., 2021). We also evaluate on MATH (Hendrycks et al., 2021b), a
larger and more challenging benchmark.

For commonsense reasoning, we measure open-ended performance on CommonsenseQA
(Talmor et al., 2019) and StrategyQA (Geva et al., 2021). We also evaluate on
a battery of multiple-choice reasoning benchmarks: both the easy and challenge
splits of the AI2 Reasoning Challenge dataset (Clark et al., 2018), BoolQ
(Clark et al., 2019), HellaSwag (Zellers et al., 2019), MMLU (Hendrycks et
al., 2021a), PIQA (Bisk et al., 2019), SIQA (Sap et al., 2019), and WinoGrande
(Sakaguchi et al., 2019).

###  3.2 Hyperparameter Selection

Contrastive decoding has three major hyperparameters: the masking ratio
$\alpha$, the contrastive strength $\beta$ and the size of the amateur model.
We find that results are fairly insensitive to $\alpha$ as long as $\beta$ is
reasonably small (below 1); unless otherwise stated we use $\alpha=0.1$ across
experiments.

Next we consider the size of the amateur model. In agreement with Li et al.
(2022), we find that performance benefits from smaller amateur models ( Figure
5); while a 1B-parameter amateur helps reasoning performance, a 7B-parameter
amateur harms it. We also examine different types of amateurs; ablation
studies show that a partially-trained amateur performs better than a fully-
trained one, and that a poorly-prompted expert can be successfully used as an
amateur as well (see subsection 4.2).

Finally, we examine the effect of $\beta$. The optimal value depends on the
task, but for both generation tasks like GSM8K and multiple-choice ranking
tasks like PIQA we find that $\beta=0.5$ performs well. Setting $\beta$ too
high can place too much weight in the contrastive penalty and harm
performance, especially with a larger gap between amateur and expert models.
$\beta=0$ corresponds to standard greedy decoding with no contrastive penalty.
Results of $\beta$ hyperparameter sweeps can be found in Table 5, Figure 5,
Figure 6 and Appendix B.

The best result on GSM8K, with LLaMA-65B and $\beta=0.25$, is 57.7 (Table 5),
outperforming PaLM-540B (56.5), LLaMA-2 (56.8) and GPT-3.5 (57.1).***OpenAI
(2023) evaluates GPT-3.5 5-shot; all others are 8-shot. (Anil et al., 2023;
OpenAI, 2023)

[0.45] Expert $\beta=0$ $\beta=0.25$ $\beta=0.5$ $\beta=1$ 7B 10.7 11.5 13.6
11.0 13B 17.0 21.0 22.9 20.4 30B 35.2 40.0 43.4 42.0 65B 51.0 57.7 56.8 44.6

Figure 4: Results on GSM8K with LLaMA-65B as the expert. While a 7B amateur
harms performance, a 1.5B amateur helps.  Figure 5: Results on GSM8K.
$\beta=0.5$ tends to give good results across expert sizes.

(a)

(b)

Figure 6: Two examples of sweeping through $\beta$ values on multiple-choice
reasoning tasks across model scales. Dashed horizontal lines mark performance
without contrastive decoding.

###  3.3 Arithmetic Reasoning

We find that contrastive decoding tends to help on arithmetic reasoning tasks
with chain-of-thought prompting; see Table 1 for all results. One exception to
this is the MATH dataset, which proves to be challenging for both standard and
contrastive decoding. We conjecture that because contrastive decoding
amplifies skills that the expert has learned better than the amateur, it
cannot help on tasks that are well beyond the expert’s ability.

We also experiment with normalizing the $\alpha$-masked CD scores via softmax,
then temperature sampling from the resulting distribution. This permits CD to
generate multiple candidate reasoning chains to be used for self-consistency
(taking the majority answer) (Wang et al., 2023b). We show across both
mathematical and commonsense reasoning, CD improves self-consistency
performance.

Model | CD | AQuA | ASDiv | GSM8K | MATH | SVAMP | Average
---|---|---|---|---|---|---|---
7B | ✗ | 21.0∗ | 40.2 | 10.7 | 3.0 | 27.3 | 20.4
13B | ✗ | 18.1∗ | 49.0 | 17.4 | 4.2 | 39.4 | 25.6
30B | ✗ | 23.8 | 60.1 | 35.3 | 6.9 | 55.9 | 36.4
65B | ✗ | 33.3 | 67.2 | 51.0 | 10.6 | 69.1 | 46.2
65B maj@20 | ✗ | 38.2 | 73.6 | 68.0 | –† | 77.3 | 64.3
7B | ✓ | 19.0∗ (-2.0) | 39.7 (-0.5) | 14.3 (+3.6) | 2.9 (-0.1) | 31.5 (+4.2) | 21.5 (+1.1)
13B | ✓ | 16.0∗ (-2.1) | 52.0 (+3.0) | 22.7 (+5.5) | 3.8 (-0.4) | 43.1 (+3.7) | 27.5 (+1.9)
30B | ✓ | 29.8 (+6.0) | 62.5 (+2.4) | 43.1 (+8.1) | 8.1 (+1.2) | 59.3 (+3.4) | 40.6 (+4.2)
65B | ✓ | 36.9 (+3.6) | 71.9 (+4.7) | 56.8 (+5.8) | 10.3 (-0.3) | 67.8 (-1.3) | 48.7 (+2.5)
65B maj@20 | ✓ |  39.4 (+1.2) |  77.4 (+3.8) |  74.0 (+6.0) | –† |  79.0 (+1.7) |  67.5 (+3.2)

Table 1: Results on math generation tasks. Contrastive decoding generally
improves performance.

###  3.4 Commonsense Reasoning

Results are more mixed for CommonsenseQA and StrategyQA. For both of these
tasks, we 8-shot prompt our model and compute the exact match score against
the ground-truth answers. We find that contrastive decoding harms performance
for smaller models, but that this harm equalizes somewhat for the 65B model
and evens out when using self-consistency. See Table 2 for full results.

Model | CD | CSQA | StrategyQA | Average
---|---|---|---|---
7B | ✗ | 40.0 | 59.2 | 49.6
13B | ✗ | 60.4 | 64.5 | 62.5
30B | ✗ | 66.4 | 68.7 | 67.6
65B | ✗ | 77.5 | 69.5 | 73.5
65B maj@20 | ✗ | 77.0 | 79.3 | 78.2
7B | ✓ | 37.3 (-2.7) | 58.3 (-0.9) | 47.8 (-1.8)
13B | ✓ | 58.5 (-1.9) | 65.5 (+1.0) | 62.0 (-0.5)
30B | ✓ | 62.8 (-3.6) | 67.6 (-1.1) | 65.2 (-2.4)
65B | ✓ | 77.1 (-0.4) | 71.5 (+2.0) | 74.3 (+0.8)
65B maj@20 | ✓ |  77.9 (+0.9) |  79.3 (+0.0) |  78.6 (+0.4)

Table 2: CD harms commonsense reasoning with a smaller expert, but performance
evens out with a larger expert-amateur gap. 11footnotetext: In the AQuA task,
the model selects one out of five given options. Thus the random baseline is
$20\%$, and results below that threshold are not meaningful.22footnotetext:
Given the size of the dataset and length of generations, we do not evaluate
maj @ 20 on MATH.

###  3.5 Contrastive Ranking

We further evaluate a contrastive objective as a scoring function to rank
answers to multiple-choice questions. These tasks are zero-shot, multiple-
choice cloze tasks; instead of open-ended generation the model scores each
potential completion, length-normalizing following Touvron et al. (2023). We
find comparable performance across most tasks, with more substantive gains on
HellaSwag and ARC-Challenge. Notably, on HellaSwag CD leads LLaMA-65B to score
88.0, which outperforms LLaMA-2 (85.3), GPT-3.5 (85.5) (OpenAI, 2023) and PALM
2-Large (86.8) (Anil et al., 2023).

$\beta$ | ARC-E | ARC-C | BoolQ | HSwag | PIQA | SIQA | WGrande | MMLU | Avg
---|---|---|---|---|---|---|---|---|---
0.0 | 79.1 | 56.1 | 84.2 | 84.2 | 82.6 | 52.3 | 77.3 | 63.5 | 72.4
0.5 | 79.0 | 59.5 | 84.3 | 87.4 | 83.1 | 53.3 | 77.8 | 63.4 | 74.9
1.0 | 76.9 | 59.7 | 84.1 | 88.0 | 82.9 | 53.3 | 76.5 | 63.2 | 74.5

Table 3: Results on multiple-choice reasoning tasks. CD generally provides a
modest boost.

##  4 Additional Studies

###  4.1 Effects of Contrastive Decoding

CD is worse at arithmetic but better at logical reasoning. We conduct a manual
error analysis of 100 randomly selected examples from the GSM8K set between
continuations from greedy decoding and CD ($\beta=0.5,\alpha=0.1$). We follow
Wang et al. (2023a) and categorize wrong answers as primarily being due to an
arithmetic error, a missing step or a semantic misunderstanding. We add one
category of “degeneration,” chosen when the model lapses into excessive
repetition. Our small-scale analysis finds that CD makes more arithmetic
errors, but that this is offset by better semantic reasoning and fewer missing
steps (see Table 4).

CD | Arithmetic | Missing Step | Semantic | Degeneration | Total Errors
---|---|---|---|---|---
✗ | 4% | 22% | 24% | 4% | 54%
✓ | 8% | 20% | 21% | 3% | 52%

Table 4: Proportion of errors in of a set of 100 GSM8K questions. CD makes
more arithmetic errors, but omits fewer steps and avoids semantic
misunderstandings.

To further explore the claim that the benefit of CD does not stem from
arithmetic evaluation, we generate a toy dataset of 1,0000 multiplication and
subtraction equations with operands up to four digits and then 8-shot prompt
models to complete the expression, measuring exact match accuracy. We find
that CD does not improve performance on this task, and in fact may degrade it
slightly. Results are shown in Table 10.

| Standard | CD
---|---|---
Correct % | 44.6 | 51.1
Parseable % | 95.2 | 95.6
Average # chars | 215.2 | 217.2

Figure 7: High-level generation statistics from sampled generations on GSM8K.
Responses are similar lengths, despite the performance improvement from CD.

Figure 8: CD reduces copying from the question in the generated Chain of
Thought, as measured by n-gram overlap on GSM8K generations.

CD reduces copying from the prompt. We analyze 26,000 sampled generations from
CD-sampling on GSM8K against the corresponding set from temperature sampling;
both of these sets of generations are used in our self-consistency study. We
find that responses are roughly the same length and follow the few-shot
template roughly the same proportion of the time. This rules out the
hypothesis that contrastive decoding simply leads the model to follow the
template better, prevents degeneration or induces longer answers with more
reasoning steps. Further, we run an automatic evaluation of greedy generations
using ROSCOE (Golovneva et al., 2022) but do not find significant differences
in any of these metrics. However, we measure the precision and recall of the
tokens in the prompt by the sampled generations and find that CD
systematically reduces token-level copying from the prompt. This may be
related to increased reasoning ability, as surface-level copying from the
prompt does not provide new information to the problem.

CD can harm factual recall. Our primary claim is that contrastive decoding
improves chain-of-thought reasoning. However, we also test CD on two pure
factual-recall tests that do not utilize chain-of-thought: OpenBookQA
(Mihaylov et al., 2018) and TriviaQA (Joshi et al., 2017). OpenBookQA
(“OBQA”), is a multiple-choice completion task, while TriviaQA is a 5-shot
generation task. Reusing the same setup from reasoning leads to a slight
degradation of performance, as seen in Table 10.

CD | OBQA | TriviaQA∗
---|---|---
✗ | 60.0 | 72.2
✓ | 57.8 (-2.4) | 69.9 (-2.1)

Figure 9: CD can harm performance on factual recall tasks.

CD | 7B | 13B | 30B | 65B
---|---|---|---|---
✗ | 31.0 | 36.3 | 52.3 | 58.4
✓ | 30.9 | 35.6 | 52.2 | 57.6

Figure 10: CD slightly harms performance on a synthetic task of evaluating
arithmetic expressions.

CD outperforms other reasoning enhancements in FLOP efficiency. We note that
contrastive decoding introduces relatively little overhead in comparison to
other reasoning-enhancing methods. We estimate that with a 1.5B amateur and
65.2B expert, contrastive decoding increases the total number of FLOPs by
$3.25\%$ (see section C of the appendix). This compares favorably to self-
consistency, which requires several extra full generation loops. We show in
Figure 6 that CD is significantly more efficient than self-consistency.

11footnotetext: On manual examination, we find the set of correct answers
provided by TriviaQA to be insufficient. Randomly sampling 100 supposedly
incorrect answers generated by CD and standard decoding, we find roughly half
are in fact correct (46/100 with CD and 49/100 without). A rough linear
extrapolation gives us estimates for non-CD and CD scores of 85.8 and 83.7,
respectively.

###  4.2 Ablation Studies

$\alpha$-masking alone is not enough. When sampling and performing self-
consistency, $\alpha$-masking prevents the sampling of tokens the expert finds
to be unlikely. It is natural to ask what portion of the benefit comes purely
from $\alpha$-masking and not the contrastive objective itself.

To answer this, we set $\beta=0$ but $\alpha=0.1$; that is, we mask out
candidates based on the expert but do not apply the contrastive objective.
When sampling one path, we expect $\alpha$-masking to improve over temperature
sampling alone as it eliminates unlikely results and thus provides a closer
approximation to greedy sampling. This holds, but as we increase the number of
paths we find no benefit from $\alpha$-masking alone. This suggests that the
contrastive objective, and not $\alpha$-masking, is the primary source of
improved self-consistency results. See Figure 12 for results of this ablation.

Figure 11: GSM8K scores via temperature sampling and maj @ $k$ with various
values of $k$. $\alpha$-masking alone does not yield significant improvement,
while full CD does.

Figure 12: Comparison of GSM8K scores with LLaMA-65B, both with and without
chain-of-thought prompts. CD only helps when using CoT.

CD requires chain-of-thought prompting to improve results. We next study
whether contrastive decoding provides an advantage in the absence of chain-of-
thought prompting. We remove the chains of thought from the GSM8K fewshot
prompt, and find that as expected performance drops for both standard and
contrastive decoding (Figure 12); further, without chains of thought
contrastive decoding provides no consistent improvement. As with the MATH
dataset, solving problems without explicit reasoning steps may be too
challenging of a task for the expert model, and thus leave too small a gap
between the expert and amateur to contrastively exploit.

CD can benefit non-LLaMA models. We conduct a short study to show that CD can
benefit models outside of the LLaMA family. For this study, we choose the
FLAN-T5 family as it is open-source, has a wide range of model sizes that
share a single tokenizer, and obtains good performance on chain-of-thought
reasoning tasks. We use FLAN-T5-XXL (11B) as the expert model and
FLAN-T5-Small (80M) as amateur. We evaluate on GSM8K using the 8-shot random
prompts from Fu et al. (2023); note that GSM8K is within the set of tasks that
FLAN-T5 is finetuned on. CD provides a slight boost in performance, as seen in
Table 6. We leave more extensive experiments on other families of models to
future work.

Table 5: FLOP increases, with increasing compute from using more samples for
self-consistency. CD achieves similar or better performance with a smaller
increase in FLOPs.

CD | $\beta$ | GSM8K
---|---|---
✗ | 0 | 16.4
✓ | 0.5 | 17.1
✓ | 1.0 | 17.4

Table 6: FLAN-T5 performance on GSM8K. CD provides a boost to performance.

Small-scale amateurs beat “negative prompting.” We experiment to determine if
there is a more effective weak amateur model to use for contrastive decoding.
We define a set of “negative prompts” by sampling 7B model outputs on the
fewshot prompts and collecting the incorrect responses. We use these responses
as fewshot prompts to mimic the failure modes of the family of models. These
negative prompts should harm the performance of models they are prompted with,
and specifically bias results towards the error distribution of the 65B model.

We find that contrasting with a negative prompt does not harm performance, but
does not improve it as much as contrasting with a small amateur (see Table 8).
In an ablation study, we find that negative prompting does not harm
performance that much; prompting a 65B model with incorrect fewshot examples
on GSM8K gives a score of 41.3, which underperforms prompting with correct
examples (51.2) but significantly beats non-chain-of-thought prompting (13.5).
This supports Wang et al. (2023a), who find that even incorrect chain-of-
thought rationales improve reasoning. A prompting strategy which better
incapacitates the expert model might yield better results.

Mid-training checkpoints make for good amateurs. We experiment with
checkpoints of a mid-training 7B-parameter LLaMA model taken 10% and 23% of
the way through the full training run. Even while a fully-trained 7B amateur
harms performance on GSM8K, we find that a partially-trained amateur improves
performance. We do not perform extensive hyperparameter sweeps here, instead
reusing $\alpha=0.1$, $\beta=0.5$ as before. We do not pursue partially-
trained amateurs for our main results as results may vary based on the order
of training data, but this result allows us to interpret contrastive decoding
as a first-order optimization step over the output of a model, highlighting
the high-level behaviors that it learns later on in the course of training.
See Table 8 for full results.

Expert | Greedy | NP | CD | CD + NP
---|---|---|---|---
7B | 10.7 | 11.4 | 14.3 | 12.7
13B | 17.4 | 17.5 | 22.7 | 20.7
30B | 35.3 | 36.9 | 43.1 | 42.9
65B | 51.0 | 52.0 | 56.8 | 54.7

Table 7: On GSM8K, negative prompting outperforms greedy decoding but weakens
CD.

Amateur | Amateur Tokens | GSM8K
---|---|---
7B | 130B | 57.0
7B | 300B | 56.8
7B | 1.3T | 49.9

Table 8: Early-training checkpoints can be good amateurs, even when late-stage
checkpoints harm performance.

##  5 Related Work

Steering methods for reasoning. Other works more explicitly model the error
distribution of reasoning steps and use this to steer decoding. For example
GRACE (Khalifa et al., 2023) uses a contrastive loss to train an external
step-level discriminator, which it then uses to select between candidate steps
sampled from a base model. Using the interpretation of contrastive decoding as
mutual distinguishability between amateur and expert, we see that our method
is close to FUDGE (Yang & Klein, 2021) where the binary predictor is an
estimate of the probability that the generated token has come from the expert
rather than the amateur.

Prompting Methods for Reasoning. There are many recent prompting methods to
improve language model reasoning; see Qiao et al. (2023) for a survey. We
perform our experiments with chain-of-thought prompting (Wei et al., 2023).

Sampling methods Several decoding methods exist to improve the quality of
generations from large language models. For open-ended generation, truncated
sampling schemes like top-$k$ sampling (Fan et al., 2018), nucleus sampling
(Holtzman et al., 2020) and typical sampling (Meister et al., 2023) have been
shown to reduce repetition in comparison to greedy decoding and beam search
while producing more coherent generations than standard temperature sampling.
However, sampling can still introduce errors into logical chains, and so
greedy decoding is used to more effectively solve reasoning tasks. (Wei et
al., 2023; Anil et al., 2023)

Contrastive Generation Methods. Our formulation’s objective can be interpreted
as a special case of DExperts (Liu et al., 2021), using the larger model as
both an expert and base LM prior. Yona et al. (2023) identify model biases
with Contrastive Input Decoding, a contrastive-decoding-style technique
similar to negative prompting that operates on perturbed text inputs.

Concurrently to our work, Chuang et al. (2023) propose DoLA, which improves
factuality and reasoning through contrastive decoding between the predictions
of later layers and earlier layers in a language model. We study a wider array
of reasoning tasks and demonstrate that a 7B amateur is too large, finding
greater gains in reasoning just by scaling down the amateur to 1.5B
parameters.

Our paper differentiates itself from Li et al. (2022), which initially
proposed Contrastive Decoding, in several ways: by testing on standard
reasoning benchmarks, by our exploration of $\beta$ as a hyperparameter, by
ablations with various types of amateurs, and by a careful analysis of the
combination of Contrastive Decoding with chain-of-thought prompting and self-
consistency.

##  6 Limitations

Our investigation is also limited mainly to the LLaMA family of models. While
the method continues to provide benefit to larger LLaMA models, further work
is required to definitively establish the effect of contrastive decoding on
larger, tuned models.

##  7 Conclusion

Our study shows that contrastive decoding can improve chain-of-thought
reasoning in large language models. While challenges like factual recall
remain, this strengthens the case for contrastive decoding as a simple,
general-purpose method to elicit more desirable behavior from large language
models.

### Reproducibility Statement

The training process and model architecture for the 1.5B-parameter LLaMA model
used as the amateur in several results is publicly available, but the weights
are not, which limits public reproducibility of results relying on that model.
The results on FLAN-T5, as well as the negative-prompting study and
examination of 7B-LLaMA as an amateur, are all built on entirely open-source
models and data.

## References

  * Anil et al. (2023) Rohan Anil, Andrew M. Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, and Zhifeng Chen et al.  Palm 2 technical report, 2023.
  * Bisk et al. (2019) Yonatan Bisk, Rowan Zellers, Ronan Le Bras, Jianfeng Gao, and Yejin Choi.  Piqa: Reasoning about physical commonsense in natural language, 2019.
  * Chuang et al. (2023) Yung-Sung Chuang, Yujia Xie, Hongyin Luo, Yoon Kim, James Glass, and Pengcheng He.  Dola: Decoding by contrasting layers improves factuality in large language models, 2023.
  * Chung et al. (2022) Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Alex Castro-Ros, Marie Pellat, Kevin Robinson, Dasha Valter, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Zhao, Yanping Huang, Andrew Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei.  Scaling instruction-finetuned language models, 2022.
  * Clark et al. (2019) Christopher Clark, Kenton Lee, Ming-Wei Chang, Tom Kwiatkowski, Michael Collins, and Kristina Toutanova.  Boolq: Exploring the surprising difficulty of natural yes/no questions, 2019.
  * Clark et al. (2018) Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord.  Think you have solved question answering? try arc, the ai2 reasoning challenge, 2018.
  * Cobbe et al. (2021) Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman.  Training verifiers to solve math word problems, 2021.
  * Fan et al. (2018) Angela Fan, Mike Lewis, and Yann Dauphin.  Hierarchical neural story generation, 2018.
  * Fu et al. (2023) Yao Fu, Litu Ou, Mingyu Chen, Yuhao Wan, Hao Peng, and Tushar Khot.  Chain-of-thought hub: A continuous effort to measure large language models’ reasoning performance, 2023.
  * Geva et al. (2021) 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, 2021.
  * Golovneva et al. (2022) Olga Golovneva, Moya Chen, Spencer Poff, Martin Corredor, Luke Zettlemoyer, Maryam Fazel-Zarandi, and Asli Celikyilmaz.  Roscoe: A suite of metrics for scoring step-by-step reasoning, 2022.
  * Hendrycks et al. (2021a) Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt.  Measuring massive multitask language understanding, 2021a.
  * Hendrycks et al. (2021b) Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt.  Measuring mathematical problem solving with the math dataset, 2021b.
  * Holtzman et al. (2020) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi.  The curious case of neural text degeneration, 2020.
  * Joshi et al. (2017) Mandar Joshi, Eunsol Choi, Daniel S. Weld, and Luke Zettlemoyer.  Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension, 2017.
  * Kaplan et al. (2020) 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.
  * Khalifa et al. (2023) Muhammad Khalifa, Lajanugen Logeswaran, Moontae Lee, Honglak Lee, and Lu Wang.  Discriminator-guided multi-step reasoning with language models, 2023.
  * Li et al. (2022) Xiang Lisa Li, Ari Holtzman, Daniel Fried, Percy Liang, Jason Eisner, Tatsunori Hashimoto, Luke Zettlemoyer, and Mike Lewis.  Contrastive decoding: Open-ended text generation as optimization, 2022.
  * Ling et al. (2017) Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom.  Program induction by rationale generation: Learning to solve and explain algebraic word problems.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 158–167, Vancouver, Canada, July 2017. Association for Computational Linguistics.  doi: 10.18653/v1/P17-1015.
  * Liu et al. (2021) Alisa Liu, Maarten Sap, Ximing Lu, Swabha Swayamdipta, Chandra Bhagavatula, Noah A. Smith, and Yejin Choi.  Dexperts: Decoding-time controlled text generation with experts and anti-experts, 2021.
  * Meister et al. (2023) Clara Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell.  Locally typical sampling, 2023.
  * Miao et al. (2021) Shen-Yun Miao, Chao-Chun Liang, and Keh-Yih Su.  A diverse corpus for evaluating and developing english math word problem solvers, 2021.
  * Mihaylov et al. (2018) Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal.  Can a suit of armor conduct electricity? a new dataset for open book question answering, 2018.
  * OpenAI (2023) OpenAI.  Gpt-4 technical report, 2023.
  * Patel et al. (2021) Arkil Patel, Satwik Bhattamishra, and Navin Goyal.  Are nlp models really able to solve simple math word problems?, 2021.
  * Qiao et al. (2023) Shuofei Qiao, Yixin Ou, Ningyu Zhang, Xiang Chen, Yunzhi Yao, Shumin Deng, Chuanqi Tan, Fei Huang, and Huajun Chen.  Reasoning with language model prompting: A survey, 2023.
  * Sakaguchi et al. (2019) Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi.  Winogrande: An adversarial winograd schema challenge at scale, 2019.
  * Sap et al. (2019) Maarten Sap, Hannah Rashkin, Derek Chen, Ronan LeBras, and Yejin Choi.  Socialiqa: Commonsense reasoning about social interactions, 2019.
  * Talmor et al. (2019) Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant.  Commonsenseqa: A question answering challenge targeting commonsense knowledge, 2019.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample.  Llama: Open and efficient foundation language models, 2023.
  * Wang et al. (2023a) Boshi Wang, Sewon Min, Xiang Deng, Jiaming Shen, You Wu, Luke Zettlemoyer, and Huan Sun.  Towards understanding chain-of-thought prompting: An empirical study of what matters, 2023a.
  * Wang et al. (2023b) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou.  Self-consistency improves chain of thought reasoning in language models, 2023b.
  * Wei et al. (2023) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou.  Chain-of-thought prompting elicits reasoning in large language models, 2023.
  * Yang & Klein (2021) Kevin Yang and Dan Klein.  FUDGE: Controlled text generation with future discriminators.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_. Association for Computational Linguistics, 2021.  doi: 10.18653/v1/2021.naacl-main.276.
  * Yona et al. (2023) Gal Yona, Or Honovich, Itay Laish, and Roee Aharoni.  Surfacing biases in large language models using contrastive input decoding, 2023.
  * Zellers et al. (2019) Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi.  Hellaswag: Can a machine really finish your sentence?, 2019.

##  Appendix A Appendix

###  A.1 Code Implementation

We include PyTorch implementations of contrastive decoding in Algorithm 1 and
Algorithm 2

# expert_logits - unnormalized scores from the expert model

# amateur_logits - unnormalized scores from the amateur model

# amateur_temp - temperature to normalize amateur distribution

# alpha - masking threshold

expert_probs = softmax(expert_logits, dim=-1)

amateur_probs = softmax(amateur_logits / amateur_temp, dim=-1)

cutoff = alpha*expert_probs.max(dim=-1, keepdim=True).values

diffs = log(expert_probs) - log(amateur_probs)

cd_logits = diffs.masked_fill(expert_probs < cutoff, -float(’inf’))

Algorithm 1 Original formulation

# expert_logits - unnormalized scores from the expert model

# amateur_logits - unnormalized scores from the amateur model

# alpha - masking threshold

# beta - expert-amateur tradeoff parameter

cutoff = log(alpha) + expert_logits.max(dim=-1, keepdim=True).values

diffs = (1 + beta)*expert_logits - beta*amateur_logits

cd_logits = diffs.masked_fill(expert_logits < cutoff, -float(’inf’))

Algorithm 2 Our formulation

###  A.2 Equivalence - Masking

For the sake of completeness, we show the equivalency between the two masking
schemes. We restrict our consideration to the generation of a single token.
Let

\- $V$ be the vocabulary size of each model

\- $\\{e_{i}\\}_{i=1}^{V}$ be the logits produced by the expert model

\- $\\{a_{i}\\}_{i=1}^{V}$ be the logits produced by the amateur model

\- $N_{e}$ and $N_{a}$ be the normalization terms of the softmax function; for
example, $N_{e}=\sum_{j=1}^{V}\exp(e_{i})$

The probability that the expert assigns to token $i$ after the softmax is by
definition $p_{e}(i)=\frac{\exp(s_{i})}{N_{e}}$

Now consider any token that is masked out. We have that
$p_{e}(i)<\alpha*p_{e}(i_{max})$, where $i_{max}$ is the the token that
maximizes $p_{e}$.

Because $e^{x}$ and $\log x$ are both strictly increasing functions, we
obtain:

$\displaystyle s_{i}-\log N_{e}$ $\displaystyle<\log\alpha+s_{max}-\log N_{e}$
$\displaystyle s_{i}$ $\displaystyle<\log\alpha+s_{max}$

These two conditions are equivalent, and so we can mask tokens by thresholding
their logits against $\log\alpha+s_{max}$.

Further, let us introduce an expert temperature parameter $\tau\in(0,\infty)$
that scales the logits arbitrarily. Then we obtain a new set of logits
$c_{i}=\frac{s_{i}}{\tau}$

By then substituting $\alpha_{\tau}=\alpha^{1/\tau}$, we obtain the same mask.
Thus the mask is a function that depends only on the quantity
$\tau\log\alpha$, or equivalently $\alpha\exp(\tau)$. As we later show, we can
fix $\tau=1$ by introducing a new hyperparameter $\beta$. So if we fix
$\tau=1$, then our mask depends solely on $\alpha$.

Letting $p_{e}^{(i)}$ correspond to the post-softmax probability that the
expert assigns to token $i$, we have shown that the valid set produced by our
method is the same as in the original:

$V_{valid}=\left\\{j\in V,p_{e}^{(j)}\geq\frac{1}{\alpha}\max_{k\in
V}p_{e}^{(k)}\right\\}$

###  A.3 Equivalence - Logit Combination

To be concise, first define $q(i)=\frac{p_{e}(i)}{p_{a}(i)}$ be the ratio of
the probability assigned by the expert model over the probability from the
amateur model, both on token $i$.

Further, let $s_{i}$ denote the value of the logit that CD assigns to token
$i$. Then

$\displaystyle s_{i}$ $\displaystyle=(1+\beta)\log p_{e}(i)-\beta\log
p_{a}(i)$ $\displaystyle\exp(s_{i})$ $\displaystyle=p_{e}(i)q(i)^{\beta}$
$\displaystyle p_{cd}(i)$ $\displaystyle\propto p_{e}(i)q(i)^{\beta}$

Expanding this, we obtain:

$p_{cd}(i)\propto\exp\left((1+\beta)e_{i}-\beta a_{i}\right)$

which is equivalent to simply linearly combining the expert and amateur
logits.

When we introduce temperatures, the equation becomes

$p_{cd}(i)\propto\exp\left(\frac{1+\beta}{\tau_{e}}e_{i}-\frac{\beta}{\tau_{a}}a_{i}\right)$
$\text{mask}(i)=f(\tau_{e}\log\alpha)$

When sampling, the temperature with which we sample from the CD logits is
introduced as $\tau_{out}$

$p_{cd}(i)\propto\exp\left(\frac{1}{\tau_{out}}\left(\frac{1+\beta}{\tau_{e}}e_{i}-\frac{\beta}{\tau_{a}}a_{i}\right)\right)$

These four parameters $\tau_{out}$, $\tau_{e}$, $\tau_{a}$ and $\beta$ combine
into only two coefficients – one for $e_{i}$ and one for $e_{i}$.

$p_{cd}(i)\propto\exp\left(\kappa_{e}e_{i}-\kappa_{a}a_{i}\right)$

We now fix $\tau_{a}$ and $\tau_{e}$ to 1. We can obtain almost the same range
of values with the $\tau_{out}$, $\beta$ formulation as with the $\kappa_{e}$,
$\kappa_{a}$ formulation. The only exception is the case for which
$\kappa_{e}=\kappa_{a}$, which we exclude after finding that weighing expert
and amateur equally gives worse results than downweighing the amateur. Despite
this exception, we prefer the $\beta,\tau_{out}$ formulation because it
decouples the scale of the final logits from the $\beta$ parameter: in
expectation $\beta$ does not scale the logits up or down, and so when sampling
$\tau$ will affect generation diversity and $\beta$ will affect the expert-
amateur tradeoff.

##  Appendix B Multiple-Choice Beta Sweep Results

Here we include the plots for all beta sweeps through the multiple-choice
tasks.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

##  Appendix C FLOP estimates

We follow Kaplan et al. (2020) and estimate the number of flops for one
forward pass of a Transformer model with $N$ non-embedding parameters as
roughly $2N$. For the purposes of this analysis, we drop the negligibly small
$2n_{layer}n_{ctx}d_{attn}$ term. This allows us to consider the cost of
generating one token to be constant regardless of the context length.

With this approximation, we find that contrastive decoding adds
$\frac{1.5}{65.2}\approx 2.30\%$ to the number of FLOPs per forward pass for a
65B expert model. To ensure a fair comparison, we also include the small
increase in generation lengths induced by CD (see Table 8), bringing its total
percent increase up to $3.25\%$.