  We propose Knowledge Crosswords, a geometric knowledge reasoning benchmark
consisting of incomplete knowledge networks bounded by structured factual
constraints, where LLMs are tasked with inferring the missing facts to meet all
constraints. The novel setting of geometric knowledge reasoning necessitates
new LM abilities beyond existing atomic/linear multi-hop QA, such as
backtracking, verifying facts and constraints, reasoning with uncertainty, and
more. Knowledge Crosswords contains 2,101 individual problems, covering diverse
knowledge domains, and is further divided into three difficulty levels. We
conduct extensive experiments to evaluate existing LLMs and approaches on
Knowledge Crosswords. Results demonstrate that baseline approaches struggle
with larger knowledge networks and semantically-equivalent entity distractors.
In light of their limitations, we propose two new approaches, Staged Prompting
and Verify-All, to augment LLMs' abilities for error-aware backtracking and
constraint verification. Our Verify-All significantly outperforms prior methods
and is more robust towards problems in the hard subset. Further analysis shows
that geometric knowledge reasoning poses new challenges to LLMs' knowledge
abilities, particularly in robustness towards varying option orders, complex
structural constraints in knowledge networks, "none of the above" scenarios,
and more.
