Game of Thought: Robust Information Seeking with Large Language Models Using Game Theory

AI summary

Overview

• Research area: Natural Language Processing / LLM agents, specifically information-seeking (clarification question asking), studied through a game-theoretic lens combining computational game solving with large language models.
• Technical level: Advanced. The paper assumes familiarity with two-player zero-sum extensive form games, Nash equilibrium, minimax, counterfactual regret minimization, and subgame search, though the high-level argument is accessible.
• Scope: The paper formally defines the Strategic Language Search (SLS) problem and its variants, proposes the Game of Thought (GoT) framework that approximates a Nash equilibrium strategy for a restricted variant using LLMs, and empirically compares GoT's worst-case performance against prompting baselines and Uncertainty of Thought across five dataset settings.

What This Paper Is About

Large language models are often deployed in situations where they are missing information needed for the task, so the ability to ask clarifying questions matters. Prior work such as Uncertainty of Thought assumes the unknown target item is drawn uniformly at random, an assumption the authors argue degrades worst-case performance and is unrealistic in high-stakes settings. This paper reframes information seeking as an adversarial two-player zero-sum game — the "Game of Twenty Questions" with an Item Chooser who picks the target to impede the Questioner — and builds a framework that optimizes the Questioner's worst-case performance without assuming any item distribution.

Key Contributions

1. Problem formalization: The authors formulate the Strategic Language Search (SLS) problem and three variants — SLS-Restricted (SLSR), Weighted-SLS (WSLS), and Weighted SLSR (WSLSR) — as two-player zero-sum extensive form games, with explicit assumptions (3.1–3.5, 3.8, 3.10) and complexity results, including a proof that deciding whether a sequence of k questions suffices for a known target is NP-complete (Theorem 3.6).
2. Game-theoretic solutions: They establish optimal game-theoretic strategies for SLS and its variants, highlighting that these strategies are necessarily randomized. For the special case where the question set is the unrestricted Q∞ and |S| = 2^k, the "even-split" strategy is shown to be optimal and to cost exactly k questions (Theorem 3.7), and the authors prove even-split is also optimal in UoT's uniform-random setting.
3. The GoT framework: They propose Game of Thought (GoT), which approximates a Nash equilibrium in the SLSR variant using on-demand subgame construction, depth-limited simulation, heuristic leaf evaluation, and solving via LiteEFG's implementation of CFR minimization. GoT is shown to be safe with respect to value estimates that depend only on S(H_t) (Theorem 5.1).
4. Empirical evaluation: Across all tested settings, GoT improves worst-case performance relative to direct prompting, direct choice, and UoT-based methods, in both unweighted and weighted variants, and under two LLM backbones.

Main Findings

• GoT beats UoT on worst-case interaction length in every reported setting. With GPT 4.1, GoT achieved worst-case lengths of 10.2 (Common), 11.8 (S128), 7.4 (Breeds), 12.2 (DX), and 7.9 (FloDial), versus UoT's 11, 13, 9, 13, and 9 respectively. With Qwen 2.5 72B Instruct, GoT scored 10.0, 10.8, 6.6, 10.5, and 7.5 versus UoT's 11, 12, 8, 12, and 9.
• Prompting baselines are sometimes competitive with UoT. Direct Prompting scored 7.8 on Breeds with GPT 4.1, beating UoT's 9, and 8.0 with Qwen versus UoT's 8. The authors note this suggests UoT may improve average case at the expense of worst case.
• All methods fall short of the theoretical optimum. The optimum is log2(|S|) by Theorem 3.7, but all methods fall short by around 2 to 3 turns of interaction, which the authors attribute to the difficulty of phrasing sufficiently natural questions that split the consistent set evenly.
• GoT improves weighted worst-case performance by 15% to 40% over UoT. In the weighted variant, GPT 4.1 GoT scores were 152.1 (Common), 23.2 (Breeds), 78.3 (DX), and 61.4 (FloDial) versus UoT's 227.4, 32.1, 110.0, and 81.0. Qwen GoT scores were 151.9, 32.3, 73.6, and 62.3 versus UoT's 228.5, 47.0, 99.0, and 74.0. UoT's advantage over pure prompting is less clear in the weighted variant.
• Deeper simulation helps GoT but not UoT. Increasing the simulation depth d improved GoT's worst-case performance before plateauing near what the authors hypothesize is the optimal strategy for the fixed set of LLM-sampled questions, while UoT showed little to no worst-case improvement from deeper lookahead.
• GoT is sensitive to candidate question quality. In an ablation on Breeds with artificially skewed weights (weight 1 for all but one item, weight 100 for the remaining item), GoT consistently reached the optimal strategy of first testing whether the highest-weight item is the target when that question was manually injected. When the question was not included, performance degraded substantially.
• Average-case performance is close between GoT and UoT. On the DX dataset under a multinomial prior (k set to 1, Qwen 2.5 72B Instruct), the gap between UoT and GoT in average conversation length is small relative to their gains over DP/DC, while GoT's worst-case advantage over UoT is comparable in magnitude to UoT's average-case gain over DP.
• Full-tree construction is prohibitively expensive. Building the complete tree for a 25-item set required 5–6 hours to construct 3763 infosets, which motivated GoT's on-demand subgame search; the paper states that for larger datasets (approximately 100 items) this becomes infeasible.
• Randomized strategies matter in small games. In Example 1, asking q(1) and q(2) in sequence guarantees at most 2 questions, but choosing the first question uniformly at random gives an expected 1/3 · 1 + 2/3 · 2 < 2 questions, showing that neither deterministic option is optimal.
• Weights change the optimal first question. In Example 3 (weights 3, 2, 2), selecting q(1), q(2), q(3) with probabilities 3/4, 1/8, 1/8 keeps expected cost no greater than 15/4, whereas selecting q1 uniformly incurs a cost of 5 when s* = s(1).

Methodology in Plain English

The authors turn question-asking into a game with two players: an Item Chooser who secretly picks an item from a known set, and a Questioner who asks binary questions to identify it. Because the Item Chooser is adversarial, the Questioner cannot rely on a probability distribution over items; instead the goal is to minimize the worst-case number of questions, which corresponds to finding a Nash equilibrium of a zero-sum extensive form game. Such equilibria generally require the Questioner to randomize among several good questions rather than always asking the "best" one.

Because the space of natural-language questions is huge, the authors restrict the game so that questions are generated from the remaining candidate items by a function g, which is implemented by prompting an LLM to propose at most m questions given the current set of possible items. A separate LLM call acts as the answer oracle f, and the paper assumes this oracle makes no mistakes.

Solving the full game tree is impractical because every infoset would need LLM calls. GoT instead builds a subgame rooted at the current infoset and truncates it to a fixed depth d, evaluating truncated leaves with a heuristic h(l) = log2(|S(l)|) (or, in the weighted case, max over remaining items of w(s) · (d(l) + log2(|S(l)|))). The truncated subgame is then solved with counterfactual regret minimization via LiteEFG to get a local strategy, and the next question is sampled from the candidate set according to that strategy. This repeats until only one item remains consistent with the answers.

For experiments, the authors construct three 20-Questions datasets (Common with 136 items, Breeds with 25 cat and dog breeds, and S128 with 128 items made up of 2 weapons, 6 scientists, 24 dishes, and 96 animals), and use Medical Diagnosis on DXBench (100 of the 461 unique diseases) and Troubleshooting on FloDial (59 unique car faults after preprocessing from 2,738 dialogs grounded on 12 flowcharts). Default settings are d = m = 3. Baselines are UoT, Direct Prompting, and Direct Choice. All methods are played against every possible target item, and the worst-case interaction length L_worst = max over items of |H^s| is reported; randomized questioner strategies are averaged over ten plays. Questions generated for GoT's simulation tree are cached and reused for the comparison methods to keep candidate sets identical. Models used are GPT 4.1 (gpt-4.1-2025-04-14 checkpoint) and Qwen 2.5 72B Instruct. Weighted experiments for MD and TS use GPT-5.2 Thinking with extended reasoning to assign integer severity weights from 1 to 10, while 20Q weights are sampled from a lognormal distribution with mu = 0 and sigma = 1.

Why This Matters

• Research impact: The paper argues against the uniform-item assumption baked into prior clarification-question work such as Uncertainty of Thought, provides the first game-theoretic formalization of adversarial information seeking with natural-language action spaces, and supplies worst-case guarantees and complexity results (including the NP-completeness of the deterministic best-response question in Theorem 3.6) that future information-seeking work can build on.
• Real-world applications:
  • Medical diagnosis, where delaying identification of a life-threatening condition has more severe consequences than delaying others, motivating the weighted variant.
  • Troubleshooting, such as a car mechanic narrowing down a fault through symptom questions.
  • General planning and other partially observable tasks where an LLM must request clarifying information before acting.
  • User-facing agents that must resolve ambiguous or underspecified requests by asking clarifying questions or eliciting preferences.
• Industry relevance: The argument that worst-case robustness should be assumed in high-stakes deployments, the finding that GoT is sensitive to the quality of LLM-proposed candidate questions, and the practical observation that explicit full-game solving took 5–6 hours for a 25-item domain and becomes infeasible near 100 items are all directly relevant to anyone building LLM agents that ask questions. The paper also notes that GoT delivers meaningful worst-case improvement with little loss in average-case performance relative to UoT.

Future Directions

• Reducing GoT's reliance on candidate question quality, since the skewed-weight ablation on Breeds showed performance degrades substantially when the optimal question is not among the LLM-proposed candidates.
• Extending GoT beyond SLSR-restricted games toward the unrestricted SLS setting, where the question space is not generated from the remaining items.
• Closing the gap to the theoretical optimum of log2(|S|), which all tested methods miss by roughly 2 to 3 turns of interaction.
• Analyzing how the Item Chooser's shift toward unfavorable priors (X_method ~ Dir(k·alpha) with alpha_0 concentrated on a single item) affects UoT versus GoT; the provided paper content is truncated mid-sentence at this analysis, so the results are not reported here.

Target Audience

Researchers and practitioners in natural language processing and multi-agent systems who work on LLM agents, clarification question asking, and interactive information seeking; game theorists interested in extending equilibria computation to natural-language action spaces; and engineers building high-stakes LLM systems — clinical decision support, troubleshooting assistants, or planning agents — who care about worst-case rather than average-case robustness. Readers need some background in game theory and LLM prompting to follow the formal sections, though the experimental tables and comparisons are readable on their own.

Authors’ abstract

Large Language Models (LLMs) are increasingly deployed in real-world scenarios where they may lack sufficient information to complete a given task. In such settings, the ability to actively seek out missing information becomes a critical capability. Existing approaches to enhancing this ability often rely on simplifying assumptions that degrade \textit{worst-case} performance. This is an issue with serious implications in high-stakes applications. In this work, we use the game of Twenty Questions to evaluate the information-seeking ability of LLMs. We introduce and formalize its adversarial counterpart, the Strategic Language Search (SLS) problem along with its variants as a two-player zero-sum extensive form game. We propose Game of Thought (GoT), a framework that applies game-theoretic techniques to approximate a Nash equilibrium (NE) strategy for the restricted variant of the game. Empirical results demonstrate that our approach consistently improves worst-case performance compared to (1) direct prompting-based methods and (2) heuristic-guided search methods across all tested settings.