ACL Findings2024
Do Large Language Models have Problem-Solving Capability under Incomplete Information Scenarios?
Yuyan Chen, Yueze Li, Songzhou Yan, Sijia Liu, Jiaqing Liang, Yanghua Xiao
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' problemsolving 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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers2
- XMeCap: Meme Caption Generation with Sub-Image AdaptabilityYuyan Chen, Songzhou Yan, Zhihong Zhu, Zhixu Li et al.ACM MM 2024 · 7 citations
- Intrinsic Credit Assignment for Long Horizon InteractionIlze Amanda Auzina, Joschka Strüber, Sergio Hernández-Gutiérrez, Shashwat Goel et al.ICML 2026 · 6 citations
Builds on5
- Large Language Models are Zero-Shot ReasonersTakeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo et al.NeurIPS 2022 · 8,168 citations
- A Systematic Study and Comprehensive Evaluation of ChatGPT on Benchmark DatasetsMd. Tahmid Rahman Laskar, M. Saiful Bari, Mizanur Rahman, Md Amran Hossen Bhuiyan et al.ACL Findings 2023 · 97 citations
- Increasing Diversity While Maintaining Accuracy: Text Data Generation with Large Language Models and Human InterventionsJohn Joon Young Chung, Ece Kamar, Saleema AmershiACL 2023 · 55 citations
- Play the Shannon Game with Language Models: A Human-Free Approach to Summary EvaluationNicholas Egan, Oleg V. Vasilyev, John BohannonAAAI 2022 · 22 citations
- BRAINTEASER: Lateral Thinking Puzzles for Large Language ModelsYifan Jiang, Filip Ilievski, Kaixin Ma, Zhivar SouratiEMNLP 2023 · 6 citations
Related papers
- Probing the Multi-turn Planning Capabilities of LLMs via 20 Question GamesYizhe Zhang, Jiarui Lu, Navdeep JaitlyACL 2024 · 2 citations
- GuessArena: Guess Who I Am? A Self-Adaptive Framework for Evaluating LLMs in Domain-Specific Knowledge and ReasoningQingchen Yu, Zifan Zheng, Ding Chen, Simin Niu et al.ACL 2025 · 5 citations
- LogicGame: Benchmarking Rule-Based Reasoning Abilities of Large Language ModelsJiayi Gui, Yiming Liu, Jiale Cheng, Xiaotao Gu et al.ACL Findings 2025 · 2 citations
- Who is the richest club in the championship? Detecting and Rewriting Underspecified Questions Improve QA PerformanceYunchong Huang, Gianni Barlacchi, Sandro PezzelleACL Findings 2026
- Hidden in Plain Sight: Reasoning in Underspecified and Misspecified Scenarios for Multimodal LLMsQianqi Yan, Hongquan Li, Shan Jiang, Yang Zhao et al.EMNLP 2025
