We show that for $k \geq 5$, the PPSZ algorithm for $k$-SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every $k\geq 5$, there is a strictly increasing function $f: [0,1] \rightarrow \mathbb{R}$ with $f(0) = 0$ that has the following property. If $F$ is a $k$-CNF formula over $n$ variables and $|{\rm sat}(F)| = 2^{\delta n}$ solutions, then PPSZ finds a satisfying assignment with probability at least $2^{-c_k n -o(n) + f(\delta) n}$. Here, $2^{-c_k n - o(n)}$ is the success probability proved by Paturi, Pudlak, Saks, and Zane for $k$-CNF formulas with a unique satisfying assignment.

Our proof rests on a combinatorial lemma: given a set $S \subseteq \{0,1\}^n$, we can partition $\{0,1\}^n$ into subcubes such that each subcube $B$ contains exactly one element of $S$. Such a partition $\mathcal{B}$ induces a distribution on itself, via $\Pr[B] = |B| / 2^n$ for each $B \in \mathcal{B}$. We are interested in partitions that induce a distribution of high entropy. We show that, in a certain sense, the worst case ($\min_{S: |S| = s} \max_{\mathcal{B}} H(\mathcal{B})$) is achieved if $S$ is a Hamming ball. This lemma implies that every set $S$ of exponential size allows a partition of linear entropy. This in turn leads to an exponential improvement of the success probability of PPSZ.