  Prior work has combined chain-of-thought prompting in large language models
(LLMs) with programmatic representations to perform effective and transparent
reasoning. While such an approach works well for tasks that only require
forward reasoning (e.g., straightforward arithmetic), it is less effective for
constraint solving problems that require more sophisticated planning and
search. In this paper, we propose a new satisfiability-aided language modeling
(SatLM) approach for improving the reasoning capabilities of LLMs. We use an
LLM to generate a declarative task specification rather than an imperative
program and leverage an off-the-shelf automated theorem prover to derive the
final answer. This approach has two key advantages. The declarative
specification is closer to the problem description than the reasoning steps
are, so the LLM can parse it out of the description more accurately.
Furthermore, by offloading the actual reasoning task to an automated theorem
prover, our approach can guarantee the correctness of the answer with respect
to the parsed specification and avoid planning errors in the solving process.
We evaluate SATLM on 8 different datasets and show that it consistently
outperforms program-aided LMs in the imperative paradigm. In particular, SATLM
outperforms program-aided LMs by 23% on a challenging subset of the GSM
arithmetic reasoning dataset; SATLM also achieves a new SoTA on LSAT and
BoardgameQA, surpassing previous models that are trained on the respective
training sets.
