  For several models of random constraint satisfaction problems, it was
conjectured by physicists and later proved that a sharp satisfiability
transition occurs. For random $k$-SAT and related models it happens at clause
density $\alpha$ around $2^k$. Just below the threshold, further results
suggest that the solution space has a "1RSB" structure of a large bounded
number of near-orthogonal clusters inside the space of variable assignments
$\{0,1\}^N$. In the unsatisfiable regime, it is natural to consider
max-satisfiability: violating the least number of constraints. For a simplified
variant, the strong refutation problem, there is strong evidence that an
algorithmic transition occurs around $\alpha = N^{k/2-1}$. For $\alpha$ bounded
in $N$, a very precise estimate of the max-sat value was obtained by
Achlioptas, Naor, and Peres (2007), but it is not sharp enough to indicate the
nature of the energy landscape. Later work (Sen, 2016; Panchenko, 2016) shows
that for $\alpha$ very large (roughly, above $64^k$) the max-sat value
approaches the mean-field (complete graph) limit: this is conjectured to have
an "FRSB" structure where near-optimal configurations form clusters within
clusters, in an ultrametric hierarchy of infinite depth inside $\{0,1\}^N$. A
stronger form of FRSB was shown in several recent works to have algorithmic
implications (again, in complete graphs). Consequently we find it of interest
to understand how the model transitions from 1RSB near the satisfiability
threshold, to (conjecturally) FRSB for large $\alpha$. In this paper we show
that in the random regular $k$-NAE-SAT model, the 1RSB description breaks down
already above $\alpha \asymp 4^k/k^3$. This is proved by an explicit
perturbation in the 2RSB parameter space, inspired by the "bug proliferation"
mechanism proposed by physicists (Montanari and Ricci-Tersenghi, 2003;
Krzakala, Pagnani, and Weigt, 2004).
