PaperlayerView exact revision on arXiv

Source-linked AI summary

Probing the Multi-turn Planning Capabilities of LLMs via 20 Question Games

Yizhe Zhang, Jiarui Lu, Navdeep Jaitly

arXiv:2310.01468v3cs.CLcs.AIcs.HCcs.LG

TL;DR

Ambiguous instructions make proactive clarification important, but directly measuring the required multi-turn reasoning and planning is challenging. The paper uses entity-deducing games to evaluate these capabilities and reports differences among LLMs and improvement through behavior cloning or reinforcement learning. Its findings suggest that these capabilities can be enhanced and may inform future autonomous agents.

  • Problem

    Proactively resolving ambiguous user intent requires multi-turn reasoning and planning, but directly measuring these capabilities is challenging.

    Source: §1 · pp. 1–2

  • Method

    The paper evaluates LLMs as guessers in an entity-deducing game, asking them to identify an entity through questions to a judge.

    Source: §1 · p. 2

  • Results

    Evaluations found significant differences among LLMs, and the authors report that behavior cloning or reinforcement learning can enhance the assessed capability.

    Source: §1 · p. 2, §8 · p. 9

  • Takeaways & Limitations

    The authors present the findings as potential avenues for advancing autonomous agents that proactively lead conversations.

    Source: §1 · p. 2, §8 · p. 9

    Judge responses were occasionally inaccurate, with annotated error rates of 3.07% for Things and 2.95% for Celebrities, creating noise shared across models.

    Source: §3.1 · p. 4

Abstract

from arXiv · show

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 \textit{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.

1 Introduction

Proactively clarifying ambiguous intent requires multi-turn state tracking, reasoning, and strategic question selection. The paper proposes entity-deducing games as a way to assess these capabilities and investigates model performance and training approaches.

1 Introduction

  • In uncertain circumstances, agents may need to ask questions proactively, requiring interactive reasoning and strategic decisions across multiple conversational turns.The paper identifies applications including multistep task completion, task-oriented chatbots, recommendations, and conversational search.Source: §1 · p. 1
  • Unclear user instructions make it difficult for agents to capture nuanced intent and require assessing dialogue state, eliminating ambiguity, and minimizing questions.The introduction frames these objectives as a challenge for dynamic rather than static interaction.Source: §1 · p. 2
  • The 20 questions game tests whether a model can deduce an unknown entity through a sequence of questions, tracking dialogue state and narrowing the search with few queries.The guesser receives “Yes,” “No,” or “Maybe” responses from a judge who knows the entity.Source: §1 · p. 2
  • The authors evaluate several LLMs, study imitation of high-performing models, and use PPO game-playing to improve vanilla Vicuna models.They present the task as a way to probe conversational reasoning and planning and provide code and data for future research.Source: §1 · p. 2

2 Related Work

Prior benchmarks assess LLMs across many reasoning and knowledge tasks, while planning and multiturn work use different evaluation settings. This paper positions entity deduction as a complementary test of generating multi-turn conversations.

2 Related Work

  • Existing benchmarks cover arithmetic, commonsense, symbolic reasoning, knowledge, coding, and factual tasks; this work aims to complement them with multi-turn deduction, state tracking, fact recall, and strategic planning.The cited benchmarks include HELM, BIG-bench, SuperGLUE, LAMA, and CoT-Hub.Source: §2 · pp. 2–3
  • Earlier LLM planning evaluations are relatively rare and report difficulties in generating plans, while this work uses textual representations of goals.The cited studies examine valid actions, heuristic dependence, and numerical or spatial planning.Source: §2 · p. 3
  • Multiturn benchmarks assess conversation and instruction following across varied tasks, whereas this work focuses on the depth of entity deduction.The related work also distinguishes image-based deduction benchmarks, which test guessing an object, from this paper’s focus on generating the conversation.Source: §2 · p. 3

3 Entity-deduction Arena (EDA)

The Entity-Deduction Arena evaluates LLMs as guessers in a judge-mediated game that demands multi-turn tracking and planning. Its experimental settings specify datasets, scoring, and judge and guesser procedures.

3 Entity-deduction Arena (EDA)

  • The judge knows the entity and answers the guesser’s questions, while the guesser must identify it in as few queries as possible.The guesser’s task combines state tracking, strategic planning, and inductive reasoning, including forming a taxonomy of candidate entities.Source: §3 · p. 3
  • In experiments, incorporating the entire dialogue history negatively affected judge accuracy.The authors report that extra history tended to confuse the judge rather than improve understanding.Source: §3 · p. 3
  • The Entity-Deduction Arena (EDA) evaluates LLMs as guessers, using entity deduction as a proxy for complex multi-turn conversation and proactive clarification.Source: §3 · p. 4

3.1 Experimental settings

  • The evaluation uses Things and Celebrities datasets, each with 500 entities; both are split into 300 training, 100 evaluation, and 100 test items.Source: §3.1 · p. 4
  • GPT-3.5-turbo serves as judge, with constrained response options; occasional judge inaccuracies create a noisy setting shared across models.Annotated judge-response error rates were 3.07% for Things and 2.95% for Celebrities.Source: §3.1 · p. 4
  • The guesser receives the current dialogue history and generates either its next question or final guess according to task instructions.Source: §3.1 · p. 4
  • Metrics include turns, success rate, yes responses, and a combined score; fewer turns and higher success rate are better.The authors describe #Yes as a statistic that correlates with final performance and define the reward’s balancing parameter as λ = 0.02.Source: §3.1 · p. 5

4 Benchmarking LLMs on EDA

GPT-4 led the evaluated models on EDA, while GPT-3.5 and Claude-2 were runners-up and some smaller open-source models performed comparably. Gameplay analyses show that strong performance involves efficient question planning, state-aware deduction, and occasional backtracking.

4 Benchmarking LLMs on EDA

  • GPT-4 performed best overall, with about one-third of entities accurately predicted; GPT-3.5 and Claude-2 were runners-up, and Vicuna 13B and Mistral 7B were not far behind.GPT-3.5 was stronger on Things, while Claude-2 was stronger on Celebrities; Vicuna 13B outperformed Claude-1 on Things.Source: §4 · pp. 5–6
  • Effective gameplay narrows the search with high-level questions, then enumerates a few possibilities when useful questions become harder to find.Weaker models showed early enumeration, redundant questions, and inconsistencies with prior answers.Source: §4 · p. 6
  • GPT-4 updates its ranked guesses as answers eliminate candidates, and may backtrack when questions rule out its leading options.The analysis also reports consistent gameplay strategies across repetitions, suggesting GPT-4 may rely on an implicit taxonomy of entities.Source: §4 · pp. 7–8
  • The trajectory-swap experiment found that GPT-4 planning improved Vicuna 7B’s score, while replacing Vicuna’s final-turn reasoner with GPT-4 brought little improvement.GPT-4’s own score regressed when Vicuna 7B handled the final turn, supporting the authors’ conclusion that planning and reasoning both matter.Source: Table 4 · p. 7, §4 · p. 8

5 Enhancing the Open-source Models via Behavior Cloning

Behavior Cloning fine-tuned Vicuna models on game demonstrations from GPT-3.5. It improved performance, with results varying by training subset, model size, and dataset.

5 Enhancing the Open-source Models via Behavior Cloning

  • Fine-tuning Vicuna 7B on 600 GPT-3.5 demonstrations improved results by more than 70% on both datasets and mitigated repetition.The demonstrations came from all training examples across Things and Celebrities; the authors report that the model used more effective strategies on unseen entities or names.Source: §5 · p. 8
  • Training Vicuna 7B on successful teacher games outperformed training on all experiences and came close to GPT-3.5 on Things, but gains were more limited on Celebrities.The successful-game subset was drawn from entities or names for which the teacher won.Source: §5 · p. 8
  • Successful-game fine-tuning also improved Vicuna 13B, though less than the improvement for Vicuna 7B, with only marginal gains on Celebrities.The authors hypothesize that celebrity guessing requires more case-specific strategies and may be harder to imitate superficially.Source: §5 · p. 8

6 Reinforcement Learning from Game-play (RLGP)

The authors trained Vicuna models through game play using Proximal Policy Optimization, calling the approach RLGP. RLGP improved in-domain Things performance, with some improvement on Celebrities.

6 Reinforcement Learning from Game-play (RLGP)

  • RLGP uses PPO to train from game play, assigning the Eq. (1) reward to the final turn and an intermediate reward to turns receiving a “Yes” response.Training used 300 Things examples and the V-FT 7B (Suc.) and V-FT 13B (Suc.) models.Source: §6 · pp. 8–9
  • RLGP improved Vicuna models over vanilla models on Things; RLGP 13B outperformed V-FT 13B and matched GPT-3.5, while RLGP 7B improved over V-FT 7B.The authors also report some improvement on the out-of-domain Celebrities dataset.Source: §6 · p. 9

7 Breakdown Analysis: Do the models agree on successful predictions?

The breakdown analysis finds that models succeed on different subsets of entities, despite correlations in their predictions. RLGP and behavior-cloned models show distinct strengths.

7 Breakdown Analysis: Do the models agree on successful predictions?

  • Models’ correct predictions overlap but also differ; RLGP 13B identified Sunglasses, which GPT-4 consistently failed to identify.Four Things items resisted successful prediction by all models, whereas every evaluated celebrity was correctly predicted by at least one model.Source: §7 · p. 9, Figure 2 · p. 9
  • RLGP tends to improve success on items vanilla models sometimes solve, while behavior cloning appears stronger on new items.V-FT 13B (Suc.) identified Post-it Note and VR headset more accurately than either Vicuna 13B or GPT-3.5, according to the authors.Source: §7 · p. 9

8 Conclusion

The paper introduces an entity-deduction testbed for evaluating LLM strategic planning and deductive reasoning, and reports that these abilities can be enhanced through Behavior Cloning or Reinforcement Learning.

8 Conclusion

  • The entity-deduction testbed evaluates LLMs’ strategic planning and deductive reasoning when asking questions about an unknown entity.Source: §8 · p. 9
  • The findings indicate that state-of-the-art LLMs maintain an intrinsic taxonomic representation of knowledge entities to some extent.Source: §8 · p. 9
  • Behavior Cloning or Reinforcement Learning can enhance this capability, which the authors identify as promising for further advancement.Source: §8 · p. 9
  • The authors identify whether Chain-of-Thought prompting can further improve performance on related tasks as a future research direction.Source: §8 · p. 9

A Dataset composition

This material describes the datasets and response conventions, additional GPT-4 probing results, and an uncertainty analysis. It also outlines how human game-play sessions were collected for a baseline.

A Dataset composition

B Prompt used for Celebrities and rationale for using “Dunno”

  • Celebrities questions use “Dunno” for unknown or personal-information questions, while Things responses can include “Maybe” for entities with variable forms.“Dunno” accounts for less than 1% of Celebrity responses, while “Maybe” appears in around 20% of Things responses.Source: B Prompt used for Celebrities and… · p. 15
  • The human baseline used 108 volunteers and collected 145 Things-30 and 71 Celebrities-30 game sessions after subsampling each dataset to 30 items.Source: B Prompt used for Celebrities and… · p. 15

C Additional results and prompt used for Dialog State Probing

D Measurement of uncertainty

  • Predicted uncertainty correlated with shifts in top guesses mainly for powerful models such as GPT-4; Vicuna’s guesses and confidence scores were often not sensible.Source: D Measurement of uncertainty · p. 16

E Full ablation results on RQ2, planning vs reasoning

The ablation reports reduced performance when GPT-4 supplies the final reasoning step for human trajectories. The accompanying material describes human-baseline collection and compares GPT-4’s game-play behaviors with those of human players.

E Full ablation results on RQ2, planning vs reasoning

  • GPT-4’s use for the final reasoning step decreased performance on human trajectories, suggesting models may fit model-generated trajectories better.Table 6 reports game scores for trajectory swaps, including GPT-4 trajectories with another model substituted for the last turn.Source: E Full ablation results on RQ2,… · p. 16, Table 6 · p. 16

F Experimental details for human baseline

G Comparison of GPT-4 vs Human player

  • GPT-4 and humans share an ability to backtrack, while LLMs can use greater knowledge but may repeat patterns and accumulate errors.Stronger models sometimes escape repetition and correct earlier errors, which the authors presume may reflect stronger adherence to a high-level plan.Source: G Comparison of GPT-4 vs Human player · p. 17

G.1 Things dataset

The game runs illustrate GPT-4’s information-gathering and recovery strategies, alongside weaker-model failures and differences between Things and Celebrities. The appendix also reports that strategy learned from Things may generalize to Celebrities.

G.1 Things dataset

  • When GPT-4 resumed a human’s Guitar game after a wrong turn, it recognized the mistaken route and asked about the overlooked category, salvaging the game.The human had also shown backtracking by retracing the error and asking a reconfirming question.Source: §G.1 · pp. 17–18
  • In Bald eagle, the human made a lucky guess after identifying a bird, while GPT-4 took three more turns to gather information before an informative guess.Source: §G.1 · p. 18

G.2 Celebrities dataset

  • On Celebrities, GPT-4 often asked questions requiring domain-specific background knowledge, while humans relied more on direct guesses that could succeed by luck but limited their overall effectiveness.The authors note such knowledge may be tacit for LLMs and unavailable to human judges.Source: §G.2 · p. 18

H Game runs and failure modes on Celebrities and Things

  • Across additional game runs, stronger models identified questions that separated the remaining possibilities, while weaker models struggled with planning and reasoning; Vicuna 7B also showed repetitive behavior and artifacts.The authors report that once a less robust model entered a repetitive pattern, escaping it became increasingly challenging.Source: H Game runs and failure modes on… · p. 18

J Generalization ability of Vicuna 7B finetuned on Things to Celebrities

K Experimental settings for Reinforcement Learning from Game-Play (RLGP)

The RLGP settings describe training on selected Things entities with a decaying intermediate reward. GPT-4’s Yoga Mat failures show that even a strong model can become trapped by an erroneous assumption.

K Experimental settings for Reinforcement Learning from Game-Play (RLGP)

  • RLGP trained Vicuna 7B and 13B on 209 Things entities that at least one off-the-shelf LLM had won, using 32 rollouts per entity and 600 training iterations; the intermediate reward decayed linearly, with early “yes” responses treated as positive.The entity selection was intended to provide experiences where the model had some chance of receiving a final reward.Source: K Experimental settings for… · p. 19

L GPT-4 failure cases

Loading 2310.01468v3…