Probing the Multi-turn Planning Capabilities of LLM s via 20 Question Games (2024)

Abstract: Large language models (LLMs) are effective at answering questions that are clearly asked. However, when faced with ambiguous queries they can act unpredictably and produce incorrect outputs. This underscores the need for the development of intelligent agents capable of asking clarification questions to resolve ambiguities effectively. This capability requires complex understanding, state tracking, reasoning and planning over multiple conversational turns. However, directly measuring this can be challenging.In this paper, we offer a surrogate problem which assesses an LLMs’s capability to deduce an entity unknown to itself, but revealed to a judge, by asking the judge a series of queries. This entity-deducing game can serve as an evaluation framework to probe the conversational reasoning and planning capabilities of language models.We systematically evaluate various LLMs and discover significant differences in their performance on this task. We find that strong LLMs like GPT-4 outperform human players by a large margin. We further employ Behavior Cloning (BC) to examine whether a weaker model is capable of imitating a stronger model and generalizing to data or domains, using only the demonstrations from a stronger model. We finally propose to use Reinforcement Learning to enhance reasoning and planning capacity of Vicuna models through episodes of game playing, which lead to significant performance improvement. We hope that this problem offers insights into how autonomous agents could be trained to behave more intelligently in ambiguous circumstances.

## introduction in uncertain circumstances, conversational agents may need to take the initiative to reduce their uncertainty by asking good questions proactively, thereby solving problems more effectively. this requires intricate, interactive, strategic decisionmaking and reasoning about the agent's next move in a multi-turn conversation. this capability is crucial in various applications like task-oriented chatbots, recommendations, and conversational search. traditional dialogue systems have been achieved by modularizing various aspects of such tasks into sub-tasks such as understanding, state tracking, planning, and generation. however, recent advances in llm have made it possible to create an end-to-end pipeline for developing autonomous agents that can complete complex tasks using enhanced planning and memory capabilities. promising autonomous agents, such as react @xcite , @xcite , and langchain (langchain-ai, 2023), require the underlying llm to recall information from previous dialogues, resembling the understanding and state tracking stage. they also rely on the llm to decompose larger tasks into more manageable components, analogous to the planning stage. among them, some approaches (e.g., hugginggpt @xcite ) use a static planning strategy by first generating the complete plan via llm and subsequently tackling subtasks. other approaches (e.g., autogpt) adopt an interactive planning strategy, where the generation of each action is conditioned on the outcome of the previous planning steps. while llm-powered agents are powerful, they can perform poorly when a user's instructions are unclear. this poses a critical challenge -how to accurately elicit and capture the user's intents, which are often nuanced and noisy, to enable dynamic rather than static human-computer interactions. for example, in figure 1 , the agent aims to: 1) accurately assess the current dialog state; 2) disambiguate user's intent and satisfy the user demand; 3) ask as few questions as possible. progress in this direction is difficult because directly measuring complex understanding, reasoning and planning capabilities is challenging. in this study, we investigate this somewhat overlooked research problem -how good the llms are at asking ## entity-deduction arena (eda) during an entity-deducing game session, two players engage in a game regarding a specific entity. one player, "judge" (j), is provided with the entity and is expected to respond to queries or guesses from the guesser using only the responses "yes," "no," or "maybe,". the other player, "guesser" @xcite , is agnostic about the entity, and is supposed to pose a series of questions to deduce the entity using as few queries as possible. the judge does not require access to the dialogue history and only needs the entity and current question to provide a response foot_0 . this task is akin to closed-book qa @xcite , which current llms can reasonably handle. on the other hand, playing the guesser is more demanding. a proficient g necessitates several multi-turn dialogue capabilities working in synergy: 1) state tracking and understanding: g must comprehend multiturn context, track asked questions, and understand its position in the game and coreference resolution. 2) strategic planning: g needs to strategically ask questions to progress efficiently towards a better state, avoiding redundant queries and ensuring consistency with prior knowledge. 3) inductive reasoning: g must use conversation comprehension to generate conjectures based on acquired knowledge. g must inherently establish a taxonomy representation to efficiently and accurately identify the correct entity among numerous options. our assessment, referred to as the entity-deduction arena (eda), focuses on evaluating the capability of various llms as the guesser, as a proxy to probe their overall capabilities in handling complex multi-turn conversational tasks involving proactively asking clarification questions. while eda may not evaluate all aspects of reasoning and planning ability, it capture several key capabilities which are important for any conversational ai agent that needs to actively elicit information from users through clarifying questions. the task provides a targeted way to probe these capabilities in a controlled setting, and provides a new and complementary benchmark compared to existing tasks for probing language models' capabilities from a different angle focused on multi-turn strategic conversation. ## benchmarking llms on eda we assess several widely-used llms, such as gpt-4, gpt-3.5, claude-1/2, vicuna (7b-v1.3, 13b-v1.3) @xcite and mistral-7b (jiang et al., 2023) using our eda benchmarks. unfortunately, we are unable to evaluate llama-2 or its derivatives due to license restrictions. llama-1 @xcite is also excluded from the comparison as it lacks a conversation finetuned model, and as such it often does not adhere to our instructions. the corresponding results are presented in in general, gpt-4 attained the best performance among the models evaluated. around 1/3 of the entities were accurately predicted. the runner-ups are chatgpt-3.5 and claude-2. chatgpt-3.5 is superior on the things datasets, while claude-2 shows better strength on the celebrities datasets. despite being much smaller, open-source models such as the vicuna 13b and mistral 7b model performed comparably well, not trailing too far behind the closed-source models. in particular, vicuna 13b outperformed claude-1 when it comes to things. this suggests that open-sourced models have significant potential. naturally, models with a higher success rate usually require fewer turns. it is plausible that a small portion of entity deduction game sessions may exist on the web and were a part of the pretraining data. however, these sessions likely contribute only a minuscule fraction. nevertheless, robust models such as gpt-4 exhibit consistently strong performance across numerous tested entities. we have also conducted a large-scale human baseline in a subset of 30 tested examples for each dataset. the discussion of these results can be found in appendix b. we present several real game runs in we also compare several games between gpt-4 and human players in appendix g, highlighting that strong llms share similarities with humans in their ability to backtrack when they are on the wrong path. one advantage of llm over humans is that llm may have a superior level of knowledge (appendix g, ## enhancing the open-source models we further investigate the potential of open-source models. we used behavior cloning (bc) to distill capabilities exhibited by the stronger models into the smaller vicuna models. we first collected game demonstrations from the gpt-3.5 model over all 600 training examples from things and celebrities. we then fine-tuned the vicuna models using these demonstrations. the experimental settings are provided in the appendix i. rq3: can smaller open-source models benefit from imitating larger close-source models? we first fine-tuned the vicuna 7b model using a total of 600 training instances from both datasets. the results are presented in rq4: should models learn from successful demonstration exclusively? to answer this, we selected all the game runs of the entities or names where the teacher model finally won the game from both datasets. this subset was then used to train the vicuna 7b model, similar to the rejection sampling @xcite . the results, referred to as v-ft 7b (suc.) in rq5: does the model size matter? we further compared the performance improvement achieved through finetuning for both vicuna 7b and 13b models. the model finetuned on vicuna 13b, v-ft 13b (suc.), also achieved much higher score than vicuna 13b. however, the improvement was less substantial than the improvement on v-ft 7b (suc.). again, the improvement over the celebrities dataset is marginal. we hypothesize that guessing the celebrity requires a more case-specific strategies compared to guessing things, thus likely to be more challenging to be superficially imitated. ## reinforcement learning via gameplay we conducted further experiments to investigate whether the performance could be further enhanced through learning solely from the model's own experience. we employed proximal policy optimization (ppo) @xcite to train the model by playing with with the judge, j, a technique we refer to as reinforcement learning from game-play rlgp. we made modifications to the trlx repository @xcite to enable multiturn setup to facilitate rlgp training. during training, we assigned the reward defined in eq. ( 1 ), to the final turn of each rollout. additionally, we assigned an intermediate reward to turns that received a "yes" response from j. we trained the v-ft 7b (suc.) and v-ft 13b (suc.) models in v-rlgp models exhibit improvement compared to the vanilla vicuna when tested on the in-domain dataset things. v-rlgp 13b seems to unlock the potential of the vicuna model, outperforming the v-ft 13b model, matching the performance of the runner-up gpt-3.5. v-rlgp 7b also show substantial improvement over v-ft 7b model. on the out-domain dataset celebrities, interestingly, v-rlgp models achieves some improvement, showing its generalization potential. ## breakdown analysis: do the models agree on successful predictions? we present a comprehensive breakdown analysis of each model's performance on a subset of 30 evaluated items for each dataset in figure 2 . within the evaluated items of things, four items consistently defy successful predictions by all models. on the other hand, celebrities exhibits a more scattered pattern, with each celebrity being correctly predicted by at least one model. there are correlations between the entities or names that each model can correctly identify, but different models exhibit their own strengths on different subsets. for instance, the rlgp 13b model can accurately predict "sunglasses", whereas the stronger models like gpt-4 consistently fails. we also provide some case studies including why gpt-4 consistently fails on "yoga mat" in appendix l. we observed that rlgp models tend to strengthen the performance on items that vanilla models occasionally succeed in, thereby improving their success rate on these specific items. however, rlgp models do not effectively facilitate learning about new items. conversely, bc fine-tuning excel in achieving success on new items. interestingly, the bc fine-tuned models displays different strengths compared to both the initial checkpoint and the expert whose demonstration it mimics. for example, the v-ft 13b (suc.) model achieves high accuracy in identifying post-it note and vr headset, whereas neither the vicuna 13b nor the gpt-3.5 performs as well in this regard. ## related work complex reasoning benchmarks extensive benchmarks have been evaluating the complex reasoning abilities of llms @xcite . these include helm @xcite bigbench @xcite , superglue (sarlin et al., 2020), lama @xcite , and cot-hub @xcite , which have enabled researchers to assess llms across a spectrum of tasks involving arithmetic and math (gsm8k) @xcite , commonsense (arc) @xcite , knowledge (mmlu) @xcite , and coding (humaneval) @xcite have been developed to gauge their realworld abilities. we aim to introduce a novel benchmark focus on evaluating multi-turn state tracking and strategical planning capability to complement existing reasoning benchmarks. evaluation of planning evaluation of the planning abilities of llms is relatively rare. valmeekam et al. (2022) proposed an assessment framework to gauge the planning capabilities of llms to generate valid actions to achieve a special goal and provide a rationale for the plan. their evaluation on 8 planning tasks reveals llms, like gpt-3 (brown et al., 2020), seem to display a dismal performance. valmeekam et al. (2023) further evaluates on gpt-4 and suggests the autonomous learning capacity of llms to formulate plans is limited and dependent on properly designed heuristics. xie et al. ( 2023 ) similarly indicate that llms may encounter difficulties in generating planning goals related to numerical or spatial reasoning, while being responsive to the specific prompts used. unlike these studies, our task solely relies on textual representations of goals. multiturn benchmarks mt-bench @xcite assesses the multi-turn conversation and instruction-following ability of llms by annotating their responses to questions involving writing, role-play, extraction, reasoning, math, coding and knowledge. @xcite evaluates llms on 23 tasks related to logical reasoning, non-textual reasoning, and commonsense reasoning. the study reveals that incorporating interactive features in llms can enhance their performance by employing multi-turn prompt engineering. lmrl gym @xcite , a concurrent work, investigated multi-turn reinforcement learning with language models across multiple tasks. in contrast, our work focuses on the depth by presenting a thorough analysis of the entity deduction task. entity-deduction game testing the model's ability to deduct an ambiguous entity or asking clarification questions @xcite has been utilized as a testbed on dia-logue systems and visual reasoning tasks. infobot @xcite uses reinforcement learning to learn an optimal dialog policy for identifying movie entries from a movie database. esp @xcite and peekaboom @xcite demonstrated that deduction games can effectively gather labeled data. guesswhat?! @xcite and referit @xcite , assess the visual reasoning capabilities of tested models by ask them to guess the referred object in the image based on the conversation. our work instead aims to gauge on the model's ability on generating the conversation. ## conclusion motivated by a need to develop agents capable of effectively addressing ambiguous user intents, we introduce a testbed for evaluating llm's strategic planning and deductive reasoning abilities in asking entity-deducing questions. our findings indicate that sota llms are able to maintain an intrinsic taxonomic representation of knowledge entities to a certain extent. we further show that this capability can be enhanced through behavior cloning or reinforcement learning, revealing great potential for further advancements. in future research, we intend to investigate whether the implementation of cot prompting can further enhance the model's performance in related tasks.