Do Large Language Models have Problem-Solving Capability under Incomplete Information Scenarios? (2024)

Abstract: The evaluation of the problem-solving capability under incomplete information scenarios of Large Language Models (LLMs) is increasingly important, encompassing capabilities such as questioning, knowledge search, error detection, and path planning. Current research mainly focus on LLMs’ problem-solving capability such as “Twenty Questions”.However, these kinds of games do not require recognizing misleading cues which are necessary in the incomplete information scenario.Moreover, the existing game such as “Who is undercover” are highly subjective, making it challenging for evaluation.Therefore, in this paper, we introduce a novel game named BrainKing based on the “Who is undercover” and “Twenty Questions” for evaluating LLM capabilities under incomplete information scenarios. It requires LLMs to identify target entities with limited yes-or-no questions and potential misleading answers. By setting up easy, medium, and hard difficulty modes, we comprehensively assess the performance of LLMs across various aspects. Our results reveal the capabilities and limitations of LLMs in BrainKing, providing significant insights of LLM problem-solving levels.

## introduction incomplete information scenarios include missing information, uncertainty, and misinformation, encountered in fields such as business negotiations, military strategy, medical diagnosis, and legal judgments @xcite . the problemsolving capability under incomplete information refer to the capability to effectively handle available information, make rational inferences, and decisions in situations lacking comprehensive data. this capability is crucial in real life as we cannot possess all the necessary information for decisionmaking. it's also important for large language models (llms), which not only tests llms' logical reasoning capabilities but also involves adjusting strategies in constantly changing environments, significantly enhancing their robustness and quality of decision-making in various fields. therefore, a natural question arises: do llms have problemsolving capability under incomplete information scenarios? previous research on problem-solving capability under incomplete information scenarios focus on simulating complex decision-making environments through games, such as "werewolf" @xcite @xcite , "poker" @xcite and "avalon" @xcite , etc. these games require players to make decisions without full information, often involving deception and strategic planning to conceal their real identities. as shown in fig. 1 (a), "who is undercover" is another incomplete information game which requires players to deduce whether they are the spy based on others' descriptions. in this running example, player with "bread" is the spy in this game and he needs to hide himself against being caught through twist the facts in his description like "it typically requires more sugar, fats, and eggs.". however, even advanced llms like gpt-3 and gpt-3.5, while excelling in general nlp tasks @xcite @xcite , revealing limitations in effective decision-making under incomplete information environments @xcite . information processing is a crucial problemsolving capability under incomplete information scenarios, exemplified by the minesweeper game @xcite , the twenty questions game @xcite , etc. as shown in fig. 1(b) , the twenty questions game requests the player to pose a series of yes-or-no questions to guess the given entity (i.e. "george clooney"), which can effectively evaluate llms' creativity @xcite , knowledge retrieval @xcite , multi-hop reasoning capabilities @xcite . however, the above-mentioned games, such as twenty questions, do not adequately assess llms' capabilities in processing information and solving problems because it lacks deception and strategic complexity that require recognizing misleading cues and formulating adaptive strategies based on limited or false information. moreover, games like "werewolf" and "who is undercover" are highly subjective, making it challenging to evaluate llms' capabilities under incomplete information scenarios effectively. therefore, in this paper, we introduce a new game named brainking by combining the "who is undercover" and "twenty questions" game to assess llms' information processing and problemsolving capabilities under incomplete information scenarios. brainking challenges llm participants to identify entities amidst potential misinformation through a limited set of yes-or-no questions across easy, medium, and hard difficulty modes. this game objectively assesses llms' world knowledge, reverse thinking, and error detection capabilities. our results explore five key questions regarding llm performance in brainking, investigating the relationship between accuracy and rounds, the impact of starting point difficulty and the number of wrong answers, and the correlation between accuracy and the ability to recognize confusion. this assessment, including questioning, knowledge retrieval, misinformation recognition, and planning abilities, effectively evaluates llms' capabilities under incomplete information scenarios through a simple-yet-effective game with objective metrics. in summary, our research makes three key contributions: the proposed brainking game, inspired by the twenty questions game, requires llm participants to identify an entity with a limited number of yesor-no questions despite potentially misleading answers. it contains three difficulty modes: easy, medium, and hard, as illustrated in fig. 2 . these modes are designed to thoroughly assess an llm's world knowledge, reverse thinking, and error detection capabilities in identifying the target entity. specifically, we utilize an open-source twenty questions dataset foot_0 , which comprises 78,890 entities. to ensure the task is manageable and not hindered by a lack of knowledge by all llm participants, we adopt gpt3.5 foot_1 to score each entity for commonness from 1 (less common) to 3 (more common), retaining the top 10,000 common entities. next, we also adopt gpt3.5 to generate a hierarchical concept list for each entity. this list must include at least three concepts, where each subsequent concept is a broader or more abstract category of the preceding one. we avoid strict academic classifications to maintain the conceptual hierarchy's logic and clarity. for instance, the hierarchical concept list for the entity "dog" q1: is it large in size? q2: does it have stripes? q3: is it often active on the ground? a1: yes a2: yes a3: yes ①easy mode ②medium mode q1: does it have stripes? q2: is it often active on the tree? q3: does it capture large prey? q4: is it often active at dusk? a1: yes a2: yes a3: yes a4: yes ③hard mode q1: does it have stripes? q2: is it often active on the ground? a1: yes a2: yes spot stripe tree small prey night ground large prey dusk similar target ① simple starting point harder starting point confusion error is "[household pets, terrestrial mammals, mammals]" instead of the strict biological hierarchy "[canis, canidae, carnivora]", as starting with canis makes it too easy to guess the dog based on prior knowledge. after that, gpt3.5 is also used to provide the most similar entity for each entity in the dataset. for example, the entity most similar to a "dog" is identified as a "wolf". ## experiments in this section, we conduct extensive experiments to evaluate different llms' performance in the proposed brainking. ## conclusions and future work in conclusion, our study highlights the importance of a multifaceted approach to evaluating the information processing and problem-solving capability of llms under incomplete information scenarios. the brainking game, as a novel benchmark, successfully challenges llms in various cognitive aspects, from basic knowledge retrieval to complex reasoning and confusion recognition. our findings offer a detailed understanding of the strengths and limitations of current llms, underscoring the need for llms to not only process information accurately but also navigate through misleading information effectively. for future work, there is potential to extend the complexity and scope of the brainking, introducing more challenging scenarios to better mimic real-world conditions.