\section{The treewidth transition}\label{sec:treewidth}

Exact inference in graphical models is the computation of learning closest to \#SAT. It computes
partition functions for maximum-likelihood estimation, marginals for prediction, and minimum-energy
assignments for decoding. The textbook algorithms all take time exponential in the treewidth:
variable elimination, junction trees, recursive conditioning, and compilation into decision diagrams
or d-DNNF; for \#SAT see~\cite{SS10}.

Kwisthout, Bodlaender and van der Gaag~\cite{KB09,KBG10} derived from ETH, through the treewidth lower
bounds of Marx~\cite{Mar10}, that bounded treewidth is necessary for efficient inference. ETH is false, so
their quantitative bound has lost its proof. The qualitative statement survives. Chandrasekaran, Srebro
and Harsha~\cite{CSH08} show that no family of graphs of unbounded treewidth admits inference in time
polynomial in the treewidth unless NP has polynomial-size circuits, and the grid-minor bounds that they
assume are now theorems~\cite{CC16}. This section settles the quantitative question for Boolean models of
bounded degree and arity. Treewidth-based algorithms take time $2^{\Theta(\tw)}$. They are not optimal for
models whose size is close to their treewidth, where the truth is $2^{\tw/\polylog\tw}$ under $\lenETH{C}$.
They are optimal again for models that may be polynomially larger.

\subsection{Subexponential inference for bounded-degree models}\label{sec:inference}

\begin{restatable}[Inference]{theorem}{thminference}\label{thm:inference}
Let $\Phi$ be a factor graph on $n$ Boolean variables with nonempty scopes, arity at most $a$, size
$\|\Phi\|$, and $|\cF|$ factors.
\begin{enumerate}[label=(\alph*)]
\item If all tables have nonnegative integer entries below $2^b$, then $Z(\Phi)$ and, if $Z(\Phi)>0$, the
marginal $\Pr[x_i=1]$ for every $i$ can be computed exactly in time $\poly(|\Phi|)\cdot2^{O(s/\sqrt{\log
s})}$, where $s=\max\{4\|\Phi\|,\ n+b|\cF|+1,\ a^2\}$.
\item If the factors carry integer energies in $\{0,\dots,b'\}$, then the minimum total energy, a
minimizer, and the number of minimizers can be computed in time $\poly(|\Phi|)\cdot2^{O(s/\sqrt{\log
s})}$, where $s=\max\{4\|\Phi\|,\ n+1,\ b'|\cF|+1,\ a^2\}$.
\end{enumerate}
For constant degree, arity, $b$ and $b'$, all of these take time $2^{O(n/\sqrt{\log n})}$.
\end{restatable}

\begin{proof}[Proof sketch]
For (a), use the counting ring with $P=n+b|\cF|+1$, which exceeds the bit length of $Z(\Phi)$; a marginal
is a ratio of two partition functions. For (b), use the profile ring with table $V^{E_f}$ for the factor
$f$ with energy $E_f$, and recover a minimizer by self-reduction as in \cref{thm:erm}
(\cref{app:treewidth}).
\end{proof}

\subsection{Separation from elimination and compilation}\label{sec:separation}

Every bounded-degree expander has treewidth $\Theta(n)$~\cite{GM09}. On such graphs the classical exact
methods are exponentially slower than \cref{thm:inference}.

\begin{restatable}[Separation]{corollary}{corseparation}\label[corollary]{cor:separation}
Let $(G_n)$ be a family of $n$-vertex graphs of maximum degree $\Delta=O(1)$ with $\tw(G_n)=\Omega(n)$, for
example bounded-degree expanders. Let $\Phi_n$ be the hardcore model on $G_n$: one variable per vertex
and the factor $\ind[\neg(x_u\wedge x_v)]$ on every edge, so that $Z(\Phi_n)$ counts independent sets.
\begin{enumerate}[label=(\alph*)]
\item The partition function $Z(\Phi_n)$ and all marginals can be computed in time
$2^{O(n/\sqrt{\log n})}$.
\item Variable elimination along any order, and junction-tree propagation over any tree decomposition,
with explicitly stored tables, take time $2^{\Omega(n)}$.
\item Every structured DNNF that represents the CNF $\bigwedge_{uv\in E(G_n)}(\neg x_u\vee\neg x_v)$ has size
$2^{\Omega(n)}$~\cite{ACMS20}. This includes every structured d-DNNF and every OBDD.
\end{enumerate}
\end{restatable}

For suitable expanders of degree $3$, Bova, Capelli, Mengel and Slivovsky~\cite{BCMS14} prove that
\emph{every} DNNF for this CNF has size $2^{\Omega(n)}$. This covers decision-DNNF, which captures the traces of
DPLL-based exact model counters~\cite{BLRS13}.

Contraction along one tree decomposition is the standard way to evaluate tensor networks and weighted
model counts~\cite{MS08,KCMR19,DDV19}, and it costs $2^{\Theta(\tw)}$. The algorithm of \cref{thm:inference}
is a signed sum of tensor networks contracted in different orders~\cite{Cla26}, or a polynomial
interpolation~\cite{OAI26}. In either form it lies outside every model of computation that fixes one
elimination order or one vtree. The preprint~\cite{Cla26} already identifies its sums with partition
functions of pairwise Markov random fields with nonnegative weights. It also notes that expanders defeat
every fixed tree of cuts, and it places its algorithm outside the contraction-tree model of Austrin, Kaski
and Kubjas~\cite{AKK22}. The statements for marginals and minimum energy, the separation from structured
DNNF, and the lower bounds below are new.

On models whose size is close to their treewidth, \cref{thm:inference} is optimal up to polylogarithmic
factors in the exponent. The reason is that OR-chains (\cref{lem:chain} below) turn a CNF of length $L$
into a model with at most $4L$ variables and treewidth at most $L+2$.

\begin{restatable}[Inference is SAT by length]{corollary}{corinflen}\label[corollary]{cor:inflen}
Assume $\lenETH{C}$, and let $\theta>0$. No randomized algorithm with error probability at most $1/3$
decides whether the partition function of a $0/1$ factor graph of arity and degree at most $3$ is
positive in time $2^{\tw/(\log\tw)^{C+\theta}}\poly(n)$, or in time $2^{n/(\log n)^{C+\theta}}$. For $C<1$, no
algorithm runs in time $2^{O(\tw/\log\tw)}\poly(n)$.
\end{restatable}

So under $\lenETH{C}$ the exponent of exact inference on such models lies between $\tw/(\log\tw)^{C+o(1)}$ and
$O(n/\sqrt{\log n})$. The second statement answers, for Boolean models and under this hypothesis, whether
the $\tw/\log\tw$ of the ETH-based bound can be beaten: it cannot.

\subsection{Treewidth is necessary again for large models}\label{sec:inflower}

Treewidth algorithms are optimal again once the model may have many more variables than its
treewidth. Lokshtanov, Marx and Saurabh~\cite{LMS18tw} proved such bounds for graph problems from CNF-SAT
without sparsification. For Maximum Independent Set, which is MAP inference in the hardcore model, their
bound is $(2-\gamma)^{\tw}$. \Cref{thm:inflower} adds the counting version under \#CNF-SETH, for models of
bounded arity and degree given with a path decomposition. The reduction copies each variable along a
path. Every clause is then checked by a chain of local OR gates, while only the current copies stay in the
bag.

\begin{restatable}[OR-chains with copying]{lemma}{lemchain}\label[lemma]{lem:chain}
Given a CNF $F$ on $N$ variables with $M$ clauses of total length $L$, one can compute in polynomial
time a factor graph $\Phi_F$ with $0/1$ tables, arity and maximum degree at most $3$, and at most $N+3L$
variables, together with a path decomposition of width at most $N+2$, such that $Z(\Phi_F)=\#F$.
\end{restatable}

\begin{restatable}[Inference lower bound]{theorem}{thminflower}\label{thm:inflower}
Assume \cref{hyp:sharpcnfseth}. For every $\gamma>0$ there is $c$ such that no algorithm that is given a
$0/1$ factor graph of arity at most $3$ and degree at most $4$ with $n$ variables, together with a path
decomposition of width $t$, computes its partition function in time $O(2^{(1-\gamma)t})$, even when
$n\le5t^{c+1}$ and the treewidth is at least $\sqrt t/2$. Under \cref{hyp:cnfseth}, the same holds for
deciding whether the partition function is positive, and so for MAP inference.
\end{restatable}

\begin{proof}[Proof sketch]
Apply \cref{lem:chain} to a CNF with $N$ variables and at most $N^c$ clauses, after deleting tautological
clauses. Then add a disjoint $\lceil\sqrt N\rceil\times\lceil\sqrt N\rceil$ grid with the all-ones factor on
each edge. The grid multiplies the partition function by a known power of $2$ and makes the treewidth at
least $\sqrt N$, while the width stays $t=N+2$ and $n\le5N^{c+1}$ (\cref{app:treewidth}).
\end{proof}

\begin{restatable}[The treewidth transition]{corollary}{cortwtransition}\label[corollary]{cor:twtransition}
Consider Boolean models of bounded degree and arity, with small nonnegative integer weights.
\begin{enumerate}[label=(\alph*)]
\item If $n\le\tw\cdot(\log\tw)^{1/2-\theta}$ for some $\theta>0$, exact inference takes time $2^{o(\tw)}$,
and treewidth-based algorithms are not optimal.
\item Under \cref{hyp:sharpcnfseth}, for every $\gamma>0$ no algorithm runs in time
$2^{(1-\gamma)\tw}\poly(n)$ on all such models. This already holds for models with $n\le\tw^{O(1)}$
variables. So treewidth-based algorithms are optimal up to $\gamma$ in the exponent once polynomially many
variables are allowed.
\end{enumerate}
\end{restatable}

Between the two regimes, when $n$ ranges from $\tw\sqrt{\log\tw}$ to $\tw^{O(1)}$, the complexity is
open. It is the complexity of \#SAT on formulas whose length lies between $N\sqrt{\log N}$ and $N^{O(1)}$
in the number $N$ of variables. The correspondence is tight in both directions. A $0/1$ factor graph of
arity $a$ with $|\cF|$ factors is a CNF with at most $2^a|\cF|$ clauses of width at most $a$: it has one
clause for each zero entry of each table. Conversely, \cref{lem:chain} turns a CNF of length $L$, in which
every variable occurs, into a $0/1$ factor graph of arity and degree $3$ with at most $4L$ variables. So
exact inference in bounded-degree $0/1$ models with $n$ variables has the complexity of \#SAT for formulas
of length $\Theta(n)$. Any improvement of the rate $1/\sqrt{\log n}$ in \cref{thm:inference} for such models
is an improvement of the rate of \#SAT as a function of formula length.