Knowledge Crosswords: Geometric Knowledge Reasoning with Large Language Models (2024)

Abstract: 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.

## introduction large language models (llms) encode wast amounts of world knowledge in model parameters @xcite . existing tasks and datasets assess llm knowledge abilities mostly by focusing on atomic (e.g., open-domain qa) @xcite @xcite or linear (e.g., multi-hop qa) @xcite @xcite ) settings, extracting one fact or a fixed concatenation of facts from llms. however, knowledge (and language) is naturally structured @xcite , going beyond linear arrangements, involving complex structural attributes, and forming an interweaving network that connects various entities and relations through multiple chains as illustrated in figure 1 . consequently, we ask: can llms extend beyond linear compositionality and aggregate information from multiple chains along with various knowledge constraints? specifically, can llms, with the help of their internal parametric knowledge and inherent reasoning patterns, infer missing facts in a network? we term such ability geometric knowledge reasoning. while compositional qa has been explored in the constrained setting of external knowledge bases @xcite @xcite @xcite , we aim to investigate whether llms could reason with non-linear fact networks solely relying on their internal parametric knowledge. formally, we define geometric knowledge reasoning as reasoning over a network by inferring missing entities based on the given contextual information, where such networks cannot be simply broken down into chains (like linear reasoning), risking the loss of structural information and constraints. geometric knowledge reasoning with llms naturally necessitates new llm abilities beyond those encountered in atomic or linear tasks, such as composing knowledge across multiple chains, reasoning with uncertainty, fact verification, error-aware backtracking, and more. since state-of-the-art llms are trained on linear sequences of texts devoid of explicit structure, it is underexplored whether they could effectively apply their linearly acquired knowledge to solve geomet-figure 1 : illustration of the differences of atomic, linear (multi-hop), and geometric knowledge reasoning. each step of atomic or linear qa leads to a unique and definite (intermediate) answer, while multiple candidates in each step should be jointly considered to satisfy structural constraints in geometric knowledge reasoning. ric reasoning tasks. llms with strong geometric knowledge reasoning abilities could serve as versatile relational databases, allowing controllable access to parametric knowledge through sql-like conditioned prompting. to this end, we propose knowledge cross-words, a geometric knowledge reasoning dataset with 2,101 problems evaluating to what extent llms could achieve such desiderata. each knowledge crossword consists of a list of constraints representing an incomplete fact network, and llms need to reconstruct the knowledge network while ensuring that all factual constraints are met. to solve knowledge crosswords, llms should ideally evaluate candidates for each blank, jointly consider factual constraints, verify intermediate solutions, and backtrack when encountering factual errors, until all constraints are met. for each incomplete fact network, we generate three sets of distractors as options that are progressively more plausible, resulting in easy, medium, and hard subsets for fine-grained evaluation. each problem also comes with two settings: w/o knowledge, where llms solve knowledge crosswords solely with parametric knowledge; w/ knowledge, where a helpful (and noisy) paragraph is prepended to each problem. we conduct extensive experiments to evaluate llms and approaches on knowledge cross-words, ranging from simple zero-shot prompting to advanced ones such as self-consistency (sc) @xcite and least-to-most prompting (ltm) @xcite . results demonstrate that baselines struggle with problems in the hard subset and have significant performance drops in the w/o knowledge setting. advanced prompting methods such as sc and ltm barely improve llms due to their reliance on left-to-right reasoning patterns. to address these challenges, we propose two new instruction-based techniques, staged prompting and verify-all, aiming at augmenting llms' abilities for backtracking, constraint verification, and more. staged prompt-ing guides llms through an elaborate problemsolving process that progressively solves and simplifies the problem blank by blank, while verify-all proposes candidates for all blanks and verifies them simultaneously. we find that verify-all achieves top performance and is more robust with harder problems, while the success of staged prompting is contingent on stronger base llms. further analysis reveals geometric knowledge reasoning poses great challenges to llm knowledge abilities, as they could be susceptible to a variety of factors such as option order, "none of the above" scenarios, number of distractors, special structural patterns, and more. we envision geometric knowledge reasoning as a challenging research question and knowledge crosswords as a comprehensive testbed to evaluate llm knowledge abilities in more complex and structured settings. ## knowledge crosswords we propose knowledge crosswords, a geometric knowledge reasoning benchmark to evaluate whether llms could reason with incomplete fact networks bounded by geometric constraints @xcite . an example knowledge crossword is presented in figure 2 . definition each knowledge crossword consists of a question graph g @xmath0, r, t)|h, @xmath1, @xmath2, where v q is the set of entities represented as nodes of g q and r is the set of all possible relations between entities. each (h, r, t) in g q denotes a directed edge representing a factual association such as (marvin minsky, has won prize, turing award). in the question graph g q , certain nodes b @xmath3, b 2 , . . . , b |b| ] for qa. the goal of each knowledge crossword is to find one combination ## our approach we hypothesize that the left-to-right reasoning patterns in autoregressive language models @xcite and prompting approaches (discussed in section 3.1) would fall short of solving knowledge crosswords, which require backtracking, maintaining problem states, verifying existing information, reasoning with structured constraints, and more. to this end, we introduce two instruction-based methods that promote these abilities, illustrated with a detailed example in figure 2 . ## results we evaluate approaches on knowledge cross-words and present results in llms have preliminary abilities for geometric knowledge reasoning. ## analysis error analysis each knowledge crossword comes with w/ and w/o knowledge settings. we conduct error analysis to investigate the impact of noisy passages on llm problem solving and present in figure 3 . we label each problem based on whether it is answered (in)correctly in w/ knowledge (k+(-)) and answered (in)correctly in w/o knowledge (n+(-)). figure 3 reveals that for easy and medium problems, the main bottleneck is knowledge access since most n-questions are correctly answered under w/ knowledge. however, for hard problems, the bottleneck is geometric knowledge reasoning abilities, given that the proportion of n-k-is consistently above 30%, showing that llms struggle to reason even when the required knowledge is provided. by including three subsets of varying difficulty in knowledge crosswords, we successfully reveal the multitudes of llm limitations in knowledge-intensive contexts, disentangling limitations of knowledge and reasoning.